Designing Memcached or an in-memory KV store

Requirements

1. High-performance, distributed key-value store

• Why distributed?
  • Answer: to hold a larger size of data

2. For in-memory storage of small data objects
3. Simple server (pushing complexity to the client) and hence reliable and easy to deploy

Architecture

Big Picture: Client-server

• client
• given a list of Memcached servers
• chooses a server based on the key
• server
• store KVs into the internal hash table
• LRU eviction

The Key-value server consists of a fixed-size hash table + single-threaded handler + coarse locking

How to handle collisions? Mostly three ways to resolve:

1. Separate chaining: the collided bucket chains a list of entries with the same index, and you can always append the newly collided key-value pair to the list.
2. open addressing: if there is a collision, go to the next index until finding an available bucket.
3. dynamic resizing: resize the hash table and allocate more spaces; hence, collisions will happen less frequently.

How does the client determine which server to query?

See Data Partition and Routing

How to use cache?

See Key value cache

How to further optimize?

See How Facebook Scale its Social Graph Store? TAO