Consistent hashing in HLD - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the hash ring size in consistent hashing.

HLD

hash_ring_size = 2[1]32

Drag options to blanks, or click blank then click option'

A*

B//

C**

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication '*' instead of exponentiation '**'.

Using integer division '//' which truncates the value.

Consistent hashing uses a hash ring, often sized as 2 to the power of 32 for a 32-bit hash space.

2fill in blank

medium

Complete the code to find the next node clockwise on the hash ring.

HLD

next_node = sorted_nodes[bisect.bisect_right(sorted_nodes, key_hash) [1] len(sorted_nodes)]

Drag options to blanks, or click blank then click option'

A-

B+

C//

D%

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition '+' without modulo causes index errors.

Using integer division '//' which is not suitable here.

Modulo '%' is used to wrap around the ring when the key's hash is beyond the last node.

3fill in blank

hard

Fix the error in the code to correctly add virtual nodes to the hash ring.

HLD

for i in range(num_virtual_nodes):
    virtual_node_key = f"{node}-VN[1]"
    hash_value = hash_function(virtual_node_key)
    hash_ring[hash_value] = node

Drag options to blanks, or click blank then click option'

Ai

Bnode

Cnum_virtual_nodes

Dhash_value

Attempts:

3 left

💡 Hint

Common Mistakes

Using the node name repeatedly without index causes key collisions.

Using hash_value inside the string causes errors.

The loop index 'i' is used to create unique virtual node keys by appending it to the node name.

4fill in blank

hard

Fill both blanks to complete the code that finds the responsible node for a given key.

HLD

key_hash = hash_function(key)
index = bisect.bisect_right(sorted_hashes, key_hash) [1] len(sorted_hashes)
responsible_node = hash_ring[sorted_hashes[index [2]]]

Drag options to blanks, or click blank then click option'

A%

B+

C-

D//

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition '+' instead of modulo causes index errors.

Using integer division '//' is incorrect here.

The modulo operator '%' wraps the index around the ring, and '-' subtracts 1 to get the correct index in the list.

5fill in blank

hard

Fill both blanks to complete the code that reassigns keys when a node is removed.

HLD

for key in keys_to_reassign:
    key_hash = hash_function(key)
    new_index = bisect.bisect_right(sorted_hashes, key_hash) [1] len(sorted_hashes)
    new_node = hash_ring[sorted_hashes[new_index [2]]]
    key_node_map[key] = new_node

Drag options to blanks, or click blank then click option'

A%

B+

C-

Attempts:

3 left

💡 Hint

Common Mistakes

Adding '+' instead of modulo causes errors.

Adding extra characters after assignment causes syntax errors.

Modulo '%' wraps the index, '-' adjusts the index to the correct node, and no extra operator is needed after assignment.

Practice

1. What is the main advantage of consistent hashing in distributed systems?

easy

A. It stores data only on one server

B. It guarantees equal data size on all servers

C. It requires no hashing function

D. It minimizes data movement when servers are added or removed

Solution

1. Step 1: Understand consistent hashing purpose

   Consistent hashing is designed to reduce the amount of data that needs to be moved when servers join or leave the system.

2. Step 2: Compare options with consistent hashing benefits

   Only It minimizes data movement when servers are added or removed correctly states this key advantage. Other options are incorrect or unrelated.

3. Final Answer:

   It minimizes data movement when servers are added or removed -> Option D

4. Quick Check:

   Minimize data movement = D [OK]

Hint: Remember: consistent hashing reduces data reshuffling [OK]

Common Mistakes:

• Thinking consistent hashing balances data perfectly
• Assuming no hashing function is needed
• Believing data is stored on only one server

2. Which of the following is a correct step in implementing consistent hashing?

easy

A. Assign each server multiple points on the hash ring (virtual nodes)

B. Store all data on a single server to avoid hashing

C. Use a linear list instead of a circular ring

D. Hash data keys directly to server IP addresses without hashing servers

Solution

1. Step 1: Recall consistent hashing implementation details

   Consistent hashing uses a circular ring and assigns multiple virtual nodes per server to balance load.

2. Step 2: Evaluate each option

   Assign each server multiple points on the hash ring (virtual nodes) correctly describes virtual nodes. Options A, C, and D contradict consistent hashing principles.

3. Final Answer:

   Assign each server multiple points on the hash ring (virtual nodes) -> Option A

4. Quick Check:

   Virtual nodes = B [OK]

Hint: Virtual nodes improve load balance in consistent hashing [OK]

Common Mistakes:

• Ignoring virtual nodes and using single points
• Using linear lists instead of circular rings
• Skipping hashing of servers

3. Given a consistent hashing ring with servers at hash points 10, 30, and 50, where will the data key with hash 35 be stored?

medium

A. Server at 50

B. Server at 30

C. Server at 10

D. Server at 35

Solution

1. Step 1: Understand consistent hashing key assignment

   Data is assigned to the next server clockwise on the ring after the key's hash.

2. Step 2: Find the next server after hash 35

   Servers are at 10, 30, and 50. After 35 clockwise is 50.

3. Final Answer:

   Server at 50 -> Option A

4. Quick Check:

   Next clockwise server after 35 = 50 [OK]

Hint: Assign data to next clockwise server on ring [OK]

Common Mistakes:

• Assigning data to previous server instead of next
• Choosing server at 30 because it's closest numerically
• Assuming server at 35 exists

4. In a consistent hashing system, a developer notices that when a new server is added, almost all data moves to the new server. What is the likely cause?

medium

A. The data keys are not hashed before assignment

B. The new server has fewer virtual nodes than others

C. The hash function is not distributing servers evenly on the ring

D. The ring is implemented as a linear list

Solution

1. Step 1: Analyze the problem of data movement on server addition

   If almost all data moves to the new server, it means the new server's position dominates the ring.

2. Step 2: Identify cause related to server distribution

   This happens if the hash function places servers unevenly, clustering many keys near the new server.

3. Final Answer:

   The hash function is not distributing servers evenly on the ring -> Option C

4. Quick Check:

   Uneven server distribution = A [OK]

Hint: Check server hash distribution to avoid data skew [OK]

Common Mistakes:

• Blaming virtual nodes count without checking hash function
• Ignoring hashing of data keys
• Confusing ring structure with linear list

5. You are designing a distributed cache using consistent hashing. To handle server failures gracefully, which approach is best?

hard

A. Assign each data key to only one server without replication

B. Use virtual nodes and replicate data on the next N servers clockwise

C. Use a fixed number of servers without adding or removing nodes

D. Hash data keys to servers randomly each time

Solution

1. Step 1: Understand fault tolerance in consistent hashing

   To handle failures, data should be replicated to multiple servers to avoid data loss.

2. Step 2: Identify best practice for replication

   Using virtual nodes improves load balance, and replicating data on next N servers clockwise ensures availability.

3. Final Answer:

   Use virtual nodes and replicate data on the next N servers clockwise -> Option B

4. Quick Check:

   Replication + virtual nodes = A [OK]

Hint: Replicate data on next servers for fault tolerance [OK]

Common Mistakes:

• Not replicating data causing data loss on failure
• Avoiding virtual nodes and causing imbalance
• Randomly hashing keys each time causing inconsistency