sectionScaling Memcache [8143e125]

1. Main data structures of memcache

Hash table
- Chained hash table, everything is a linked list
Cache item data structure
Slab allocator
- Memcached Items
  - Item that holds data for a k,v pair
- allocators
- A slab is a list of memory sections containing objects (pages) categories by the memroize size range they fall into
  - By default the memory is split into 42 slabs
  - first slab for items less than 96 bytes
  - second for 96-120 bytes
  - etc
LRU list
- For evicting the oldest and least used items, LRU matches to different slabs

Adaptive slab allocator
- Peroidic rebalancing of slabs
- If slabs needs more memory if it is evicting a lot of items, or if an item that is evicted was being used 20% more recently than the average of the least recently used item in other slab classes
- When we identify a needy slab, we free up the least recently used slab and transer it to the needy class
Short lived keys are pruned using a circular buffer than removes one item every second

Key load is managed by consistent hashing
although this means we need a memcached router for balancing, hence github.com/facebook/mcrouter
MC router talks with the memcache ASCII protocol
Network efficiency issue: incast congestion
- When a large number of responses to request overload a DC's cluster and rack switches, when we to rack to rack, such as broadcasting with memcache
- Use a sliding window, similar to TCP
High load issues
- Stale sets
  - When a sequence of concurrent operations get reordered
- Thundering herd
  - When multiple clients attempt to request the same thing at once
- Solution: use leases
  - We "lease" the key value to a client by allocating a token, to set the item, the client has to provide the token again
  - A token can be invalidated if the Memcached server receives a delete request for the key
    - Similar to load-linked and store-conditionals
Different applications need different sizes, what do we do?
- Different pools of memcached, such as low-churn keys and high-churn keys
- Replication within pools to improve latency and divide the load
  - Sometimes we want to split the keyset, but other times we might just want to replicate the key set
Small outages
- Add "gutter" servers, which do not rehash the key-value items to other Memcached using consistent hashing. K/V's in the gutter pool are drained quickly

Scaling a cluster natively makes it so that our networks start to face incast congestion
We'd rather replicate clusters
But how do we invalidate when we replicate?
THere needs to be two ways of invalidation: either the backend DB invalidates the key on an update, or the client does
- We can set an invalidation daemon that discovers or just broadcasts UDP to all memcached instances to invalidate
- Note that the dameons batch as well

How many places should keys be replicated?
Create a regional pool of memcached servers that multiple clients share, and move data between different pools as needed

New pools should look at warm pools to replicate, not the DB, otherwise it threatens to overwhelm the DB
To avoid races, we hold off delete operations, and clients add to the new cluster instead of the old