6장: 키-값 저장소 설계

*<가상 면접 사례로 배우는 대규모 시스템 설계 기초> 을 참고하여 작성한 게시물입니다.

키-값 저장소 설계

키-값 저장소는 키-값 데이터베이스라고도 불리는 비관계형 데이터베이스다. 이 저장소에 저장되는 값은 고유 식별자(identifier)를 키로 가져야한다. 키와 값 사이의 이런 연결 관계를 "키-값" 쌍(pair)라고 지칭한다. 키-값 쌍에서의 키는 유일해야하며, 해당 키에 달린 값은 키를 통해서만 접근할 수 있다. 키는 일반 텍스트일 수도 있고 해시 값일수도 있는데, 성능 상의 이유로 키는 짧을 수록 좋다. 값은 문자열일수도, 리스트일수도, 객체(object)일수도 있다. 무슨 값이 오든 상관하지 않는다. 가장 널리 알려진 것으로 Amazon Dynamo, memcached, redis 등이 있다.

put(key, value):키-값 쌍을 저장소에 저장한다.
get(key): 인자로 주어진 키에 매달린 값을 꺼낸다.

이 연산을 지원하는 키-값 저장소를 설계해보자.

문제 이해 및 설계 범위 확정

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

단일 서버 키-값 저장소

가장 직관적인 방법은 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것 그러나 이는 빠른 속도를 보장하기는 해도, 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다는 약점을 가지고 있다. 이를 해결하기 위한 개선책으로는 1)데이터 압축, 2)자주 쓰는 데이터만 메모리에 두고 나머지는 디스크에 저장 이 있다. 그러나 이렇게 해도 한 대 서버로는 부족한 때가 찾아온다. 많은 데이터를 저장하려면 분산 키-값 저장소를 만들 필요가 있다.

분산 키-값 저장소

이는 분산 해시 테이블이라고도 불린다. 분산 시스템을 설게할때는 CAP 정리(Consistency, Availability, Partition Tolerance theorem)을 이해하고 있어야 한다.

• CAP 정리
  • 데이터 일관성(consistency: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다.), 가용성(availability: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.), 파티션 감내(partition tolerance: 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다.)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리다. 이들 가운데 어떤 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다는 것을 의미한다.

키-값 저장소는 앞서 제시한 세가지 요구사항 중 어느 두가지를 만족하느냐에 따라 다음과 같이 분류할 수 있다.

• CP 시스템: 일관성과 파티션 감내를 지원하는 키-값 저장소. 가용성을 희생함.
• AP 시스템: 가용성과 파티션 감내를 지원하는 키-값 저장소. 데이터 일관성을 희생함.
• CA 시스템: 일관성과 가용성을 지원하는 키-값 저장소. 파티션 감내는 지원하지 않는다. 그러나 통상 네트워크 장애는 피할 수 없는 일로 여겨지므로 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다. 따라서 실세계에 CA 시스템은 존재하지 않는다.

예시를 보면 다음과 같다. 분산 시스템에서 데이터는 보통 여러 노드에 복제되어 보관되는데, 세 대의 복제 노드 n1,n2,n3에 데이터를 복제하여 보관한다고 하자. 이상적 환경이라면 네트워크가 파티션되는 상황은 저대로 일어나지 않아서, n1에 기록된 데이터는 자동적으로 n2,n3에 복제되어 데이터 일관성과 가용성도 만족된다. 그러나 실세계의 분산시스템은 파티션 문제를 피할 수 없다. 그리고 파티션 문제가 발생하면 일관성, 가용성 사이 중 하나를 선택해야 한다. n3에 장애가 발생하여 n1, n2와 통신할 수 없다면, 클라이언트가 n1, n2에 기록한 데이터는 n3에 전달되지 않고 n3에 기록되었으나 아직 n1, n2로 전달되지 않은 데이터가 있다면 n1,n2는 오래된 사본을 갖고 있을 것이다.

CP 시스템이라면 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1,n2에 대해 쓰기 연산을 중단시켜야 하는데, 그러면 가용성이 꺠진다. 은행권은 보통 데이터 일관성을 양보하지 않는다. 예로 온라인 뱅킹 시스템이 계좌 최신 정보를 출력하지 못하면 큰 문제일 것이다. 네트워크 파티션 떄문에 일관성이 깨질 수 있는 상황이 발생하면 이런 시스템은 상황 해결시까지 오류를 반환해야 한다.

AP 시스템이라면 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용해야하는데, 아울러 n1, n2는 계속 쓰기 연산을 허용할 것이고, 파티션 문제가 해결된 후에 새 데이터를 n3에 전송할 것이다.

분산 키-값 저장소를 만들 때는 그 요구사항에 맞도록 CAP 정리를 적용해야 한다.

시스템 컴포넌트

구현에 사용될 핵심 컴포넌트 및 기술들이다.

• 데이터 파티션

  • 대규모 어플리케이션의 경우 전체 데이터를 한 대 서버에 욱여넣는 것은 불가능하므로, 가장 단순하게는 데이터를 작은 파티션으로 분할한 다음 여러 대 서버에 저장하는 것이다. 파티션 단위로 나눌 대는 다음 두 가지 문제를 중요히 따져야 하는데, 1)데이터를 여러 서버에 고르게 분산할 수 있는가. 2)노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가. 이때 안정 해시가 이런 문제를 푸는 데 적합하다. 이를 이용하여 데이터를 파티션하면 다음과 같은 장점이 있다. 1)규모 확장 자동화(automatic scailing):시스템 부하에 따라 서버가 자동으로 추가/삭제되도록 할 수 있다. 2)다양성(heteroogeneity):각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다. 즉, 고성능 서버는 더 많은 가상 노드를 갖도록 설정할 수 있다.

• 데이터 다중화(replication)

  • 높은 가용성, 안전성 화보를 위해 데이터를 N개 서버에 비동기적으로 다중화할 필요가 있다. 여기서 N은 튜닝 가능한 값으로, 어떤 키를 해시 링 위에 배치한 후 그 지점으로부터 시계 방향으로 링을 순회하면서 만나는 첫 N개 서버에 데이터 사본을 보관하는 방식으로 서버를 선정한다. 그러나 가상 노드 사용 시 N이 대응할 실제 물리 서버의 개수보다 커질 수 있다. 이를 피하려면 노드 선택 시 같은 물리 서버를 중복 선택하지 않도록 해야한다. 같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등의 문제를 동시에 겪을 가능성이 있으므로 안정성 담보를 위해 데이터 사본은 다른 센터의 서버에 보관, 센터들은 고속 네트워크로 연결해야 한다.

• 일관성(consistency)

  • 여러 노드에 다중화된 데이터는 적절히 동기화가 되어야한다. 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다. N=사본 개수, W=쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야함. R=읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 읽기 연산이 성공했다는 응답을 받아야 함. 인데, W,R,N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 갖는 전형적 과정이다. 이게 적을수록 응답 속도는 빠를 것이고, 클수록 일관성 수준은 향상되지만 응답속도가 느려질 것이다. W+R>N인 경우 강한 일관성이 보장된다.
  • R=1, W=N: 빠른 읽기 연산에 최적화된 시스템
  • W=1, R=N: 빠른 쓰기 연산에 최적화된 시스템
  • W+R>N: 강한 일관성이 보장됨(보통 N=3, W=R=2)
  • W+R<=N: 강한 일관성이 보장되지 않음.
  • 일관성 모델(consistency model)은 데이터 일관성의 수준을 결정하는데, 종류가 다음과 같다. 1)강한 일관성:모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 다시 말해 클라이언트는 절대로 낡은 데이터를 보지 못한다. 2)약한 일관성: 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다. 3)최종 일관성: 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(동기화)되는 모델이다. 강한 일관성에 달성하는 일반적 방법은 모든 사본에 현재 쓰기 연산 결과가 반영되기까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것인데, 고가용성 시스템에는 적합하지 않다. 다이나모, 카산드라 같은 저장소는 최종 일관성 모델을 택하고 있다. 최종 일관성 모델을 따를 경우 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨어질 수 있는데, 이는 클라이언트가 해곃한다. 클라이언트측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 하는 기법은 아래와 같다.(데이터 버저닝)

• 일관성 불일치 해소(inconsistency resolution)

  • 데이터 버저닝. 데이터를 다중화하면 가용성은 높아지나 사본간 일관성이 깨질 가능성이 높아진다. 버저닝(versioning)과 벡터 시계(vector clock)은 그 문제를 해소하기 위해 등장한 기술이다. 버저닝은 데이터 변경시마다 해당 데이터의 새로운 버전을 만드는 것으로, 각 버전의 데이터는 변경 불가능이다. 쓰기 연산으로 인해 v1, v2사이에 다른 값이 일어나 충돌한다고 하자. 원래 값인 v1을 무시할 수 있으나, 두 버전 사이의 충돌은 해소하기 어렵다. 이를 해결하려면 충돌을 발견하고 자동으로 해결해 낼 버저닝 시스템이 필요하다. 벡터 시계는 이를 푸는데 보편적으로 사용되는 기술이다.
  • 벡터 시계는 [서버,버전]의 순서쌍을 데이터에 매단 것으로, 어떤 버전이 선행이고 후행인지, 아니면 다른 버전과 충돌이 있는지 판별하는데 쓰인다.벡터 시계는 D([Si, Vi],...)로 쓰이는데, D는 데이터고 Si는 서버 번호, Vi는 버저나운터다. 데이터 D를 서버 Si에 기록하면 시스템은 1)[Si,Vi]가 있으면 Vi를 증가시킨다. 2)그렇지 않으면 새 항목 [Si,1]을 만든다. 를 수행해야한다. 벡터 시계를 사용하면 어떤 버전 X가 어떤 버전 Y의 이전 버전인지(충돌이 있는지 없는지) 쉽게 판단할 수 있다. 버전 Y에 포함된 모든 구성요소 값이 X에 포함된 모든 구성요소 값보다 크거나 같은지만 보면 된다. 어떤 버전 X, Y 사이에 충돌이 있는지 보려면(그 두 버전이 같은 이전 버전에서 파생된 다른 버전들인지 보려면) Y의 벡터 시계 구성 요소 가운데 X의 벡터 시계 동일 서버 구성 요소보다 작은 값을 갖는 것이 있는지 보면 된다(모든 구성 요소가 작은 값을 가지면 Y는 X의 이전 버전임). 그러나 벡터 시계를 이용해 충돌을 감지, 해소하는 데에는 단점이 있다. 1)충돌 감지 및 해소 로직이 클라이언트에 들어가서 클라이언트 구현이 복잡해진다. 2)[서버:버전]의 순서쌍 개수가 굉장히 빨리 늘어난다. 이를 해결하려면 길이에 임계치를 설정하고, 임계치 이상이 되면 오래된 순서쌍을 벡터 시계에서 제거하도록 해야하는데, 이렇게 되면 버전간 선후 관계가 정확하게 결정될 수 없어 충돌 해소 과정의 효율성이 낮아지게 된다.(그러나 아마존 dynamo DB 관계 문헌에 따르면 실제 서비스에서 그런 문제가 벌어지는 것을 발견된 적이 없다고 함. 실제 기업에서 적용해도 괜찮은 솔루션일 것.)

• 장애 처리

  • 장애를 어떻게 처리할 것이냐 하는 것은 중요하다.
  • 장애 감지: 분산 시스템에서는 그저 한 대 서버가 죽었다고 바로 장애처리하지는 않는다. 두 대 이상 서버가 똑같은 장애를 보고해야 해당 서버에 실제 장애가 발생했다고 간주한다. 모든 노드 사이에 멀티 캐스팅 채널을 구축하는 것이 서버 장애 감지에 가장 손쉬운 방법이나, 서버가 많을때는 비효율적이다. 가십 프로토콜(gossip protocol) 같은 분산형 장애 감지(decentralized failure detection) 솔루션을 채택하는 편이 보다 효율적이다. 가십 프로토콜은 다음과 같이 동작한다. 1)각 노드는 멤버십 목록(membership list)을 유지한다. 멤버십 목록은 가가 멤버 ID와 그 박동 카운터(heartbeat counter)쌍의 목록이다. 2)각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다. 3)각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다. 4)박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신한다. 5)어떤 멤버의 박동 카운터 값이 지정 시간동안 갱신되지 않으면 해당 멤버는 장애(offline) 상태인 것으로 간주한다. 즉, 어떤 노드가 오랫동안 갱신되지 않은 것을 발견하면 그를 발견한 노드는 무작위로 선택된 다른 노드들에게 박동 카운터 목록을 전달하고, 이를 전달받아 박동 카운터가 오랫동안 증가되지 않았음을 발견한 노드들은 모두 해당 노드를 장애 노드로 표시한다.
  • 일시적 장애 처리: 가십 프로토콜로 장애를 감지한 시스템은 가용성 보장을 위해 필요한 조치를 해야한다. 엄격한 정족수(strict quorum) 접근법을 쓰면, 읽기와 쓰기 연산을 금지해야 한다. 느슨한 정족수(sloppy quorum) 접근법은 이 조건을 완화하여 가용성을 높인다. 정족수 요구사항을 강제하는 대신 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고른다. (장애 상태인 서버는 무시) 그리고 네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리한다. 그동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영하여 데이터 일관성을 보존한다. 이를 위해 임시로 쓰기 연산을 처리한 서버에는 그에 대한 단서(hint)를 남기고, 이러한 장애 처리 방안을 단서 후 임시 위탁(hinted handoff) 기법이라 부른다.
  • 영구 장애 처리: 영구적인 노드의 장애 처리를 위해서는, 반-엔트로피(anti-entropy)프로토콜을 구현하여 사본들을 동기화한다. 반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함한다. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클(Merkle)트리(해시 트리라고도 불리며, 각 노드에 그 자식 노드들에 보관된 값의 해시(자식 노드가 종단 노드일 경우), 또는 자식 노드들의 레이블로부터 계산된 해시값을 레이블로 붙여두는 트리. 해시 트릴르 사용하면 대규모 자료구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증할 수 있음.)를 사용한다. 두 머클 트리의 비교는 루트 노드 해시값을 비교하는 것으로 시작하여, 루트 노드의 해시값이 같으면 두 서버는 같은 데이터를 갖는 것이다. 다르면 왼쪽 자식 노드 해시 값, 그 다음으로 오른쪽 자식 노드의 해시 값을 비교한다. 이렇게 아래쪽으로 탐색해나가다보면 다른 데이터를 갖는 버킷을 찾을 수 있으므로 그 버킷들만 동기화하면 된다. 머클 트리를 사용하면 동기화해야하는 데이터 양은 실제 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터의 총량과는 무관해진다. 그러나 실제로 쓰이는 시스템의 경우 버킷 하나의 크기가 꽤 크다는 것을 알아야 한다. (ex.10억개의 키를 백만 개의 버킷으로 관리하면 하나의 버킷 당 1000개의 키를 관리하게 된다.)
  • 데이터 센터 장애 처리: 데이터를 여러 데이터 센터에 다중화하는 것이 중요하다.

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

  • 1)클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, 즉 get 및 put과 통신한다. 2)중재자는 클라이언트에게 키-값 저장소에 대한 proxy 역할을 하는 노드다. 3)노드는 안정 해시의 해시 링 위에 분포한다. 4)노드를 자동으로 추가 또는 삭제할 수 있도록 시스템은 완전히 분산된다.(decentralized) 5)데이터는 여러 노드에 다중화된다. 6)모든 노드가 같은 책임을 지므로 SPOF는 존재하지 않는다.
  • 완전히 분산된 설계를 채택하였으므로, 모든 노드는 클라이언트 API, 장애 감지, 데이터 충돌 해소, 장애 복구 메커니즘, 다중화, 저장소 엔진 등의 기능을 모두 지원해야 한다.
    

• 쓰기 경로(write path)

  • 쓰기 요청이 특정 노드에 전달되면 무슨 일이 벌어지는지를 보여준다. 1)쓰기 요청이 커밋 로그(commit log) 파일에 기록된다. 2)데이터가 메모리 캐시에 기록된다. 3)메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable(Sorted-String Table. <키,값>의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블)에 기록된다.

• 읽기 경로(read path)

  • 읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지부터 살펴서, 있으면 해당 데이터를 클라이언트에게 반환한다. 메모리에 없으면 디스크에서 가져와야 한다. SSTable에 찾는 키가 있는지 알아낼 효율적 방법이 필요할 것인데, 블룸 필터(Bloom filter)가 흔히 사용된다. 1)데이터가 메모리에 있는지 검사한다. 없으면 2로 간다. 2)데이터가 메모리에 없으므로 블룸 필터를 검사한다. 3)블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아낸다. 4)SSTable에서 데이터를 가져온다. 5)해당 데이터를 클라이언트에게 반환한다.

요약

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