키-값 저장소 설계

key-value store

• 키는 일반 텍스트일 수도 있고 해시값일 수도 있다.

• 값은 문자열일 수도 있고, 리스트일수도 있고, 객체일 수도 있다. 값으로 무엇이 오든 관계없다.

• 대표적인 key-value 저장소로는 Amazon DynamoDB, memcached, Redis등이 있다

문제이해 및 설계 범위 확정

다음의 특성을 갖는 저장소를 설계해볼 것

• 키-값 쌍의 크기는 10KB 이하

• 큰 데이터를 저장할 수 있어야 한다

• 높은 가용성을 제공해야 한다 →장애가 있떠라도 빨리 응답한다

• 높은 규모의 확장성을 제공해야 한다 → 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어진다.

• 데이터 일관성 수준은 조정이 가능해야 한다

• 응답 지연시간이 짧아야 한다

단일 서버 키-값 저장소

• 한대의 서버만 사용하는 키-값 저장소를 설계하는 것은 쉬운일 → 키 값 쌍을 전부 메모리에 해시 테이블로 저장하는 것

• 빠른 속도를 보장하긴 하지만 모든 데이터를 메모리에 두는 것은 불가능. 문제를 해결하기 위한 개선책은 크게 두 가지

  • 데이터 압축

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

• 위와 같은 방법을 써도 한 대 서버로는 부족한 때가 찾아온다. 분산 키-값 저장소를 만들 필요가 있다.

분산 키-값 저장소

분산 해시테이블로도 불리는 분산 키-값 저장소는 키-값 쌍을 여러 서버에 분산시킨다. 분산 시스템을 설계할 때는 CAP정리(Consistency, Availability, Partition Tolerance theorem)를 이해하고 있어야 한다.

CAP 정리

각 요구사항의 의미

데이터 일관성

분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다

---

가용성

분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.

---

파티션 감내(분할 허용)

파티션은 두 노드사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 의미한다.

세 가지 요구사항 중 어느 두가지를 만족하느냐에 따라 CP시스템, AP시스템, CA시스템으로 분류할 수 있다.

CA시스템은 일관성과 가용성을 지원하고 파티션감내는 지원하지 않는다. 하지만 통상 네트워크 장애는 피할수 없는 일로 여겨지므로 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다. 따라서 CA시스템은 존재하지 않는다.

예시

이상적 상태

이상적 환경이라면 네트워크가 파티션되는 상황은 절대로 일어나지 않을 것이다. n1에 기록된 데이터는 자동적으로 n2와 n3에 복제된다 → 데이터 일관성과 가용성도 만족된다.

---

실세계의 분산 시스템

• 실세계에서는 파티션 문제를 피할 수 없다.

• 파티션 문제가 발생하면 일관성과 가용성 사이에서 하나를 선택해야 한다.

n3에 기록된 데이터는 n1및n2에 전달되지 않는 경우가 발생한다.

가용성 대신 일관성을 선택 → 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 모든 쓰기 연산을 중단(가용성이 깨진다, 은행권 시스템)

일관성대신 가용성을 선택 → 낡은 데이터를 반환할 위험이 있더라도 n1,n2는 계속 읽기와 쓰기 연산을 허용하고, 파티션 문제가 해결된 뒤에 새 데이터를 n3에 전송

• 분산 키-값 저장소를 설계할 때는 그 요구사항에 맞도록 CAP정리를 적용해야한다. 면접관과 상의하고 설계하자.

시스템 컴포넌트

키-값 저장소 구현에 사용될 핵심 컴포넌트 및 기술들

데이터 파티션

데이터를 파티션 단위로 나눌 때 체크리스트

• 데이터를 여러 서버에 고르게 분산할 수 있는가

• 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화 할 수 있는가

안정해시는 이런 문제를 푸는데 적합한 기술이다.

서버를 해시 링에 배치한다. 키-값 쌍을 어떤 서버에 저장할지 결정하려면 우선 해당키를 같은 링 위에 배치한 뒤 시계방향으로 순회하다 만나는 첫 번째 서버가 바로 저장할 서버. key0은 s1에 저장된다

안정해시를 사용할 때의 장점

• 규모 확장 자동화 : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만든다

• 다양성 : 각 서버의 용량에 맞게 가상노드의 수를 조정할 수 있다.

데이터 다중화

높은 가용성과 안정성을 확보하려면 → N개의 서버에 비동기적으로 다중화

링을 순회하면서 만나는 첫 N개의 서버에 데이터 사본을 보관. 그림은 N=3일시 key0은 s1, s2, s3에 저장

• 하지만 가상 노드를 사용한다면 N개의 노드가 대응될 실제 물리 서버의 개수가 N보다 작아질 수도 있다.

• 이 문제를 피하려면 노드를 선택할 때 같은 물리 서버를 중복 선택하지 않도록 해야함!

• 같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해등의 문제를 동시에 겪을 수도 있기때

데이터 일관성

• 여러 노드에 다중화된 데이터 → 동기화 필요

• 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.

• N\=사본 개수

• W\=쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 한다.

• R\=읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야 한다.

일관성 모델

일관성 모델은 데이터 일관성 수준을 정하는데, 종류가 다양하다

• 강한 일관성 : 모든 읽기 연산은 최근에 갱신된 결과를 반환한다. 절대로 낡은 데이터를 보지 못한다

  • 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지

  • 고가용성 시스템에 부적합

• 약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수도 있다

• 결과적 일관성 : 약한 일관성의 한 형태로 갱신결과가 결국에는 모든 사본에 반영(동기화)되는 모델이다.

  • 다이나모, 카산드라 같은 저장소에서 쓰이는 방법

  • 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있다 → 클라이언트 측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 하는 기법을 사용

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

• 데이터 다중화 → 가용성 높아진다 → 복제본 간에 일관성이 깨질 가능성이 높아진다.

• 버저닝(versioning)과 벡터시계(vector clock)는 그 문제를 최소화 하기 위해 등장한 기술

  • 일관성이 깨지는 예시

    어떤 데이터의 사본이 n1,n2에 보관 되어 있을때, 데이터를 가져오려는 서버1과 서버2는 연산의 결과로 같은 값을 얻는다

    

    이번에는 이번에는 서버1은 name의 값을 johnSanFrancisco로 바꾸고, 서버2는 johnNewYork로 바꾼다고 한다. 이러면 값이 충돌하게 되는데 각각을 v1, v2라고한다

    

    변경이 이루어진 후에 원래값(john)은 무시할 수 있다. 하지만 마지막 두 버전 v1, v2사이의 충돌은 해결하기 어려워 보인다.

    이 문제를 해결하려면 충돌을 발견하고 자동으로 해결해 낼 버저닝 시스템이 필요하다.벡터 시계는 이런 문제 해결에 보편적으로 사용되는 기술이다.

• 벡터시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것이다.

• 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는 데에 쓰인다.

• 벡터 시계는 D([S1, v1], [S2, v2] ... [Sn, vn])와 같이 표현한다고 가정하자. D는 데이터, vi는 카운터, si는 서버 번호이다.

• 만일 데이터 D를 서버 Si에 기록하면, 시스템은 아래 작업 가운데 하나를 수행해야 한다.

  • [Si, vi]가 있다면 vi를 증가시킨다.

  • 그렇지 않으면 새 항목[Si, 1]를 만든다.이 추상적 로직이 실제로 어떻게 수행되었는지를 구체적 사례를 통해 알아본다.

1. 클라이언트가 데이터 D1을 시스템에 기록한다. 이 쓰기 연산을 처리한 **서버는 Sx**이다. 따라서 벡터 시계는 D1[(Sx, 1)]으로 변한다.

2. 다른 클라이언트가 데이터 D1을 읽고 D2로 업데이트 한 다음 기록한다. D2는 D1에 대한 변경이므로 D1을 덮어쓴다.이 때 쓰기 연산은 같은 서버 **Sx**가 처리한다고 가정하자. 벡터 시계는 **D2([Sx, 2])**로 바뀔 것이다.

3. 다른 클라이언트가 D2를 읽어 D3로 갱신한 다음 기록한다. 이 쓰기 연산은 Sy가 처리한다고 가정하자. 벡터 시계 상태는 D3([Sx, 2], [Sy, 1]])로 바뀐다.

4. 또 다른 클라이언트가 D2를 읽고 D4로 갱신한 다음 기록한다. 이 때 쓰기 연산은 서버 Sz가 처리한다고 가정하자. 벡터 시계는 D4([Sx, 2], [Sz, 1])일 것이다.

5. 어떤 클라이언트가 D3와 D4를 읽으면 데이터 간 충돌이 있다는 것을 알게 된다. D2를 Sy와 Sz가 각기 다른 값으로 바꾸었기 때문이다. 이 충돌은 클라이언트가 해소한 후에 서버에 기록한다. 이 쓰기 연산을 처리한 서버는 Sx였다고 하자. 벡터 시계는 D5([Sx, 3], [Sy, 1], [Sz, 1])로 바뀐다.

---

충돌이 일어났다는 것을 감지하는 방법

• 벡터 시계를 사용하면 어떤 버전 X가 버전 Y의 이전 버전인지(따라서 충돌이 없는지) 쉽게 판단할 수 있다.

• 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 모든 구성요소 값보다 같거나 큰지만 보면 된다.

  • 예를 들어 벡터 시계 D([S0, 1], [s1, 1])은 D([s0, 1], [s1, 2])의 이전 버전이다. 따라서 두 데이터 사이에 충돌은 없다.

• 버전 X와 Y사이에 충돌이 있는지 보려면 Y의 벡터 시계 구성요소 가운제 X의 벡터 시계 동일 서버 구성요소보다 작은 값을 갖는 것이 있는지 확인해 보면 된다.

이 방식에는 두 가지 단점이 있다.

1. 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로, 클라이언트 구현이 복잡해진다.

2. [서버:버전] 의 순서쌍 개수가 굉장히 빨리 늘어난다.

장애 감지와 처리

• 분산 시스템에서는 그냥 서버 한대가 죽었다고 "지금 서버 A가 죽었습니다" 라고 해서 바로 서버 A를 장애처리 하지 않는다.

• 보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 실제로 해당 서버에 장애가 발생했다고 간주한다.

장애감지 : 가십프로토콜

• 각 노드는 멤버십 목록을 유지.

• 각 노드는 주기적으로 자신의 Heatbeat counter를 증가시킨다

• 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 Heartbeat counter 목록을 보냄

• 목록을 받은 노드는 멤버십 목록을 최신값으로 갱신

• 어떤 멤버의 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애상태인 것으로 간주한다.

일시적 장애 처리

• 가십프로토콜로 장애를 감지하면 시스템은 가용성을 보장하기 위해 조치를 해야한다

• 엄격한 정족수 접근법을 쓴다면 → 읽기와 쓰기 연산을 금지

• 느슨한 정족수 접근법을 쓴다면 → 조건을 완화하여 가용성을 높인다.

  • 정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고른다. 이때 장애 상태인 서버는 무시

• 장애 서버는 복귀 되었을 때 데이터를 일괄 반영하여 데이터 일관성을 보존.

영구적 장애처리 : 반-엔트로피 프로토콜

• 사본간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클트리를 사용

• 머클트리 만들어보기

  키 공간이 1~12인 머클 트리를 만들때.

  일관성이 깨진 데이터는 색으로 표시됨

  키 공간을 버킷으로 나눈다.(예제는 4개로 나눔)

버킷에 포함된 각각의 키에 균등 분포 해시 함수를 적용해서 해시 값을 계산한다.

버킷별로 해시 값을 계산한 후, 해당 해시 값을 레이블로 갖는 노드를 만든다

자식 노드의 레이블로부터 새로운 해시 값을 계산하여, 이진 트리를 상향식으로 구성해 나간다

• 머클 트리의 비교는 루트 노드의 해시값을 비교하는 것으로 시작한다. 루트 노드의 해시값이 일치한다면 같은 데이터를 갖는 것.

• 값이 다를 경우 왼쪽 자식 노드의 해시 값을 비교하고, 그다음 오른쪽 자식 노드의 해시 값을 비교한다. 아래쪽으로 탐색해 나가다 보면 다른 데이터를 갖는 버킷을 찾을 수 있으므로 해당 버킷만 동기화 하면 된다.

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

주요기능

• 클라이언트는 키-값 저장소가 제공하는 두가지 단순한 API인 get(key)와 put(key,value)로 통신한다

• 중재자는 클라이언트에게 키-값 저장소에 대한 프록시 역할을 하는 노드다

• 노드는 안정 해시의 해시 링 위에 분포한다.

• 노드를 자동으로 추가 또는 삭제할 수 있도록 시스템은 완전히 분산된다

• 데이터는 여러 노드에 다중화된다

쓰기 경로

1. 쓰기 요청이 커밋 로그 파일에 기록된다

2. 데이터가 메모리 캐시에 기록된다

3. 메모리 캐시가 가득 차거나 사전에 정의된 임계치에 도달하면 데이터는 디스크에 있는 SSTable(Sorted-String Table)에 기록된다. (SSTable은 <키,값> 순서쌍을 정렬된 리스트 형태로 관리하는 테이블)

읽기 경로

데이터가 메모리 캐시에 있을 경우

데이터가 메모리 캐시에 없을 경우

읽기 요청을 받으면 메모리 캐시부터 살펴본다. 데이터가 메모리에 없는 경우에는 디스크에서 가져온다. 어느 SSTable에 찾는 키가 있는지 알아내는 효율적인 방법으로는 Bloom filter가 흔히 사용된다.

1. 데이터가 메모리에 있는지 검사 있으면 바로 반환. 없으면 2번으로 간다

2. 없으면 블룸필터를 검사해서 어떤 SSTable에 키가 보관되어 있는지 알아낸다

3. SSTable에서 데이터를 가져와서 반환한다

정리

키-값 저장소가 가져야 하는 기능과 그 기능 구현에 사용되는 기술

참고

블룸필터(Bloom Filter) 개념과 원리 그리고 예제 코드

SSTable를 이용한 데이터 저장