Location Search and Search at Scale.

Saturday evening in Bengaluru. The e-commerce platform from this week launches "Now": essentials delivered in minutes from dark stores across the city. Within half an hour, location breaks it. (An illustrative scene: the platform, numbers and times are made up; each failure is a classic one.)

None of these is a text-search bug. Each is about space: indexing "near", handling things that move, and everyone being in the same place.

Yesterday (Day 4) built typeahead: answering a prefix of text in milliseconds because the work was done ahead of time. Today the idea comes back for places: a geohash is a string whose prefix is a region, a trick both powerful and leaky. The last part keeps the operations essentials of this week's cluster: topology, shard sizing and reindexing with aliases.

01Chapter 1: Why "Near" Breaks a B-tree#

1.1 The Simple Definitions#

• Point of interest (POI): something that stays put (a store, an ATM). Few writes, rich filters.
• Moving object: a position that streams (a delivery partner, a driver). Constant writes, simple questions.
• Radius query: everything within r of a point. k-nearest (kNN): the k closest, however far.
• Cell: one tile of a grid over the Earth, with an ID. A covering is a set of cells that contains a shape.

1.2 Two Numbers, One Circle#

A B-tree sorts by one key. An index on (lat, lng) sorts by longitude only among rows with exactly the same latitude, which never happens. So it can use the latitude range, and the longitude test filters every row in it.

1.3 The Core Idea: Cells, Coverings, Refine#

Every technique today does three steps:

1. Map 2-D to 1-D. Number grid cells so nearby cells usually get nearby numbers (a space-filling curve). A sorted index works again.
2. Cover the query. Turn "within 2 km" into a short list of cells or cell ranges.
3. Refine. Compute exact distances for the candidates in those cells; throw away the corners.

The trade-off is in step 2: big cells mean few lookups and many wasted candidates, small cells the reverse. Cell size for the radius is the main tuning knob.

%% title: Filter and refine: cells give candidates, distance gives answers
flowchart TD
  Q@{ icon: "sd:map-pin", label: "Query<br/>12.9352, 77.6245 · within 2 km" }
  COV["Cover<br/>radius → cells or cell ranges"]:::core
  IDX@{ icon: "sd:index", label: "Cell index<br/>cell id → items" }
  CAND["Candidates<br/>everything in those cells"]:::service
  REF["Refine<br/>exact great-circle distance ≤ 2 km"]:::core
  OUT(["Answer<br/>sorted by distance or score"]):::ok
  DROP(["Corners thrown away<br/>the price of square or hex cells"]):::bad
  Q ==> COV ==> IDX ==> CAND ==> REF ==> OUT
  REF -.-> DROP
  class Q client
  class IDX store

02Chapter 2: Geohash#

2.1 How a Geohash Is Built#

Geohash (Gustavo Niemeyer, 2008) halves the world again and again: the first bit says east or west of the prime meridian, the second north or south of the equator, alternating from there. The bits are written 5 at a time in base 32 (digits and lowercase letters except a, i, l, o). Every character adds 5 bits and divides the cell by 32.

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"   # no a, i, l, o

def geohash(lat, lng, precision=6):
    """Interleave longitude and latitude bits, 5 bits per character."""
    lat_lo, lat_hi, lng_lo, lng_hi = -90.0, 90.0, -180.0, 180.0
    bits, use_lng, out = 0, True, []
    for i in range(precision * 5):
        if use_lng:                                   # even bits: longitude
            mid = (lng_lo + lng_hi) / 2
            bit = lng >= mid
            lng_lo, lng_hi = (mid, lng_hi) if bit else (lng_lo, mid)
        else:                                         # odd bits: latitude
            mid = (lat_lo + lat_hi) / 2
            bit = lat >= mid
            lat_lo, lat_hi = (mid, lat_hi) if bit else (lat_lo, mid)
        bits = (bits << 1) | bit
        use_lng = not use_lng
        if i % 5 == 4:                                # 5 bits -> one character
            out.append(BASE32[bits])
            bits = 0
    return "".join(out)

print(geohash(12.9352, 77.6245, 6))   # tdr1w6   Koramangala

A shared prefix means a shared cell: every point in Koramangala's tdr1w6 is also in tdr1w, tdr1 and tdr. As with yesterday's typeahead, a prefix search on a sorted key is a range scan.

The size per character, from Elasticsearch's geohash grid docs (worst case, at the equator):

Cells shrink east to west as you leave the equator ("cell dimensions vary with latitude", in the docs' words): in Bengaluru, at 13°N, a length-6 cell is about 1.19 km × 0.61 km.

India Post's DIGIPIN uses the same recursive idea with a different alphabet: a 4 × 4 grid at each of ten levels, so each character carries 4 bits instead of 5. The DIGIPIN case file designs a whole service around it.

2.2 Neighbours and the Edge Problem#

The guarantee only runs one way. Wikipedia's summary is exact: a longer shared prefix means the points are closer, but "the reverse of this is not guaranteed, as two points can be very close but have a short or no shared prefix".

Two points in east Bengaluru, 43 metres apart on the same latitude: (12.9352, 77.6951) is tdr1xf, (12.9352, 77.6955) is tdr384. They share only tdr: they sit either side of a line where the curve jumps between quarters of the tdr cell. Across the equator or the prime meridian, neighbours share nothing. That's launch night's 20:14 bug.

The standard fix: search the point's cell plus its 8 neighbours, at a precision where a cell is at least as wide as the radius, then refine. Redis does exactly this, checking "the 1+8 areas needed to cover the whole shape and discarding elements outside it" (Redis docs). Compute neighbours with a library: cells thin out near the poles and wrap at ±180°.

03Chapter 3: Quadtrees#

3.1 Splitting Where the Data Is#

A geohash grid is the same everywhere: a length-6 cell over the Thar desert is the same size as one over Koramangala. A quadtree (named by Finkel and Bentley in 1974; the version here, splitting into equal quarters, is the point-region or "bucket" variant) adapts. Start with one square; when it holds more than N points, split it into four; keep splitting the busy quarters. Dense city centres get tiny cells, empty land stays one big cell, and every leaf holds at most N items.

%% title: A quadtree splits only where the points are (leaf capacity 100, illustrative)
flowchart TD
  ROOT["India<br/>20M places · split"]:::core
  NW["North-west quarter<br/>split again"]:::service
  NE["North-east quarter<br/>80 places · leaf"]:::ok
  SW["South-west quarter<br/>split again"]:::service
  SE["South-east quarter<br/>split again"]:::service
  BLR["… Bengaluru centre<br/>split again and again"]:::hot
  KOR["Koramangala leaf, 13 levels down<br/>~400 m square · 97 places"]:::ok
  ROOT --> NW
  ROOT --> NE
  ROOT --> SW
  ROOT --> SE
  SE --> BLR
  BLR --> KOR

3.2 Static vs Dynamic#

• Static: built from a snapshot, held in memory, replaced by a fresh build every few minutes or hours. Ideal for POIs, which change rarely. No locks, no rebalancing.
• Dynamic: inserts and deletes in place, splitting full leaves and merging empty siblings. Needed when points move, and costly: every boundary crossing is a delete plus an insert, busy leaves churn as crowds come and go, and readers need locks or copy-on-write.

Quadtrees answer kNN naturally: walk the tree best-first, nearest node first, until the k-th result is closer than the next node. The catch: a quadtree is a data structure, not a key. You can't use "a quadtree node" in a sorted database index or as a shard key. S2 fixed that.

04Chapter 4: S2 Cells and H3 Hexagons#

4.1 S2: A Quadtree You Can Number#

Google's S2 projects "the six faces of a cube onto the unit sphere" and subdivides "each cell into four children recursively": a quadtree per face, levels 0 to 30, leaf cells "about 1cm across" (S2 docs). Two choices make it database-friendly:

• Every cell is a 64-bit S2CellId, ordered along Hilbert curves "linked together to form a single continuous loop over the entire sphere". Unlike geohash's Z-order, "if the S2CellIds of two cells are close together, then the cells are also close together".
• A cell's descendants are one contiguous ID range (range_min() to range_max()): everything inside a cell is one range scan.

S2RegionCoverer turns a circle or polygon into a few cells at mixed levels, with max_cells as the budget: the docs report a median covering 1.98× the region's area with 8 cells, 1.42× with 20. More cells, less waste. S2 cells aren't equal-area: at level 12 they range from 3.04 km² to 6.38 km².

Uber used this in 2015. InfoQ's report of Matt Ranney's QCon London talk: "the driver's phones post location updates to the server every four seconds", Uber "chose to use Google's S2 Geometry Library" with cells of about 3.31 km² as the shard key, and wanted to "handle one million writes a second and a much higher read rate" (InfoQ, March 2015).

4.2 H3: Why Hexagons#

In 2018 Uber open-sourced H3. It projects the Earth onto an icosahedron and tiles it with hexagons, plus "twelve pentagons, one at each of the icosahedron vertices", since hexagons alone can't tile a sphere. It "supports sixteen resolutions", each with "one seventh the area" of the one above, and every index is a 64-bit integer (Uber Engineering, 2018; h3geo.org).

Why hexagons? Their neighbours. Squares have 8 neighbours at two distances, triangles 12 at three, and "for hexagons, all neighbors are equidistant" (H3 docs). Uber adds that hexagons "minimize the quantization error introduced when users move through a city"; it calculates "surge pricing by measuring supply and demand in hexagons". In practice:

• Rings approximate circles. "Within k steps" (grid_disk) is a near-circular disc of 3k(k+1) + 1 cells (away from the 12 pentagons), so a radius search over-fetches less than a square of squares.
• Smoothing is easy. Averaging demand over a cell and its 6 neighbours treats every neighbour the same.
• The cost: hexagons don't nest. "Hexagons do not cleanly subdivide into seven finer hexagons": a parent's 7 children only roughly cover it, though "logical containment in the index is exact". Rolling counts up resolutions is approximate at the edges, unlike S2 or geohash.

4.3 Choosing a Grid#

05Chapter 5: R-trees, PostGIS and Elasticsearch#

5.1 R-trees and PostGIS GiST#

Grids carve up space; an R-tree (Guttman, SIGMOD 1984) groups the data. Each node stores the bounding box of everything below it; boxes can overlap; a search descends only into boxes that intersect the query. It handles shapes as easily as points: a delivery polygon, a flood zone, a district boundary.

That's what PostgreSQL's spatial extension uses: "PostGIS uses an R-Tree index implemented on top of GiST", and "spatial indexes store only the bounding box of geometries" (PostGIS docs). The exact geometry test runs after the index narrows things down: filter and refine again.

CREATE TABLE stores (
  id       bigint PRIMARY KEY,
  name     text,
  location geography(Point, 4326),      -- longitude first: ST_MakePoint(x, y)
  zone     geography(Polygon, 4326)     -- the delivery area, drawn by ops
);
CREATE INDEX stores_location_gix ON stores USING GIST (location);
CREATE INDEX stores_zone_gix     ON stores USING GIST (zone);

-- Radius: stores within 2 km. ST_DWithin uses the index; geography units are metres.
SELECT id, name, ST_Distance(location, ST_MakePoint(77.6245, 12.9352)::geography) AS metres
FROM stores
WHERE ST_DWithin(location, ST_MakePoint(77.6245, 12.9352)::geography, 2000)
ORDER BY metres;

-- k-nearest: the <-> operator walks the GiST index when it's in ORDER BY.
SELECT id, name
FROM stores
ORDER BY location <-> ST_MakePoint(77.6245, 12.9352)::geography
LIMIT 5;

-- The real question: which stores' delivery zones contain this customer?
SELECT id FROM stores
WHERE ST_Intersects(zone, ST_MakePoint(77.6245, 12.9352)::geography);

From the docs: ST_DWithin "includes a bounding box comparison that makes use of any indexes", and for geography "units are in meters" with use_spheroid = true by default; <-> "will make use of 2D GiST indexes" when it's in ORDER BY. A WHERE ST_Distance(...) < 2000 gives the same answer but can't use the index, so it computes a distance for every row.

The last query is the one that matters. A real delivery area isn't a circle: a river, a flyover with no exit or a one-way street turns 800 m on the map into 3 km on the road. Ops draw zones; the system answers "which zones contain this point". The Blinkit side quest precomputes this into an H3 cell → stores table so no geometry runs at request time.

5.2 Location in Elasticsearch#

This week's product index can filter by place too, with a geo_point field. Watch the order: "String geopoints are ordered as lat,lon, while array geopoints, GeoJSON and WKT are ordered as the reverse" (Elasticsearch docs); mix them up and Bengaluru lands in the Arctic, off Svalbard, without an error. These points aren't in Day 1's inverted index: since 6.0 the default structure is "the new block k-d tree (BKD)" (Elastic, 2019).

"Milk near me", with location as a filter (Day 3: filters don't score and can be cached) and distance as a tiebreaker:

GET products-now/_search
{
  "query": {
    "bool": {
      "must":   { "match": { "name": "milk" } },
      "filter": [
        { "term": { "in_stock": true } },
        { "geo_distance": {
            "distance": "2km",
            "store_location": { "lat": 12.9352, "lon": 77.6245 } } }
      ]
    }
  },
  "sort": [
    "_score",
    { "_geo_distance": {
        "store_location": { "lat": 12.9352, "lon": 77.6245 },
        "order": "asc", "unit": "km" } }
  ]
}

geo_distance matches "within a given distance of a geopoint", using arc by default or plane, which is "faster, but inaccurate on long distances and close to the poles". This version indexes one document per product per store, which is simple and grows fast. The usual alternative is two steps: look up which stores serve the customer's cell, then search products with a terms filter on those store IDs.

06Chapter 6: Asking the Questions#

6.1 Radius Queries End to End#

%% title: "Milk within reach": cell lookup, then product search on the stores that can deliver
sequenceDiagram
  autonumber
  participant A as Customer app
  participant S as Search API
  participant Z as Zone index, cell to stores
  participant E as Product index
  participant L as Live partners
  A->>S: q milk, at 12.9352, 77.6245
  S->>S: point to H3 cell, resolution 9
  S->>Z: which stores deliver to this cell?
  Z-->>S: stores 41 and 57
  S->>E: match milk, filter in stock at 41 or 57
  E-->>S: 23 products, scored
  S->>L: free partners near 41 and 57?
  L-->>S: 6 and 2, ETA estimates
  S-->>A: results with a delivery-time promise

The cell size comes from the radius:

• Geohash: the longest precision whose cell is at least as wide as the radius, then the 9-cell search.
• H3: grid_disk(origin, k) must contain every point within r. For edge length e, a safe k is ceil((r + 2e) / 1.5e) − 1, since the query point and a far cell's points can each be up to e from their centres. Take e from the cells where you are, not H3's global average: cell sizes vary by place, and in Mumbai, where res-9 cells are ~9% smaller than average, the average gives k = 7, which misses points 2 km away. The code below uses the query cell's shortest edge, to be safe. Or compute an exact covering of the circle.
• S2: let S2RegionCoverer choose within a max_cells budget.

6.2 k-Nearest: Grow the Search, Then Prove You're Done#

"The 5 nearest free partners" has no radius. You grow one: scan the origin cell, then ring 1, ring 2, and so on. The trap is when to stop.

import h3, heapq

def shortest_edge_km(cell):
    """H3 cells vary in size by place: use this cell's own shortest edge, not the global average."""
    return min(h3.edge_length(e, unit="km") for e in h3.origin_to_directed_edges(cell))

def ring_bound(ring, edge_km):
    """Closest that any point beyond `ring` can be: a conservative lower bound."""
    return (ring + 1) * 1.5 * edge_km - 2 * edge_km

def k_nearest(cells, lat, lng, k, res=8, max_rings=40):
    """cells: {h3 cell: {partner_id: (lat, lng)}}. Returns the k nearest (km, id)."""
    origin = h3.latlng_to_cell(lat, lng, res)
    edge = shortest_edge_km(origin)
    found = []
    for ring in range(max_rings + 1):
        for cell in h3.grid_ring(origin, ring):              # only the new ring
            for pid, pos in cells.get(cell, {}).items():
                found.append((h3.great_circle_distance((lat, lng), pos, unit="km"), pid))
        best = heapq.nsmallest(k, found)
        if len(best) == k and best[-1][0] <= ring_bound(ring, edge):
            return best                                       # nothing unscanned can beat these
    return heapq.nsmallest(k, found)                          # fewer than k within max_rings

Straight-line distance only picks candidates; dispatch re-ranks the top few by road ETA. And cap the search (max_rings, Redis's COUNT) so an empty area doesn't scan half the state.

07Chapter 7: Partners Are Not Stores#

7.1 Two Indexes, Two Workloads#

Stores and partners both have a location, and the launch-night mistake was treating them alike.

Elasticsearch is the wrong home for 4-second pings. An update isn't in place: the document "must still be reindexed" (Elastic docs), so each ping writes a new copy and deletes the old, and refreshes (every second on searched indices) make segments that merges must clean up. At 10,000 pings a second, that's the 20:09 incident.

7.2 The Write Path#

The trick for moving objects: overwrite the position on every ping, touch the cell index only when a partner crosses a cell edge.

%% title: Live locations: overwrite in memory, move between cells rarely, keep history elsewhere
flowchart TD
  P@{ icon: "sd:phone", label: "Partner app<br/>ping every 4 s" }
  GW@{ icon: "sd:gateway", label: "Ingest gateway<br/>auth, rate limit" }
  K@{ icon: "tech:kafka", label: "Kafka · location trail<br/>keyed by partner" }
  LIVE["Live index shard<br/>partner → position, cell, seen at<br/>cell → partners"]:::core
  DISP["Dispatch and ETA<br/>who is free near store 41?"]:::service
  LAKE@{ icon: "sd:object-storage", label: "History<br/>trips, analytics, disputes" }
  SRCH@{ icon: "sd:search", label: "Search API<br/>delivery promise" }
  P ==> GW ==> LIVE
  GW --> K --> LAKE
  DISP --> LIVE
  SRCH --> LIVE
  class P client
  class GW edge
  class K queue
  class LAKE store
  class SRCH service

import math, time
import h3

class LiveLocations:
    """Partner positions in memory, bucketed by H3 cell. Most pings touch only the position."""

    def __init__(self, res=8, ttl_s=30):
        self.res, self.ttl = res, ttl_s
        self.pos = {}      # partner -> (lat, lng, cell, seen_at)
        self.cells = {}    # cell -> set of partners

    def ping(self, partner, lat, lng, now=None):
        now = now or time.time()
        cell = h3.latlng_to_cell(lat, lng, self.res)
        old = self.pos.get(partner)
        if old is None or old[2] != cell:                 # about 1 ping in 45 at res 8
            if old:
                self.cells[old[2]].discard(partner)
            self.cells.setdefault(cell, set()).add(partner)
        self.pos[partner] = (lat, lng, cell, now)          # every ping: overwrite in place

    def nearby(self, lat, lng, radius_km, now=None):
        now = now or time.time()
        origin = h3.latlng_to_cell(lat, lng, self.res)
        e = min(h3.edge_length(d, unit="km") for d in h3.origin_to_directed_edges(origin))
        k = math.ceil((radius_km + 2 * e) / (1.5 * e)) - 1   # this cell's size, not the average
        hits = []
        for cell in h3.grid_disk(origin, k):
            for p in self.cells.get(cell, ()):
                plat, plng, _, seen = self.pos[p]
                if now - seen > self.ttl:                  # app killed, phone off: not "nearby"
                    continue
                d = h3.great_circle_distance((lat, lng), (plat, plng), unit="km")
                if d <= radius_km:                         # refine: exact distance
                    hits.append((d, p))
        return sorted(hits)

The TTL matters as much as the index: a phone that dies at a traffic light never says goodbye, and without an expiry stays "2 minutes away" forever. It's Week 6, Day 4's presence again: positions are hints that expire.

Redis GEO offers this as a service: GEOADD keeps members in a sorted set scored by a "52-bit integer" of interleaved latitude and longitude bits, and GEOSEARCH (Redis 6.2+) queries it. From the docs: longitude comes first; the Earth is modelled as a sphere, with error "up to 0.5%"; and COUNT n ANY returns as soon as it has n matches, which may be unsorted and not the nearest, but far cheaper in a crowd. Sorted-set members have no TTL of their own, so you track last-seen and remove stale partners yourself (ZREM).

GEOADD    partners:blr 77.6245 12.9352 partner:8812
GEOSEARCH partners:blr FROMLONLAT 77.6245 12.9352 BYRADIUS 2 km ASC COUNT 20 WITHDIST

7.3 Sharding Geo Data and Hot Cells#

One machine holds a city's partners easily; the national write rate, read traffic and failure isolation force sharding. The shard key is a cell:

• By city or region. Simple and local, but cities aren't equal, and one Redis key per city puts a whole city's writes on one node.
• By cell range along a space-filling curve. S2's Hilbert order keeps neighbours together, so a shard is a run of cell IDs, rebalanced by moving split points to even out load, not area. Uber sharded on S2 cell IDs in 2015.
• By coarse hexagon. Uber Eats search grouped "thousands of narrow latitude stripes" into shards offline with Spark; they go uneven "in densely populated urban areas", so it also uses hex sharding on H3, typically "size 2 or 3" (Narayanan and Ramasamy, InfoQ, 2025, from their QCon San Francisco 2024 talk).

Every scheme has boundaries: a search near a shard edge needs both shards. Query both (the router knows which shards the covering's cells live on) or, for read-mostly POIs, index edge documents in both. Uber Eats does the latter: "documents falling on shard boundaries are indexed in both neighboring shards".

%% title: Shards are runs of cells, sized by load: the city centre gets small ones
flowchart TD
  RT["Geo router<br/>covering cells → shards"]:::core
  S1@{ icon: "sd:servers", label: "Shard 1<br/>north and west Bengaluru<br/>many cells, light load" }
  S2@{ icon: "sd:servers", label: "Shard 2<br/>east Bengaluru, Whitefield" }
  S3["Shard 3<br/>central business district<br/>few cells, heavy load"]:::hot
  S3R@{ icon: "sd:servers", label: "Shard 3 read replicas<br/>for match-night reads" }
  C@{ icon: "sd:cache", label: "Nearby cache<br/>key: cell, 5 s TTL" }
  Q@{ icon: "sd:map-pin", label: "Query near a shard edge<br/>covering spans shards 2 and 3" }
  Q ==> RT
  RT --> C
  RT ==> S2
  RT ==> S3
  RT -.-> S1
  S3 --> S3R
  class S1,S2,S3R store
  class C cache
  class Q client

Hot cells are hot keys (Week 1, Day 4 · Hot Keys and Skew) with a map attached: a stadium, a station at 7 pm, a mall on sale day. The fixes:

1. Split by load, not area: smaller cell ranges where it's busy, the quadtree's insight applied to shards.
2. Cache by cell: everyone in the stadium asks about the same few cells, so cache each answer for a few seconds.
3. Replicate reads of a hot shard; writes stay on the primary.
4. Cap the work: COUNT 20 ANY, max_rings. No query needs all 3,000 partners in a cell.
5. Degrade: show the cell's recent average delivery time instead of a live computation.

The geo layer lives inside this week's search cluster, which still has to be sized and run. The compact version:

08Chapter 8: Topology, Shard Sizing and Reindexing#

8.1 Cluster Topology#

%% title: Production cluster: roles separated, copies spread across zones
flowchart TD
  APP@{ icon: "sd:api", label: "Search API" }
  subgraph CO["Coordinating nodes · route and merge"]
    direction LR
    C1@{ icon: "sd:router", label: "Coord 1" }
    C2@{ icon: "sd:router", label: "Coord 2" }
  end
  subgraph MA["Dedicated master-eligible nodes · cluster state only"]
    direction LR
    M1["Master 1<br/>zone A"]:::core
    M2["Master 2<br/>zone B"]:::service
    M3["Master 3<br/>zone C"]:::service
  end
  subgraph DA["Data nodes · shards, queries, indexing"]
    direction LR
    D1@{ icon: "sd:database", label: "Data · zone A<br/>primaries and replicas" }
    D2@{ icon: "sd:database", label: "Data · zone B" }
    D3@{ icon: "sd:database", label: "Data · zone C" }
  end
  APP ==> CO
  CO ==> DA
  MA -.->|"shard allocation"| DA
  class APP edge
  class C1,C2 edge
  class D1,D2,D3 store

• Three master-eligible nodes: "so that if one of them fails then the remaining two still form a majority" (Elastic). Four tolerate no more failures than three.
• Coordinating nodes fan queries out to shards and merge results, so data nodes do only shard work.
• Data nodes hold "at least two copies of each shard", primary and replica in different zones.
• Heap: at most 50% of RAM, leaving the rest to the file cache where the index lives, and below the compressed-pointers threshold: "26GB is safe on most systems and can be as large as 30GB on some". The old "31 GB" rule of thumb goes past that range; don't use it as a target.

8.2 Shard Sizing and Capacity#

Elastic's guidance: "Aim for shard sizes between 10GB and 50GB", under "200 million" documents each. Too few and too many both hurt: "each shard runs the search on a single CPU thread", so more shards mean more parallelism, but searching "a large number of shards can deplete a node's search thread pool". By default a node takes at most 1,000 non-frozen shards.

The product index from earlier this week, worked through:

Data nodes = the largest of what storage, memory and CPU each need: storage at normal traffic, CPU at peak. Location adds a lever: geo-partitioned indices. If queries are local, an index per region means a Bengaluru search touches Bengaluru's shards, not all 32, and a hot region can get more replicas. Tinder's Elasticsearch setup does this: "partitioning users into geo-indexes" so it "examines only nearby profiles instead of the entire global user base", which "lowered CPU usage by four times" (Elastic customer story).

8.3 Reindexing With Aliases#

Geo changes force reindexes: a new h3_r9 field for cell filters, geo_point to geo_shape for zones, a new shard count. Day 2 built the full procedure; in short:

1. Clients only use an alias (products-now), never an index name.
2. Create products-now-v2, backfill it while the pipeline writes to both.
3. Verify counts and sample queries against v1.
4. Swap the alias in one request: "multiple actions in a single atomic operation" (Elastic), so it never points at both or neither.
5. Keep v1 for rollback: the same swap the other way.

POST _aliases
{
  "actions": [
    { "remove": { "index": "products-now-v1", "alias": "products-now" } },
    { "add":    { "index": "products-now-v2", "alias": "products-now" } }
  ]
}

09Chapter 9: How Real Companies Do It#

10Chapter 10: Common Mistakes to Avoid#

10.1 Mistake 1: A B-tree on Latitude and Longitude#

10.2 Mistake 2: Pings in the Search Index#

10.3 Mistake 3: Trusting the Prefix#

10.4 Mistake 4: One Shard per City, One Size for Every Cell#

11Chapter 11: Interview Tips and Phrases#

11.1 When to Bring It Up#

• "Find nearby" anything: proximity is the deep dive.
• Ride-hailing, food or quick commerce: expect the moving-object write path and hot cells.
• E-commerce search with local delivery: the cell → stores lookup plus a product filter.

11.3 Questions to Ask the Interviewer#

• Are the things we search for static, moving or both? How often does a moving one report?
• Is it "within r" or "the nearest k"? Straight-line or road distance?
• How uneven is the density: one city or the whole country?

11.4 Common Follow-Up Questions#

12Chapter 12: Practice Problems#

Summary#

Further Reading#

Engineering Blogs and Talks#

• Blog

  Uber — H3: Uber's Hexagonal Hierarchical Spatial Index (June 2018): https://www.uber.com/blog/h3/

• Read

  InfoQ — Uber's Realtime Market Platform (Matt Ranney at QCon London, March 2015): https://www.infoq.com/news/2015/03/uber-realtime-market-platform

• Read

  HighScalability — How Uber Scales Their Real-time Market Platform (September 2015): https://highscalability.com/how-uber-scales-their-real-time-market-platform/

• Blog

  InfoQ — Optimizing Search Systems: Balancing Speed, Relevance, and Scalability (Uber Eats search, July 2025): https://www.infoq.com/articles/optimizing-search-systems/

• Blog

  Elastic — BKD-backed geo_shapes in Elasticsearch (December 2019): https://www.elastic.co/blog/bkd-backed-geo-shapes-in-elasticsearch-precision-efficiency-speed

• Read

  Elastic — Tinder customer story: https://www.elastic.co/customers/tinder

• Read

  News24 — Deepinder Goyal explains 10-minute deliveries (January 2026): https://news24online.com/india/after-gig-workers-strike-zomato-ceo-deepinder-goyal-explains-10-minute-deliveries-says-rider-drives-an-average-of-under-2kms-in-about-8-minutes/700638/

Official Documentation#

• Docs

  H3 — Tables of cell statistics across resolutions: https://h3geo.org/docs/core-library/restable/

• Docs

  H3 — Aggregation (why hexagons): https://h3geo.org/docs/highlights/aggregation

• Docs

  H3 — Indexing (hierarchy, aperture 7): https://h3geo.org/docs/highlights/indexing

• Docs

  H3 — Grid traversal (gridDisk): https://h3geo.org/docs/api/traversal

• Docs

  S2 — S2Cell hierarchy: https://s2geometry.io/devguide/s2cell_hierarchy

• Read

  S2 — Cell statistics: https://s2geometry.io/resources/s2cell_statistics

• Docs

  Elasticsearch — geo_point: https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-point.html

• Docs

  Elasticsearch — geo_distance query: https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-geo-distance-query.html

• Docs

  Elasticsearch — Sort search results (_geo_distance): https://www.elastic.co/guide/en/elasticsearch/reference/current/sort-search-results.html

• Docs

  Elasticsearch — Geohash grid aggregation (cell sizes): https://www.elastic.co/guide/en/elasticsearch/reference/current/search-aggregations-bucket-geohashgrid-aggregation.html

• Docs

  Elasticsearch — Size your shards: https://www.elastic.co/guide/en/elasticsearch/reference/current/size-your-shards.html

• Docs

  Elasticsearch — Designing for resilience: https://www.elastic.co/guide/en/elasticsearch/reference/current/high-availability-cluster-design.html

• Docs

  Elasticsearch — JVM heap size: https://www.elastic.co/guide/en/elasticsearch/reference/current/advanced-configuration.html

• Docs

  Elasticsearch — Aliases: https://www.elastic.co/guide/en/elasticsearch/reference/current/aliases.html

• Docs

  Elasticsearch — Near real-time search: https://www.elastic.co/guide/en/elasticsearch/reference/current/near-real-time.html

• Blog

  PostGIS — Spatial indexes: https://postgis.net/docs/using_postgis_dbmanagement.html

• Blog

  PostGIS — ST_DWithin: https://postgis.net/docs/ST_DWithin.html

• Blog

  PostGIS — <-> KNN operator: https://postgis.net/docs/geometry_distance_knn.html

• Docs

  Redis — GEOADD: https://redis.io/docs/latest/commands/geoadd/

• Docs

  Redis — GEOSEARCH: https://redis.io/docs/latest/commands/geosearch/

Papers#

• Read

  Guttman — R-Trees: A Dynamic Index Structure for Spatial Searching (SIGMOD 1984)

• Read

  Finkel and Bentley — Quad Trees: A Data Structure for Retrieval on Composite Keys (Acta Informatica, 1974): https://doi.org/10.1007/BF00288933

• Wiki

  Geohash (Wikipedia, for the encoding and its edge cases): https://en.wikipedia.org/wiki/Geohash