6. 키-값 저장소 설계
Last updated
Last updated
키-값 저장소(Key-Value Store)는 키-값 데이터베이스라고도 불리는 비 관계형(non-relational) 데이터베이스이다.
저장소에 저장되는 값은 고유 식별자(identifier)를 키로 가져야 한다.
키와 값 사이의 이런 연결 관계를 키-값 쌍(key-value pair)라고 한다.
키-값 쌍에서 키는 유일해야 하며, 해당 키에 매달린 값은 키를 통해서만 접근할 수 있다.
키는 일반 텍스트, 해시 값 등일 수 있다. 값을 구분할 수 있는 키면 된다.
키는 짧을 수록 좋다.
값은 문자열, 리스트(List), 딕셔너리(Dictionary), 객체(Object) 등이고, 값으로 무엇이 오든지 상관없다.
, , 등이 있다.
완벽한 설계란 없다. 읽기, 쓰기 그리고 메모리 사용량 사이에 어떤 균형을 맞추고, 데이터의 일관성과 가용성 사이에서 타협적 결정을 내려야 한다.
키-값 상의 크기는 10KB 이하이다.
큰 데이터를 저장할 수 있어야 한다.
높은 가용성을 제공해야 한다. 따라서 시스템은 설사 장애가 있더라도 빨리 응답해야 한다.
높은 규모 확장성을 제공해야 한다. 따라서 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 한다.
데이터의 일관성 수준은 조정이 가능해야 한다.
응답 지연시간(Latency)이 짧아야 한다.
한 대의 서버만 사용하는 키-값 저장소를 설계하는 것은 쉽다.
가장 직관적인 방법은 키-값 전부를 메모리에 해시 테이블로 저장하는 것이다.
이 접근법은 빠른 속도를 보장하긴 하지만 모든 데이터를 메모리 안에 두는 것이 불가능할 수 있다.
데이터 압축(Compression)
자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장
분산 해시 테이블이라고도 불린다.
분산 시스템을 설계할 떄는 CAP 정리(Consistency, Availability, Partition tolerance theorem)을 이해하고 있어야 한다.
데이터 일관성(Consistency), 가용성(Availability), 파티션 감내(Partition tolerance)를 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하는 정리이다.
어떤 두가지를 충족하려면 나머지 하나는 반드시 희생되어야 하는 것을 의미한다.
시스템에 맞는 요구사항을 파악하고 CAP 정리를 적용해야 한다.
분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다.
분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다.
네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다.
일관성과 파티션 감내를 지원, 가용성을 희생한다.
장애가 발생한다면, 각 노드 별로 생기는 데이터 불일치 문제를 해결하기 위해서 노드 별 쓰기 연산을 중단해야 한다.
은행권 시스템은 보통 데이터 일관성을 양보하지 않는다.
가용성과 파티션 감내를 지원, 데이터 일관성을 희생한다.
장애가 발생한다면, 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용해야 한다.
장애가 나는 노드 외에 다른 노드들에 쓰기 연산을 허용하고, 파티션 문제가 해결된 이후에 데이터를 장애가 났던 노드 쪽으로 전송할 것이다.
일관성과 가용성을 지원, 파티션 감내를 지원하지 않는다.
네트워크 장애는 피할 수 없는 일로 여겨지므로, 분산 시스템에서 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다.
실세계에서 CA 시스템은 존재하지 않는다.
대규모 애플리케이션의 경우, 전체 데이터를 한 대의 서버에 욱여넣는 것은 불가능하다.
가장 단순한 해결책은 데이터를 작은 파티션으로 분할한 다음 여러 대의 서버에 저장하는 것이다.
데이터를 여러 서버에 고르게 분산할 수 있는가
노드가 추가되거나 삭제될 때 데이터의 이동을 최소화 할 수 있는가
데이터 파티션 문제를 해결할 때 적합한 방법
규모 확장 자동화(autometic scaling): 시스템의 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있다.
다양성(heterogeneity): 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다.
높은 가용성과 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화할 필요가 있다. (N은 튜닝이 가능한 값)
N개의 서버를 선정하는 방법은 어떤 키를 해시 링에 배치한 후, 그 지점으로부터 시계 방향으로 링을 순회하면서 만나는 첫 N개 서버에 데이터 사본을 저장하는 것이다.
가상 노드를 사용한다면, N개의 노드가 대응될 실제 물리 서버의 개수가 N보다 작아질 수 있다. 이럴 때는 노드를 선택할 때 같은 물리서버를 중복으로 선택하지 않도록 해야 한다.
여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 한다.
정족수의 합(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.
강한 일관성
모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 클라이언트는 절대로 낡은(Out-of-date) 데이터를 보지 못한다.
모든 사본이 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것
약한 일관성
읽기 연산은 가장 최근에 갱신한 결과를 반환하지 못할 수 있다.
최종 일관성
약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영되는 모델이다.
데이터를 다중화하면 가용성은 높아지지만, 사본 간 일관성이 깨질 가능성은 높아진다.
데이터 버저닝과 벡터 시계는 그 문제를 해소하기 위하여 등장한 기술이다.
버저닝은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미한다.
각 버전의 데이터는 변경 불가능(Immutable)하다.
벡터 시계는 *[서버, 버전]*의 순서쌍을 데이터에 기록한 것이다.
버전의 선후 여부, 다른 버전과의 충돌 여부를 판단하기 위해 사용한다.
어떤 버전 X가 버전 Y의 이전 버전인지(따라서 충돌이 없는 지) 쉽게 판단할 수 있습니다. 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 모든 구성요소 값보다 같거나 큰지만 확인하면 된다.
단점
충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로, 클라이언트 구현이 복잡해진다.
벡터 시계에서 *[서버: 버전]*의 순서쌍 개수가 빠르게 늘어나는데, 이 경우를 해소하려면 길이에 임계치를 설정하고 임계치 이상으로 길어진다면, 오래된 순서쌍부터 벡터 시계에서 제거하도록 해야 한다. 해당 방법으로 해소하는 경우, 버전 간 선후 관계가 정확하게 결정될 수 없기 때문에 충돌 해소 과정의 효율성이 낮아진다.
분산 시스템에서는 보통 두 대 이상의 서버가 똑같은 장애를 겪어야 해당 서버에 실제로 장애가 발생하였다고 간주한다.
모든 노드 사이에 멀티케스팅(Multicasting) 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법이다. 이 방법은 N:N 연결이기 때문에 서버가 많은 경우 비효율적이다.
가십 프로토콜(Gossip protocol) 같은 분산형 장애 감지(decentralized failure detection) 솔루션을 채택하는 것이 보다 효율적이다.
각 노드는 멤버십 목록을 유지한다. 멤버십 목록은 각 멤버 ID와 Heartbeat Counter 쌍의 목록이다.
각 노드는 주기적으로 자신의 Heartbeat Counter를 증가시킨다.
각 노드는 무작위로 선정된 노드들에게 주기적으로 자신의 Heartbeat Counter 목록을 보낸다.
Heartbeat Counter 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신한다.
어떤 멤버의 Heartbeat Counter 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애(offline) 상태인 것으로 간주된다.
가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해 필요한 조치를 해야 한다.
엄격한 정족수(Strict quorum) 혹은 느슨한 정족수(Sloppy quorum) 접근법을 선택하여 장애처리한다. 엄격한 정족수의 경우 읽기와 쓰기 연산을 금지시켜서 데이터 일관성을 보장하고, 느슨한 정족수는 장애가 일어나지 않은 건강한 서버에서 데이터를 가져와 가용성을 보장한다.
네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버에서 잠시 맡아 처리한다. 그동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영하여 데이터 일관성을 보존한다. 이를 위해 임시로 쓰기 연산을 처리한 서버에는 그와 관련된 단서를 남겨둔다. 이와 같은 장애 처리 방안을 단서 후 임시 위탁(Hinted Handoff) 기법이라고 한다.
영구적인 노드의 장애 상태 처리를 위해서 반-엔트로피(anti-entropy) 프로토콜을 구현하여 사본들을 동기화한다.
반-엔트로피 프로토콜은 사본들을 비교하여 최신버전으로 갱신하는 과정을 포함한다.
사본간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서 머클(Merkle) 트리를 사용한다.
해시 트리라고도 불리는 머클 트리는 각 노드에 그 자식 노드들에 보관된 값의 해시, 또는 자식 노드들의 레이블로부터 계산된 해시값을 레이블로 붇여두는 트리이다.
대규모의 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증할 수 있다.
머클트리를 사용하면 동기화해야 하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터의 총량과는 무관해진다.
실제로 쓰이는 시스템의 경우, 버킷 하나의 크기가 꽤 크다는 것을 인지해야 한다.
머클트리 계산 과정
키 공간을 버킷(임의의 영역)으로 나눈다.
버킷에 포함된 각각의 키에 균등 분포 해시 함수를 적용하여 해시 값을 계산한다.
버킷별로 해시값을 계산한 후, 해당 해시 값을 레이블로 갖는 노드를 만든다.
자식 노드의 레이블로부터 새로운 해시 값을 계산하여, 이진 트리를 상향식으로 구성해 나간다.
머클트리 비교
두 서버의 루트 노드의 해시 값이 일치한다면 두 서버는 같은 데이터를 갖고 있는 것이다.
값이 다른 경우, 자식 노드의 해시 값을 비교하며 다른 값을 갖는 버킷을 찾는다.
값이 다른 버킷들을 정리 후, 해당 버킷들만 동기화한다.
정전, 네트워크 장애, 자연재해 등 다양한 이유로 발생할 수 있다.
데이터 센터 장애에 대응할 수 있는 시스템을 만드려면, 데이터를 여러 데이터 센터에 다중화하는 것이 주용하다.
한 데이터 센터가 완전히 망가져도 사용자는 다른 데이터 센터에 보관된 데이터를 이용할 수 있을 것이다.
클라이언트는 키-값 저장소가 제공하는 두가지 단순한 API, 즉 GET(key), PUT(key, value)와 통신한다.
중재자(Coordinator)는 클라이언트에게 키-값 저장소에 대한 프록시 역할을 하는 노드이다.
노드는 안정 해시의 해시 링 위에 분포한다.
노드를 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산된다.
데이터는 여러 노드에 다중화된다.
모든 노드의 같은 책임을 지므로, SPOF(Single Point of Failure)는 존재하지 않는다.
쓰기 요청이 커밋 로그 파일에 기록된다.
데이터가 메모리 캐시에 기록된다.
읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는 지부터 살핀다.
블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는 지를 알아낸다.
SSTable에서 데이터를 가져온다.
해당 데이터를 클라이언트에게 반환한다.
메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 에 기록된다.
데이터가 메모리에 없으므로 를 검사한다.