개요
키-값 저장소는 키-값 데이터베이스라고도 불리는 비관계형 데이터베이스이다. 저장되는 값은 고유 식별자(identifier)를 키 값으로 가져야 하고, 키에 묶인 값은 키를 통해서만 접근할 수 있다.
키는 일반 텍스트일수도 있고 해시 값일수도 있는데, 성능상의 이유로 키는 짧을수록 좋다.
•
일반 텍스트 키 : “last_logged_in_at”
•
해시 키 : 253DDEC4
키에 묶이는 값은 문자열일수도 있고 리스트나 객체일수도 있다. 키-값 저장소로 널리 알려진 것은 아마존 DynamoDB, memached, Redis 등이 있다.
키-값 저장소
키-값 저장소에 대해 알아보고 키 값 저장소를 설계해보자. 키-값 저장소에서 주요 연산은 다음 두 가지이다.
•
put(key, value) : 키-값 저장소에 저장한다
•
get(key) : 키를 통해 값을 조회한다.
문제 이해 및 설계 범위 확정
읽기, 쓰기, 메모리 사용량 사이에서 균형을 찾고, 데이터의 일관성과 가용성 사이에서 타협적 결정(tradeoff)을 내린 설계를 내리는 것이 중요하다.
이번 장에서는 다음과 같은 특성을 가지는 키-값 저장소를 설계해볼 것이다.
•
키-값 쌍의 크기는 10KB 이하
•
큰 데이터를 저장할 수 있어야 함
•
높은 가용성, 장애가 있어도 시스템은 빠르게 응답
•
높은 규모 확장성, 트패릭에 따라 자동 증설/삭제
•
조정 가능한 데이터 일관성 수준
•
짧은 응답 지연시간(latency)
단일 서버 키-값 저장소
한 대의 서버만 사용하는 키-값 저장소를 설계하는 직관적인 방법은, 키-값 쌍을 전부 메모리에 해시 테이블로 저장하는 것이다.
이 방법은 빠른 속도를 보장하지만 모든 데이터를 메모리에 두는 것이 불가능할 수 있다는 한계가 있다. 이를 해결하기 위해 데이터를 압축하거나 디스크에 저장하고 자주 쓰이는 데이터만 메모리에 두는 방법이 있다.
하지만 이렇게 개선하더라도 한 대의 서버로는 감당하기 어려운 순간이 올 수 있다. 더 많은 데이터를 저장하는 방법은 분산 키-값 저장소를 만드는 것이다.
분산 키-값 저장소
분산 키-값 저장소는 분산 해시 테이블이라고도 불리는데, 키-값 쌍을 여러 서버에 분산시켜 저장한다.
CAP 정리
CAP 정리는 데이터 일관성(Consistency), 가용성(Availability), 파티션 감내(Partition tolerence)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리이다.
•
데이터 일관성 : 분산 시스템에 접속하는 모든 클리언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 봐야한다.
•
가용성 : 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야한다.
•
파티션 감내 : 두 노드 사이에 통신 장애가 발생하더라도 시스템은 계속 동작해야한다.
CAP 정리는 위 세 가지 요구사항 중 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다는 의미이다. 따라서 아래와 같이 세 요구사항 중 두 가지를 만족하는 시스템으로 분류할 수 있다.
•
CP 시스템 : 일관성과 파티션 감내를 지원하고 가용성을 희생한다.
•
AP 시스템 : 가용성과 파티션 감내를 지원하고 데이터 일관성을 희생한다.
•
CA 시스템 : 일관성과 가용성을 지원하고 파티션 감내를 희생한다. 통상 네트워크 장애는 피할 수 없으므로, 분산 시스템은 반드시 파티션 감내를 지원해야하기 때문에 실세계에서 CA 시스템은 존재하지 않는다.
몇 가지 구체적인 사례를 통해 이해해보자.
분산 시스템에서는 데이터를 여러 노드에 복제해 보관하는데, 3대의 복제 노드 n1, n2, n3에 데이터를 보관하는 상황은 다음과 같을 것이다.
이상적인 환경이라면 파티션(네트워크 통신 장애)이 발생하지 않으므로, n1에 기록된 데이터가 자동으로 n2와 n3에 복제되어 데이터 일관성과 가용성을 만족한다.
하지만 분산 시스템은 파티션 문제를 피할 수 없기 때문에, 파티션이 발생하면 우리는 일관성과 가용성 중 한 가지를 선택해야한다.
위 그림처럼 n3에 장애가 발생해 n1, n2와 통신할 수 없는 상황이라면,
•
n1 또는 n2에 기록한 데이터는 n3에 전달되지 않거나
•
n3에 기록되었으나 n1 혹은 n2에 전달되지 않은 데이터가 있을 수 있다.
이러한 상황에서 가용성 대신 일관성을 선택한다면(CP 시스템), 세 서버 사이에 생길 수 있는 데이터 불일치를 피하기 위해 n1과 n2에 쓰기 연산을 중단 시켜야 하고 그러면 가용성이 깨지게 된다. 보통 은행권 시스템은 데이터 일관성을 양보하지 않기 때문에 장애가 발생하면 모든 쓰기를 중단하는 CP 시스템을 선택한다.
하지만 일관성 대신 가용성을 선택한다면(AP 시스템), 최신화 되지 못한 데이터를 반환하더라도 계속 읽기 연산을 허용한다. 추후 파티션 문제가 해결된 뒤에 새 데이터를 n3에 전달하여 일관성 문제를 해결한다.
분산 키-값 저장소를 설계할 때는 요구사항에 맞춰 CAP 정리를 적용해야한다. 면접관과 상의하고 결론에 따라 시스템을 설계하자.
시스템 컴포넌트
키-값 저장소 구현에 사용될 핵심 컴포넌트 및 기술들을 알아보자.
•
데이터 파티션
•
데이터 다중화(replication)
•
일관성(consistency)
•
일관성 불일치 해소(inconsistency resolution)
•
장애 처리
•
시스템 아키텍처 다이어그램
•
쓰기 경로(write path)
•
읽기 경로(read path)
여기서 다루는 내용은 DynamoDB, Cassandra, BigTable의 사례를 참고한 내용들이다.
데이터 파티션
대규모 애플리케이션에서는 전체 데이터를 한 대의 서버에 모두 저장하는 것은 불가능한데, 이에 대한 가장 단순한 해결책으로 데이터를 파티션들로 분할하여 여러 서버에 저장하는 방법이 있다.
데이터를 파이션 단위로 나눌 때에는 다음 두 가지 문제를 중요하게 따질 필요가 있다.
•
데이터를 여러 서버에 고르게 분산할 수 있는가(균등 분포)
•
노드가 추가되거나 삭제될 때 데이터 재배치를 최소화할 수 있는가
위 문제를 안정 해시(consistent hash) 알고리즘으로 해결할 수 있다.
안정해시를 사용하여 데이터를 파티션하면 다음과 같은 이점이 있다.
•
규모 확장 자동화 : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 잇다.
•
다양성 : 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다.
데이터 다중화
높은 가용성과 안정성을 확보하기 위해 데이터를 여러 서버에 비동기적으로 다중화(replication)할 필요가 있다. 어떤 키를 해시 링 위에 배치 후, 그 지점부터 시계 방향으로 링을 순회하면서 만나는 N개의 서버에 데이터 사본을 보관하여 다중화한다.
위 그림에서 N=3으로 설정한다면 key0는 s1, s2, s3에 저장된다.
만약 가상노드를 사용한다면, N개의 서버를 선택할 때 실제 물리 서버의 개수가 N보다 작아지는 경우가 생길 수 있다. 이 문제를 피하려면 노드를 선택할 때 물리 서버를 중복 선택하지 않도록 해야한다.
데이터일관성
여러 노드에 다중화된 데이터는 적절히 동기화 되어야한다. 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.
•
N = 데이터 사본 개수
•
W = 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산에 성공했다는 응답을 받아야 함
•
R = 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 읽기 연산에 성공했다는 응답을 받아야 함
W = 1의 의미는 데이터가 한 대의 서버에만 기록된다는 것이 아니고, 중재자가 서버 중 쓰기 연산이 성공했다는 응답을 최소 한 개 이상 받아야 쓰기 연산에 성공했다고 판단한다는 의미이다. 중재자는 s1에서 성공 응답을 받으면 s0과 s2에서 응답을 기다릴 필요가 없다. 이처럼 중재자는 클라이언트와 노드 사이에서 프록시 역할을 한다.
W, R, N의 값을 결정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정이다. W = 1 또는 R = 1인 구성은 한 대의 서버에서만 응답을 받으면 되니 응답 속도가 빠를 것이다. 반대로 W나 R이 전체 서버의 수와 동일하다면 데이터 일관성이 완벽히 지켜지겠지만 가장 느린 서버로부터 응답을 기다려야 하므로 응답 속도도 느려질 것이다. W + R > N인 경우, 일관성을 보증할 최신 데이터를 가진 노드가 최소 하나는 겹칠 것이므로 강한 일관성이 보장된다.
•
R = 1, W = N : 빠른 읽기 연산에 최적화된 시스템
•
W = 1, R = N : 빠른 쓰기 연산에 최적화된 시스템
•
W + R > N : 강한 일관성이 보장됨(보통 N = 3, W = R = 2)
•
W + R ≤ N : 강한 일관성이 보장되지 않음
위 상황에 맞춰 W, R, N의 값을 조정하면 된다.
일관성 모델은 키-값 저장소를 설계할 때 고려해야할 중요한 요소 중 하나이다.
•
강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다.
•
약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
•
결과적 일관성 : 약한 일관성의 한 형태로, 갱신 결과가 결국 모든 사본에 동기화(반영)되는 모델이다.
강한 일관성을 달성하는 일반적인 방법은, 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것이다. DynamoDB나 카산드라의 경우 결과적 일관성 모델을 택하고 있는데, 쓰기 연산이 병렬적으로 발생하면 시스템의 일관성이 깨질 수 있다. 이 문제는 데이터의 버전 정보를 통해 깨진 데이터를 읽지 않도록 하는 등 클라이언트에서 해결해야 한다.
다중화를 통해 가용성이 높아질수록 데이터 일관성이 깨질 가능성이 높아진다. 버저닝(versioning)과 벡터 시계(vector clock)를 통해 문제를 해결할 수 있다.
서버에 john이라는 값이 저장되어 있을 때,
위처럼 각각 다른 서버에서 동시에 수정을 시도한다면 충돌하는 두 값을 갖게 될 것이다. 이 버전을 각각 v1과 v2라고 하면, v1과 v2의 충돌을 발견하고 자동으로 해결해 낼 버저닝 시스템이 필요하다.
버저닝은 데이터를 변경할 때마다 변경 불가능한 새로운 버전을 만드는 것이고, 벡터 시계는 [서버, 버전]의 순서쌍을 데이터데 매달아두는 것이다. 이를 통해 어떤 버전이 선행인지, 후행인지, 다른 버전과 충돌이 있는지를 판별할 수 있다.
벡터 시계는 D([s1, v1], [s2, v2], …, [sn, vn])와 같이 표현되고, 여기서 D는 데이터, vi는 버전 카운터, si는 서버 번호이다. 데이터를 si 서버에 기록할 때, [si, vi]가 있다면 vi를 증가시키고 그렇지 않다면 [si, 1]을 새항목으로 만든다.
벡터 시계를 사용하면 어떤 버전 X가 버전 Y의 이전 버전인지, 충돌이 있는지를 쉽게 판단할 수 있다. 버전 Y에 포함된 모든 구성요소의 값이 버전 X에 포함된 모든 구성요소 값보다 같거나 큰지만 보면 된다. 예를 들면 D([s0, s1], [s1, 1])은 D([s0, 1], [s1, 2])의 이전 버전임을 알 수 있다. 반대로 D([s0, 1], [s1, 2])와 D([s0, 2], [s1, 1])는 서로 충돌한다는 것을 알 수 있다.
이러한 벡터 시계는 두 가지 단점을 가지고 있다.
첫 번째로는 충돌 감지 및 해소 로직이 클라이언트에 포함되어야해서 클라이언트 구현이 복잡해진다는 점이다.
두 번째로는 [서버:버전]의 순서쌍이 굉장히 빠르게 늘어난다는 점이다. 이 문제를 해결하려면 임계치를 설정하고, 임계치 이상으로 길어지면 오래된 순서쌍을 제거해야한다. 하지만 이렇게 하면 충돌 해소의 효율성이 낮아지게 된다.(Dynamo 관계 문헌에 따르면 실제 서비스 중 그런 문제 발생한 적 없다고 한다)
장애 처리
대규모 시스템에서의 장애는 아주 흔하게 벌어지는 사건인데, 따라서 장애를 어떻게 처리할 것이냐는 중요한 문제이다.
분산 시스템에서 장애 감지는 그저 한 대의 서버가 죽었다고해서 장애처리 하지 않고, 두 대 이상의 서버가 동일한 장애를 보고해야 실제 장애가 발생했다고 간주한다.
위 그림처럼 모든 노드 사이에 멀티캐스팅 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법이다. 하지만 이 방식은 서버가 많아진다면 비효율적이기 때문에, 가십 프로토콜(gossip protocol)과 같은 분산형 장애 감지 솔루션을 채택하는 것이 효율적이다.
가십 프로토콜의 동작 원리는 다음과 같다.
•
각 노드가 멤버 ID와 박동 카운터(heartbeat count)의 쌍인 멤버십 목록(membership list)를 유지
•
각 노드는 주기적으로 자신의 박동 카운터 증가
•
각 노드는 무작위로 선정된 도드들에게 주기적으로 자기 박동 카운터 목록을 전송
•
박동 카운터 목록을 받은 노드는 최신 값으로 갱신
•
특정 멤버의 박동 카운터 값이 일정 시간동안 갱신되지 않으면 해당 멤버를 장애(offline) 상태로 간주
위 그림에서는 s2의 박동 카운터가 오랫동안 증가되지 않았음을 발견하고, 다른 무작위의 노드에 박동 카운터 목록을 전달한다. 이를 또다시 전파하여 모든 노드에서 s2 노드를 장애 노드로 표시하게 된다.
가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해 조치를 취해야 한다.
엄격한 정족수 접근법을 쓴다면, 데이터 일관성을 유지하기 위해 읽기와 쓰기 연산을 금지하게 될 것이다. 느슨한 정족수 접근법을 쓴다면, 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 골라 처리한다.
네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리하고, 이후 장애 서버가 복구 되었을 때 일괄 반영하여 데이터 일관성을 보존한다. 이를 위해 임시로 쓰기 연산을 처리한 서버에는 그에 대한 단서(hint)를 남겨둔다. 이 방법을 임시 위한(hinted handoff) 기법이라 부른다.
영구적인 노드의 장애 상태를 처리하기 위해서는 반-엔트로피(anit-entropy) 프로토콜을 구현하여 사본들을 동기화한다. 반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는데, 일관성이 깨진 감지하고 전송 데이터 양을 줄이기 위해 머클 트리를 사용한다.
해시 트리(hash tree)라고도 불리는 머클 트리는 각 노드에 자식 노드들에 보관된 값의 해시를 붙여두는 트리이다. 해시 트리를 사용하면 대규모 자료 구조의 내용을 효과적이면서 보안상 안정한 방법으로 검증할 수 있다.
키 공간이 1부터 12까지인 머클트리는 먼저 위와 같이 키 공간을 4개의 버킷으로 나누고, 버킷에 포함된 각각의 키에 균등 분포 해시 함수를 적용하여 해시 값을 계산한다.
버킷별로 계산된 해시값을 레이블로 갖는 노드를 만들고,
자식 노드의 레이블로부터 새로운 해시값을 계산하여 상향식으로 이진 트리를 구성해 나간다.
위의 두 머클 트리 비교는 루트 노드의 해시값을 비교하는 것부터 시작하여, 해시값이 다른 데이터를 갖는 버킷을 찾아나아가 해당 버킷들만 동기화한다. 이러한 방식 때문에 머클 트리를 사용하여 동기화하면, 동기화하는 데이터의 양은 두 서버에 보관된 데이터 총량과는 무관하게 실제 존재하는 버킷의 크기에 따라서만 달라진다.
데이터 센터의 장애는 정전, 네트워크 장애, 자연재해 등의 다양한 이유로 발생할 수 있다. 때문에 데이터 센터의 장애에 대응할 수 있는 시스템을 만들기 위해서는 데이터를 여러 데이터 센터에 다중화하는 것이 중요하다. 한 데이터 센터가 망가지더라도 다른 데이터 센터를 통해 데이터를 이용할 수 있게 하는 것이다.
시스템 아키텍처 다이어그램
키-값 저장소의 아키텍처를 이해하고 아키텍처 다이어그램을 만들어보자.
•
클라이언트는 키-값 저장소의 get(key)와 put(key, value) API로 통신한다.
•
중재자(coordinator)는 클라이언트에게 키-값 저장소에 대한 프록시 역할을 한다.
•
노드는 안정 해시의 해시 링 위에 분포한다.
•
노드를 자동으로 추가하거나 삭제할 수 있도록 시스템은 완전히 분산된다.
•
데이터는 여러 노드에 다중화된다.
•
모든 노드가 같은 책임을 지므로 SPOF는 존재하지 않는다.
완전히 분산된 설계이므로, 모든 노드는 위 그림의 기능을 전부를 지원해야한다.
쓰기 경로
위 그림은 카산드라에서 쓰기 요청이 특정 노드에 전달되는 과정을 나타낸다. 쓰기 요청이 특정 노드에 전달되면,
1.
커밋 로그 파일에 쓰기 요청을 기록
2.
데이터를 메모리 캐시에 기록
3.
메모리 캐시가 가득차거나 임계치에 도달하면 디스크의 SSTable에 기록
SSTable
Sorted-String Table의 약어로, 키-값 순서쌍을 정렬된 리스트 형태로 관리하는 테이블이다.
읽기 경로
읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지 확인 후, 있다면 해당 데이터를 클라이언트에 반환하고 없다면 디스크의 SSTable에서 가져온다. 여기서 어떤 SSTable에 데이터가 존재하는지는 효율적인 방법이 필요한데, 블룸 필터(Bloom filter)가 흔히 사용된다.
블룸 필터(Bloom filter)
블룸 필터는 Burton Howard Bloom에 의해 고안된 자료구조로, 데이터 집합에 특정 값이 존재하는지 여부만 알 수 있는 자료구조이다.
블룸 필터는 Boolean 테이블과 여러 개의 해시 함수를 사용하는데, 데이터를 넣을 때는 각각의 해시 함수 결과로 얻은 값들에 1을 할당한다.
반데로 데이터를 찾을 때는 모든 해시 값들의 값이 1인지 확인한다. 모든 값이 1이더라도 반드시 존재한다는 의미가 아니라 있을수도 있다는 점을 주의하자.
블룸 필터는 O(k)를 보장하여 가볍고 빠르고 메모리도 적게 쓰지만, 오직 추가만 가능하고 삭제가 불가능하며 결과가 항상 정확하지도 않는다.
