Experiments and implementations · Intermediate

Measure hash-placement changes for fixed keys

Compare three and four owners for ten thousand fixed keys, verifying movement targets, skew, virtual points and reproducible old placement.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Compare fixed keys before and after one addition
  2. Read deterministic encoding and successor lookup
  3. Assert that reassigned keys move only to D
  4. Interpret a skewed finite ring without a universal fraction
  5. Identify what live movement still needs
  6. Give every reported count a precise meaning
  7. Solve the changed-key-set exercise
  8. Ask Logeia about this articleCheck your understanding

Compare fixed keys before and after one addition

Place key-0 through key-9999 across A, B and C, then add D. Read consistent hashing first. Only the ownership function changes; no live data is copied or authority transferred. Fixed strings and SHA-256 reproduce placement across runs. Share the same KEYS before and after so configuration effects are not mixed with input changes.

Run separate configurations with one and sixty-four virtual points per node. They are not stages of one migration: changing virtual-point count also changes existing placement. Compare three-to-four membership within each configuration. The metrics are reassigned keys and per-node key counts, not duration, transfer bytes or production traffic balance. Equal keys can still have unequal values or request rates. These scope choices make the claimed placement property directly testable.

Read deterministic encoding and successor lookup

Save rebalance.py and run it with Python 3.12 or later. Encode strings as UTF-8, hash with SHA-256 and interpret bytes as a big-endian integer. Virtual identities such as A:v0 remain stable. Sort point-owner pairs and use bisect_left to find the first point at or above the key. Modulo point count wraps beyond the last point to the first.

No process-randomized built-in hash is used. Persistent placement needs fixed computation and encoding. The known short identities make delimiters unambiguous here; arbitrary-string extensions need an explicit framing rule. Sorted physical identity participates in equal-point handling and belongs in the contract. Selecting SHA-256 alone does not normalize every possible input representation. A cross-language implementation should reproduce encoded bytes, point order and selected owner, not merely use a function with the same familiar name.

Assert that reassigned keys move only to D

Collect keys whose before and after owners differ. D contributes new points while existing ones stay unchanged, so every changed key must now select D. Also assert that assignments not owned by D remain equal to before. Removing D and recomputing the original membership must reproduce before exactly. This is a placement-function property, not recovery of values written at D.

Output counts also sum to ten thousand and account for each owner. Renaming existing IDs or regenerating points with a new seed can invalidate localized movement. If testing those changes, preserve why the original assertion fails instead of deleting it to accept arbitrary remapping. State which property the revised design promises. Deterministic assertions should expose a changed contract, not be rewritten merely to match an attractive observed result.

python
import bisect,collections,hashlib
KEYS=[f'key-{i}' for i in range(10000)]
def digest(text):return int.from_bytes(hashlib.sha256(text.encode()).digest(),'big')
def place(nodes,virtuals):
    points=sorted((digest(f'{node}:v{v}'),node) for node in nodes for v in range(virtuals))
    tokens=[p[0] for p in points]
    return [points[bisect.bisect_left(tokens,digest(key))%len(points)][1] for key in KEYS]
for virtuals in [1,64]:
    before=place(['A','B','C'],virtuals);after=place(['A','B','C','D'],virtuals)
    moved=[i for i in range(len(KEYS)) if before[i]!=after[i]]
    assert moved and all(after[i]=='D' for i in moved)
    assert all(before[i]==after[i] for i in range(len(KEYS)) if after[i]!='D')
    restored=place(['A','B','C'],virtuals);assert restored==before
    print('virtuals',virtuals,'moved',len(moved),'before',dict(collections.Counter(before)),'after',dict(collections.Counter(after)))
print('placement verified; no live data was copied')

Interpret a skewed finite ring without a universal fraction

In the recorded one-point configuration, C initially holds 8,651 keys and D takes 5,593 after addition. With sixty-four points, 2,566 move to D and final counts are 2,301, 2,365, 2,768 and 2,566. These are results for this exact hash and key set. They refute treating one quarter as a guaranteed movement fraction for every finite ring.

The larger point count reduces key-count skew in this input, but the program does not assert universal optimality. Additional points cost metadata and lookup work, and a hot key can dominate traffic despite even counts. Byte- or frequency-weighted assessment would be another experiment. The published code has executed and verified movement and restoration; it is not a production performance or network-transfer measurement. Preserve empirical counts rather than replacing them with a convenient theoretical average.

Identify what live movement still needs

A real system must copy changed keys, retain updates and deletions during movement and cut over write authority by configuration generation. The final print explicitly states no live data was copied. Reproducing old ownership does not justify routing back to an old server without checking post-cutover updates. Include deduplication identities and pending send intent if they belong to the moved state.

Failure before publishing after differs from failure after publication. Simultaneous configuration visibility across clients is also an assumption requiring a real protocol. Return to the rebalancing stage table for propagation and fencing. The model remains useful by making its non-executed responsibilities explicit. Its value is a precise tested placement invariant that can guide the next implementation test, rather than an inflated claim that live migration is already complete.

Give every reported count a precise meaning

Per-owner counts sum to ten thousand before and after addition. Movement values 5,593 and 2,566 count indices whose before and after owners differ. They count neither disappeared keys nor completed network transfers. If used to plan an operational migration, keep separate counters for intended reassignment, copied values, change catch-up and authority cutover. A progress display reaching the reassignment count does not prove the later stages. This is especially relevant when values differ in size or updates continue during copying: equal key counts can correspond to unequal transfer work. The placement model supplies a fixed intended set against which those later procedures can be checked without claiming to have executed them.

Keep every counter labeled by stage and unit before comparing progress across implementations.

Solve the changed-key-set exercise

Using different ten-thousand-key sets before and after does not measure reassignment of the same keys. Keep KEYS fixed and compare each owner pair. New-key distribution is a legitimate different experiment with its own label. Separate input, configuration and metric; a fixed hash does not make changed input irrelevant.

Restoring before after removing D does not prove data recovery, because the program stores and moves no values. No service or database needs cleanup. Retain source and output as placement evidence. The learning outcome distinguishes movement rate, skew, live copying and read/write guarantees as separate questions.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 18

Choose a learning path