Photo Cache Ring
A photo site keeps thumbnails on a handful of cache servers. With hash(key) mod N, adding a fifth server to four would move about 4 in 5 keys to a different server, and that flood of cache misses would land on the database at once. A hash ring moves only the keys next to the new server's points. Each server is placed at several points on the ring (virtual nodes) so the load evens out, and a key can be stored on the next few distinct servers clockwise, so a copy survives when one server dies.
This is the ring from Consistent Hashing, used to spread keys across cache servers (Caching) and to choose replicas in leaderless key-value stores (Design a Key-Value Store).
Your task
The ring has positions 0 to 232 − 1. Positions come from ringHash(s), a 32-bit FNV-1a hash followed by a mixing step. It is given in the starter code in both languages, so JavaScript and Python agree exactly; use it as it is.
Write a class HashRing:
constructor(vnodes): every server getsvnodespoints.addNode(name): add the server's points. Pointi(from 0 tovnodes − 1) has the labelname + "#" + iand sits atringHash(label). Adding a server that is already on the ring does nothing.removeNode(name): remove all of that server's points. Removing a server that is not on the ring does nothing.owners(key, count): start at positionringHash(key)and walk clockwise: the first point at or after that position, then the next, wrapping from the highest position back to the lowest. Collect server names in the order you meet them, skipping servers already collected, until you havecountnames or have seen every server. Return the list. An empty ring gives[].
If two points share a position, the one whose label sorts first (comparing character codes) comes first clockwise.
class HashRing
Examples
new HashRing(2)
.addNode("cache-a")
.addNode("cache-b")
.addNode("cache-c")
.owners("sun.jpg", 1)
.owners("sun.jpg", 2)
.owners("photo-3", 3)
.removeNode("cache-b")
.owners("sun.jpg", 1)
.owners("photo-3", 3)[null, null, null, null, ["cache-b"], ["cache-b", "cache-c"], ["cache-a", "cache-c", "cache-b"], null, ["cache-c"], ["cache-a", "cache-c"]]
In millions, the six points sit at a#0 25.1, a#1 152.6, c#1 414.5, b#0 616.2, b#1 1,845.2 and c#0 3,752.1. "sun.jpg" hashes to 476.3, so the first point clockwise is b#0: owner cache-b. For two owners the walk goes on to b#1, which is cache-b again and is skipped, then c#0: cache-c. "photo-3" hashes to 3,939.4, past the last point, so the walk wraps to a#0, then a#1 (skipped), c#1, b#0. After cache-b leaves, "sun.jpg" moves to the next point, c#0, while "photo-3" still starts at cache-a: only keys that cache-b owned have moved. With two servers left, asking for 3 owners returns 2.
new HashRing(1)
.owners("cat.jpg", 2)
.addNode("solo")
.addNode("solo")
.owners("cat.jpg", 2)
.removeNode("ghost")
.owners("cat.jpg", 1)[null, [], null, null, ["solo"], null, ["solo"]]
An empty ring has no owners. Adding "solo" twice still leaves one point, so even with 2 owners requested only one server exists. Removing a server that was never added changes nothing.
Constraints
- 1 ≤ vnodes ≤ 50
- At most 20 servers on the ring at once; names are 1 to 20 letters, digits or hyphens
- Keys are 1 to 40 printable ASCII characters
- 1 ≤ count ≤ 20
- At most 1,000 calls per test
Start with brute force
For each lookup you could compute the clockwise distance from the key to every point, (point − key) mod 232, and sort. That is correct but costs O(P log P) per lookup for P points: with 20 servers × 50 points, 1,000 points sorted for every single cache read.
Keeping the points sorted once, when servers join or leave (rare), turns each lookup into a binary search plus a short walk.
Hints
0 of 4 shown- Hint 1
Forget servers for a moment and think only about points on a circle. Given a position, how do you find the first point at or after it quickly if the points are kept sorted? What if there is none?
- Hint 2
Keep every point as
(position, label, server)in a list sorted by position, then label. Binary search finds the first point with position ≥ the key's position; if it runs off the end, start at index 0. - Hint 3
For several owners, keep walking from that index, wrapping with
% points.length, and use a set of servers already collected to skip their other points. Stop aftercountservers, or after one full lap. - Hint 4
Adding a server inserts its
vnodespoints and keeps the list sorted; removing it filters its points out. Keep a set of servers on the ring so adding twice and removing an unknown server are easy to ignore.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The ring is a sorted list of points. A lookup is a binary search for the first point at or after the key's position, then a clockwise walk that wraps with % n. Servers change rarely, so re-sorting on add is fine; lookups happen on every cache read, so they get the fast path.
Trace the first example (positions in millions). Sorted points: a#0 25.1, a#1 152.6, c#1 414.5, b#0 616.2, b#1 1,845.2, c#0 3,752.1.
owners("sun.jpg", 2): hash 476.3. Binary search lands on index 3, b#0: cache-b. Index 4, b#1: cache-b again, skip. Index 5, c#0: cache-c. Two names: done.owners("photo-3", 3): hash 3,939.4 is above every point, so the search returns 6 = n, and6 % 6 = 0wraps to a#0: cache-a. Then a#1 (skip), c#1: cache-c, b#0: cache-b.- Remove cache-b: the list becomes a#0, a#1, c#1, c#0. "sun.jpg" now lands on index 3, c#0: cache-c. "photo-3" still wraps to cache-a.
The skip-seen set matters: without it, a server's second virtual node would be counted as a second replica, and both copies of a key would sit on one machine. Stopping when every server has been collected keeps the walk to one lap even when count is larger than the number of servers.
function ringHash(s) {
let h = 2166136261;
for (let i = 0; i < s.length; i++) h = Math.imul(h ^ s.charCodeAt(i), 16777619) >>> 0;
h = (h ^ (h >>> 13)) >>> 0;
h = Math.imul(h, 0x5bd1e995) >>> 0;
return (h ^ (h >>> 15)) >>> 0;
}
class HashRing {
constructor(vnodes) {
this.vnodes = vnodes;
this.points = []; // [position, label, server], sorted by position then label
this.servers = new Set();
}
addNode(name) {
if (this.servers.has(name)) return;
this.servers.add(name);
for (let i = 0; i < this.vnodes; i++) {
const label = name + '#' + i;
this.points.push([ringHash(label), label, name]);
}
this.points.sort((a, b) => a[0] - b[0] || (a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0));
}
removeNode(name) {
if (!this.servers.delete(name)) return;
this.points = this.points.filter((p) => p[2] !== name);
}
owners(key, count) {
const n = this.points.length, h = ringHash(key);
let lo = 0, hi = n; // first point with position >= h
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.points[mid][0] < h) lo = mid + 1; else hi = mid;
}
const out = [], seen = new Set();
for (let k = 0; k < n && out.length < count && out.length < this.servers.size; k++) {
const server = this.points[(lo + k) % n][2]; // % n wraps past the top
if (!seen.has(server)) { seen.add(server); out.push(server); }
}
return out;
}
}from bisect import bisect_left
def ring_hash(s):
h = 2166136261
for ch in s:
h = ((h ^ ord(ch)) * 16777619) & 0xFFFFFFFF
h ^= h >> 13
h = (h * 0x5BD1E995) & 0xFFFFFFFF
return h ^ (h >> 15)
class HashRing:
def __init__(self, vnodes):
self.vnodes = vnodes
self.points = [] # (position, label, server), sorted by position then label
self.servers = set()
def add_node(self, name):
if name in self.servers:
return
self.servers.add(name)
for i in range(self.vnodes):
label = f"{name}#{i}"
self.points.append((ring_hash(label), label, name))
self.points.sort()
def remove_node(self, name):
if name not in self.servers:
return
self.servers.remove(name)
self.points = [p for p in self.points if p[2] != name]
def owners(self, key, count):
n = len(self.points)
start = bisect_left(self.points, (ring_hash(key),)) # first position >= hash
out, seen = [], set()
for k in range(n):
if len(out) == count or len(out) == len(self.servers):
break
server = self.points[(start + k) % n][2] # % n wraps past the top
if server not in seen:
seen.add(server)
out.append(server)
return outRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.