- initial architecture and overview
- memcache works with a thick client architecture, where as much complexity as possible is moved into the client to ensure that the core data service is performant with a restricted set of functionalities.
- This was used in Facebook as a database query cache as well as a generic key value cache, with the client itself performing a replacement in the cache if a key does not exist. This pattern is known as a “demand-filled look aside cache”. Here, look-aside means that the client will handle all communication between the cache and the database. The web server will also invalidate values in the cache when it updates some data.
- items are distributed across memcached servers using consistent hashing. One of the most popular pages causes 512 distinct items to be fetched from memcached - so it’s very likely that every web server talks to every memcached server in a short period of time.
- Latency and ease of use are important factors that the system design is adjusted to prioritize.
- Low-level Cache Primitives
- SET
- GET
- DELETE
- Read path (Application)
- Cache Hit: value returned to the server by the cache
sequenceDiagram participant cl as Client participant c as Memcached cl->>c: GET A c->>cl: OK VAL_A- Cache Miss: Request goes to the database, and the requested value gets written back into the cache by the client
sequenceDiagram participant c as Client participant m as Memcached participant db as Database c->>m: GET A m->>c: FAIL c->>db: SELECT A db->>c: VAL_A c->>m: SET A VAL_A m->>c: OK - Write Path (Application)
- Update: Write request issued to database and key deleted from cache (deleted and not updated because deletes are idempotent)
sequenceDiagram participant c as Client participant m as Memcached participant db as Database c->>db: SET A VAL_B c->>m: DELETE A m->>c: OK
- Update: Write request issued to database and key deleted from cache (deleted and not updated because deletes are idempotent)
- the problems
- stale sets - because in this architecture, the memcached client itself orchestrates data movement between the database and the cache, concurrent requests that write back into the cache can get reordered, causing a stale value to be accidentally written as the latest value for that key in the cache.
- thundering herds - "When a specific key undergoes heavy read and write activity, and the write path repeatedly invalidates the freshly set value for the key, many reads will default to the more costly path"
- what are leases?
- A lease is a 64-bit integer bound to a specific key
- memcached gives a lease to a client that experiences a cache miss - this is permission for the client to set that data back into the cache. The client provides this token to memcached when it sets the value back into the cache.
- memcached then uses the token to arbitrate between concurrent writes and determine if data should be stored (how?)
- "Verification can fail of memcached has invalidated the lease token due to receiving a delete request for that item"
- how do leases solve stale sets?
- stale sets - because in this architecture, the memcached client itself orchestrates data movement between the database and the cache, concurrent requests that write back into the cache can get reordered, causing a stale value to be accidentally written as the latest value for that key in the cache.
- "Load-Link/Store-Conditional" https://en.wikipedia.org/wiki/Load-link/store-conditional - "Load-link returns the current value of a memory location, while a subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link." - this is how memcached uses leases to solve stale sets
- in LL/SC, the Store-Conditional is guaranteed to fail if the address in question has been modified since the load-link.
- how do leases solve thundering herds?
- thundering herds - "When a specific key undergoes heavy read and write activity, and the write path repeatedly invalidates the freshly set value for the key, many reads will default to the more costly path" (also known as a cache stampede)
- memcached can control the rate of issuance of leases (i.e. essentially throttle the number of write-back requests that come in) - they issue only one lease every ten seconds for a given key. A client trying to read a value will get a special response telling it to wait; within the time period (a few milliseconds), the client with the lease has usually written a value back to the cache, so the incoming request can read it. This prevents the massive load on the database.
Stale Set - Problem Diagram
sequenceDiagram
participant c1 as Client 1
participant c2 as Client 2
participant m as Memcached
participant db as Database
rect rgb(0, 0, 255, 0.1)
note right of c1: Client 1 updates A=1
c1->>db: SET A 1
note over db: A:1
c1->>m: DELETE A
m->>c1: OK
end
rect rgb(0, 255, 255, 0.1)
note right of c1: Client 1 Reads A from Cache, Misses
c1->>m: GET A
m->>c1: FAIL
c1->>db: GET A
db->>c1: A=1
end
activate c1
note right of c1: Client 1 has a GC Pause
rect rgb(0, 0, 255, 0.1)
note right of c2: Client 2 updates A=2
c2->>db: SET A 2
note over db: A:2
c2->>m: DELETE A
m->>c2: OK
end
rect rgb(255, 255, 0, 0.1)
note right of c2: Client 2 Reads A from Cache, Misses
c2->>m: GET A
m->>c2: FAIL
c2->>db: GET A
db->>c2: A=2
c2->>m: SET A 2
note over m: A:2 ✅
m->>c2: OK
end
deactivate c1
rect rgb(0, 255, 255, 0.1)
c1->>m: SET A 1
note over m: A: 1 ❌
m->>c1: OK
end
Does the lease have a clock or some kind of monotonicity for tracking?
Stale Set - Solution Diagram
sequenceDiagram
participant c1 as Client 1
participant c2 as Client 2
participant m as Memcached
participant db as Database
rect rgb(0, 0, 255, 0.1)
note right of c1: Client 1 updates A=1
c1->>db: SET A 1
note over db: A:1
c1->>m: DELETE A
m->>c1: OK
end
rect rgb(0, 255, 255, 0.1)
note right of c1: Client 1 Reads A from Cache, Misses
c1->>m: GET A
m->>c1: FAIL
note over m: CREATE_LEASE(A, Client 1)
c1->>db: GET A
db->>c1: A=1
end
activate c1
note right of c1: Client 1 has a GC Pause
rect rgb(0, 0, 255, 0.1)
note right of c2: Client 2 updates A=2
c2->>db: SET A 2
note over db: A:2
c2->>m: DELETE A
note over m: INVALIDATE_LEASE(A, Client 1)
m->>c2: OK
end
rect rgb(255, 255, 0, 0.1)
note right of c2: Client 2 Reads A from Cache, Misses
c2->>m: GET A
note over m: CREATE_LEASE(A, Client 2)
m->>c2: FAIL
c2->>db: GET A
db->>c2: A=2
c2->>m: SET_WITH_LEASE A 2
note over m: A:2 ✅
m->>c2: OK
end
deactivate c1
rect rgb(0, 255, 255, 0.1)
c1->>m: SET_WITH_LEASE A 1
note over m: Lease is invalid!
note over m: A:2 ✅
m->>c1: FAIL
end
If deletes are idempotent, is lease invalidation idempotent too? I wonder how that's implemented - incrementing a sequence number isn't idempotent!