[대규모 시스템 설계 기초] 6장 키-값 저장소 설계

 

 

👩🏻‍🏫 키-값 저장소 시스템을 설계해 주세요!

라는 요청을 받았다면?

 

먼저 키-값 저장소가 무엇인지 알아야 한다.

 

🤔 키-값 저장소?

• 자료구조의 Map과 같이 키(key)를 식별자로 값(value)을 저장하는 일종의 데이터 베이스
• 비관계형 데이터베이스 (ex. 아마존 다이나모, memcached, 레디스)

💬 키-값 저장소의 특징

✔️ 키는 유일해야 한다.

✔️ 오직 키로 대응되는 값에 접근할 수 있다.

✔️ 키는 일반 텍스트이거나 해시 값이다.

✔️ 키는 짧을수록 성능이 좋다.

✔️ 값은 문자열, 리스트, 객체 등 다양한 형태의 데이터를 가질 수 있다.

 

 

기본적인 기능(put(key, value), get(key))을 가진 키-값 저장소 시스템을 설계 해보자!

 

---

 

1️⃣ 단일 서버 키-값 저장소

 : 키-값 쌍 전부를 메모리에 해시 테이블로 저장

• 속도가 빠르다.
• 데이터가 많아지면 메모리에 모든 데이터를 저장할 수 없다.
  💡 해결책
    - 데이터 압축
    - 자주 쓰이는 데이터만 메모리에 저장하고 나머지는 디스크에 저장

🤔 하나의 서버에서 데이터 읽기/쓰기 연산은 어떻게 동작할까?

✔️ 쓰기 경로

1.  쓰기 요청이 커밋 로그 파일에 기록된다.
2. 데이터가 메모리 캐시에 키록된다.
3. 메모리 캐시가 가득차거나 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록된다.

* SSTable: Sorted-String Table, <키, 값>의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블

 

✔️ 읽기 경로

1.  데이터가 메모리에 있는지 검사한다. 있으면 바로 결과를 반환하고 없다면 2로 간다.
2. 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아낸다.
3. SSTable에서 데이터를 가져온다.
4. 해당 데이터를 반환한다.

* 블룸 필터: 어느 SSTable에 찾는 키가 있는지 찾아주는 필터

 

하지만 데이터가 계속 증가하면 결국 하나의 서버로는 감당할 수 없다.

키-값 쌍을 여러 서버에 분산시켜 저장해보자!

 

2️⃣ 분산 키-값 저장소

 : 데이터를 작은 파티션들로 분할한 다음 여러 대의 서버에 저장

 

🤔 데이터를 어떻게 분할해야 할까?

 ▪️ 데이터를 여러 서버에 고르게 분산해야 한다.

 ▪️ 노드(서버)가 추가되거나 삭제될 때 데이터의 이동을 최소화해야 한다.

 

💡 해결책은 안정 해시

• 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제 되도록 만들 수 있다.
• 각 서버 용량에 맞게 가상 노드의 수를 조정할 수 있다.

📎 [대규모 시스템 설계 기초] 5장 안정 해시 설계

 

---

 

하지만 여기서 끝이 아니라,

데이터의 높은 가용성과 안전성을 확보하기 위해서 데이터를 여러 서버에 다중화 해야 한다. (SPOF 방지)

 

N개의 서버에 데이터를 다중화하기로 했다면,

🤔 어떻게 다중화 할 서버를 선택할까?

• 키(key)를 해시 링 위에 배치한 뒤, 시계방향으로 만나는 첫 N개 서버에 저장
• 가상 노드를 사용하면 선택되는 물리 서버가 중복될 수 있으므로 중복 처리를 해주어야 한다.

❕ 이때, 데이터 센터 장애 시 가용성을 확보하려면 물리 서버가 다른 데이터 센터에 있도록 하는 것도 고려해야 한다.

 

다중화할 서버를 결정 했다면..

🤔 N개의 서버에서 데이터 동기화는 어떻게 할까?

💡 정족수 합의 프로토콜을 사용해서 읽기/쓰기 연산 모두에 일관성 보장 가능

 

❓ 정족수 합의 프로토콜?
1️⃣ 클라이언트가 데이터 연산(읽기, 쓰기)을 요청한다.
2️⃣ 중재자(프록시)가 해당 연산을 다중화된 서버에 요청한다.
3️⃣ 다중화된 서버에서 연산 결과를 중재자에게 전달한다.
4️⃣ 중재자가 성공 응답의 수와 해당 연산의 정족수를 비교해 클라이언트 요청의 성공 여부를 결정한다. 

 

🤔 읽기 연산의 정족수(W)와 쓰기 연산의 정족수(R)는 어떻게 정해야 할까?

💡 데이터 일관성과 높은 가용성 사이의 트레이드오프를 고려해서 결정해야 한다! (bc. CAP정리)

• W또는 R이 작으면 프록시는 적은 연산 결과만 가지고도 클라이언트에게 응답할 수 있다 (높은 가용성)
• W또는 R이 크면 데이터 일관성의 수준이 향상된다.

❕ CAP 정리
 : 데이터의 일관성(consistency), 가용성(availability), 파티션 감내(partition torweance theomrem)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리

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

이들 가운데 어떤 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다.
하지만 분산 시스템은 네트워크 장애를 피할 수 없으므로 파티션 감내는 무조건 가져가야 한다. (결국 CP, AP 시스템 중 선택)

 

그렇다면 시스템에서 필요한 일관성의 수준이 어느 정도인지 파악해보자!

 

• 강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. (W + R > N)
• 약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 도 있다.
• 결과적 일관성 : 약한 일관성의 한 형태로, 클라이언트 측에서 데이터 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 하는 기법 (결국에는 갱신 결과가 모든 사본에 반영)

❕ 강한 일관성을 달성하는 일반적인 방법은, 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 연산을 금지하는 것

 

🤔 W + R > N가 왜 강한 일관성을 보장할까?
N = 3이고 W = 2, R = 2으로 설정했다고 가정하자.

쓰기 작업을 1, 2, 3 서버 중 1, 2서버에서 수행했고, 3 서버에서 실패했다고 해보자.
다음 읽기 작업에서 최소 2대의 서버에서 읽기를 수행해야 하는데, 이때 3 서버가 읽기를 수행했더라도 1과 2 서버 중 하나는 무조건 읽기에 참여하기 때문에 중재자가 최신 데이터를 확인하고 응답할 수 있다!

 

강한 일관성과 약한 일관성의 중간이라고 볼 수 있는 결과적 일관성을 다이나모, 카산드라에서도 선택하고 있다.

 

어쨋든, 가용성을 포기하고 강한 일관성을 선택하지 않는 이상 데이터 불일치는 발생할 수밖에 없다!

🤔 데이터 비일관성을 어떻게 해결할 수 있을까?

💡 데이터 버저닝, 벡터 시계

 

❓ 데이터 버저닝

 : 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것 (ex. ETag)

 

❓ 벡터 시계

 : [서버, 버전]의 순서쌍을 데이터에 함께 저장하는 것

1️⃣ 클라이언트가 쓰기 연산 요청을 보냈다. (데이터 비 일관성 문제는 쓰기 연산에서 발생)
2️⃣ 서버 Sx가 쓰기연산을 수행하고, 벡터 시계가 D1([Sx, 1])이 된다. (D는 데이터) 
3️⃣ 서로 다른 클라이언트가 같은 데이터의 쓰기 연산을 동시에 요청 했다.
4️⃣ 서버 Sy와 Sz가 각각의 연산을 수행하고 벡터 시계가 각각 D2([Sx, 1], [Sy, 1]), D3([Sx, 1], [Sz, 1])
5️⃣ 클라이언트가 D2와 D3를 읽으면, 데이터 간 충돌(어느 쪽도 다른 벡터 시계보다 우선하지 않음)을 확인하고 다시 쓰기 연산을 요청
6️⃣ Sx가 쓰기 연산을 수행하고, 백터 시계가 D4([Sx, 2], [Sy, 1], [Sz, 1])로 변경

*A의 벡터 시계에 있는 모든 요소가 B의 백터 시계에 있는 요소보다 작거나 같고 적어도 하나의 요소가 더 작은 경우 A가 B보다 먼저 발생하는 것으로 간주

 

• 충돌 감지 및 해소 로직이 클라이언트에 들어가 있어, 클라이언트 구현이 복잡해진다.
• [서버: 버전]의 순서쌍이 굉장히 빨리 늘어난다.
  💡 해결책
    - 벡터 시계의 길이 임계치를 설정하고, 임계치를 넘으면 오래된 순서쌍을 제거

 

---

 

이제 가용성과 일관성을 잘 조율해서 키-값 저장소 시스템을 설계했다!

마지막으로 장애(offline)에 대응할 수 있도록 시스템에 설계를 추가해보자!

 

장애를 처리할려면, 일단 장애가 발생했다는 것을 감지해야한다.

🤔 장애는 어떻게 감지할 수 있을까?

💡 가십 프로토콜 (분산형 장애 감지)

 

❓가십 프로토콜?
1️⃣ 각 노드는 멤버십 목록(다른 노드들)을 유지한다. (멤버십 목록: 각 멤버 ID와 그 박동 카운터 쌍)
2️⃣ 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다
3️⃣ 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다.
4️⃣  어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주한다.

 

 

장애를 감지했다면,

🤔 어떻게 장애를 처리할 수 있을까?

 

장애는 일시적인 장애와 영구적인 장애로 구분할 수 있다! 각각 장애 상황에 맞는 처리 방법을 알아보자.

 

✔️ 일시적 장애 처리

💡 엄격한 정족수 접근법을 사용하고 있었다면, 느슨한 정족수 접근법으로 변경

💡 그 후 장애 서버로 가는 요청을 다른 서버가 잠시 맡아 처리하고, 그 동안 발생한 변경 사항(단서)을 장애 서버가 복구 되었을 때 일괄 반영하는단서 후 임시위탁 기법을 사용

 

* 느슨한 정족수 접근법: 정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버(장애 서버X)를 해시링에서 고른다.

 

✔️ 영구적 장애 처리

💡 반-엔트로피 프로토콜

❓반-엔트로피 프로토콜?
1️⃣ 각 노드는 정기적으로 다른 노드의 데이터와 자신의 데이터를 비교합니다.
2️⃣ 두 노드 간에 데이터의 차이가 발견되면, 이를 식별합니다.
3️⃣ 차이가 발견된 데이터는 최신 상태로 업데이트되어, 모든 노드가 동일한 데이터를 가지도록 합니다.

 

두 노드 간에 데이터를 비교하기 위해 머클 트리가 사용된다.

❓머클 트리(해시 트리)?
 : 각 노드에 그 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리 (자식 노드가 종단 노드라면 자식 노드들에 보관된 값의 해시)

1️⃣ 키 공간을 버킷으로 나눈다.
2️⃣ 버킷에 포함된 각각의 키에 균등 분포 해시 함수를 적용하여 해시 값을 계산한다.
3️⃣ 버킷별로 해시값을 계산한 후, 해당 해시 값을 레이블로 갖는 노드를 만든다.
4️⃣ 자식 노드의 레이블로부터 새로운 해시 값을 계산하여, 이진 트리를 상향식으로 구성해 나간다.
이제 두 서버의 머클 트리를 비교해 보자
5️⃣  루트 노드의 해시값을 비교한다. (해시값이 일치한다면 두 서버는 같은 데이터를 갖는 것이다.)
6️⃣ 해시값이 다르다면, 왼쪽 자식 노드의 해시값을 비교하고, 그 다음으로 오른쪽 자식 노드의 해시값을 비교한다. (DFS같군..)
7️⃣ 이렇게 아래쪽으로 탐색해 나가면서 불일치하는 데이터를 발견하고 동기화한다.

❕ 머클 트리에서 동기화해야 하는 데이터의 양은 실제로 존재하는 데이터 차이에 비례, 데이터의 총량의 비례X (효율적)

 

 

---

 

이제 공부를 잘 했다면, 아래의 질문에 대답해보자

👩🏻‍🏫 아래와 같은 요구사항을 가진 키-값 저장소 시스템을 설계해 주세요.

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

 

(힌트) 요구사항을 만족하기 위해 필요한 기능들

• 클라이언트 API
• 다중화
• 데이터 충돌 해소
• 장애 감지
• 장애 복구 메커니즘
• 저장소 엔진
• ....