# 6. 키-값 저장소

## 💬 키-값 저장소

* 비 관계형 데이터베이스이다.
* 키는 유일한 고유식별자여야 하며 짧을수록 성능에 좋다.
* 값은 문자열, 리스트, 객체 등 어떤 값이든 가능하다.
* 아마존 다이나모, memcached, redis 등이 이에 해당한다.

### 단일 서버

* 모든 데이터를 하나의 메모리 내에 두는 것은 사실 상 불가능하다.
* 단일 서버를 사용하려면 데이터를 압축해 저장하거나 자주쓰는 데이터만 메모리에 두고 나머지는 디스크에 저장해야 한다.

### 분산 서버

* key-value 쌍을 여러 서버에 분산시키는 형태이다.

#### CAP 정리

* Consistency, Availability, Partition Tolerance theorem
* **데이터 일관성, 가용성, 파티션 감내를 모두 만족하는 분산 시스템 설계는 불가능**하다는 정리이다. 두 가지를 충족하려면 반드시 나머지 하나는 희생된다.
  * 데이터 일관성: 어느 서버에 접속하든 항상 같은 데이터를 얻어야 한다.
  * 가용성: 일부 서버에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
  * 파티션 감내: 두 노드 사이에 통신 장애가 발생했음을 의미하는 파티션이 생기더라도 시스템은 동작해야 한다.
* 통신 장애는 막을 수 없으므로 파티션 감내는 반드시 충족되어야 한다.
* CP 시스템: 가용성을 희생하고 일관성, 파티션 감내를 지원하는 시스템
* AP 시스템: 일관성을 희생하고 가용성과 파티션 감내를 지원하는 시스템
* 일관성 vs 가용성
  * 은행권 시스템의 경우 일관성이 더욱 중요 (계좌 정보 등등)
  * 가용성을 선택한 시스템(ex 블로그, 카페 등) 은 예전 데이터를 반환할 가능성이 있더라도 끊김 없이 읽기 연산을 허용해야 한다.

## 💬 분산 키-값 저장소를 위한 컴포넌트 및 기술

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FsjeH1OKgAH49pXcjRvp9%2Fimage.png?alt=media&#x26;token=9d92a552-e6ae-4ac3-9183-7bcea0854f97" alt=""><figcaption></figcaption></figure>

### 데이터 파티션

* 안정 해시를 사용해 데이터를 파티션하여 다음과 같은 이점을 얻을 수 있다.
  * 규모 확장 자동화
    * 시스템 부하에 따라 쉽게 서버를 scale-out, scale-in할 수 있다.
  * 다양성
    * 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다. 고성능 서버의 경우 가상 노드를 더 배치하도록 하면 더 많은 데이터가 저장될 것이다.

### 데이터 다중화

* 높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 복제해야 한다.
* 데이터를 여러 서버에 중복 저장해두기 위한 방법으로 해시링에서 시계 방향으로 돌며 N개의 서버에 저장할 수 있으나, 가상 노드를 사용하는 경우 같은 물리 서버를 여러 번 선택하지 않도록 주의해야 한다.
* 같은 데이터 센터에 속한 서버 노드들은 정전, 네트워크 이슈, 자연재해 등 문제를 동시에 겪을 수 있으므로, 안정성을 위해 데이터 사본은 다른 데이터 센터의 서버에 보관하고 데이터 센터들은 고속 네트워크로 연결해야 한다.

### 데이터 일관성

* Quorum Consensus 프로토콜
  * 읽기/쓰기 연산 모두에 일관성을 보장하기 위한 방법이다.
  * N개 서버에 사본이 있고, W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 하고, R개의 서버로부터 읽기 연산이 성공했다는 응답을 받아야 한다.
  * 중재자
    * 읽기/쓰기 연산이 성공했다는 것을 판단하기 위해 W, R 값을 사용한다. 모든 조건이 만족되는 경우에만 클라이언트로 응답을 보낸다.
    * 클라이언트와 노드 사이에서 프록시 역할을 한다.
    * W, R 값이 1보다 큰 경우 비교적 응답 속도가 느린 두번째 \~ W번째 응답까지 받아야 하므로 전체 응답 속도가 느려질 것이다.
  * 강한 일관성 보장을 위해서는 `W+R > N` 이 되어야 한다. (보통 N=3 , W=R=2)

### 일관성 모델

* 종류
  * 강한 일관성
    * 읽기 요청 시에 절대로 옛날 데이터를 절대 반환하지 않는다.
    * 모든 사본에 쓰기 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지시켜야 달성 가능하다.
    * 일시적으로 반응하지 않을 수 있어 고가용성 시스템에 적합하지 않다.
  * 약한 일관성
    * 읽기 요청 시에 옛날 데이터를 반환할 수도 있다.
  * 최종 일관성
    * 최종적으로는 모든 사본에 최신 데이터가 반영되지만, 동기화 과정이 완료되기 전에는 옛날 데이터를 반환할 수 있다.
    * 다이나모, 카산드라 등은 최종 일관성 모델을 택하고 있다.
    * 쓰기 연산이 병렬적으로 발생하면 사본마다 시스템에 저장된 값의 일관성이 깨질 수 있다. 따라서 클라이언트 측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 해야 한다.

#### 비 일관성 해소 모델

* 데이터 버저닝
  * 데이터를 변경할 때마다 데이터의 새로운 버전을 생성하는 방식
  * 각 버전의 데이터는 변경 불가능하다.
  * 여러 서버에 걸쳐 존재하는 동일 데이터에 동시에 수정이 가해지는 경우, 각 서버 데이터의 마지막 버전이 다를 수 있다.
* 벡터 시계
  * 서버, 버전 순서쌍을 \[server1, version1] 형태로 데이터에 매달아둔다. 이 때 서버는 WAS 등을 의미한다.
  * &#x20;조회 시에 데이터 충돌이 발생했음을 확인하면 직접 해소한 후 서버에 기록한다.
  * `Data1([Server0, v1], [server1, v1])`은 `Data1([Server0, v2], [server1, v1])` 의 이전 버전이다.
  * `Data1([Server0, v1], [server1, v2])`과  `Data1([Server0, v2], [server1, v1])` 은 충돌이 일어난 상태이다.
  * 단점
    * 충돌 감지 및 해소 로직이 서버에 들어가므로 구현이 복잡해진다.
    * 보통 순서쌍 개수가 빠르게 증가하기 때문에, threshold를 설정하여 threshold 이상으로 늘어나면 오래된 순서쌍을 벡터 시계에서 제거해야 한다. 하지만 이렇게 하면 버전 간 선후 관계가 모호해져 충돌 해소 과정의 효율성이 낮아진다.
  * 다음은 벡터 시계를 활용한 충돌 해소 플로우이다.&#x20;
    * 3\~4번 과정에서 동시에 쓰기 연산이 처리되어 버전이 충돌된 상태가 된다.
    * 클라이언트가 데이터를 요청하면, 서버 측에서는 버전 충돌이 있다는 정보들을 전달한다.
    * 클라이언트는 서버로부터 받은 정보들을 기반으로 버전 충돌을 해소한 데이터를 서버에 보내 쓰기 연산을 처리하도록 한다.

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FC6OclR8qMvylyCkBuqrE%2Fimage.png?alt=media&#x26;token=f4d9b398-e5c7-470e-b395-972811f02922" alt=""><figcaption></figcaption></figure>

### 장애 처리

#### 장애 감지 기법

* 모든 노드 사이에 multicasting 채널을 구축하는 방법이 있으나, 서버가 많을 경우 연결이 많아져 비효율적이다.

#### 분산형 장애 감지

* 각 노드마다 heartbeat counter 를 가지며, 주기적으로 증가시킨다.
* 각 노드마다 membership list가 있고, 그 리스트에는 다른 노드들의 heartbeat counter를 저장해둔다.
* 각 노드는 무작위로 선정된 노드들에게 heartbeat counter들을 저장해둔 목록을 주기적으로 전송한다.
* heartbeat가 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주한다.

#### 일시적 장애 처리

* sloppy quorum
  * 쓰기 연산을 수행할 정상 서버와 읽기 연산을 수행할 정상 서버를 각각 해시 링에서 고른다.
  * 장애가 발생한 노드에 저장되었어야 할 것을 임시로 다른 서버에 저장해두게 된다. 이 때 임시 데이터에는 hint를 남겨두어야 한다. (hinted handoff)
  * 장애 발생하였던 서버가 복구되면 그동안 발생한 변경사항들을 일괄 반영받는다.

#### 영구 장애 처리

* anti entropy 프로토콜을 통해 사본들을 비교한 후 최신 버전으로 갱신하여 사본들을 동기화해야 한다.
* 사본들끼리 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 **머클 트리**를 사용할 수 있다.
* 머클 트리란 **자식 노드들에 보관된 값의 해시 / 자식 노드들의 레이블로부터 계산된 해시 값을 부모 노드의 레이블로 붙여두는 트리**이다.
* 머클 트리 만드는 과정
  *   키 공간을 버킷 단위로 나누고 키에 uniform hash 함수를 적용한다.

      <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2Fo4TUNKMt5QmlTiGo5QHO%2Fimage.png?alt=media&#x26;token=c47a0ef9-83e7-490a-a3aa-4b9a18ba5a22" alt=""><figcaption></figcaption></figure>
  *   버킷 단위로 해시 값을 계산하여 해시 값을 레이블로 갖는 노드를 만든다.

      <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2F8UtBVW2RQsNhBfVCWAvp%2Fimage.png?alt=media&#x26;token=557ee1b9-2cfc-434e-b9d5-8c5fc9badc61" alt=""><figcaption></figcaption></figure>
  *   자식 노드의 레이블로부터 해시 값을 계산해 이진 트리를 만들어나간다.

      <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FatrHtaamxHe7WyV917Sc%2Fimage.png?alt=media&#x26;token=1094d1d4-3e79-4ebd-84f1-5e2b2a5dd162" alt=""><figcaption></figcaption></figure>
* 머클 트리를 비교할 때에는 부모 노드에서 자식 노드로 이동하며 값이 동등한지 확인한다. 만약 값이 다르다면 일관성이 깨진 상황이므로 해당 버킷들에 존재하는 데이터를 동기화해주어야 한다.

## 💬 데이터 쓰기/읽기

### 쓰기 경로

* 쓰기 요청이 먼저 커밋 로그에 기록되고, 그 다음 메모리 캐시에 저장한다.
* 메모리 캐시가 가득 차거나 특정 조건이 되면 데이터가 디스크의 SSTable(Sorted String Table)에 기록된다.

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FTC6uff2DuX6B2SYxeV2z%2Fimage.png?alt=media&#x26;token=5ee586fc-ce6e-4281-aa9a-b3648593e77f" alt=""><figcaption></figcaption></figure>

### 읽기 경로

* 데이터가 메모리 캐시에 있으면 바로 반환한다.
* 데이터가 메모리 캐시에 없다면 블룸 필터를 검사하여 어떤 SSTable에 키가 존재하는지 확인한 후 데이터를 가져온다.

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FpVUQ8XR3mNFpZzJdq8tE%2Fimage.png?alt=media&#x26;token=d2fdc0d0-f6d3-4ff3-8cdc-87dab63b3127" alt=""><figcaption></figcaption></figure>
