Stale Values Made by Invalidation Order

한 줄 요약

캐시가 DB 와 다른 값을 내놓는 시간은 '무효화를 했느냐' 보다 읽기와 쓰기의 연산이 어떤 순서로 끼어들었느냐 가 정합니다. 같은 전략도 순서 하나에 따라 몇 ms 만 틀리기도 하고, TTL 이 없으면 다음 쓰기가 올 때까지 계속 틀립니다.

왜 이게 필요했나

cache-aside 에서 읽기는 "캐시 확인 → 없으면 DB 읽기 → 캐시에 넣기" 세 걸음이고, 쓰기는 "DB 커밋 + 캐시 처리" 두 걸음입니다. 걸음 사이마다 다른 요청의 걸음이 끼어들 수 있습니다. 가장 많이 인용되는 기록이 Facebook 의 Scaling Memcache at Facebook(NSDI 2013)입니다. 그들은 쓰기 경로에서 캐시를 갱신하지 않고 삭제하는데, 이유를 "삭제는 멱등하기 때문" 이라고 적습니다.

그래도 문제는 남습니다. 논문은 stale set 을 "웹 서버가 캐시에 넣은 값이 넣어야 할 최신 값이 아닌 경우" 로 정의하고, 동시 갱신이 재정렬될 때 생긴다고 설명합니다. 해법은 lease 입니다. 캐시 미스 때 memcached 가 그 키에 묶인 64비트 토큰을 주고, 클라이언트가 값을 넣을 때 토큰을 함께 보내며, 그사이 delete 가 오면 토큰이 무효가 되어 넣기가 거절됩니다.

패턴 자체 — cache-aside, 무효화, 스탬피드, TTL 지터, stale-while-revalidate — 는 'Redis 와 캐싱' 코스가 다룹니다. 이 모듈은 그 아래층, 끼어들기 순서를 결정적으로 재현하고 오래된 읽기를 세는 자리입니다.

어떻게 동작하나

대표적인 끼어들기 셋입니다(R 은 읽기, W 는 쓰기).

이름	순서	남는 것
늦게 도착한 읽기의 set	R 미스 → R 이 DB 에서 v0 읽음 … W 커밋(v1) → W 삭제 … R 이 v0 를 set	삭제보다 늦게 들어온 v0
삭제 먼저, 커밋 나중	W 삭제 … R 미스 → v0 읽음 → v0 set … W 커밋(v1)	커밋 전에 다시 채워진 v0
쓰기 둘의 역순 set	W1 커밋(v1) … W2 커밋(v2) → v2 set … W1 이 v1 set	늦게 도착한 v1

첫 줄은 '쓰기 후 삭제' 로도 막히지 않습니다. 지연 이중 삭제(삭제 → 커밋 → 잠시 뒤 다시 삭제)는 늦은 set 이 두 번째 삭제보다 먼저 도착할 때만 막습니다. 기다리는 시간이 읽기의 지연보다 짧으면 소용없습니다. 그런데 읽기 경로의 최악 지연(GC 멈춤, 재시도, 느린 네트워크)은 평소 지표의 중앙값에 드러나지 않으므로, 이 전략은 대개 멀쩡하다가 드물게 무너집니다. 둘째 줄이 '삭제 후 쓰기' 가 안전하지 않은 이유입니다 — 삭제와 커밋 사이의 창에 읽기가 옛 값을 다시 채웁니다.

버전 비교(CAS). 캐시에 값과 함께 DB 버전을 넣고 "지금 캐시에 있는 버전보다 엄격히 클 때만 덮는다" 를 캐시 안에서 원자적으로 확인하면, 늦게 도착한 옛 버전이 새 버전을 덮지 못합니다. Redis 트랜잭션 문서는 WATCH 로 check-and-set 을 제공한다고 적습니다. 감시한 키가 EXEC 전에 바뀌면 트랜잭션 전체가 중단되고 null 을 돌려줍니다. 8.4 부터는 문자열 키에 대해 SET 의 IFEQ 같은 비교 옵션도 있습니다. memcache 의 lease 도 같은 발상이라, 논문은 load-link/store-conditional 에 빗댑니다. 비교 방향을 거꾸로 쓰면 막으려던 일이 그대로 일어납니다.

TTL 은 상한이지만 커밋 기준이 아니다. TTL 은 캐시에 넣은 순간부터 셉니다. 옛 값이 늦게 들어오면 그 값은 들어온 시각부터 TTL 동안 삽니다. 그래서 오래됨의 상한은 TTL 이 아니라 '늦은 set 의 지연 + TTL' 입니다. TTL 이 없으면 끼어든 옛 값은 다음 쓰기가 올 때까지 남습니다. Amazon Builders' Library 의 캐싱 글도 TTL 을 클라이언트가 오래된 데이터를 얼마나 견딜 수 있는지와 데이터가 얼마나 정적인지로 고른다고 적습니다.

무엇을 재나. 이 모듈은 오래됨을 커밋 시각 기준으로 정의합니다: 읽기가 끝난 시각 − 그 읽기가 돌려준 버전을 대체한 커밋의 시각. 쓰기를 시작한 시각부터 재면 커밋 전의 시간이 섞이는데, 그동안은 DB 도 옛 값이었으니 캐시가 거짓말한 것이 아닙니다.

현장에서 만나는 모습

같은 논문은 lease 의 두 번째 쓰임으로 thundering herd 완화를 들고, 이 문제에 취약한 키들에서 DB 조회 최고치가 초당 17K 에서 1.3K 로 줄었다고 보고합니다 — 스탬피드 쪽 이야기는 'Redis 와 캐싱' 코스로 이어집니다. 캐시 무효화를 이벤트로 흘리는 설계(아웃박스)는 '마이크로서비스 아키텍처' 코스가, 메시지가 두 번 오거나 순서가 바뀌는 장면은 '주문이 두 번 도착했고 한 번은 사라졌다' 코스가 다룹니다. 실습의 시나리오 다섯은 위 표의 순서를 하나씩 재현하도록 시각과 지연을 손으로 고른 것이고, 채점기가 쓰는 숨은 시나리오는 같은 규칙으로 무작위로 섞은 것입니다. 어느 쪽이든 여기서 던질 질문은 같습니다. 이 순서에서 캐시는 얼마 동안 틀렸나, 그리고 스스로 고쳐지나.

다음 실습에서 할 것

결정적 시뮬레이터에 쓰기·읽기 전략을 제너레이터로 끼워 넣습니다. 다섯 시나리오에서 전략 여섯 개의 오래된 읽기 수와 최대 오래됨을 재고, 영영 고쳐지지 않는 조합을 가려낸 뒤, 숫자로 전략 하나를 고릅니다.