|
69
|
1 # Distributed Cache (Focus: Hashing & System Logic)
|
|
|
2
|
|
|
3 - Question: Implement a Cache Router
|
|
|
4
|
|
|
5 Level 1 (Easy - Modulo Hashing): Write a function that maps a key (string) to one of N servers.
|
|
|
6
|
|
|
7 Task: Implement getServerIndex(key, serverCount).
|
|
|
8
|
|
|
9 Expected Logic: Simple hash modulo: hash(key) % serverCount.
|
|
|
10
|
|
|
11 Critique: The interviewer will ask, "What happens to the existing keys if we add one server (change N to N+1)?" (Answer: Almost all keys get remapped, causing a massive cache miss storm).
|
|
|
12
|
|
|
13 Level 2 (Medium - Consistent Hashing): Solve the remapping problem. Implement a ConsistentHash class.
|
|
|
14
|
|
|
15 Task: Map servers to points on a circle (0 to 360 degrees or a large integer range). Map keys to the same circle. A key belongs to the first server it encounters moving clockwise.
|
|
|
16
|
|
|
17 Goal: Prove that adding a server only requires remapping the keys that fall between the new server and its predecessor.
|
|
|
18
|
|
|
19 Level 3 (Hard - Virtual Nodes): The servers have uneven capacity, or the data distribution is skewed (some segments of the ring have way more keys).
|
|
|
20
|
|
|
21 Task: Modify the class so that each physical server exists at multiple points on the ring (e.g., "Server A" is at positions 10, 150, and 290).
|
|
|
22
|
|
|
23 Goal: Distribute load more evenly and handle "hot spots" better.
|
|
|
24
|
|
|
25 ---
|
|
|
26
|
|
|
27 Questions:
|
|
|
28
|
|
|
29 - Async
|
|
|
30 - Threads
|
|
|
31 - DB
|
|
|
32 - Cache
|
|
|
33 - KV
|
|
|
34 - Distribution
|
|
|
35
|
|
|
36
|
|
|
37 ---
|
|
|
38
|
|
|
39 FE
|
|
|
40
|
|
|
41 - Fetching URL
|
|
|
42 - Storing it as useMemo and what not.
|
|
|
43
|
