AI-off twin: the hash ring
Why it matters The wrapped log in Fixation on yourself had one idea at its core. Here it is again, in a system you might really build, with the tutor off.
The tutor is switched off for this problem. Work it out yourself.
A cache cluster spreads keys over servers with consistent hashing. Every server owns some positions on a ring of whole numbers from 0 up to about two billion. A key is hashed to a number, and it belongs to the first node position at or after that number, going round the ring: past the largest position, it wraps to the smallest.
The node positions are stored sorted in a shared table, but the table is a circular buffer: it starts wherever the last writer left off. Every read of the table is a network round trip, so reads are counted.
The data
from creative.budget import Tape
ring = Tape([700, 900, 100, 300]) # sorted positions 100, 300, 700, 900, stored from 700
hashes = [250, 950]
# owners(ring, hashes) -> [300, 100]Write owners(ring, hashes). ring is a Tape of distinct node positions that are sorted but may be rotated (stored from any starting point, possibly 0). It holds at least one node. For each hash h, return the smallest position >= h; if there is none, return the smallest position of all. Budget: with 100,000 nodes and 200 hashes you may read at most 20,000 values. len(ring) is free.
AI off: no tutor, hints or worked solution on this one. Your own thinking only.
Spotted a problem in this lesson? Report it · Ask about this lesson
This exercise opens soon
Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.
This browser is blocking cookies for learn.floati.life, so lessons you finished here cannot open in order. Allow cookies for this site and reload.