6장. 키-값 저장소 설계

키-값 저장소란,

키-값 데이터베이스라고도 불리는 비 관계형 데이터베이스이다.

키-값 쌍에서 키는 유일해야 하며 해당 키에 매달린 값은 키를 통해서만 접근할 수 있다.

• 키는 일반 텍스트일 수도 있고, 해시 값일 수도 있다. 하지만 성능 상의 이유로 키는 짧을수록 좋다.
• 값은 문자열일 수도 있고 리스트일 수도, 객체일 수도 있다. 보통 값으로 무엇이 오든 상관없다.

 

문제 이해 및 설계 범위 확정

완벽한 설계란 없으며, 읽기-쓰기 그리고 메모리 사용량 사이에 어떤 균형을 찾고, 데이터의 일관성과 가용성 사이에 타협적 결정을 내린 설계를 만드는 것이 바람직하다.

 

 

단일 서버 키-값 저장소

가장 직관적인 방법은 키-값 쌍을 전부 메모리에 해시 테이블로 저장하는 것

빠른 속도를 보장하긴 하지만, 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다는 단점 존재.

 

개선책

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

 

분산 키-값 저장소

분산 해시 테이블이라고도 불린다. -> 키-값 쌍을 여러 서버에 분신시키기 때문

분산 시스템을 설계할 때는 CAP 정리를 이해하고 있어야 한다.

 

CAP 정리

세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하며, 셋 중 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다.

 

Consistency(일관성)

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

Availability(가용성)

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

Partition Tolerance(파티션 감내)

• 파티션: 두 노드 사이에 통신 장애가 발생하는 경우
• 네트워크에 파티션이 생기더라도 시스템은 계속 동작해야 한다.

 

실제로는 통상 네트워크 장애를 피할 수 없는 일로 여기므로, 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다. 따라서 실세계에서는 CA 시스템은 존재하지 않는다.

 

분산 시스템에서 데이터는 보통 여러 노드에 복제되어 보관된다.

하지만 파티션 문제를 피할 수는 없어서, 파티션 문제가 발생하면 우리는 일관성과 가용성 사이에서 하나를 선택해야 한다.

 

좀 더 구체적인 사례로, n3 에 장애가 발생해 n1 및 n2 와 통신할 수 없는 상황이 존재한다고 가정한다.

이때 클라이언트가 n1 또는 n2 에 기록한 데이터는 n3 에 전달되지 않는다.

n3 에 기록되었으나 아직 n1, n2 로 전달되지 않은 데이터가 있다면, n1 과 n2 는 오래된 사본을 갖고 있을 것이다.

 

만약 가용성 대신 일관성을 선택한다면, 세 서버 간 데이터 불일치 문제를 피하기 위해 n1 과 n2 에 대해 쓰기 연산을 중단시켜야 하고, 그렇게 되면 가용성이 깨지게 된다. 보통 은행권, 핀테크 쪽은 보통 데이터 일관성을 더욱 중요시 여기는데, 이러한 상황처럼 데이터 일관성이 깨질 수 있는 상황이 발생하면 상황이 해결될 때까지 계속 오류를 반환시켜서 일관성을 유지한다.

 

반면 일관성 대신 가용성을 선택한다면, 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용해야 한다.

n1 과 n2는 계속해서 쓰기 연산을 허용할 것이고, 파티션 문제가 해결된 뒤에 새 데이터를 n3 에 전송할 것이다.

 

시스템 요구사항에 맞게 CAP 정리를 잘 적용해서 시스템을 설계하도록 하자.

 

 

시스템 컴포넌트

데이터 파티션

전체 데이터를 한 대 서버에 욱여넣는 것은 불가능하므로, 데이터를 작은 파티션들로 분할한 다음 여러 대 서버에 저장해야 한다.

 

데이터를 파티션 단위로 나눌 때는 두 가지를 고려해야 한다.

• 데이터를 여러 서버에 고르게 분산할 수 있는가
• 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가

 

이때 가장 적합한 기술이 안정 해시 기법이다.

• 마찬가지로 해시 링에 서버와 키를 배치
• 키-값 쌍을 어떤 서버에 저장할지를 정할 때, 키가 놓인 지점으로부터 링을 시계 방향으로 순회하다 만나는 첫 번째 서버를 찾으면 된다.

 

이렇게 안정 해시를 사용해 데이터를 파티션했을 때, 다음과 같은 이점이 있다.

• 규모 확장 자동화(automatic scaling): 시스템 부하에 따라 서버가 자동으로 추가/삭제
• 다양성: 각 서버의 용량에 맞게 가상 노드의 수를 조정 가능 - 고성능 서버는 더 많은 가상 노드를 갖도록

 

데이터 다중화

높은 가용성과 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화(Replication)할 필요가 있다.

마찬가지로 안정 해시 방식을 적용하면

• 어떤 키를 해시 링 위에 배치한 후
• 그 지점으로부터 시계 방향으로 링을 순회하면서 만나는 첫 N개 서버에 데이터 사본을 저장하면 된다.

그러나 만약 가상 노드를 사용한다면, 위의 그림과 같이 선택한 N 개의 노드가 대응될 실제 물리 서버의 개수가 N 보다 작아질 수 있다. 이러한 문제를 피하려면 노드를 선택할 때 같은 물리 서버를 중복 선택하지 않도록 해야 한다.

 

 

데이터 일관성

여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 한다.

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

• N = 사본 개수
• W = 쓰기 연산에 대한 정족수 - 쓰기 연산 성공으로 간주하기 위한 최소 W 개의 서버로부터 응답
• R = 읽기 연산에 대한 정족수 - 읽기 연산 성공으로 간주하기 위한 최소 R 개의 서버로부터 응답

 

예를 들어 위의 그림과 같이 S0, S1, S2 에 데이터가 다중화되는 경우,

W = 1 의 의미는, 쓰기 연산이 성공했다고 판단하기 위해 중재자는 최소 한 대 서버로부터 쓰기 성공 응답을 받아야 한다는 뜻이다. (데이터가 한 대 서버에만 기록된다는 뜻이 아님) 만약 S1 으로부터 성공 응답을 받았다면, S0, S2 로부터의 응답을 기다릴 필요가 없다.

중재자는 클라이언트와 노드 사이에서 프록시 역할을 수행한다.

 

W, R, N 의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정

 

e.g) N = 3

• R = 1, W = N : 빠른 읽기 연산에 최적화된 시스템
• W = 1, R = N : 빠른 쓰기 연산에 최적화된 시스템
• W + R > N : 강한 일관성이 보장됨 (보통 N = 3, W = R = 2)
• W + R <= N : 강한 일관성이 보장되지 않음

 

일관성 모델

일관성 모델은 키-값 저장소를 설계할 때 고려해야 할 또 하나의 중요한 요소 -> 데이터 일관성의 수준 결정

• 강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환
  • 클라이언트는 절대 낡은(out-of-date) 데이터를 보지 못함
• 약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
• 최종 일관성 : 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(즉, 동기화) 되는 모델
  • 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨어질 수 있는데, 이 문제는 클라이언트가 해결해야 한다.
  • 클라이언트 측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 하는 기법 적용 필요(아래에서 설명)

 

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

데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성은 높아진다.

그러한 문제를 해결하기 위해 버저닝과 벡터 시계 기법을 사용할 수 있다.

- 버저닝: 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미

 

서버 1과 서버 2에 동일한 데이터 사본이 저장되어 있다고 가정하자.

이때 서버 1과 서버 2에서 각각 다른 데이터를 저장하려고 한다면 서로 충돌하는 두 값을 갖게 된다.

그리고 그 버전을 각각 v1, v2 라고 하자.

이렇게 v1 과 v2 간에 충돌이 발생하게 되는데, 이를 발견하고 자동으로 해결할 수 있는 버저닝 시스템이 필요하다.

그리고 벡터 시계는 이런 문제를 푸는데 보편적으로 사용되는 기술이다.

 

벡터 시계: [서버, 버전] 의 순서쌍을 데이터에 매단 것 -> 어떤 버전이 선행/후행 버전인지, 충돌이 있는지 판별

e.g) D([s1, v1], [s2, v2] ..., [sn, vn])

 

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

• [Si, Vi] 가 있으면 Vi 를 증가
• 그렇지 않으면 새 항목 [Si, 1] 를 생성

 

5번 단계에서, 어떤 클라이언트가 D3, D4 를 읽으면 데이터 간 충돌이 있다는 걸 알게 된다. (충돌 감지는 뒤에서 설명)

D2 를 Sy 와 Sz 가 각기 다른 값으로 바꾸었기 때문이다. 이렇게 충돌이 발생한 경우 클라이언트가 해소한 후 서버에 기록한다. 이러한 쓰기 연산을 처리한 서버가 Sx 였다고 할 때, 벡터 시계는 D5([Sx, 3], [Sy, 1], [Sz, 1]) 로 바뀌게 된다.

 

버전 X 가 버전 Y 의 이전 버전인지 확인하려면,

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

• e.g) D([S0, 1], [S1, 1]) 은 D([S0, 1], [S1, 2]) 의 이전 버전이다. -> 이런 경우 두 데이터 사이 충돌은 없음

 

버전 X 와 버전 Y 사이에 충돌이 있는지 보려면(두 버전이 같은 이전 버전에서 파생된 다른 버전인지 보려면)

Y의 벡터 시계 구성요소 가운데, X 의 벡터 시계 동일 서버 구성요소보다 작은 값을 갖는 것이 있는지 보면 된다.

• e.g) D([S0, 1], [S1, 2]), D([S0, 2], [S1, 1]) 은 서로 충돌한다.

 

벡터 시계를 사용해 충돌을 감지하고 해소하는 방법의 단점

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

 

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

• 임계치를 설정해 그 이상으로 길어지는 경우 오래된 순서쌍을 벡터 시계에서 제거해야 하는데, 그러면 버전 간 선후 관계가 불분명해질 수 있어 충돌 해소 과정의 효율성이 낮아짐

 

장애 감지

분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 특정 서버의 장애를 보고해야 해당 서버에 실제로 장애가 발생했다고 간주. 다음의 두 방식을 사용해서 파악할 수 있다.

 

멀티 캐스팅

다음 그림과 같이 모든 노드 사이에 멀티캐스팅 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법이다.

하지만 서버가 많을 때는 비효율적임

 

가십 프로토콜

분산형 장애 감지 솔루션으로, 서버가 많을 때도 효율적으로 동작

멤버십 목록: 각 멤버의 ID 와 하트비트 카운터를 저장하고 있는 목록

동작 원리

• 각 노드는 멤버십 목록을 가지고 있으며, 주기적으로 자신의 하트비트를 증가시킨다.
• 각 노드는 무작위로 선정된 노드들에게 주기적으로 자신의 하트비트 카운터 목록을 보낸다.
• 하트비트 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신한다.
• 특정 멤버의 하트비트 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애(offline) 상태인 것으로 간주

 

장애 처리

일시적 장애 처리

가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해 다음과 같은 필요한 조치를 해야 한다.

 

1) 엄격한 정족수 (Strict Quorum)

• 읽기와 쓰기 연산 모두 금지

 

2) 느슨한 정족수 (Sloppy Quorum)

• 장애 서버를 대신해 쓰기 연산을 대신할 w 개의 서버와, R 개의 서버를 고른다.
• 쓰기 연산을 대신한 서버에는 hint 를 남겨두어 장애 서버가 복구되었을 때 일괄 반영하여 데이터 일관성을 보존한다.
  • 단서 후 임시 위탁 기법(hinted handoff) 이라고 부른다.

 

영구 장애 처리

반-엔트로피 프로토콜을 구현하여 사본들을 동기화 해야한다. 해당 프로토콜은 사본들을 비교해 최신 버전으로 갱신하는 과정을 포함한다.

사본 간 일관성이 망가진 상태를 탐지하고, 전송 데이터의 양을 줄이기 위해서는 머클 트리(해시 트리)를 사용할 수 있다.

 

해시 트리

각 노드에 자식 노드들에 보관된 값의 해시값, 또는 자식 노드들의 레이블로부터 계산된 해시값을 레이블로 붙여두는 트리

(아래 그림에서는 일관성이 망가진 데이터가 위치한 상자를 빨간 색으로 표시함)

 

1단계: 키 공간을 버킷으로 분리

 

2단계: 버킷에 포함된 각각의 키에 균등 분포 해시 함수 적용해 해시 값 계산

 

3단계: 버킷 별로 해시값을 계산 후, 해당 해시 값을 레이블로 갖는 노드 생성

 

4단계: 자식 노드의 레이블로부터 새로운 해시 값을 계산해 이진 트리를 상향식으로 구성

 

이후 두 해시 트리의 비교는 루트 노드의 해시값을 비교하는 것으로 시작한다.

루트 노드의 해시 값이 일치한다면 두 서버는 같은 데이터를 갖는 것!

값이 다른 경우 왼쪽 자식, 오른쪽 자식 순으로 노드의 해시 값을 비교하고, 아래 쪽으로 계속 탐색해 나가며 다른 데이터를 갖는 버킷을 찾아 그 버킷들만 동기화한다.

-> 동기화해야 하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터의 총량과는 무관

 

하지만 실제로 쓰이는 시스템의 경우 버킷 하나의 크기가 꽤 클 수 있음을 환기하자.

 

 

데이터 센터 장애 처리

정전, 네트워크 장애, 자연 재해 등으로 한 데이터 센터 전체에 장애가 발생할 수 있으므로, 여러 데이터 센터에 다중화 해두어야 한다.

 

 

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

최종적으로 설계한 키-값 저장소 아키텍처 다이어그램을 다음과 같이 나타낼 수 있다.

• 클라이언트는 get(key), put(key, value) 와 통신
• 중재자는 클라이언트에게 키-값 저장소에 대한 프록시 역할 제공
• 노드는 안정 해시의 해시 링 위에 분포
• 노드를 자동으로 추가/삭제가 가능한 완전히 분산된 시스템
• 데이터는 여러 노드에 다중화된다.
• 모든 노드가 같은 책임을 지므로 SPOF 가 존재하지 않음

완전히 분산된 설계를 채택하였으므로, 모든 노드는 아래 제시된 모든 기능을 지원해야 함

 

쓰기 경로

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

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

3. 메모리 캐시가 임계치에 도달하면 데이터는 디스크에 있는 SSTable 에 기록된다.

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

 

 

읽기 경로

1. 데이터가 메모리에 있는지 검사. 있으면 바로 응답, 없으면 2번 수행

2. 블룸 필터를 검사한다.

3. 블룸 필터를 통해 어떤 SSTable 에 키가 보관되어 있는지 알아낸다.

4. SSTable 에서 데이터를 가져온다.

5. 해당 데이터를 클라이언트에게 반환한다. 

 

 

블룸 필터

N 비트 크기의 비트 배열과, J 개의 해시 함수를 사용해 구현

3 개의 해시 함수를 사용한다고 가정할 때, 

1. 특정 값을 해시 함수 f(x), g(x), h(x) 를 사용해 각 해싱값에 해당하는 인덱스의 비트값을 1로 수정

2. 이후 w 라는 값이 저장되어 있는 곳을 찾기 위해 마찬가지로 f(w), g(w), h(w) 의 해싱값을 구함

3. 해당 해싱값에 해당하는 인덱스의 비트값이 모두 1이면 이전에 저장된 값으로 인식

 

특징: 부정확한 결과를 가질 수도 있음

• False Negative(존재하는데 존재하지 않는다고 여기는 것) 는 불가능
• False Positive(존재하지 않는데 존재한다고 여기는 것) 은 가능

 

사용 예

• IP 블랙리스트 관리