Apache Lucene™ onAmazon.com
Amazon06.17.2019

Who are we?
§ Mike McCandless-Long-time Lucene committer, author Lucene in Action
2nd edition§ Mike Sokolov-Search Veteran, new Lucene/Solr committer§ Contributions from many teammates @Amazon in Boston,
Palo Alto, San Francisco, Dublin, Tokyo, Seattle
2AmazonOutline• Overview• Service architecture• Performance measurement• Analysis challenges• Query optimizations• Multiphase ranking• Summary3Amazon

Using Lucene for shopping on Amazon
Amazon has strong search requirements:§ High and peaky query rate
§ Low latency bound§ Large, volatile catalog
Can Lucene handle these requirements?

4AmazonWhy Lucene?
Lucene is a modern, mature, feature rich IR engine
20 years old!
Apache open-source model, with generous license, works wellWidely used inside and outside Amazon
Active, passionate community is always innovating (e.g.,maxscore scoring, Weak AND, Codec impacts in 8.0)
§ Rich text analytics (full Unicode), modern scoring models,pluggable codecs§§§§§

5AmazonLucene design§ 100% Java§ On-disk search index with small
in-memory index structures§ Lucene can search very large indices with little RAM§ Highly concurrent indexing and searching§ Memory-mapped IO, rely on OS to cache hot pages§ Segmented design gives fast updates to a single index§ Near-real-time, transactional “point in time” search§ Write-once design allows for good value compression

6AmazonLucene features we are using
§
§
§
§
§
§
§
§§

7

Near-real-time segment replication
Concurrent searching (“thread per segment per query”)
Index time joins, static index sort, early termination
Dimensional points for range filters and lightning deals
Custom Collector, DoubleValuesSource, QueryCustom term frequency for behavioral signals
Taxonomy facets
Multi-phase ranking
ExpressionsAmazon

Open-source at Amazon™

§ Lucene is a strategic open-source project§ Developers are encouraged to interact with open-source
community, push changes back, open issues, etc.
§ Recent Lucene improvements:§ Custom term frequencies§ Concurrent indexing updates§ Concurrent faceting§ FST direct arc addressing§ Off-heap FSTs

8AmazonOutline• Overview• Service architecture• Performance measurement• Analysis challenges• Query optimizations• Multiphase ranking• Summary9AmazonNear-real-time segment replication
§§§§
§
§§§

10Large indexes and low latency → sharded index
High query throughput → replicated index
Solr, Elasticsearch use document replication
Lucene’s segments are a natural replication unit
Index and merge each segment once
Share segments using durable, highly-connected cloud storage
External queue ensures no lost updates, consistency
Preserve Lucene’s transactional semantics

AmazonService architecture
Build on AWS infrastructure
Indexer, searcher nodes run inside ECS containers
Catalog changes arrive via Kinesis queues and DynamoDBgRPC APIs trigger Lucene refresh, new near-real-timesearcher every ~60 seconds§ Near-real-time index snapshots are saved in S3§ Index always re-built on each software deployment§ Service warmed using synthetic queries§§§§

11Amazon

12

AmazonSearching a segmented index
100
100
95
94
47
42
36
36
25

13

Merge Sort

95
19
42
17
3
25
1
2
7

Amazon

100
19
36
17
3
25
1
2
7

100
19
36
17
3
25
1
2
7

94
19
47
17
325
1
2
7

Per-Slice Collection

Searching a segmented index concurrently§§§§§§

14Index is statically sorted by item “quality”
Per-segment early termination
Thread per segment per query
Better long-pole query latencies, but worse red-line QPS
Can we fall back to single threaded near red-line?
Can we use multiple threads to search a large segment?

AmazonP99 query latency and segment replication

AmazonOutline• Overview• Service architecture• Performance measurement• Analysis challenges• Query optimizations• Multiphase ranking• Summary16Amazon

Internal nightly benchmarks§ Similar to Lucene’s nightly benchmarks§ Track progress and catch accidental regressions§ Measure both functionality and performance metrics

17AmazonMeasuring performance§ Long-pole (P99+) query latency is a key metric§ Query latencies measured with open-loop client, Poissonarrival times§ Avoids “coordinated omission” bug§ Latency measured under what conditions?
§ Red-line QPS measured with closed-loop client§ Goal: drive up red-line QPS while holding down latencies
below red-line18Amazon

Concurrent refresh§ Problem: Lucene “borrows” application indexing threads
to provide concurrent refresh§ If application uses only one thread calling refresh(), that’s
single threaded – common case?
§ On highly concurrent hardware this is very slow
§ Solution: use expert Lucene API to refresh concurrently(LUCENE-8700)

19

AmazonGathering metrics using Lucene’s abstractions
§§§§
§

20

Wrap DirectoryReader to count term lookups
Wrap Directory, IndexInput to gather IO counters
How many bytes does each query visit?
How many times does each query lookup terms?
Track per-query metrics in nightly benchmarks

AmazonFull garbage collection is bad!
§§§§

We use JDK11’s (deprecated) CMS garbage collector
We don’t trust G1GC yet
Use Azul’s jHiccup to measure real pauses
We hit 8 second stop-the-world full GC pauses§ Reduced heap usage§ Increased heap size
§ Changed GC parameters (poached from Elasticsearch)§ -XX:CMSInitiatingOccupancyFraction=75§ -XX:+UseCMSInitiatingOccupancyOnly

AmazonLucene nightly benchmarks
Restore Parallel GC

JDK 11Amazon

Outline• Overview• Service architecture• Performance measurement• Analysis challenges• Query optimizations• Multiphase ranking• Summary23Amazon

Context-sensitive analysis

l24

What does “plane” mean to you?

AmazonContext-sensitive analysis

AnAirplane?

25

AmazonContext-sensitive analysis

A benchplane?

26

AmazonContext-sensitive analysis§ Synonyms applied only during indexing§ We have a helpful synonym “plane”“airplane,” but weprobably shouldn’t apply it to tools§ Lucene switches analysis per field§ We switch synonyms based on field values like product type,and other contextual information

27

AmazonNumbers are special§ “Toy for 3 year old” should match toys with text “for age 2-4years”§ 1500 ml should match 1.5 liters.
§ 1,100 == 1100 == 1.100 != 1/100 or 1:100§ It’s hard to handle these after StandardTokenizer!

28

AmazonWordDelimiterGraphFilter§ Splits on non-letter/number characters§ Cannot accept a token graph§ Messes up offsets§ Many many options§ Useful with whitespace tokenization

29

AmazonOutline• Overview• Service architecture• Performance measurement• Analysis challenges• Query optimizations• Multiphase ranking• Summary30Amazon

Indexed queries§ Many queries share common sets of filters+asin_or_proffer:asin +is_idq_suppressed:0+is_campus_custom:0 +adult-product:0§ Let’s factor them out during indexing (like Percolate)§ … and searching, replacing with a single TermQuery clause

31

AmazonFactoring queries
§§§
§

32

Factoring general Boolean expressions is hard!
Luckily, our queries are mostly conjunctive
FP-growth algorithm works well
Simplify by handling one level of nesting

AmazonResults§ +30% red-line QPS!
§ P99 latency 81ms -> 54ms33

AmazonIndexing tuples§ This is a similar idea, but for full text
§ Index common pairs of words (tuples)casa_iphone: 20535
iphone_plus: 10297
dress_woman: 7956
shoe_woman: 7497
casa_galaxy: 5175
galaxy_samsung: 4912
led_light: 4854
day_valentine: 4840

34

AmazonLightning deals using dimensional points§ Each lightning deal has a unique
name, and start/end time range§ Each product can have multiple
deals§ Very time sensitive – e.g. on
Prime Day 2019
§ Custom 3D shape and query

35

AmazonOutline• Overview• Service architecture• Performance measurement• Analysis challenges• Query optimizations• Multiphase ranking• Summary

36

AmazonRanking§ Machine-learned models using custom evaluator§ Multiple input signals§ Custom term freqs for behavioral scores§ Doc values fields for per-document signals§ Custom scoring functions as DoubleValuesSource§ Heavy use of Lucene expressions

37

AmazonMulti-phase ranking§§§§

Top K0 matching docs ordered by index rank
Top K1 of K0 reordered with fast rank
Top K of K1 with precise final rank
Tunable tradeoff of speed/precision

K039

AmazonK1K

Phase 0 concurrent collection
§§§§
§
§

Conservatively, collect K0 for each segment
Guarantees same top K0 as sequential collection
How likely is this worst case?
For random distribution in p segments:(1/p)^K0; p ~ 20, and K0 ~1000(1/20)^1000 = not going to happenK40

Amazonp

Proportional collection§ Expected portion of top n in segment k is n*pk
§ LUCENE-8681§ Multinomial p.d.f gives probability (number ofcombinations) of a given document
distribution

41

AmazonOutline• Overview• Service architecture• Performance measurement• Analysis challenges• Query optimizations• Multiphase ranking• Summary42AmazonSummary§§§§43

Lucene works well for Amazon’s product search!
Segment replication is efficient for deep clusters
Thread per segment concurrency yields low latencies
If you enjoy working on Lucene open source, and high scale,high impact software… come join us!

AmazonThank you
AmazonQUESTIONS?
now … or come find us at our booth!