Reads, not writes: what our rank histogram really bounds

I wanted a player's rank on a big board to cost the same to read as it does on a small one.

The problem

Our index stores every player in exact rank order, but DynamoDB has no operation for "what position is this row in". The only way to an exact rank is counting every entry ahead of the player, and asking for a count instead of the rows reduces the bytes coming back, not the reads being charged. Rank 40,000 costs forty times what rank 1,000 costs: a strange thing to put in a public endpoint, where the more players you attract, the more each one costs to answer.

Tools here: DynamoDB Query with Select: COUNT, one small metadata item per board, vitest, Stryker for mutation testing, and DynamoDB Local for the route benchmark.

How it works

Picture a queue you cannot see the front of. Counting everyone ahead of you is exact but takes as long as the queue is. So instead the room keeps a tally board: how many people are holding a ticket in each price band. Count the bands above yours, and you know your position to within the size of your own band.

Precisely: the service keeps a histogram of 128 buckets per leaderboard, where a bucket is just a counter of how many players have a score in that range. The bands are logarithmic, so each one covers a constant ratio of score rather than a constant amount. The mapping, verbatim from the shipped code:

bucket = Math.min(127, Math.floor(Math.log1p(score) / Math.log(SCORE_CEILING) * 128));

SCORE_CEILING is 10¹², and ln(10^12) is about 27.631. A concrete example: score 1,000 lands in bucket 32, score 10,000 in bucket 42, and score 1,000,000 in bucket 64. Every factor of ten costs about 10.7 buckets, because ln(10) / ln(10^12) × 128 is 10.67.

Log spacing fits because scores are ratios, not amounts. Going from 100 to 200 points is an achievement; going from 900,000,000,000 to 900,000,000,100 is noise. Equal-width buckets over a domain of 10¹² would file every ordinary trivia score into bucket zero.

Figure 1. Bucket index for ten sample scores, produced by calling the shipped mapping function on 2026-09-18. These are computed values, not measurements.

The read path

The query counts index entries ahead of the player and stops at 2,000. Below that, the answer is exact: rank is the count plus one. At exactly 2,000 the count is abandoned and the board's single metadata row is read instead; the buckets above the player's own are summed, and the response carries a rank range, a percentile range and a rounded midpoint. rank stays null, because an estimate that looks exact is worse than no number.

Worst-case work is therefore at most 2,000 index entries plus one fixed-size item, whatever the population. Constant in population is not the same as cheap: 2,000 entries is still 2,000 entries.

Figure 2. The read path for a player's rank, from the shipped calculator and the design document behind it.

The width of the estimate is the honest part of the design. The player could be anywhere inside their own bucket, so the response says so. Ordering inside a bucket is invisible to the histogram, and the range deliberately covers every tied position that could be correct.

The thing I want to correct

An earlier draft of this write-up claimed the histogram spreads writes across buckets and so avoids hot partitions. That is wrong, and worth naming, because I believed it while writing it.

The histogram bounds reads. It does nothing to writes. Our rank key is still invertedScore#achievedAtMillis#playerId, with no bucket component anywhere in it, so bucketing changes nothing about which partition a score row lands on. If anything it concentrates writes: all 128 counters for a board are attributes on a single item, so every accepted score on that board updates the same row.

Our decision record flagged exactly that as a risk to measure before deployment, and the measurement happened. On 2026-08-19 we drove 1,000 new-player submissions at one board on DEV. At eight in flight all 1,000 succeeded. At 64, 525 succeeded and 475 failed, with the run's decision note recording that DynamoDB throttled nothing, so the limit is transaction conflict on that one row, not capacity.

Figure 3. Latency of new-player submissions to one all-time board, DEV us-east-1, 2026-08-19T01:35:30Z, 1,000 attempted at each level. These are write-path numbers for the same row the rank estimate reads; they are not the propagation SLO measurement.

The rule taken from that run is to review sharding before more than eight simultaneous new or improving writes land on one board, or when the counter row reaches a quarter of the table's write consumption. At the zero-failure level the table consumed 6,868 write capacity units in its peak minute, and the run put the counter row's share at 29.1 percent of that: a figure it marks as inferred, since DynamoDB reports capacity per table and not per item.

The recorded decision was not to shard yet. I notice that 29.1 percent is already past the 25 percent line in our own trigger, which is a contradiction sitting in our notes that nobody has resolved, including me.

What has actually been tested

What	Evidence	Limit
The bucket mapping	unit tests only	no load test of 128 as a bucket count
The calculator's logic	99.30% mutation score, 1 survivor of 143 mutants	one snapshot, committed 2026-08-19
The route end to end	2,501 rows on DynamoDB Local, 25 samples, p99 70.292 ms	not AWS latency, not a capacity or price measurement
Estimate width	rank interval 500, percentile interval 20	one fixture, one distribution
The counter row under load	the DEV run above	one board, one period, new players only

Two things to be plain about. The 70.292 ms p99 comes from DynamoDB Local, which reproduces neither AWS network latency nor service capacity nor billing, and the artifact says so itself. And the interval widths (500 ranks, 20 percentage points) come from one seeded distribution, so I have no idea yet whether a real board's crowding makes them wider.

What we still do not know

• Whether 128 is the right number. It is unit-tested and never load-tested. A bigger histogram is a bigger row; a smaller one is a wider estimate. Nothing has measured that trade.
• What a rank read costs on AWS. There is no per-request consumed-capacity measurement for this route at all. The follow-up that would have produced one was specified in detail and never run: no commits, no report.
• How ordinary scores really spread. From the code's own formula, scores of 0 to 9,999 occupy buckets 0 to 42 and touch 40 distinct buckets: three indices (1, 2 and 4) hold no integer score at all, because down there the buckets are finer than the integers they separate. That is arithmetic, not data.
• Whether the estimate is ever too wide to show. The decision record asks for median and p99 interval widths before a display policy is accepted. We have one number from one fixture.

Key takeaways

• If an exact answer costs more the more successful you are, cap it and say so in the response. Ours stops counting at 2,000 and returns a range beyond that.
• Logarithmic buckets fit scores because scores are ratios. Each factor of ten costs about 10.7 of our 128 buckets.
• Never dress an estimate as a fact. rank is null on the estimated path, and the range comes with it.
• A histogram bounds reads. It does not spread writes, and putting all 128 counters on one row concentrates them.
• Unit tests and a local benchmark tell you the shape is right. They say nothing about the AWS price.

What we would do next

1. Log consumed capacity per request on the rank route against a run-scoped DEV board, so the read has a real price and not just a bound.
2. Record median and p99 estimate widths across several distributions before any interface promises a percentile.
3. Test 64 and 256 buckets against the same fixtures, so the bucket count is a measured choice rather than a reasonable-sounding one.
4. Settle the contradiction above: either the 25 percent line is wrong, or the counter row is due for sharding now. It cannot be both.

Evidence

All times UTC.

• 128 buckets, the 2,000 cap, and the mapping: src/lib/rank-percentile-calculator.js: EXACT_RANK_LIMIT = 2_000, HISTOGRAM_BUCKET_COUNT = 128, scoreToHistogramBucket, and calculateRankPercentile returning kind: 'estimated' with rank: null, rankRange and percentileRange.
• SCORE_CEILING = 1,000,000,000,000: src/constants/score-limits.js. ln(10^12) ≈ 27.631 and ln(10)/ln(10^12) × 128 ≈ 10.67 are arithmetic on that constant.
• Bucket indices in Figure 1, and the 0–9,999 spread: computed on 2026-09-18 by calling the shipped scoreToHistogramBucket on each score, and by a binary search over the same function for the reachable-bucket count. Computed, not measured.
• The rank key has no bucket component: src/lib/score-key-builder.js: buildRankKey returns <invertedScore(13)>#<achievedAtMillis(13)>#<playerId>.
• The counter row was flagged as a hot spot, and the storage shape: docs/adr/0013-bounded-rank-percentile.md ("One metadata item is a per-board write hot spot") and docs/design/rank-percentile.md (meta#<leaderboardId>, playerCount, histogramVersion, bucket000–bucket127).
• DEV write run: 1,000/1,000 at 8 in flight, 525/1,000 at 64, latency percentiles, 6,868 peak-minute write units, 29.1% inferred share, and the sharding trigger: benchmarks/LFL26LEADBORD-035/metadata-counter-dev.json, measured 2026-08-19T01:35:30.415Z, deployed commit e3fb772; narrative in the same directory's README.md; reviewed as Lapis-Foundry-Labs/online-leaderboard#52.
• Route benchmark: 2,501 rows, 25 samples, p99 70.292 ms, rank interval 500, percentile interval 20: reports/LFL26LEADBORD-036/local-route-benchmark.json, measured 2026-08-19T02:51:38Z, with its own limitations field naming DynamoDB Local's limits; reports/LFL26LEADBORD-036/README.md repeats them.
• Calculator mutation score 99.30% (141 killed, 1 timeout, 1 survived of 143): recomputed from the per-mutant statuses in reports/LFL26LEADBORD-055/mutation.json, committed 2026-08-19.
• The AWS-scale measurement that never ran: docs/archive/specifications/ticket-054-logging-specification.md; git log --all returns no commit mentioning LFL26LEADBORD-054 and reports/ holds no directory for it.