educative.io

How to implement rate limiter lock using hash table

Courses
,
#1

In discussion on atomicity, the page says “If we are using a simple hash-table, we can have a custom implementation for ‘locking’ each record to solve our atomicity problems.” How exactly does that work?

#2

Hi Thape,

We are suggesting a locking mechanism similar to Java’s ConcurrentHashMap. Here is a bit background:

HashMap (in java) is not synchronized and so doesn’t provide any thread safety. In contrast Hashtable is synchronized and provides thread safety but on the stake of performance. Hastable write operation uses map wide lock which means it locks the complete map object. As you can see, this locking is not efficient.

ConcurrentHashMap works bit different as it acquires lock per Segment which means instead of single map wide lock, it has multiple Segment level locks.

We can take the similar idea to lock individual keys, but it will have storage implications.

Some good reads:


Hope this will help.

2 Likes
#3

This solves on single server. How would you solve for multiple servers?

2 Likes
#4

Exactly!
They did not mention how they will implement a distributed hash table (with multiple replicas) with soft lock.
I am bit frustrated with their “one liner” unexplained solutions to different problems.

In youtube design they chose to use SQL (because the data was structured) without explaining how scalability of youtube scale is handled in such case.

2 Likes
#5

I think it is rebuilding the wheel if you want to build your own distributed hash table with atomic property when memcahce or redis can provide one.

#6

This video talks about distributed rate limiter.
Here he explicitly callout that you cannot achieve 100% atomicity in distributed rate limiter. He says if you use object locking than you will have to incur additional latency for other requests since they are all waiting for a single request to release lock.

#7

So if I am understanding correctly, essentially the “simple hash-table” is to just use one entry/row for each customer where userID is the key and the count-time are the value. When there is a request to update the status for a user, it locks the entry/row and do the update, without affecting all other userID’s data. If we are using java hash-table or Redis provided function to store our key-value, it would need lock the whole hash-table for thread-safety purpose. Am I right?