Eventually consistent cache에는 두 가지 장애가 있습니다. 오래된 값을 돌려 줄 수 있고, 그 값이 얼마나 오래됐는지 호출자가 판단하지 못할 수 있습니다. 두 번째 문제가 product마다 복잡성을 만듭니다. Developer는 retry를 넣고 distributed state machine은 update가 이미 도착했다고 가정하며 asynchronous action은 아직 region을 건너는 자료를 반복 조회하다 스스로 과부하됩니다.
Meta는 database shard 수백만 개와 초당 read query 수십억 건 규모에서 이 문제를 겪었습니다. TAO는 여러 region에서 social-graph 자료를 cache하고 Wormhole이라는 ordered pub-sub system이 database change를 전달합니다. 이 pipeline은 durable, at-least-once, in-order delivery를 제공합니다. 중요한 보장이지만 hot shard 하나, overloaded publisher 하나, 누락 segment 하나가 뒤의 모든 entry를 지연시킬 수 있습니다. Average lag가 낮아도 long tail에는 쓸 수 있는 상한이 없습니다[1].
Skybridge는 역할이 더 좁은 두 번째 replication path를 둡니다. Changed object를 운반하지 않고 Wormhole을 교체하지도 않습니다. “이 cache key에 local cache가 아직 보지 못한 최근 write가 있는가?”라는 질문에 답할 metadata만 전달합니다. Main stream은 durability와 ordered recovery를 최적화하고 Skybridge는 timely evidence를 최적화합니다.
Key별 evidence가 필요한 freshness proof
TAO는 committed write에 hybrid logical clock(HLC)을 이미 붙입니다. MySQL은 shard마다 HLC를 증가시키고 Wormhole은 약 500ms마다 heartbeat를 넣습니다. Cache host는 replication watermark와 현재 시간을 비교합니다. Watermark가 2초 threshold보다 새로우면 그 이전의 change가 모두 도착했으므로 local entry가 fresh하다고 판단할 수 있습니다.
어려운 경우는 watermark가 뒤처졌을 때입니다. Shard의 모든 key를 stale로 선언하면 안전하지만 비쌉니다. Read traffic은 skew되어 있어 빠진 interval 동안 대부분의 cached object는 바뀌지 않았습니다. 모두 refill하면 cache가 cross-region proxy로 바뀌고 latency가 늘며 database를 향한 thundering herd가 생겨 원래 lag를 악화할 수 있습니다.
Skybridge는 fine-grained staleness oracle입니다. 일반 watermark로 freshness를 증명하지 못하면 TAO는 요청 key가 최근 write 집합에 있는지 묻습니다. Negative answer는 오래돼 보이는 cache entry가 실제로는 바뀌지 않았음을 증명합니다. Positive answer는 최신 HLC를 주고 TAO는 충분히 새로운 버전을 upstream에서 가져옵니다. Expensive refill capacity를 실제로 stale일 수 있는 작은 key 집합에만 씁니다.
두 번째 database를 만든 것은 아닙니다. Skybridge는 value가 아니라 key와 HLC pair를 보관합니다. Cache가 필요한 것은 key의 latest known 버전이므로 last-write-wins merge면 충분합니다. Payload 감소가 작은 footprint와 짧은 replication latency의 기반입니다.
Gap 탐지가 바꾸는 replication contract
원문은 이 약한 stream semantics를 gap 탐지 replication(RGD)이라고 부릅니다. 자료 loss와 out-of-order delivery를 허용하지만 loss를 반드시 탐지해야 합니다. Skybridge가 interval이 incomplete임을 알면 indeterminate result를 반환합니다. TAO는 보수적으로 refill하거나 fail-closed request라면 error를 반환합니다. 해당 interval이 조용히 빠졌는데도 “recent write 없음”이라고 답하지 않는 것이 correctness 조건입니다.
Disorder 허용은 head-of-line blocking을 없앱니다. 저장하는 tuple은 add-only set이므로 insertion order가 결과를 바꾸지 않고 duplicate delivery도 무해합니다. Read path는 key마다 maximum HLC를 고릅니다. 오래된 unavailable window를 기다리지 않고 더 새로운 metadata를 먼저 전달할 수 있습니다.
Gap 탐지는 writer에서 시작합니다. TAO writer는 어느 process가 shard에 쓸 수 있는지 정하는 lease를 사용하고 bounded window를 닫는 heartbeat를 보냅니다. Skybridge는 relevant lease holder 모두의 evidence가 있어야 window가 complete하다고 판단합니다. Heartbeat 누락, writer crash, lost batch는 explicit gap으로 남습니다. Downstream replica는 여러 write-path 및 read-path peer에서 window를 가져오고 newest metadata를 우선하며, 오래된 unavailable window를 포기하더라도 complete라고 가장하지 않습니다.
두 path의 독립성이 중요합니다. Main stream과 같은 publisher queue 및 recovery barrier를 공유하는 fast side channel은 correlated lag를 함께 겪습니다. Skybridge는 TAO write path에서 metadata를 받고 별도 replication topology를 사용합니다. Durable path는 object content와 eventual repair의 source of truth로 남고 fast path는 bounded, conservative evidence를 제공합니다.
Oracle 호출을 줄이는 local filter
모든 TAO read에서 network service를 호출하면 병목 위치만 옮깁니다. Skybridge는 recent write의 compact bloom filter를 TAO host로 계속 보냅니다. Lagging cache reader는 ordinary watermark와 cached item HLC를 먼저 확인합니다. 충분하지 않으면 negative bloom-filter result로 network hop 없이 recent-write set에 key가 없음을 증명합니다. Possible match만 in-region getWrites request를 보냅니다.
Filter에는 false positive가 있을 수 있지만 complete interval에 false negative는 없어야 합니다. False positive는 불필요한 query 하나를 만들 뿐이지만 false negative는 stale 자료를 노출합니다. Filter stream이 incomplete하면 TAO는 그것을 proof로 쓰지 않습니다. Common case는 host-local arithmetic으로 끝내고 uncertainty에는 conservative escape path를 남깁니다.
Memory capacity가 retention interval을 정합니다. Skybridge는 모든 shard에 기본 history를 유지하고, 반복된 TAO request가 limit 접근을 보여 주는 shard만 retention을 늘립니다. 운영 배치는 traffic 변화에 따라 약 93초에서 109초의 write를 보관했습니다. 몇 분씩 lagging한 shard는 결국 window 밖으로 나가 ordinary upstream path가 필요합니다.
Average가 아닌 tail에서 나온 운영 결과
Meta는 tens of regions에서 7일 동안 system을 측정했습니다. Skybridge가 없을 때 TAO는 sampled check의 99.993%에서 2초 consistency를 제공했고 때로 99.985% 아래로 내려갔습니다. Skybridge를 쓴 best-effort read는 99.9993%에 도달했습니다. Freshness를 증명하지 못하면 자료 대신 error를 주는 fail-closed read는 99.99998%였습니다. Read가 수십억 건이면 남은 fraction도 실제 request이므로 반올림해 없앨 수 없습니다.
Filtering path도 같은 정도로 중요합니다. Wormhole watermark만으로 read의 99.96%가 current임을 증명했습니다. Host-local bloom filter를 더하면 99.98%로 올라가 초당 수천만 potential query를 없앴습니다. In-region Skybridge lookup까지 포함하면 99.9996%가 current로 증명돼 0.0004%만 upstream freshness fetch가 필요했습니다.
Skybridge P99 replication lag는 약 700ms였고 P99.99도 몇 차례 spike를 제외하면 1.5초 안팎이었습니다. 한 tier가 모든 committed write의 metadata를 받는 데 4.8~7.9GB/s를 썼고 Wormhole full stream의 TAO ingest는 170~300GB/s였습니다. 전체 Skybridge와 lease system은 TAO server footprint의 0.54%를 사용했습니다.
이 수치는 Skybridge가 기본적으로 TAO를 linearizable하게 만든다는 뜻이 아닙니다. Best-effort read는 protective rate limit이 걸리면 fail open합니다. Hard contract가 필요한 caller는 fail-closed behavior를 요청하고 freshness를 증명하지 못할 때 error를 받아들입니다. Meta는 2초 interval을 기다린 뒤 이런 read를 보내 normal traffic을 primary database로 향하게 하지 않고 primary-only 또는 causal check에 가까운 behavior도 제공합니다.
Consistency에 포함되는 overload control
Freshness mechanism은 자체 metastable failure를 만들 수 있습니다. Incomplete window가 getWrites call을 늘리면 query가 replication 및 filter publishing과 경쟁합니다. Replication이 느려지면 incomplete window와 call이 더 늘어납니다. Skybridge는 replication을 최우선, bloom-filter delivery를 다음, query를 마지막 priority로 둡니다. Re-fetch traffic도 rate limit해 degraded state를 벗어나는 데 필요한 evidence가 굶지 않게 합니다.
TAO는 circuit breaker도 사용합니다. Lease wait나 expensive consistency check가 많아지면 default traffic은 fail open해 latency와 availability를 보호합니다. Fail-closed request에는 capacity budget 일부를 예약합니다. Wide replication incident 중 모든 reader가 database를 과부하시키지 않으면서 selected call에는 strong answer를 주는 contract입니다.
Lease plane에서도 운영 bug가 나타났습니다. Misrouted TAO release 때문에 writer가 unexpected lease를 열었고 delta compression이 듣지 않아 lease backend가 과부하됐습니다. Lease change에 rate limit을 걸어 control-plane surge가 모든 downstream window를 incomplete하게 만드는 것을 막았습니다. Metadata는 자료보다 작지만 admission control과 priority isolation이 여전히 필요합니다.
Clock uncertainty도 proof에 남습니다. Meta는 NTP를 사용하며 skew를 고려해 effective threshold를 50ms 앞으로 옮깁니다. 실제 skew가 assumed margin을 넘으면 physical-time freshness claim이 깨질 수 있습니다. 더 정확한 synchronization 또는 큰 safety allowance는 달성 가능한 bound를 바꿉니다.
적용 조건과 시스템 판단
Skybridge는 cache에 authoritative refill path가 있고 write에 comparable 버전이 있으며 missing metadata를 탐지할 수 있기 때문에 동작합니다. 이 조건이 하나라도 없는 system은 bloom filter 하나를 더하는 방식으로 설계를 복사할 수 없습니다. Dynamic shard movement는 lease와 gap protocol을 resharding control plane과 조정해야 합니다. Global secondary index는 result 하나가 수백만 source shard의 write에 의존할 수 있고 repair도 single-key refill이 아니어서 더 어렵습니다.
재사용할 design point는 eventual replication과 synchronous replication 사이에 있습니다. Truth를 위한 durable stream을 유지하고 recent-change evidence용 independent compact stream을 더한 뒤 uncertain read는 conservative fallback으로 보냅니다. Weak stream은 weakness가 observable하기 때문에 쓸 수 있습니다. Metadata를 잃거나 reorder할 수는 있어도 unknown interval을 조용히 freshness proof로 바꿀 수는 없습니다.
Operator가 볼 dashboard는 average replication lag 하나가 아닙니다. Watermark, filter, remote check가 각각 증명한 fraction, fail-open 및 fail-closed rate, retention coverage, upstream refill pressure, clock-skew margin, replication percentile을 함께 봐야 합니다. 그래야 2초 contract가 지켜지는지, mechanism이 이를 깨뜨릴 feedback loop에 접근하는지 판단할 수 있습니다.
Skybridge는 모든 cache read를 synchronous하게 만들지 않고 consistency를 강화할 수 있음을 보였습니다. 비용은 gap, lease, retention, priority, clock을 자료 path만큼 세심하게 관리해야 하는 두 번째 control system입니다. Meta 규모에서 이 system은 unbounded promise를 거의 모든 read에 대한 2초 operational contract로 바꿨습니다.
출처와 저작권 안내
이 글은 Silicon & Systems가 작성한 편집 분석으로, architecture와 measurement, limitation을 우리 표현으로 다시 썼습니다. 원문의 문장, 표, 도판은 재수록하지 않았고 도판은 이 글을 위해 새로 만들었습니다. 전체 논문은 USENIX OSDI 2025 발표 페이지에서 확인할 수 있습니다. 저작권은 저자에게 있습니다. 2025.