Key - Value(키 - 값) 저장소 설계

단일 서버에서와 분산 서버에서의 키 값 저장소는 어떻게 설계할 수 있을까?

Key - Value(키 - 값) 저장소

키-값 저장소(key-value store)는 비 관계형(non-relational) 데이터베이스 입니다. 이 저장소에 저장되는 값은 고유 식별자(identifier)를 가져야 하며 키와 값 사이의 이런 연결 관계를 “키-값” 쌍(pair)이라고 지칭합니다. 키 값 저장소로 널리 알려진 것으로는 아래와 같습니다.

1. Amazon 다이나모
2. memcached
3. redis

이번 절 에서는 put(key, value), 와 get(key)의 기능을 가지고 있는 저장소를 설계해보겠습니다.

설계 방향성

책에서 제시된 설계 요구사항입니다.

• 키-값 쌍의 크기는 10KB 이하이다.
• 큰 데이터를 저장할 수 있어야 한다.
• 높은 가용성을 제공해야 한다. 따라서 시스템은 설사 장애가 있더라도 빨리 응답해야 한다.
• 높은 규모 확장성을 제공해야 한다. 따라서 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 한다.
• 데이터 일관성 수준은 조정이 가능해야 한다.
• 응답 지연시간(latency)이 짧아야 한다.

단일 서버에서의 키 - 값 저장소

단일 서버에서 키 값 저장소를 설계하는 것은 단순하게 키,값 전부를 메모리에 해시 테이블로 저장하는 방식을 채택할 수 있습니다. 이 방법은 빠르지만 모든 데이터를 메모리에 저장한다면 규모가 커지게 된다면 OOM이 나는 등 문제가 발생할 수 있습니다. 따라서

1. 데이터 압축
2. 자주 조회되는 데이터를 메모리에 상주 시키고 나머지는 디스크에 저장할 수 있습니다.

   분산 서버에서의 키 - 값 저장소

   분산 키-값 저장소는 분산 해시 테이블이라고도 불립니다. 먼저, 분산 시스템을 설계할 때는 CAP 정리(Consistency, Availability, Partition Tolerance theorem)를 이야기해야 합니다.

CAP 정리

CAP 정리는

1. Consistency(일관성)
   • 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다.
2. Availability(가용성)
   • 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
3. Partition Tolerance(파티션 감내)
   • 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다.

CAP 정리는 이들 가운데 어떤 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다는 것을 의미합니다.

CP 시스템: 일관성과 파티션 감내를 지원합니다. 
AP 시스템: 가용성과 파티션 감내를 지원합니다. 
CA 시스템: 일관성과 가용성을 지원합니다. 
일반적인 경우에 네트워크 파티션이 불가피하므로 CA 시스템은 존재하지 않습니다.

3대의 복제 노드가 보관되어있다고 생각해보겠습니다. 이상적인 상태에서는 n1에 써진 데이터가 n2와 n3에 복제되어 데이터의 일관성과 가용성이 만족되는 상황입니다. 반면 위와 같은 그림에서는 클라이언트 n1 또는 n2에 기록된 데이터는 n3에 전달되지 않고, n3 기록되었으나 아직 n1 및 n2로 전달되지 않은 데이터가 있다면 n1과 n2는 옛날 사본을 들고있을 것입니다.

위와 같은 문제에서 두 가지 해결책이 있습니다.

1. CP 시스템(일관성을 선택한 경우) 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1과 n2에 대해 쓰기 연산을 중단시켜야 합니다. 은행권 시스템과 같이 일관성을 유지해야 할 때 사용됩니다.

2. AP 시스템(가용성을 선택한 경우) 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용해야 한다. n1과 n2는 계속 쓰기 연산을 허용할 것이고, 파티션 문제가 해결된 뒤에 새 데이터를 n3에 전송할 것입니다.

시스템 아키텍쳐

아키텍쳐를 설명해보면

1. 클라이언트는 get(key) 및 put(key, value)요청과 응답을 주고 받습니다.
2. 중재자(coordinator)는 클라이언트에게 키-값 저장소에 대한 프락시(proxy) 역할을 하는 노드입니다.
3. 노드는 안정 해시(consistent hash)의 해시 링(hash ring) 위에 분포시켜 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산됩니다.
4. 모든 노드가 같은 책임을 지므로, SPOF(Single Point of Failure)는 존재하지 않게 됩니다.

put(key, value)

1. 쓰기 요청이 커밋 로그(commit log) 파일에 기록됩니다.
2. 데이터가 메모리 캐시에 기록됩니다.
3. 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록됩니다.

get(key)

1. 데이터가 메모리에 있는 경우
   • 데이터가 메모리에 있는지 검사 후 있으면 클라이언트에게 바로 반환한다.
2. 데이터가 메모리에 없을 경우
   • 데이터가 메모리에 있는지 검사하고 없으면 바로 아래로 내려갑니다.
   • 데이터가 메모리에 없으므로 블룸 필터를 검사합니다.
   • 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아내고 SSTable에서 데이터를 가져옵니다.
   • 해당 데이터를 클라이언트에게 반환합니다.