Key-value Store #1 - Scalability & Replication

Introduction to key-value stores

키값 저장소는 분산 해시테이블이다. 키는 해시함수를 사용해 생성되며 고유하다. 보통 값의 크기를 비교적 작게 (KB to MB) 유지하는 것이 선호된다.

전통적 DB 를 강한 일관성과 높은 가용성을 유지하면서 분산 환경으로 확장시키는것을 어려운 일이다. 많은 서비스들이 전통적인 OLTP DB 대신 primary key 를 통한 저장소 접근을 사용하고 있다.

Design of a Key-value store

Requirements

• Functional
  • Configurable service
    • 여러 일관성 모델을 사용할 수 있도록 서비스를 설정 가능하게 만들어야 한다.
    • 가용성, 일관성, 비용효율성, 성능 사이의 트레이드오프를 제어할 수 있도록 해야한다.
  • Ability to always write
    • 언제든 저장소에 쓰기를 할 수 있어야 한다. 만약 강한 일관성을 원할경우 이 요구사항은 CAP 이론에 따라 충족되지 못할 수 있다.
  • Hardware heterogeneity
    • 시스템은 서로 구분되는 노드가 아닌 기능적으로 동일한 노드들을 사용해야 한다.
• Non-functional requirements
  • Scalable
    • 키값 저장소는 수만대의 분산된 서버에서 동작할 수 있어야 한다. 서버의 가용성을 해치지 않고 서버를 추가하거나 제거할 수 있어야 한다.
  • Available
    • 무중단 서비스를 제공해야 하기 때문에 가용성이 중요하다. 이 속성은 일관성과 관련하여 설정 가능해야 한다.
  • Fault tolerance
    • 장애 상황에도 정상적으로 동작해야 한다.

Assumptions

디자인을 심플하게 하기 위해 아래와 같이 가정한다

• 서비스를 호스팅하는 데이터센터는 신뢰할 수 있다
• 필요한 인증 및 인가는 완료된 상태이다
• 사용자 요청과 응답은 HTTPS 로 릴레이된다

API design

• Get function
  • get(key)
  • key 에 대한 value 를 반환
• Put function
  • put(key, value)
  • key 에 대한 value 매핑 저장

 

Ensure scalability and replication

Add scalability

핵심 요구사항중 확장성 하나만 먼저 고려하자. 상황에 따라 노드를 추가하거나 제거할 수 있다. 또한 로드를 모든 노드에 분산시키기 위해 데이터를 파티션 해야한다.

전통적인 모듈러 연산으로 데이터를 파티션할 경우 노드 추가제거시 데이터를 리밸런싱하는 코스트가 크다.

Consistent hashing

consistent hashing 은 개념적인 해시 링이 있다고 생각하고, 가능한 해시 값의 범위는 0 에서 n-1 로 설정된다. 각 노드의 아이디를 이용해 해시를 계산한 후 링에 해시값을 매핑한다. 각 요청은 링에서 시계방향으로 바로 다음에 있는 노드에 의해 처리된다.

링에 노드가 새로 추가되면 바로 다음 노드가 영향을 받는다. 다른 노드들은 영향받지 않아 변경사항을 최소화하기 용이하다.

이렇게 변경 범위를 최소화하기엔 유리하지만 실무에서는 로드가 균등하게 분산되지 않는다.

이런 경우 가상 노드를 사용해 로드를 좀더 균등하게 분산시킬 수 있다. 해시함수를 하나 대신 여러개를 사용할 것이다. 그림과 같이 물리노드 1에 해당하는 가상노드는 초록색이고, request Id 로 얻어진 첫번째 해시값으로 처리될 가상 노드를 고른 후, 해당 가상노드에 대응하는 물리노드가 요청을 처리하게 된다.

이 방법은 장애상황에서도 로드가 좀더 고르게 분산될 수 있게 하며, 각 물리노드가 얼마나 많은 가상 노드를 가질지를 물리장비의 성능에 따라 결정할 수 있다.

Data replication

Primary-secondary approach

primary-secondary 방식에서는 스토리지 영역 중 하나는 primary 이고, 나머지는 primary 를 복제하는 secondary 이다. primary 노드 장애시 쓰기를 할 수 없어 primary 가 SPOF 가 된다.

Peer-to-peer approach

peer-to-peer 방식에서는 모든 영역이 primary 이며 데이터를 복제하여 업데이트된 상태를 유지한다. 모든 노드에서 쓰기 읽기를 할 수 있으며 모든 노드에 복제를 하는 것은 비효율적이기 때문에 복제될 노드 수를 보통 3 에서 5 정도로 선택한다.

이 방식에서 읽기와 쓰기를 처리하는 노드를 coordinate 라 한다. coordinate 가 키 K 를 할당받으면 이를 시계방향으로 이어진 n-1 개의 노드에 복제할 책임이 있다. 이렇게 이어진 가상노드의 리스트를 preference list 라고 한다. 같은 물리노드에 복제본을 두는 것을 피하기 위해 preference list 는 같은 물리노드에 있는 가상노드를 건너뛸 수도 있다.