←

Distributed Key-Value Store

System Design

Understand it step by step (한국어로 이해 → 영어로 말하기)

단순한 get(key) / put(key, value) API 두 개만 제공하지만, 데이터가 한 서버에 다 안 들어가는 분산 키-값 저장소를 설계한다. 핵심은 수백 대 서버에 데이터를 어떻게 나누고(샤딩), 한 대가 죽어도 데이터가 안 사라지게(복제) 만드는 것이다. DynamoDB나 Cassandra가 실제로 이렇게 동작한다.
  1. 1

    기능 요구사항은 딱 두 개로 좁힌다: get(key)로 값 읽기, put(key, value)로 값 쓰기. 값은 작다고 가정 (최대 10KB, 예: 세션 데이터, 사용자 프로필). 비기능 요구사항이 진짜 핵심이다: 가용성이 일관성보다 중요하다(AP 시스템). 즉 서버 몇 대가 죽어도 항상 읽고 쓸 수 있어야 하고, 대신 잠깐은 옛날 값이 보일 수 있다(eventual consistency). p99 지연시간은 10ms 이하 목표.

    ⚖️ Trade-off: CAP 정리상 네트워크 장애 시 일관성(C)과 가용성(A) 중 하나를 포기해야 한다. 여기선 가용성을 택해서, 장애 중에도 쓰기를 받되 충돌은 나중에 해결한다.

    ✅ Fix: 면접관에게 먼저 'strong consistency가 필요한가, 아니면 eventual로 충분한가'를 물어 범위를 못 박는다. KV 스토어는 보통 AP로 간다.

    🔧 도구:DynamoDBCassandraRedis

    🗣 영어로 말해

    “Two operations: get and put. I'll prioritize availability over strong consistency, targeting p99 under 10 milliseconds.”

    checking microphone…

  2. 2

    규모를 숫자로 잡는다. 일일 활성 사용자 1억 명, 사용자당 하루 10번 접근이면 하루 10억 요청. 초당 평균 약 12,000 QPS, 피크는 5배인 약 60,000 QPS로 본다. 읽기:쓰기 비율은 10:1 (읽기가 훨씬 많다). 데이터 양: 키-값 1개당 평균 1KB, 항목 100억 개면 원본 10TB. 복제본 3개 두면 30TB. 한 서버에 1TB 저장 가능하다고 보면 최소 30~40대 노드가 필요하다.

    ✅ Fix: 이 숫자들로 '한 서버에 다 못 들어간다 → 샤딩 필수, 장애 대비 → 복제 필수'라는 설계 동기를 명확히 만든다.

    🔧 도구:consistent hashingsharding

    peak QPS  ~ 60,000
read:write ~ 10:1
data      = 100억 keys * 1KB = 10TB
with RF=3 = 30TB -> ~30-40 nodes
    🗣 영어로 말해

    “About sixty thousand peak QPS, ten-to-one read-write ratio, and thirty terabytes with replication.”

    checking microphone…

  3. 3

    API는 두 개만 노출한다. get은 key를 받아 value와 버전을 돌려주고, put은 key/value를 받아 저장한다. 일관성 수준을 요청마다 고를 수 있게 quorum 파라미터를 둔다. 데이터 모델은 단순한 (key, value, version, timestamp) 한 행. 파티션 키는 key 자체이고, key를 해시해서 어느 노드로 갈지 정한다. 충돌 해결을 위해 version(vector clock 또는 timestamp)을 같이 저장한다.

    🔧 도구:vector clockconsistent hashingDynamoDB

    GET  /v1/kv/{key}?consistency=quorum
  -> 200 { value, version, timestamp }
PUT  /v1/kv/{key}
  body: { value }
  -> 200 { version }

// stored row
{ key: string,        // partition key
  value: bytes,       // <= 10KB
  version: vclock,    // conflict resolution
  timestamp: int64 }
    🗣 영어로 말해

    “Just get and put. The key is the partition key, hashed to pick the node, with a version for conflicts.”

    checking microphone…

  4. 4

    요청 흐름: 클라이언트 → 로드 밸런서 → 코디네이터 노드 → 실제 데이터 노드들. 핵심은 어떤 노드든 코디네이터가 될 수 있다는 점이다(중앙 마스터 없음, single point of failure 제거). 코디네이터가 key를 consistent hashing 링에 올려 담당 노드 N개(replica)를 찾는다. 쓰기는 그 N개 노드에 동시에 보내고, 자주 읽는 키는 각 노드 앞단의 Redis 캐시로 막는다. 노드 상태는 gossip 프로토콜로 서로 공유한다.

    ⚖️ Trade-off: 중앙 마스터를 없애면 SPOF는 사라지지만, 멤버십/장애 감지를 gossip 같은 분산 방식으로 직접 해결해야 해서 복잡도가 올라간다.

    ✅ Fix: consistent hashing 링으로 key → 노드 매핑을 결정론적으로 만들어서, 어떤 코디네이터든 같은 답을 내게 한다. 노드가 추가/삭제돼도 키의 일부만 이동한다.

    🔧 도구:consistent hashinggossip protocolRedisload balancer

    ring position = hash(key) mod 2^32
replicas = next N nodes clockwise on the ring
    🗣 영어로 말해

    “Any node can coordinate; consistent hashing maps the key to N replica nodes around a ring.”

    checking microphone…

  5. 5

    딥다이브 1 — 복제와 일관성 (quorum). 데이터를 N개(보통 3) 노드에 복제한다. 읽기 정족수 R, 쓰기 정족수 W를 둔다. W개 노드가 ack하면 쓰기 성공, R개에서 읽으면 읽기 성공. R + W > N이면 read set과 write set이 겹치므로, 장애/동시쓰기/느슨한 quorum 같은 예외가 없을 때 최신으로 ack된 write를 볼 가능성이 커진다(예: N=3, W=2, R=2). 하지만 이것만으로 Dynamo류 시스템이 자동으로 linearizable해지는 것은 아니다. 노드가 잠깐 죽으면 hinted handoff로 다른 노드가 대신 받아뒀다가 복구되면 넘겨준다. 같은 key에 동시 쓰기로 충돌이 나면 vector clock으로 감지하고, 못 풀면 둘 다 클라이언트에 줘서 해결시킨다(또는 last-write-wins).

    ⚖️ Trade-off: W를 키우면 쓰기가 더 안전하지만 느려지고, R을 키우면 읽기가 정확하지만 느려진다. W=1/R=1은 빠르지만 옛날 값을 읽을 위험이 커진다.

    ✅ Fix: N=3, R=2, W=2로 잡아 latency와 consistency를 균형 맞춘다. read repair와 anti-entropy(Merkle tree)로 복제본 간 차이를 백그라운드에서 메운다.

    🔧 도구:quorum (N,R,W)vector clockhinted handoffMerkle treeread repairCassandraDynamoDB

    N = 3 replicas
W = 2, R = 2   // R + W > N -> read/write quorum overlap
ack when W nodes confirm; read merges R responses
    🗣 영어로 말해

    “I use quorum with N three, R two, W two, so the read and write quorums overlap; then I still handle conflicts and repair stale replicas.”

    checking microphone…

  6. 6

    딥다이브 2 — 핫 키(hot key)와 재분배. 특정 key 하나에 트래픽이 몰리면(예: 인기 매물 ID) 그 키를 담당하는 노드 한 대만 터진다. consistent hashing만으로는 안 풀린다. 해결: (1) 핫 키를 Redis로 캐싱해 노드 부하를 흡수, (2) key 뒤에 랜덤 suffix를 붙여 여러 파티션으로 쪼개는 key splitting, (3) 노드마다 가상 노드(virtual node) 100~200개를 링에 올려 부하를 고르게 분산. 노드 추가 시에도 virtual node 덕분에 일부 키만 이동한다.

    ⚖️ Trade-off: key splitting은 쓰기 부하를 분산하지만, 읽을 때 여러 파티션을 다 모아야 해서 읽기 로직이 복잡해진다. virtual node를 늘리면 분산은 좋아지지만 메타데이터와 gossip 트래픽이 늘어난다.

    ✅ Fix: 평소엔 virtual node로 균등 분산하고, 모니터링으로 핫 키가 감지되면 그 키만 Redis 캐시 + splitting을 적용한다.

    🔧 도구:virtual nodesRediskey splittingconsistent hashing

    // virtual nodes: each physical node -> 150 ring tokens
// hot key fix
shardKey = hotKey + ":" + (requestId % 10)
    🗣 영어로 말해

    “For hot keys I add virtual nodes for even spread, then cache and split the hottest keys.”

    checking microphone…

  7. 7

    트레이드오프 정리: strong consistency를 포기했으니 잠깐 옛날 값이 보일 수 있다(eventual consistency) — 세션/프로필엔 괜찮지만 잔액 같은 데엔 부적합. 범위 쿼리(range scan)나 secondary index는 안 된다 — 순수 key 조회만 빠르다. 운영 복잡도(gossip, anti-entropy)가 높다. 모니터링은 노드별 p99 지연시간, key별 QPS(핫 키 탐지), replica lag(복제 지연), quorum 실패율, 디스크 사용량을 본다. 알람: p99 > 10ms, replica lag 급증, 노드 down.

    ⚖️ Trade-off: 단순함과 가용성을 얻는 대신, 강한 일관성과 풍부한 쿼리(range/index)를 포기했다. 이게 맞는지는 use case에 달렸다.

    ✅ Fix: 강한 일관성이 필요한 일부 데이터는 quorum을 R=N으로 올리거나 별도 시스템(예: 관계형 DB)으로 분리한다.

    🔧 도구:PrometheusGrafanap99 latencyreplica lag monitoring

    alerts:
  p99_latency > 10ms
  replica_lag > 5s
  quorum_failure_rate > 1%
  node_down
    🗣 영어로 말해

    “I traded strong consistency and range queries for availability, and I watch p99 latency and replica lag.”

    checking microphone…

7단계 영어를 다 말하면 → 이 메커니즘 전체를 영어로 설명할 수 있게 된다.

🎙 이 카드 AI랑 음성 대화 · 기록 저장