Design a Thread-Safe Concurrent LRU Cache

Problem

Implement an LRU cache that is correct under concurrent get/put from many threads.

Example

Multiple threads; O(1) ops; no races

Constraints

• High contention

Discussion

Lock striping/sharding vs a single lock; trade-offs vs a lock-free design.