[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 6. 키-값 저장소 설계

키-값 저장소(key-value store)는 고유 식별자를 키로 갖는 값들이 저장된 비 관계형 데이터베이스이다. 이런 연결 관계를 “키-값” 쌍이라고 지칭한다.

• 키-값 쌍에서 키는 유일해야 하며, 키에 매달린 값은 키를 통해서만 접근 가능
  
• 키는 텍스트이거나 해시값일 수 있고, 성능상 키는 짧을수록 좋음
  
• 값은 문자열, 리스트, 객체 등 어떤 값이 오든 상관 없음
  
• 키-값 저장소 예시: DynamoDB, memcached, Redis
  

이번 장에서는 put/get 연산을 지원하는 키-값 저장소를 설계해볼 것이다.

• put: 키-값 쌍을 저장소에 저장
  
• get: 인자로 주어진 키에 매달린 값을 꺼냄
  

문제 이해 및 설계 범위 확정

설계 목표

• 읽기, 쓰기, 그리고 메모리 사용량의 균형
  
• 데이터 일관성과 가용성 사이에서의 타협
  

설계 범위

• 키-값 쌍의 크기는 10KB 이하
  
• 큰 데이터를 저장할 수 있어야함
  
• 높은 가용성을 가져 장애가 있어도 빠른 응답 가능
  
• 높은 규모 확장성으로 인해 트래픽 양에 따라 자동으로 서버 증설/삭제 가능
  
• 데이터 일관성 수준 조정 가능
  
• 짧은 응답 지연시간
  

단일 서버 키-값 저장소

단일 서버로 키-값 저장소를 설계하는 쉬운 방법은 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것이다. 하지만 이 방식은 모든 데이터를 메모리 안에 두는 것이 불가능 할 수도 있다는 약점을 갖는다. 개선책은 다음과 같다.

• 데이터 압축
  
• 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장
  

하지만 위의 방법도 한계가 명확하여 분산 키-값 저장소를 만들 필요가 있다.

분산 키-값 저장소

분산 키-값 저장소는 키-값 쌍을 여러 서버에 분산시킨다. 분산 시스템을 설계할 땐느 CAP 정리 (Consistency, Availablity, Partition tolerence theorem)를 이해해야 한다.

CAP 정리

CAP 정리는 데이터 일관성(consistency), 가용성(availability), 파티션 감내(partition tolerance)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리이다.

• 데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 접속 노드와 상관없이 언제나 같은 데이터를 봐야함
  
• 가용성:분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생해도 항상 응답을 받을 수 있어야 함
  
• 파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생한 것인데, 네트워크 파티션이 생겨도 시스템은 계속 동작해야 함
  

세 가지 요구사항 중 어떤 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다. 두 가지를 만족하는 것을 분류하면 다음과 같다.

• CP 시스템: 일관성 + 파티션 감내를 지원하는 키-값 저장소, 가용성 희생
  
• AP 시스템: 가용성 + 파티션 감내를 지원하는 키-값 저장소, 일관성 희생
  
• CA 시스템: 일관성 + 가용성을 지원하는 키-값 저장소, 파티션 감내 희생
  • 그러나 네트워크 장애는 피할 수 없는 일로 여겨지므로, 실세계에서 CA 시스템은 존재하지 않음
    
  • 분산 시스템에서 파티션 문제는 반드시 감내할 수 있도록 설계되어야 함
    
  • 즉, 일관성을 택할 것인가 가용성을 택할 것인가의 문제가 됨
    

실세계의 분산 시스템

분산 시스템에서는 파티션 문제를 피할 수 없다. 따라서 파티션 문제가 발생하면 일관성과 가용성 중 하나는 택해야한다. 아래 그림에서는 n3 노드에 장애가 발생하여 n1 및 n2 노드와 통신할 수 없는 상황이다.

• n1, n2에 기록한 데이터는 n3에 전달되지 않음
  
• n3에 기록되었으나 n1 및 n2로 전달되지 않은 데이터가 있다면 n1과 n2는 오래된 사본을 갖게됨
  
• 일관성 선택(CP 시스템)
  • 항상 같은 데이터를 전달받는 것이 더 중요한 경우 선택
    
  • 데이터 불일치 문제를 피하기 위해 살아있는 n1,n2에 대해 쓰기 연산 중단
    
  • 네트워크 파티션 때문에 일관성이 깨질 수 있다면, 상황이 해결될 때까지 오류를 반환하도록 함
    
• 가용성 선택(AP 시스템)
  • 데이터의 일관성보다 항상 응답을 받을 수 있는 상태를 유지하는 것이 더 중요할 경우 선택
    
  • 설사 오래된 데이터를 반환할 위험이 있더라고 계속 읽기 연산을 허용
    
  • n1, n2는 계속 쓰기 연산을 허용할 것이고, 이후 복구된 뒤 새 데이터를 n3에 전송
    

시스템 컴포넌트

키-값 저장소 구현에 사용될 핵심 컴포넌트들 및 기술들을 살펴보자.

데이터 파티션

대규모 애플리케이션의 경우, 데이터를 작은 파티션들로 분할하고 여러 대의 서버에 저장하는 것이 좋다. 이때 다음 두가지 문제를 중요하게 따져봐야 한다.

• 데이터를 여러 서버에 고르게 분산
  
• 노드가 추가/삭제될 때 데이터 이동을 최소화
  

안정 해시(consistent hash)는 이런 문제를 풀기에 적합하다. 키는 시계방향으로 가장 가까운 서버에 저장된다.

안정 해시를 사용한 데이터 파티셔닝의 장점

• 규모 확장 자동화 (auto-scaling): 시스템 부하에 따라 서버 자동으로 추가/삭제 가능
  
• 다양성(heterogeneity): 각 서버 용량에 맞게 가상노드 수 조정 가능 (좋은 서버는 더 많은 가상노드 가능)
  

데이터 다중화

높은 가용성과 안정성을 위해 데이터를 N개의 서버에 비동기적으로 다중화(replication)할 필요가 있다.

• 어떤 키를 해시 링 위에 배치 후, 시계 방향으로 순회하면서 만나는 첫 N개의 서버에 데이터 저장
  
• 위 그림에서 N=3인 경우, key0은 서버 s1,s2,s3에 저장
  
• 가상노드를 사용하면 실제 저장되는 물리 서버 수가 N보다 작을 수 있으므로, 같은 물리 서버를 중복 선택하지 않도록 함
  

같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등 문제를 동시에 겪을 가능성이 있다. 따라서 안정성을 담보하기 위해 데이터의 사본은 다른 센터의 서버에 보관하고, 센터들은 고속 네트워크로 연결한다.

데이터 일관성

다중화된 데이터에 대해 일관성을 보장하기 위해서는 데이터간의 적절한 동기화가 필요하다. 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다. 관련된 정의를 살펴보자.

• N = 사본의 개수 (아래의 예시에서는 3)
  
• W = 쓰기 연산에 대한 정족수 (W개 이상의 서버에서 쓰기 연산 성공해야 성공으로 간주)
  
• R = 읽기 연산에 대한 정족수 (R개 이상의 서버에서 읽기 연산 성공해야 성공으로 간주)
  
• 중재자(coordinator): 연산 성공을 판단하고, 클라이언트와 노드 사이에서 프록시의 역할을 수행
  

N, W, R의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정이다.

예를 들어 W=1 또는 R=1 인 경우, 중재자는 한 서버로부터 응답만 받으면 되니 응답 속도가 빠르다.

반면 W나 R이 1보다 크면 일관성은 커지지만, 응답속도는 가장 느린 서버로부터의 응답을 기다려야 하므로 느리다.

요구되는 일관성 수준에 따라 적절히 N, W, R의 값을 조정하면 된다.

• R=1, W=1: 가장 빠른 응답, 가장 낮은 일관성
  
• R=1, W=N: 빠른 읽기에 최적화
  
• R=N, W=1: 빠른 쓰기에 최적화
  
• R+W > N: 강한 일관성 보장
  
• R+W ≤ N: 강한 일관성 보장되지 않음
  

일관성 모델은 데이터 일관성의 수준을 결정한다.

• 강한 일관성: 모든 읽기 연산은 가장 최근에 갱신된 결과 반영, 절대로 낡은 데이터를 주지 않음
  • 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기 금지
    
  • 새 요청의 처리가 중단되므로 고가용성 시스템에 적합하지 않음
    
• 약한 일관성: 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있음
  
• 결과적 일관성(eventual consistency): 약한 일관성의 한 형태, 갱신 결과가 결국에는 모든 사본에 반영되는 모델
  • 연산이 병렬적으로 발생하면 일관성이 깨질 수 있는데, 이는 클라이언트가 해결
    
  • 결과적으로는 결국 모든 데이터가 동기화되긴 함
    
  • DynamoDB, 카산드라 등 결과적 일관성 사용
    
  • 데이터 버저닝을 통한 비 일관성 해소가 가능
    

비 일관성 해소 기법: 데이터 버저닝

문제 상황: 동시에 한 데이터에 대해 쓰기 연산이 발생

• 이후 name 데이터를 조회할 때 일관성이 깨지는 문제가 발생함
  
• 해소를 위해서는 충돌을 발경하고 자동으로 해결할 수 있는 시스템 필요
  
• 벡터 시계로 해결 가능
  

벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매달아(associate) 어떤 버전이 먼저인지 판단하고, 다른 버전과 충돌이 있는지 판단할 때 사용되는 기술이다.

• 벡터 시계는 다음과 같이 표현 → D([S1,v1], [S2,v2], … [Sn,vn])
  • D는 데이터, Si는 서버 번호, vi는 버전 카운터
• 데이터 D를 서버 Si에 기록 시 알고리즘
  • [Si,vi]가 있으면 vi를 증가시킴 (버전 있으면 v 증가)
  • 그렇지 않으면 새 항목 [Si,1] 생성 (새 버전)
• 예시

  1. D1을 Sx 서버에서 처리 → 새 버전 → 벡터시계: D1([Sx,1])

  2. D2을 Sx 서버에서 처리 → 버전 있으므로 v 증가 → 벡터시계: D2([Sx,2])

  3. D3을 Sy 서버에서 처리 → 새 버전 → 벡터시계: D3([Sx,2], [Sy,1])

  4. D4을 Sz 서버에서 처리 → 새 버전 → 벡터시계: D4([Sx,2], [Sz,1])

  5. D5을 Sx 서버에서 처리 → 버전 있으므로 v 증가→ 벡터시계: D5([Sx,3], [Sy,1],[Sz,1])

     • 클라이언트가 D3,D4를 읽으면 데이터 간 충돌이 있다는 것을 알게됨
       
     • 충돌을 클라이언트에서 해소 (이때 클라이언트가 직접 병합 or 어떤 규칙에 의해 자동으로 병합할 수 있음)
       
     • 서버에 기록
• 벡터 시계 비교 방식

  1. X ≤ Y: 벡터 X의 모든 항목이 벡터 Y와 같거나 작다면, X는 Y의 이전 상태이다.

     • D2([Sx,2]) 는 D3([Sx,2], [Sy,1])에 대해 모든 항목이 작거나 같으므로 (포함하므로) 이전 상태
       

  2. X ≠ Y and X ⊀ Y and Y ⊀ X: 서로 비교할 수 없는 경우, 두 상태는 충돌로 간주된다.

     • D3([Sx,2], [Sy,1])과 D4([Sx,2], [Sz,1])는 우위에 있는 쪽이 없다. Sy에 대해선 D3가 우위고, Sz에 대해선 D4가 우위이다.
       
     • D([S0,1], [S1,1])와 D([S0,2], [S1,0]) 도 마찬가지로, 어느 한 쪽도 우위에 있지 않으므로 충돌
       

클라이언트 충돌 해소 전략

• 자동 충돌 해소
  • LWW(last write wins): 동일 데이터에 대한 여러 버전이 존재할 때, 마지막 쓰기 연산을 채택하는 방식
    • 타임스탬프나 버전 번호를 비교하여 가장 최신의 데이터를 선택할 수 있음
      
    • 구현이 쉽고, 클라이언트단에서 복잡한 충돌 해소를 구현하지 않아도 됨
  • OT(Operational Transformation)
    • 입력한 순서에 따라 중앙 서버가 이를 적절히 변형하여 전달하는 방식
      • 충돌이 날 수 있는 부분에 대해서 먼저 발생된 사건 순으로 정렬
        
      • 서버에서 이를 순차적으로 처리하여 보정
        
      • 위의 예에서 만약 User1의 연산이 먼저 수행되었다고 보면, C를 인덱스 0에 추가한 후, User2의 연산을 수행. 이때 인덱스 0을 삭제하는 것이 한 칸씩 밀리면서 인덱스 1을 삭제하는 것으로 보정됨
        
    • 장점: 직관적인 방법
      
    • 단점: 변경사항을 보정해줄 중앙 서버가 필요하고, 트래픽이 몰렸을 때 과부하가 올 수 있음
      
    • 현재는 잘 사용되지 않는 방식
  • CRDT(Conflict-free Replicated Data Type)
    • 전략: 어떤 변경사항을 받으면, 순서와 상관없이 변경사항만 같으면 같은 상태
      
    • 시간이나 우선순위에 상관없이, 수정된 각 개체를 유니크한 값으로 봄
      • OT 방식과 달리 유니크한 인덱스 0.5가 부여되므로 보정 작업이 필요 없음
        
      • 클라이언트간의 변경사항만 잘 공유하면 됨
        
    • 장점: 중앙 제어 서버가 필요하지 않고, 데이터를 수정하는 유저들끼리만 데이터를 교환하면 되므로 빠름
      
    • 단점: 데이터가 섞여버리는 문제가 발생할 수 있음
• 수동 충돌 해소
  • 사용자가 직접 해결: 병합 도구를 제공하거나 충돌된 부분을 마킹해서 보여줌으로 사용자가 직접 해결할 수 있도록 하는 방법
    • Git merge conflict 해결 도구 등
• 참고: https://velog.io/@heelieben/%EC%8B%A4%EC%8B%9C%EA%B0%84-%EB%8F%99%EC%8B%9C-%ED%8E%B8%EC%A7%91-OT-%EC%99%80-CRDT
  

벡터 시계는 충돌을 감지하고 해소하는 좋은 방법이지만, 두 가지 단점이 존재한다.

• 클라이언트 구현의 복잡성 증가
  
• 빠르게 늘어나는 [서버, 버전] 순서쌍
  • 임계치를 설정하여 오래된 순서쌍을 제거하는 방식 사용 가능
    
  • 버전간의 선후 관계가 불명확해질 수 있지만, DynamoDB 측에 의하면 그런 문제는 존재하지 않았다고 함
    

장애 처리

대규모 시스템에서 장애는 아주 흔하게 벌어지는 사건이며, 장애를 어떻게 처리할 것이냐 하는 것은 매우 중요한 문제이다. 장애 감지 기법을 먼저 살펴보고, 이후 장애 해소(처리) 전략들에 대해 알아볼 것이다.

장애 감지

• 분산 시스템에서는 보통 두 대 이상의 서버가 똑같은 장애를 보고하면 장애로 간주한다.
  

• 모든 노드사이에 멀티캐스팅 채널을 구축하여 장애를 감지할 수 있지만, 서버가 많아질수록 비효율적인 방법이다. 분산형 장애 감지로는 가십 프로토콜이 훨씬 효율적이다.
  

• 가십 프로토콜(gossip protocol)

  • 동작 방식
    • 각 노드는 멤버 ID와 박동 카운터 쌍이 기록된 멤버십 목록을 가짐
      
    • 각 노드는 주기적으로 자신의 박동 카운터를 증가시킴
      
    • 각 노드는 무작위로 다른 노드들에게 주기적으로 자신의 박동 카운터 목록 전송
      
    • 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
      
    • 어떤 멤버의 박동 카운터 값이 지정된 시간동안 갱신되지 않으면, 해당 멤버는 장애 상태인 것으로 간주
      

일시적 장애처리

• 가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해 필요한 조치를 해야한다.
  
• 엄격한 정족수 접근법: 장애 서버에 대해 읽기와 쓰기 연산 금지
  
• 느슨한 정족수 접근법: W개의 건강한 서버와 R개의 건강한 서버에 대해 각각 쓰기 및 읽기 연산 수행
  • 장애 상태인 서버는 무시
    
  • 조건을 완화하여 가용성을 높이는 방시
    
• hinted handoff 기법: 장애 상태인 서버로 가는 요청을 잠시 다른 서버가 맡아서 처리하고, 복구되면 그동안 발생한 변경사항 반영
  • 임시로 쓰기 연산을 처리한 서버에는 그에 관한 힌트를 남겨둠
    
  • 해당 힌트를 통해 어떤 변경사항을 반영할 수 있고, 일관성을 유지할 수 있음
    

영구 장애처리

• 반 엔트로피 프로토콜: 사본들을 비교하여 최신 버전으로 갱신
  • 사본 간의 일관성이 망가진 상태 탐지하고 데이터의 양을 줄이기 위해 머클(Merkle) 트리 사용
    
• 머클(Merkle) 트리: 각 노드에 그 자식 노드들에 보관된 값의 해시 값을 레이블로 붙여두는 트리 (해시트리라고도 함)
  • 즉, 각 데이터의 해시들로 어떤 해시값을 만들고, 또 그 해시값들로 상위의 해시값을 재귀적으로 만들어 트리를 구성
    
  • 이 방식으로 대규모 자료 구조의 내용을 효과적이고 보안적으로 안전한 방법으로 검증 가능
    
  • 예제
    1. 키 공간이 1~12, 버킷이 4개인 경우 환경에서 일관성이 망가진 데이터를 찾는 과정 (이상 데이터 빨간색 표기)
    2. 버킷에 포함된 키에 해시 함수를 적용하여 해시 값 계산
    3. 다시 버킷별로 해시값을 계산하고, 해당 해시 값을 레이블로 갖는 노드 생성
    4. 자식 노드의 레이블로부터 새로운 해시 값을 계산하여, 이진 트리를 상향식으로 구성
       • 완성된 두 트리의 노드 값(해시 값)을 비교하며, 값이 다른 곳을 효율적으로 탐색
       • 두 노드의 해시 값이 같다면 두 노드의 데이터는 일치함
       • 일관되지 않은 버킷에 대해서는 동기화
         

데이터 센터 장애 처리

• 데이터 센터 장애는 정전, 네트워크 장애, 자연재해 등 다양한 이유로 발생 가능
  
• 여러 데이터 센터에 데이터를 다중화하는 것이 중요 (망가져도 다른 데이터 센터 사용)
  

시스템 아키텍처 다이어그램

• 클라이언트는 키-값 저장소가 제공하는 두 API인 get(key), put(key, val)로 통신한다.
• 중재자는 클라이언트에게 키-값 저장소에 대한 프록시 역할을 하는 노드이다.
• 노드는 안정 해시의 해시 링 위에 분포한다.
• 노드를 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산된다(decentralized).
• 데이터는 여러 노드에 다중화된다.
• 모든 노드가 같은 책임을 지므로 SPOF(Single Point of Failure)는 존재하지 않는다.
• 모든 노드는 아래의 기능을 지원한다.
  • 클라이언트 API
  • 데이터 충돌 해소
  • 다중화
  • 장애 감지, 장애 복구 메커니즘
  • 저장소 엔진 등
    

쓰기 경로

1. 쓰기 요청이 커밋 로그 파일에 기록됨
2. 데이터가 메모리 캐시에 기록됨
3. 메모리 캐시가 가득 차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 SSTable에 기록됨

• SSTable(Sorted-String Table): 키-값 순서쌍을 정렬된 리스트 형태로 관리하는 테이블
  

읽기 경로

1. 데이터가 메모리 캐시에 있는지 검사 (있으면 그대로 반환)

2. 데이터가 캐시에 없으면 블룸 필터를 검사

3. 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 확인

   • 블룸 필터(Bloom filter): 특정 원소가 집합에 속하는지 검사하는데 사용할 수 있는 확률형 자료 구조

4. SSTable에서 데이터 가져옴

5. 결과 데이터를 클라이언트에 반환