6장 키-값 저장소 설계

•

비 관계형 데이터베이스

•

이 저장소에 저장되는 값은 고유 식별자를 키로 가진다.

•

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

•

성능상의 이유로 키 값은 짧을수록 좋다.

•

put(key, value): 키-값 쌍을 저장소에 저장한다.

•

get(key): 키로 값을 가져온다.

문제 이해 및 설계 범위 확정

•

읽기, 쓰기, 메모리 사용량 사이의 균형과 데이터의 일관성과 가용성 사이 타협적 결정

•

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

•

높은 가용성을 제공해야 한다. 따라서 서버 장애 시에도 서비스가 문제없이 운영되어야 한다.

•

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

•

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

•

응답 지연시간(latency)이 짧아야 한다.

단일 서버 키-값 저장소

•

한 대 서버만 사용하면 모든 데이터를 키-값 형태의 데이터를 메모리에 해시 테이블로 저장하면 된다.

•

빠른 속도와 데이터 정합성을 보장하지만 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다. 메모리는 비싸고 작기때문!

•

그래서 데이터 압축이나 자주 쓰이는 데이터만 메모리에 저장하고 나머지는 디스크에 저장하는 방법이 있다.

•

그러나 단일 서버로는 부족한 때가 결국 찾아오게 되어 있기때문에 분산 키-값 저장소를 만들 필요가 있다!

분산 키-값 저장소

키-값 데이터 쌍을 여러 서버에 분산시킨다.

CAP 정리

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

•

데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했는지에 관계없이 언제나 같은 데이터를 응답받는다.

•

가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생해도 항상 응답을 받는다.

•

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

CAP 를 모두 만족할 수는 없다.

•

CP: 일관성과 파티션 감내를 지원하는 키-값 저장소, 가용성을 희생

•

AP: 가용성과 파티션 감내를 지원하는 키-값 저장소, 일관성을 희생

•

CA: 통상 네트워크 장애는 피할 수 없는 일로 여겨지기때문에 CA 는 없다.

세 대의 복제 노드가 있다.

이상적 상태

네트워크 파티션 없이 n1 에 기록된 데이터는 자동으로 n2 와 n3 에 복제된다. 일관성과 가용성도 만족한다.

실세계의 분산 시스템

파티션 문제를 피할 수 없다. 파티션이 발생하면 일관성과 가용성 중 하나를 선택해야 한다.

•

n3 에 장애가 발생해서 n1 과 n2 에 통신할 수 없는 상황

•

n1과 n2 에 저장한 데이터는 n3 에 전달되지 않고 n3 에 저장되었으나 미처 n1 과 n2 에 복제되지 않은 데이터가 있을 수 있다.

•

CP: 세 서버 사이 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1 과 n2 에 대한 쓰기 연산을 중단한다. 이러면 가용성이 깨진다. 보통 은행권 시스템에서 CP 시스템을 사용한다.

•

AP: 계속 읽기 연산을 허용한다. n3 에만 저장되어 있던 데이터는 n1 과 n2 에서 응답하지 못한다. 쓰기 연산은 계속된다. 그래서 데이터 일관성은 깨지지만 가용성은 챙길 수 있다.

시스템 컴포넌트

•

데이터 파티션

•

데이터 다중화(replication)

•

일관성

•

일관성 불일치 해소

•

장애 처리

•

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

•

쓰기 경로, 읽기 경로

데이터 파티션

•

전체 데이터를 한 대 서버에 넣는 것은 불가능하다.

•

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

•

데이터를 파티션 단위로 나눌 때

◦

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

◦

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

•

고려해야한다.

•

파티션 키로 안정 해시를 사용!

◦

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

◦

다양성: 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다. 고성능 서버는 더 많은 가상 노드를 가질 수 있다.

데이터 다중화

•

높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 다중화해야 한다. 

•

4개의 서버 중 2개의 서버에 비동기적으로 다중화한다고 하면 k1 은 s1 과 s2 에 저장된다.

•

가상 노드를 사용하면 같은 물리 서버를 중복 선택하지 않도록 해야 한다.

•

같은 DC 에 속한 노드는 자연재해 등의 문제를 겪을 수 있으므로 복제는 다른 센터에 보관하고 센터끼리 고속 네트워크로 연결한다.

데이터 일관성

•

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

•

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

•

N=3 일 때

•

W = x 는 중재자가 최소 x 개의 서버로부터 ACK 를 받아야 함

•

x가 1이라면 응답 속도는 빠르겠지만 일관성이 낮아진다.

•

x가 커질수록 일관성은 향상되지만 응답 속도는 저하된다.

•

W+R>N 일 경우 강한 일관성이 보장

•

R=1, W=N 일 경우 빠른 읽기 연산

•

R=N, W=1 일 경우 빠른 쓰기 연산

•

W+R≤N 일 경우 강한 일관성 보장 X

일관성 모델

•

강한 일관성

◦

모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 클라이언트가 절대 낡은 데이터를 보지 못한다.

•

최종 일관성

◦

약한 일관성의 한 형태로 갱신 결과가 결국에는 모든 사본에 반영되는 모델

◦

잘 모르겠다

◦

쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨어질 수 있는데 이 문제는 클라이언트가 해결해야 한다.

◦

클라이언트 측에서 데이터의 버전 정보로 일관성이 깨진 데이터를 읽지 않도록 하는 기법이 있다.

데이터 버저닝

•

버저닝과 벡터 시계로 문제 해소

•

“name”: “eden” 이라는 데이터의 사본이 n1 과 n2 에 저장되어 있을 때

•

서버 1은 chalee 로 바꾸고 서버 2는 kkara 로 동시에 바꾼다.

•

충돌되는 두 값을 갖게 된다.

•

벡터 시계는 [서버, 버전] 의 순서쌍을 데이터로 갖는다. 어떤 버전이 선행인지 판별할 수 있다.

•

벡터 시계에 대해서는 더 공부해보기! 

장애 처리

•

대다수 대규모 시스템에서 장애는 아주 흔하게 벌어진다.

장애 감지

•

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

•

모든 노드 사이에 멀티캐스팅 채널을 구축하는 것이 서버 장애를 감지하는 가장 쉬운 방법이지만 서버가 많을 때 매우 비효율적이다.

•

가십 프로토콜

◦

각 노드는 각 멤버 ID와 박동 카운터 쌍으로 된 멤버십 목록이 있다.

◦

각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다.

◦

각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다.

◦

박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신

◦

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

s1 멤버십 목록

member id	heartbeat counter	time
1	10232	12:00:01
2	10224	12:00:10
3	10237	12:00:30
4	9958	11:57:58

•

흐름

◦

노드 s1 이 노드 s4 의 박동 카운터가 오랫동안 증가되지 않은 것을 발견

◦

노드 s1 은 박동 카운터 목록을 무작위로 다른 노드에게 보냄

◦

노드 s4 의 박동 카운터가 오랫동안 증가되지 않은 것을 발견한 노드들은 모두 해당 노드를 장애로 간주

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

•

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

•

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

•

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

•

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

•

모든 노드가 같은 책임을 지므로, SPOF는 존재하지 않는다.

쓰기 경로

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

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

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

읽기 경로

•

데이터가 메모리 캐시에 있는지 보고 있으면 바로 반환한다.

•

데이터가 메모리에 없으면 디스크에서 가져와야 한다. 찾는 키가 어느 SS Table 에 있는지 알아내기 위한 효율적인 방법은 블룸 필터이다.

데이터가 메모리에 있는지 검사하고 없으면 2로 간다.

데이터가 메모리에 없으므로 블룸 필터를 검사한다.

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

SS Table 에서 데이터를 가져온다.

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

요약

목표/문제	기술
대규모 데이터 저장	안정 해시를 사용해서 서버들에 부하를 분산
읽기 연산에 대한 높은 가용성 보장	데이터를 여러 데이터 센터에 다중화
쓰기 연산에 대한 높은 가용성 보장	버저닝 및 벡터 시계를 사용한 충돌 해소
데이터 파티션	안정 해시
점진적 규모 확장성	안정 해시
다양성	안정 해시
조절 가능한 데이터 일관성	정족수 합의
일시적 장애 처리	느슨한 정족수 프로토콜
영구적 장애 처리	머클 트리
데이터 센터 장애 대응	여러 데이터 센터에 걸친 데이터 다중화