키-값 저장소 설계

키-값 쌍에서의 키는 유일해야 하며 해당 키에 매달린 값은 키를 통해서만 접근할 수 있다. 키는 일반 텍스트일 수도 있고 해시 값일 수도 있다. 성능상의 이유로, 키는 짧을수록 좋다. 아래는 키의 몇 가지 사례다.
- 일반 텍스트 키:"last logged_in_at"
- 해키 키: 253DDEC4

완벽한 설계란 없다. 읽기, 쓰기 그리고 메모리 사용량 사이에 어떤 균형을 찾고, 데이터의 일관성과 가용성 사이에서 타협적 결정을 내린 설계를 해야한다.

한 대 서버만 사용하는 키-값 저장소를 설계하는 것은 쉽다. 그 방법은 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는것. 그러나 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다.이를 위한 개선책으로 다음과 같은 방법이 있다.
- 데이터 압축
- 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장

### 분상 키-값 저장소
키-값 쌍을 여러 서버에 분산시키는 방법. 분산 시스템을 설계할 때는 CAP 정리를 이해하고 있어야 한다.

 

C - Consistency (일관성)|모든 노드가 같은 시점에 같은 데이터를 보여줌 (예: DB A에서 쓴 값을 DB B도 즉시 읽을 수 있음)
A - Availability (가용성)|클라이언트의 모든 요청에 대해 항상 응답을 제공 (정확하지 않더라도 응답을 함)
P - Partition Tolerance (분할 허용성)|네트워크 장애로 노드 간 통신이 불가능해져도 시스템이 계속 작동

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

따라서, 실제 시스템은 일반적으로 다음 중 하나로 설계된다.
- CP 시스템: 일관성과 분할 허용성을 보장 (ex: HBase, MongoDB 설정에 따라)
- AP 시스템: 가용성과 분할 허용성을 보장 (ex: Cassandra, Couchbase)
- CA 시스템: 이론적으로만 가능, 실제 분산 환경에서는 불가능
분산 시스템은 파티션 문제를 피할 수 없다. 

#### 대규모 파티션
대규모 애플리케이션의 경우 전체 데이터를 한 대 서버에 욱여넣는 것은 불가능하다. 가장 단순한 해결책은 데이터를 작은 파티션들로 분할한 다음 여러 대 서버에 저장하는 것이다.
이때 고려할 사항은
- 데이터를 여러 서버에 고르게 분산할 수 있는가
- 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가

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

#### 데이터 다중화
높은 가용성과 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화할 필요가 있다. N개 서버에 비동기 적으로 저장한다고 했을때, 해시링을 순회하면서 N번째 노드에 데이터 사본을 보관하는 방법으로 다중화를 할 수 있다. 이때 선택한 노드가 물리적으로 같은 서버일 수 있는데, 이를 피해야한다.

#### 데이터 일관성
다중화된 데이터는 적절히 동기화가 되어야 한다. 

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

N,W,R의 값을 어떻게 정해야 할까?
- R=1, W=N: 빠른 읽기 연산에 최적화된 시스템
- W=1, R=N: 빠른 쓰기 연산에 최적화된 시스템
- W+R>N: 강한 일관성이 보장됨 (보통 N=3, W=R=2)
- W+R≤N: 강한 일관성이 보장되지 않음

##### 일관성 모델
- 강한 일관성(strong consistency): 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 다시 말해서 클라이언트는 절대로 낡은(oul-of-date) 데이터 를 보지 못한다.

- 약한 일관성(weak consistency): 읽기 연산은 가장 최근에 갱신된 결과를반 환하지 못할 수 있다.

- 최종 일관성(eventual consistency): 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(즉, 동기화)되는 모델이다.


강한 일관성은 고가용성 시스템에는 적합하지않다. 새로운 요청 처리가 중단되기 때문
다이나모 또는 카산드라같은 저장소는 최종 일관성 모델을 택한다.

##### 비 일관성 해소 기법 : 데이터 버저닝
데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성은 높아진다. 버저닝과 벡터 시계는 그 문제를 해소하기 위해 등장한 기술이다. 각 버전의 데이터는 변경 불가능하다.

데이터 저장이 동시에 일어났을때 충돌이 발생하는데, 벡터 시계는 충돌 문제를 해결하는데 사용되는 기술이다.

요약하면 과정에서 출돌이 일어났을때 클라이언트가 데이터를 읽게되면 충돌이 있었다는것을 알게된다. 이 충돌은 클라이언트가 해소한 후에 서버에 기록한다.

벡터 시계의 단점으로는 클라이언트에 충돌 해소 로직이 들어가야 하므로, 클라이언트 구현이 복잡해진다. 또한 버전의 개수가 굉장히 빠르게 늘어난다는 단점이 있다. 때문에 임계치를 정해 그 이상으로 길어지면 오래된 순서대로 삭제가 필요하다. 다이나모에서 이 방법을 사용하는데 문제가 없다고하니 대부분의 기업에서 백터시계를 적용해도 괜찮을것이다.

#### 장애 처리

##### 장애감지

가십 프로토콜
- 각 노드는 멤버십 목록(membership list)를 유지한다. 멤버십 목록은 각 멤버 ID와 그 박동 카운터(heartbeat counter) 쌍의 목록이다.
- 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다.
- 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록  
    을 보낸다.
- 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신한다.
- 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버 는 장애(offine) 상태인 것으로 간주한다.


##### 일시적 장애 처리
장애가 난 서버를 제외하고 w개의 쓰기 서버와 r개의 읽기 서버를 선정하여 장애 서버를 대신한다.

##### 영구 장애 처리

영구적인 노드 장애 상태 처리는 반-엔트로피(anti-entropy) 프로토콜을 구현하여 사본들을 동기화할 것이다.
반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함한다. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄 이기 위해서는 머클(Merkle) 트리를 사용할 것이다.

머클 트리 사용 (해시 트리)
- 해시 트리(Hash Tree)라고도 하며, 각 리프 노드는 데이터 블록의 해시값이고, 상위 노드는 자식 노드들의 해시값을 다시 해시하여 구성된 트리입니다.
    
- 최상단 루트 노드의 해시값만 비교하면 전체 데이터의 정합성을 빠르게 확인할 수 있음.

🛠 Merkle Tree 기반 장애 조치 과정 (Failover & Sync)
분산 시스템에서 노드 A와 노드 B의 데이터 동기화를 예로 설명합니다.

1. 장애 감지
- 노드 A가 장애로 인해 잠시 오프라인 상태가 됨.
    

2. 복구 후 데이터 비교
- 노드 A가 다시 온라인이 되었을 때, 노드 B와 데이터가 동일한지 빠르게 비교해야 함.
- 이때 전체 데이터를 비교하는 것은 비용이 매우 큼.
    

3. Merkle Tree를 이용한 효율적 비교
- A와 B는 Merkle Tree의 루트 해시값을 서로 교환함.
- 해시값이 같으면 데이터 전체가 동일 → 추가 작업 불필요.
- 해시값이 다르면 → 트리를 따라 내려가면서 불일치 지점 탐색.
    

4. 불일치 구간만 동기화
- 차이가 발생한 리프 노드(=데이터 블록)만 A 또는 B에서 가져와서 동기화.
- 장애 이전 상태로 정합성 있게 빠르게 복구됨.

> SSTable이란?
SSTable은 정렬된 불변 구조의 디스크 저장 파일로, 빠른 쓰기와 정합성 유지, 장애조치에 유리한 저장 방식
Merkle Tree와 결합되면, 어떤 블록이 손상되었는지를 정확히 짚어내어 **효율적인 복구와 노드 동기화**가 가능