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

 

 

 

 

 

키-값 저장소 (key-value store)

• 키-값 데이터베이스라고도 불리는 비 관계형 데이터베이스 
• 고유 식별자(identifier)를 키로 가짐 
  • 키는 유일해야하며 해당 키에 매달린 값은 키를 통해서만 접근이 가능 
  • 키는 해시값이나 일반 테스트 모두 가능 
  • 성능상의 이유로 키는 짧을수로 좋음 
• 키-값 쌍 (pair)
  • 키-값 사이의 연결관계 
• 연산
  • put(key, value) : 키-값 쌍을 저장소에 저장
  • get(key) : 인자로 주어진 키에 매달린 값을 꺼냄 
• ex) 아마존 다이나모, memcached, 레디스 등 

 

 

문제 이해 및 설계 범위 확정 

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

 

 

단일 서버 키-값 저장소 

• 가장 직관적인 방법
  • 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것 
    • 빠른 속도를 보장하지만, 모든 데이터를 메모리 안에 가두는 것이 불가능할 수도 있음 
    • 데이터 압축, 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장하는 방법을 사용해서 개선 가능 
    • 그러나 개선하더라도 한대 서버로 부족한 시기가 찾아옴 

 

 

분산 키-값 저장소 

• 분산 해시 테이블 
  • 키-값 쌍을 여러 서버에 분산시킴 

CAP 정리

https://en.wikipedia.org/wiki/CAP_theorem

• 데이터 일관성 (consistency), 가용성(availability), 파티션 감내(partition tolerance)라는 세가지 요구 사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리 
  • 데이터 일관성 
    • 분산 시스템에 접속하는 모든 클라이언트가 어떤 노드에 접속하는지에 관계 없이 언제나 같은 데이터를 봄 
  • 가용성 
    • 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 함 
  • 파티션 감내
    • 파티션 = 두 노드 사이에 통신(네트워크) 장애 발생 
    • 파티션이 발생하더라도 시스템은 계속 동작되어야 함 
• 이들 가운데 어떤 두가지를 충족하려면 나머지 하나는 반드시 희생되어야 하는 것을 의미
  • CP 시스템 
    • 일관성과 파티션 감내를 지원하는 키-값 저장소 
    • 가용성을 희생 
  • AP 시스템 
    • 가용성과 파티션 감내를 지원하는 키-값 저장소 
    • 데이터 일관성을 희생 
  • CA 시스템 
    • 일관성과 가용성을 지원하는 키-값 저장소 
    • 파티션 감내는 지원하지 않음 
    • 네트워크 장애는 피할 수 없는 일로 여겨지므로 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 하므로 실세계에 CA 시스템은 존재하지 않음 
• 예시
  • 이상적 상태
    • 네트워크가 파티션되는 상황이 일어나지 않는 상황 
      • n개의 분산 시스템이 자동적으로 서로 복제되어 데이터 일관성과 가용성도 만족됨 
  • 실세계의 분산 시스템 
    • 파티션 문제를 피할 수 없음 
    • 일관성과 가용성 사이에서 택해야 함 
      • 일관성을 선택하는 경우 
        • 분산시스템 중 한 시스템이 장애상황에서 데이터 불일치를 피하기 위해 나머지 서버에 대한 쓰기 연산을 중산시킴 
        • ex) 은행 시스템
          • 전산 문제를 해결하기 전까지는 오류를 응답 
      • 가용성을 선택하는 경우 
        • 낡은 데이터를 반환할 위험이 있더라도 계속 읽기/쓰기 연산을 허용 
        • 파티션 문제가 해결된 뒤에 새 데이터를 복구된 서버에 전송 

 

시스템 컴포넌트

데이터 파티션 

• 대규모 애플리케이션의 경우 전체 데이터를 한 대 서버에 욱여넣는 것은 불가 
• 가장 단순한 해결책 
  • 데이터를 작은 파티션으로 분할한 뒤 여러대의 서버에 저장하는 것 
  • 고려사항 
    • 데이터를 여러 서버에 고르게 분산 가능한 지
    • 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화 할 수 있는가 
      • 앞서 배운 안정 해시가 문제 해결 수단이 될 수 있음 
        • 규모 확장 자동화 
          • 시스템 부하에 따라 서버가 자동으로 추가/삭제 되도록 구현 가능
        • 다양성
          • 각 서버의 용량에 맞게 가상 노드의 수 조정 가능 
          • 고성능 서버는 더 많은 가상노드를 가지도록 설정 가능 

 

데이터 다중화 

• 높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 다중화 할 필요가 있음 
• 해시링위에 키를 배치한 후 그 지점에서 시계방향으로 링을 순회하면서 만나는 첫 N개의 서버에 데이터 사본을 보관 
  • 가상노드를 사용하면 선택한 N개의 노드가 대응될 실제 물리 서버의 개수가 N보다 작아질 수 있음에 유의 
    • 노드를 선택할 때 같은 물리 서버를 중복 선택하지 않도록 해야함 
    • 같은 데이터 센터에 속한 노드는 네트워크 이슈, 자연재해 등의 문제 동시 발생 가능성이 있어 안정성을 위해 데이터 사본은 다른 센터의 서버에 보관하고 센터는 고속 네트워크로 연결 

 

일관성

• 여러 노드에 다중화 된 데이터는 적절히 동기화가 되어야 함 
• 정족수 합의 프로토콜 (Quorum Consensus)
  • 읽기/쓰기 연산 모두 일관선 보장 가능 
    • N = 사본 개수 
    • W = 쓰기 연산에 대한 정족수로 쓰기 연산이 성공한 것으로 간주되려면 적어도 W 개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함 
    • R = 읽기 연산에 대한 정족수로 읽기 연산이 성공한 것으로 간주되려면 적어도 R 개의 서버로부터 읽기 연산이 성공했다는 응답을 받아야 함 
    • 중재자는 클라이언트와 노드 사이에서 프록시 역할을 하면서 응답의 개수를 체크 
    • W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정 
      • W + R > N 인 경우 
        • 강한 일관성 보장 
        • 보통 N = 3, W = R = 2 
      • W + R <= N 
        • 강한 일관성이 보장되지 않음 
      • R = 1, W = N 
        • 빠른 읽기 연산에 최적화 된 시스템 
      • W =1, R = N 
        • 빠른 쓰기 연산에 최적화 된 시스템 
• 일관성 모델 
  • 강한 일관성 
    • 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환 
    • 클라이언트는 항상 최신의 데이터를 봄 
    • 모든 사본에 현재 쓰기 연산의 결과가 반영될 때 까지 해당 데이터에 대한 읽기/쓰기를 금지 
    • 새로운 요청에 대한 처리가 중단되기 때문에 고가용성 서버에 맞지 않음 
  • 약한 일관성 
    • 가장 최근에 갱신된 결과를 반환하지 못할 수 있음 
    • 최종 일관성
      • 약한 일관성의 한 형태로 갱신 결과가 결국에는 모든 사본에 동기화 됨 
      • 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있으므로 클라이언트가 데이터의 버전 정보를 활용해서 문제를 해결해야 함 
      • ex) 다이나모, 카산드라 

 

일관성 불일치 해소 

• 버저닝
  • 데이터를 변경할 때 마다 해당 데이터의 새로운 버전을 생성 
  • 각 버전의 데이터는 변경 불가능 
• 벡터 시계 
  • [서버, 버전]의 순서쌍을 데이터에 매단 것으로 어떤 버전이 선행 또는 후행인지, 다른 버전과 충돌이 있는지 판별하는데 사용됨 
  • ex) D([S1, V1], [S2, V2], ...) 
    • D = 데이터 
    • S = 서버 
    • V = 버전 
    • [Si, Vi]가 있으면 Vi를 증가 시키고 없으면 [Si, 1]을 만듬 
    •  단점 
      • 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로 클라이언트 구현이 복잡해짐 
      • [서버, 버전]의 순서쌍 개수가 굉장히 빨리 늘어남 
        • 그 길이에 임계치를 설정하고 임계치 이상으로 길이가 길어지면 오래된 순서쌍을 벡터 시계에서제거하도록 해야함 
          • 버전간 선후 관계가 정확하게 결정될 수 없기 때문에 충돌 해소 과정의 효율성이 낮아짐 
          • 그러나 아마존은 실제 서비스에서 그런 문제가 벌어지는 것을 발견한 적은 없음 
     

https://www.geeksforgeeks.org/vector-clocks-in-distributed-systems/

 

 

장애 처리 

• 장애 감지 기법 
  • 분산시스템에서는 모든 노드 사시에 멀티캐스팅 채널을 구축하여 서버 장애를 감지할 수 있음
    • 보통 두대 이상의 서버가 특정 서버의 장애를 보고해야 실제로 장애라고 판단함  
    • 서버가 많을 때는 비효율적 
    • 가십 프로토콜 같은 분산형 장애 감지 솔루션을 채택하는 편이 보다 효율적 
    • 동작 원리 
      • 각 노드는 멤버십 목록을 유지 
        • 멤버십 목록 = 각 멤버 ID와 박동 카운터 쌍의 목록 
      • 각 노드는 주기적으로 자신의 박동 카운터를 증가 
      • 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보냄 
      • 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신 
      • 어떤 멤버의 박동 카운터 값이 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애 상태로 간주됨 
• 일시적 장애 처리 
  • 가십 프로토콜로 장애가 감지된 시스템은 가용성을 보장하기 위해 필요한 조치를 해야함 
    • 엄격한 정족수(strinct quorum)을 쓴다면, 읽기와 쓰기 연산을 금지 
    • 느슨한 정족수(sloppy quorum)을 쓴다면 조건을 완화하여 가용성을 높임 
      
      • 임시 위탁 기법 (hinted handoff) 
        • 정족수 요구사항을 강제하는 대신 장애 서버를 제외하고 쓰기 연산을 수행할 W 개의 건강한 서버와 읽기 연산을 수행할 R 개의 건강한 서버를 해시링에서 선택
        • 네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리 
        • 그동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영하여 데이터 일관성 보존 
        • 임시로 쓰기 연산을 처리한 서버에는 단서를 남겨둠 
• 영구 장애 처리 
  • 반 엔트로피 (anti-entropy) 프로토콜 
    • 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함하여 동기화 
    • 사본 감간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 머클(Merkle) 트리를 사용 
      • 머클트리 
        • 해시트리
        • 각 노드에 그 자식 노드들에 보관된 값의 해시 (자식 노드가 종단 노드인 경우), 또는 자식 노드들의 레이블로부터 계산된 해시값을 레이블로 붙여두는 트리 
        • 대규모 자료구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증 가능 
    • 루트노드의 해시값을 비교
      • 루트 노드의 해시값이 일치한다면 두 서버가 같은 데이터를 가짐
      • 다른 경우 왼쪽 자식 노드와 오른쪽 자식 노드 해시값을 비교하여 아래쪽으로 탐색해나가 다른 데이터를 갖는 버킷을 찾음 
        • 해당 버킷만 동기화 
    • 동기화 해야 하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터 총량과는 무관해짐 
    • 실제로는 버킷 하나의 크기가 꽤 큼 
• 데이터 센터 장애 처리 
  • 데이터를 여러 데이터 센터에 다중화 하는 것이 중요 

 

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

• 주된 기능 
  • 클라이언트는 키-값 저장소가 제공하는 두가지 단순한 API (get(key), put(key, value))와 통신 
  • 중재자는 클라이언트에게 키-값 저장소에 대한 프록시 역할을 하는 노드 
  • 노드는 안정해시의 해시링 위에 분포 
  • 노드를 자동으로 추가 또는 삭제할 수 있도록 시스템은 완전히 분산됨 
  • 데이터는 여러 노드에 다중화 
  • 모든 노드가 같은 책임을 지므로 SPOF(Single Point Of Failure)는 존재하지 않음 

 

쓰기 경로 

1. 쓰기 요청이 커밋 로그 파일에 기록됨 
2. 데이터가 메모리 캐시에 기록됨 
3. 메모리 캐시가 가득차거나 사전에 정의된 임계치에 도달되면 데이터는 디스크에 있는 SSTable에 기록됨
   • SSTable
     • Sorted-String Table
     • <키, 값> 순서쌍을 정렬된 리스트 형태로 관리하는 테이블 

읽기 경로 

1. 데이터가 메모리캐시에 있는지 확인 
2. 있으면 메모리에서 반환하고 메모리에 없는 경우 디스크에서 가져옴 
3. 블룸필터(Bloom Filter)를 사용해 어느 SSTable에 찾는 키가 있는지 찾음 
4. SSTable에서 데이터를 가져옴 
5. 해당 데이터를 킄ㄹ라이어느에게 반환 

 

 

 

정리 

목표 / 문제	기술
대규모 데이터 저장	안정 해시를 사용해 서버들에 부하 분산
읽기 연산에 대한 높은 가용성 보장	데이터를 여러 데이터 센터에 다중화
쓰기 연산에 대한 높은 가용성 보장	버저닝 및 벡터 시계를 사용한 충돌 해소
데이터 파티션	안정 해시
점진적 규모 확장성	안정 해시
다양성 (heterogeneity)	안정 해시
조절 가능한 데이터 일관성	정족수 합의 (quorum consensus)
일시적 장애 처리	느슨한 정족수 프로토콜 (sloppy quorum)과 단선 후 임심 위탁 (hinted handoff)
영구적 장애 처리	머클 트리 (Merkle tree)
데이터 센터 장애 대응	여러 데이터 센터에 걸친 데이터 다중화