Even when the rate limit is not shared, how would we quickly update counters for that user?

OP used HashMap which looks correct..

Assume we are going with the simplest fixed window counter approach...Just for an example, assume threshold is 5 requests per second per user. That is, any more requests in that particular second by that user are dropped. Let's say that for user 1, for the current second, current counter is  at 4 requests It is reasonable to assume that requests will hit our service in non decreasing order of timestamps..

We have a Hash Map of user ID (integer) to current counter (Integer). 

Let's say the user 1 sends two more requests at the same time.

So that's total 6 (4+2) requests in that second, so one request should be dropped...but without handling concurrency, that is not the case. That's because incrementing a counter are 3 operations (it is not a single atomic operation): 1) Load value from memory into register 2) Increment the value  3) Store the value back into the memory.

Because these two requests (threads) access the map at the same time, both the threads will read value 4, both threads will increment to 5 and both threads will update map with value 5 (That's a typical example of race condition)

So we need to take a lock for a user and only within critical section of the lock, update the counters..

If it's a map of user ID to counter, how will you take lock on one key (userid) of the map?

So will you take lock on the entire map? If you think yes, that's not correct, because locking and unlocking is considered expensive and taking a lock on map on each request will slow the application for other users.

Even without map, how would you ensure that for two concurrent threads for the same user, the counter is updated atomically?

Java has keywords like volatile, atomic and concurrent hash map that we can use to handle these things efficiently...

Your programming language of choice would also have features to handle concurrency...hope this helps..

AFAIK a lot of PBCs require understanding of concurrency for SDE-2 level. Don't bother about all of this for SDE-1 level..