DEV Community

ssh412
ssh412

Posted on

The ten-line binary search that balanced a four-million-item crawl

#distributedsystems #kubernetes #backend #scaling

A short field note. I had to crawl every item in a public registry (~4 million of them) in about a day. One idea did most of the work.

The problem

Split the sorted keyspace into N ranges, run one worker per range, done. That's the plan. It falls apart because keys aren't uniformly distributed. Cut the alphabet into even chunks and one chunk swallows all the dense prefixes while the rest finish in minutes and sit idle. My first cut had a single shard holding 71% of the work.

And your crawl is only as fast as the slowest shard. So that skew throws away almost all the parallelism: a 56-way fan-out that finishes no faster than a 3-way one. I didn't need equal alphabet width. I needed equal item count per range.

The trick: your source already ranks keys

So the whole thing reduces to one question: which key sits at global position P in the sorted list? Answer that, and the balanced cut points are just the keys at ranks total/N, 2·total/N, ….

Turns out the listing endpoint answers it for free. Ask for one row starting at any key, and it hands back that key's global offset, its rank in the full sorted order:

GET /list?startkey="<key>"&limit=1
→ { "offset": 3200000, "total_rows": 4000000, ... }
Enter fullscreen mode Exit fullscreen mode

rank(key) is monotonic in the sorted key. That's the whole trick. Monotonic means I can binary-search the keys themselves, using rank() as the compare, to run it backwards: give me a target rank, I'll find the key.

def key_at_offset(targetOffset):
    lo, hi = "", "\uffff"               # full key range
    for _ in range(40):                 # ~40 iterations across millions of keys
        mid  = midpoint_string(lo, hi)  # a key lexicographically between lo and hi
        rank = offset_of(mid)           # one cheap API call: the oracle
        if rank < targetOffset: lo = mid
        else:                   hi = mid
    return hi

boundaries = [ key_at_offset(i * total // N) for i in range(1, N) ]
Enter fullscreen mode Exit fullscreen mode

Each step halves the key window, so ~40 calls land a boundary within an item or two. N-1 boundaries is a couple hundred calls total. I run it once, offline, and bake the resulting table straight into the crawler.

Here's what ranking buys you over guessing: even spacing on the rank axis turns into uneven spacing on the key axis. Dense regions get boundaries packed tight, sparse regions get a few wide ones. Every slice is ~1/N of the items, however wide it is in the alphabet.

 rank axis  0 ──────────────────────────────────────────────► ~4M
 even cuts  │    │    │    │    │    │    │    │    │    │    │    (every ~1/N)
 keys       a0 a3 a6 a9   b    c    e   hp hp   m    r    s   w  z
            └─── dense ───┘         └ hot ┘          └── sparse: wide ──┘
            many cuts, packed       drilled          few cuts, wide ranges

 BEFORE  even alphabet, 2 shards      AFTER  offset-balanced, N shards
 one shard  ███████████████ 71%       every shard  █ ~1/N
 finish = the 71% shard               finish ≈ average  → ~1 day
Enter fullscreen mode Exit fullscreen mode

The payoff

The fattest shard went from 71% of the work to ≈ 1/N. That's it. A few hundred offline API calls, and a one-week crawl becomes a one-day crawl.

Everything else was plumbing (durable per-shard cursors so a dead worker resumes where it stopped, idempotent writes so retries cost nothing). Necessary, but not the part worth writing about.

Takeaway

If your source hands you a rank or an offset for a key, you've got a binary-search oracle. Use it. Build balanced partitions, not even-looking ones. Balanced sharding, "give me the item at percentile X", jump-to-position: same ten lines every time, because a monotonic rank() is all bisection ever needs.

Personal notes and my own views, not my employer's. This is a generic distributed-systems write-up, not a description of any specific product, service, or internal system. Names like Kubernetes are trademarks of their respective owners, used nominatively with no endorsement implied.

Top comments (0)