키-값 저장소 설계

키-값 저장소 설계

• 키-값 저장소에 저장된 값은 고유한 식별자를 키로 가져야 함
• 키-값 쌍에서 키는 유일해야함
• 키는 문자 또는 해시값일 수 있음
• 성능상의 이유로 키는 짧을수록 좋음

CAP

• 네트워크 파티션은 불가피하기 때문에, 일관성과 가용성 사이에서 선택을 해야함

데이터 저장

• 안정 해시를 사용해서 데이터를 어떤 서버에 저장할지 결정

데이터 다중화

• 안정 해시에서 만나는 여러개의 노드에 모두 데이터를 저장
• 가상 노드를 사용하는 경우, 실제 서버의 갯수를 카운트가 채워질 때까지 체크해야 함

데이터 일관성

정족수 합의 Quorum Consensus

• N : 사본 갯수
• W : 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함
• R : 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함
• N,R,W 의 결정 : 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정
  • R=1, W=N : 빠른 읽기 연산
  • W=1, R=N : 빠른 쓰기 연산
  • W+R > N : 강한 일관성이 보장됨 (보통 N=3, W=R=2)

일관성 모델

• 강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 보장한다
• 약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다
• 최종적 일관성 : 약한 일관성의 한 형태. 갱신 결과가 결국에는 모든 사본에 반영되는 모델이다.
• 강한 일관성을 달성하는 가장 일반적인 방법은, 모든 사본에 대해서 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것이다
• 이 방법은 고가용성 시스템에서는 적합하지 않다. 새로운 요청의 처리가 중단되기 때문이다.
• 결과적 일관성 모델을 따르는 경우, 쓰기 연산이 병렬적으로 발생하면서 시스템에 저장된 값의 일관성이 깨질 수 있다.
• 이 문제는 클라이언트가 해결해야 한다.

비일관성 해소 방법, 데이터 버저닝과 백터 시계

• 버저닝
  • 데이터에 대한 write 연산이 수행되면 (server, version)의 쌍이 생성된다
  • 최초로 수정하는 서버에선느 (Server, 1)이 생기고, 이미 기록이 있으면 (Server, old+1)이 저장된다
• 벡터 시계
  • 서로 다른 서버에서 각각의 수정 기록을 가지고 있을 떄,
  • 한 서버가 가진 모든 수정 기록이, 다른 서버가 가진 기록보다 모두 같거나 과거의 기록일 때 충돌이 없음을 확인할 수 있다
• 벡터 시계의 단점
  • 백테 시계를 사용해서 충돌을 감지하고 해소하는 방법이 클라이언트에 포함되어야 하여 복잡도 증가
  • 서버:버전의 순서쌍 갯수가 굉장히 빨리 늘어남
    • 어떤 임계치를 설정하고 오래된 순서쌍을 제거
    • 업계에서 벡터 시계의 임계치 설정으로 문제가 발생하지 않았음이 보고됨

멀티 노드에서의 장애 대응

장애 감지, 가십 프로토콜

• 분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 서버 장애를 감지하는 방법을 사용함
• 모든 노드 사이에서 서로의 상태를 체크하는 방법이 가장 쉬운 방법이지만, 서버가 많을 때에는 비효율적인 접근
• 가십 프로토콜
  • 각 노드는 자신이 관리해야하는 목록을 유지한다
  • 이 목록은 각 멤버의 ID와 heartbeat counter를 포함한다
  • 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다
  • 각 노드는 무작위로 선정된 노드들에게 주기적으로 자신의 heartbeat counter 목록을 보낸다
  • 목록을 받은 노드는 최신의 값으로 갱신한다
  • 어떤 멤버의 박동 카운터가 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주한다

장애 처리, 일시적인 방법 (느슨한 정족수)

• quorum에서 W,R를 엄격하게 접근한다면 읽기와 쓰기 연산을 금지해야 한다.
• 느슨하게 관리한다면 해시 링에서 W,R개의 건강한 서버를 고른다.
• 해시 링에서 장애 상태로 존재하는 서버에 대한 요청은 다른 서버가 임시적으로 맡아서 처리한다
• 그 동안 발생한 변경 사항은 복구가 된 뒤에 일괄 반영된다
• 이를 위해 임시로 쓰기 연산을 처리한 서버에서는 관련된 힌트를 남겨둔다.

장애 처리, 영구 장애 처리 (anti-entropy protocol)

• 영구적인 장애를 처리하기 위해서는 반-엔트로피 프로토콜을 구현해서 사본을 동기화 해야한다.
• 사본을 비교해서 최신 버전으로 갱신하는 과정을 포함한다 (사본 간의 일관성이 망가진 상태를 탐지)
• 전송 데이터의 양을 줄이기 위해서는 Merkle Tree(=Hash Tree)를 사용한다
• 해시 트리 : 각 노드에는 그 노드의 자식들에 보관된 값의 해시를 라벨로 추가한다
  • 트리의 루트만 비교해서 전체가 동일한지 아닌지 알 수 있다
  • 차이가 발생하는 부분을 알기 위해서는 루트부터 자신의 라벨을 순서대로 확인하면 된다
  • 이를 통해 장애가 영구적으로 발생했을 때, 복구의 필요성을 탐지하고, 탐지가 필요한 경우 최소한의 데이터만 이동해서 복구할 수 있다

Reference

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초 6장