06장. 키-값 저장소 설계

개요

• 키-값 저장소는 키-값 데이터베이스라고도 불리는 비 관계형 데이터베이스이며 여기에 저장되는 고유 식별자를 키로 가져야 함. 
• 키와 값 사이의 연결 관계를 '키-값' 쌍 (pair)라고 지칭.
  • 키는 유일해야하고 값은 키를 통해 접근 가능하며 일반 텍스트일 수 있고 해시 값일 수도 있음.
  • 성능 상의 이류로 키는 짧을 수록 좋음
• 값은 문자열, 리스트, 객체일수 있고 보통 값으로 무엇이 저장되던 상관이 없음
  • 키-값 저장소 : 아마존 다이나모 , memcached, 레디스

 

키-값 저장소 설계하기

문제 이해 및 설계 범위 확정

• 읽기, 쓰기, 그리고 메모리 사용량 사이에 어떤 균형을 찾고 데이터의 일관성과 가용성 사이에 타협적 결정을 내린 설계이면 좋음
• 설계 조건
  • 키-값 쌍의 크기는 10KB이하이다.
  • 큰데이터를 저장할 수 있어야 한다..
  • 높은 가용성을 제공해야한다. 
    • 시스템은 장애가 발생해도 빠르게 응답해야함
  • 높은 규모 확장성을 제공해야한다.
    • 트래픽 양에 따라 자동적으로 서버 증석/살제가 이루어져야 함
  • 데이터 일관성 수준은 조정이 가능해야한다.
  • 응답 지연시간이 짧아야 한다.

 

단일 서버 키-값 저장소

• 가장 직관적인 방법으로 키-값 쌍 전부를 메모리에 해시 테이블로 저장
• 빠른 속도를 보장하기는 하지만 모든 데이터를 메모리 안에 저장하는 것은 불가능하여 아래와 같은 항목으로 개선
  • 데이터 압축
  • 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장
• 이 개선에도 한계가 있고 결국 많은 데이터를 저장하려면 분산 키-값 저장소를 사용해야 함.

 

분산 키-값 저장소

• 키-값 쌍을 여러 서버에 분산시켜 분산 해시 테이블이라고도 함
• 분산 시스템을 설계할 때는 CAP 정리(Consistency, Availiabillity, Partition Tolerance theorem)를 이해해야 함

CAP정리

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

 

이들 가운데 어떤 두 가가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다.

 

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

 

사례

이상적 상태

• 이상적 환경이라면 네트워크가 파티션되는 상황은 절대로 일어나지 않을 것임.

n1에 기록된 데이터는 자동적으로 n2와 n3에 복제됨으로서 데이터 일관성과 가용성도 만족

실세계의 분산 시스템

• 분산 시스템은 파티션문제를 피할수 없고 문제가 발생하면 일관성과 가용성 사이에 하나를 선택해야 함.
• 클라이언트가 n1 또는 n2에 기록된 데이터는 n3에 전달되지 않음. n3에 기록되었으나 n1 및 n2로 전달되지 않은 데이터가 있다면 n1과 n2는 오래된 사본을 갖고 있을 것.

n3에 장애가 발생하여 n1 및 n2가 통신할 수 없는 상황

• 가용성 대신 일관성을 선택한다면 세 서버 사이에 생길 수 있는 데이터 불일치를 피하기 위해 n1과 n2에 대해 쓰기 연산을 중단시켜야 하는데 그러면 가용성이 깨짐
  • 은행권 시스템은 가용성을 포기하지 않음
• 일관성대신  가용성을 선택한 시스템은 설사 낡은 데이터를 반환할 위험이 있어도 계속 읽기 연산을 허용해야 함.
• n1과 n2는 계속 쓰기 연산을 허용할 것이고 파티션 문제가 해결된 뒤에 새 데이터를 n3 전송

 

시스템 컴포넌트

• 키-값 저장소 구현에 사용될 핵심 컴포넌트들 및 기술
  • 데이터 파티션
  • 데이터 다중화
  • 일관성
  • 일관성 불일치 해소
  • 장애처리
  • 시스템 아키텍처 다이어그램
  • 쓰기 경로
  • 읽기 경로

 

데이터 파티션

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

 

데이터 다중화

• 높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 다중화할 필요기 있는데 N은 튜닝 가능한 값.
• N개 서버를 선정하는 방법
• 어떤 키를 해시 링 위에 배치 후 그 지점으로부터 시계 방향으로 링을 순회하면서 만나는 첫 N개 서버에 데이터 사본을 보관하는 것

• 위 그림에서 N을 3으로 설정하면 key0은 s1,s2, s3에 저장
• 이렇게 가상 노드를 사용하면 선택한 N개 노드가 대응될 실제 물리서버의 개수가 N보다 작아질 수 있는데 이 문제를 피하려면 같은 물리서버를 중복 선택하지 않도록 해야함
• 같은 데이터센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등 문제를 동시에 겪을 가능성이 있음
• 따라서 안정성을 담보하기 위해 데이터 사본은 다른 센터의 서버에 보관하고 센터들은 고속 네트워크로 연결

 

데이터 일관성

• 여러 노드에 다중화된 데이터는 적절히 동기화 되어야 함
• 정족수 합의 (Quorom Consensus) 프로토콜 사용하면 읽기/쓰기 연산 모두에 일관성 보장 가능
• 관계된 정의
• N = 사본 개수
• W = 쓰기 연산에 대한 정족수, 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함
• R = 읽기 연산에 대한 정족수, 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로 부터 응답을 받아야 함.
  
  

 

데이터가 s0, s1, s2에 다중화되는 상황

 

 

• N이 3인 경우 W=1은 데이터가 한 대 서버에만 기록된다는 뜻이 아님
• 위 상황에서 W=1은 쓰기 연산이 성공했다고 판단하기 위해 중재자(coordinator)는 최소 한대 서버로부터 쓰기 성공 응답을 받아야 한다는 의미
  • s1으로부터 성공 응답을 받았다면 s0과 s2의 응답은 기다릴 필요가 없음
  • 중재자는 클라이언트와 노드 사이의 프록시(proxy)역할을 함
• W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾아가는 전형적은 과정으로 W=1 또는 R=1인 구성의 경우 중재자는 하나의 서버의 응답만 받으면 되어 응답속도는 빠름
• W나 R이 값이 1보다 큰 경우엔 시스템이 보여주는 데이터 일관성의 수준을 향상되지만 중재자의 응답속도는 가장 느린 서버로부터 응답을 기다려야 해 느려질 것임
• W + R > N 의 경우 강한 일관성(strong consistency)이 보장
  • W=N, R=1 : 빠른 읽기 쓰기 연산에 최적화된 시스템
  • W=1, R=N : 빠른 쓰기 쓰기 연산에 최적화된 시스템
• 요구되는 일관성 수준에 따라 W, R, N의 값을 저장하면 됨

 

일관성 모델

• 일관성 모델은 키-값 저장소를 설계할 때 고려해야할 또 하나의 중요한 요소로 데이터 일관성의 수준을 결정하는데 종류가 다양함
• 종류
  • 강한 일관성 (strong consistency) : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환. 즉, 클라이언트는 절대로 낡은 데이터(out-of-date) 를 보지 못함
  • 약한 일관성 (weak consistency) : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있음.
  • 최종 일관성 ( eventual consistency) : 약한 일관성의 한 형태로 갱신 결과가 결국 모든 사본에 반영(즉, 동기화)되는 모델
• 강한 일관성을 달성하는 일반 방법은 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지
• 새로운 요청 처리가 중단되기 때문에 고가용성 시스템에는 적합하지 않음.  
• 최종 일관성을 선택할 경우 쓰기 연산이 병렬로 발생하면 시스템에 저장된 값의 일측에서 데이터 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 하는 기법이 있음

 

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

• 데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 꺠질 가능성이 높아짐
• 버저닝(versioning)과 벡터 시계(vertor clock)는 이 문제를 해결하기 위한 기술
• 버저닝은 데이터를 변경 시 마다 해당 데이터의 새로운 버전을 만듦
• 각 버전의 데이터는 변경 불가(immutable)

v1 : 어떤 데이터의 사본이 노드 n1과 n2에 보관되어 있고 이 데이터를 가져오려는 서버1과 서버2는 get("name") 연산의 결과로 같은 값을 얻음

 

v2 : 서버1은 "name'값을 "johnSanFrancisco", 서버2는 "name"을 "johnNewyork"으로 변경

• 이 두 연산이 동시에 이뤄지며 충돌하는 두 값을 갖도록 만들고 버전을 v1과 v2로 지정
• 변경이 끝난 옛날 값이라 변경이 이루어진 이후 원래 값은 무시 가능.
• 하지만 마지막 두 버전 사이의 충돌은 해소하기 어려운데 이를 해결하려면 충돌을 발견하고 자동으로 해결해 낼 버저닝 시스템이 필요.
• 벡터 시계는 이런 문제를 푸는데 보편적인 기술로 동작 원리는 다음과 같다.
• 백터 시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것으로 어떤 버전이 선행 버전인지 후행 부전인지 아니면 다른 버전과 충돌이 있는지 판별하는데 쓰임
• 백터시계를 D([S1, v1], [S2, v2], ..., [Si, vi] 로 표현한다는 가정하에 여기서 D는 데이터이고, vi는 버전 카운터, Si는 서버 번호
• 만약 데이터D를 서버 Si 에 기록하면 시스템은 두가지 중 하나를 수행해야  함
• [Si, vi]가 있으면 vi 증가
• 그렇지 않으면 새 항목 [Si, 1]를 만듦

 

추상적 로직이 실제로 어떻게 수행되는지에 대한 구체적 사례

 

1. 클라이언트가 데이터 D1을 시스템에 기록. 이 쓰기 연산을 처리한 서버는 Sx이다. 따라서 벡터시계는 D1([Sx,1])으로 변함
2. 다른 클라이언트가 데이터 D1을 읽고 D2로 업데이트 후 기록. D2는 D1에 대한 변경이므로 D1을 덮어씀. 이 떄 쓰기 연산은 같은 서버 Sx가 처리한다고 가정하면 벡터시계는 D2([Sx, 2])로 변함
3. 다른 클라이언트가 D2를 읽어 D3로 갱신 후 기록. 이 쓰기를 Sy가 처리한다고 가정하면 벡터 시계 상태는 D3([Sx, 2], [Sy, 1])로 바뀜
4. 또 다른 클라이언트가 D2를 읽고 D4로 갱신 후 기록, 이 때 쓰기 연산은 서버 Sz가 처리한다고 가정하면 벡터 시계는 D4([Sx, 2], [Sz, 1] 로 변경
5. 어떤 클라이언트가 D3과 D4를 읽으면 데이터 간 충돌이 있는 것을 알게된다. D2를 Sy와 Sz가 각기 다른 값으로 바꿨기 때문 (3, 4의 과정) 이 충돌은 클라이언트가 해소 후 서버에 기록하고 이 쓰기 연산을 처리한 서버는 Sx라고 가정하면 벡터 시계는 D5([Sx, 3], [Sy, 1], [Sz, 1])로 변경됨

• 벡터 시계를 활용하면 어떤 버전 X가 버전 Y의 이전 버전인지 쉽게 판단함으로써 충돌이 없는지도 알 수 있다.
• 버전 Y에 포함된 모든 구성 요소의 값이 X에 포함된 모든 구성 요소 값도 같거나 큰지만 보면 됨.
• 예를 들어 D([S0, 1], [s1, 1])은 D([s0, 1], [s1, 2])의 이전 버전이다. -> 충돌 X

 

• 벡터 시계를 사용해 충돌을 감지/해소 하는 방법에는 두가지가 있다.
  1. 1) 충돌 감지 및 해소 로직이 클라이언트에 들어가야해 클라이언트의 구현이 복잡해진다.
  2. 2) [서버: 버전]의 순서쌍이 굉장히 빨리 늘어나는데 이 문제를 해결하려면 그 길이에 대한 임계치를 설정해야한다. 이 임계치 이상으로 길이가 길어지면 오래된 순서쌍을 벡터 시계에서 제거해야하는데 이렇게 되면 버전 간 선후 관계가 정확하게 결정될 수 없어 충돌 해소 과정의 효율성이 낮아진다. (실제 사례에서는 이런 문제가 발견된 적이 없다고 함)

 

장애처리

• 장애감지 기법과 장애 해소 전략들을 짚어볼 것.

장애감지

• 분산 시스템에서 그저 한 대 서버가 "지금 서버 A가 죽었습니다"라고 한다해서 바로 서버 A를 장애처리 하지 않음. 
• 보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 장애가 발생했다고 간주함
• 모든 노드 사이에 멀티태스킹 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법이지만 이 방법은 서버가 많을 때는 비효율적.

멀티 태스킹 방법

• 가십 프로토콜 같은 분산형 장애 감지 솔루션을 채택하는 것이 효율적.
• 가십 프로토콜의 동작 원리
• 각 노드는 멤버십 목록을 유지. 멤버십 목록은 각 멤버 ID와 그 박동 카운터 쌍의 목록
• 각 노드는 주기적으로 자신의 박동 카운터를 증가
• 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보냄
• 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
• 어떤 멤버의 박동 카운터 값이 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애(offline)상태로 간주.

 

• 노드 s0은 위 테이블과 같은 멤버십 목록을 가진 상태
• 노드 s0은 노드 s2(멤버 ID=2)의 박동 카운터가 오랫동안 증가되지 않았다는 것을 발견
• 노드 s0은 노드 s2를 포함하는 박동 카운터 목록을 무작위로 선택된 다른 노드에게 전달
• 노드 s2의 박동 카운터가 오랫동안 증가되지 않았음을 발견한 모든 노드는 해당 노드를 장애 노드로 표시

 

일시적 장애처리

• 가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위한 조치를 취해야 하는데 엄격한 정족수 (strict quorum) 접근법을 사용하면 읽기 쓰기 연산을 금지해야 함
• 느슨한 정족수 접근법 : 이 조건을 완화하여 가용성을 높이는데 정족수 요구사항을 강제하는 대신 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시링에서 고른다. (장애 상태 서버 무시)
• 네트워크나 서버 장애인 서버로 가는 요청은 다른 서버가 잠시 처리하고 그 동안 발생한 변경사항은 해당 서버가 복구됐을 때 일괄 반영해 데이터 일관성을 보존 
• 임시로 쓰기 연산을 처리한 서버는 그에 관한 힌트를 남겨두는데 이러한 처리 방안을 단서 후 임시 위탁 (hinted handoff) 기법이라 부름

 

 

장애상태인 s2에 대한 읽기 쓰기 연산은 일시적으로 노드 s3가 처리하고 s2가 복구되면 s3은 갱신된 데이터를 s2로 인계

 

영구 장애 처리

• 영구적인 노드 장애 상태는 반-엔트로피(anti-entropy) 프로토콜을 구현해 사본들을 동기화하고 그 사본들을 비교해 최신 버전으로 갱신하는 과정도 포함.
• 사본 간의 일관성이 망가진 상태를 잠지하고 전송 데이터의 양을 줄이기 위해 머클 트리를 사용할 것.

머클트리란? (위키디피아)

• 해시 트리 (hash tree)라고도 불리는 머클트리는 각 노드에 그 자식 노드들에 보관된 값의 해시 (자식 노드가 종단 leaf 노드인 경우), 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리다. 해시트리를 사용하면 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증(verification)할 수 있다.

 

■ 키 공간 (key space)이 112일 때 머클 트리를 만드는 예제 살펴보기

• 일관성이 망가진 데이터가 위치한 상자는 다른 색으로 표시함
• [1단계]  네 개의 버킷으로 나누기

 

• [2단계] 버킷에 포함된 각각의 키에 균등 분포 해시(uniform hash)함수 적용해 해시 값 계산

 

• [3단계] 버킷 별로 해시 값 계산 후 해당 해시 값을 레이블로 갖는 노드를 만든다.

 

• [4단계] 자식 노드의 레이블로부터 새로운 해시 값을 계산해 이진 트리를 상향식으로 구성해 나간다.

• 위 두 머클 트리의 비교는 루트 노드의 해시값을 비교하는 것으로 시작하고 루트 노드 해시 값이 일치하면 두 서버는 같은 값을 가짐.
• 그 값이 다른 경우에는 왼쪽 자식 노드의 해시 값을 비교하고 그 다음으로 오른 자식 노드의 해시 값을 비교함으로써 다른 데이터를 갖는 버킷을 잦아내 동기화 한다.
• 머클 트리를 사용하면 동기화해야 하는 데이터 양은 실제로 존재하는 차이의 크기에 비례할 뿐 두 서버에 보관된 데이터 총량과는 무관해짐
• 하지만 실제로 쓰이는 시스템의 경우 버킷 하나의 크기가 꽤 큼
• 예를들면 10(1B)개의 키를 백만(1M)개의 버킷으로 관리한다하면 이 경우에는 하나의 버킷은 1,000개의 키를 관리하게 되는 것.

 

데이터 센터 장애 처리

• 데이터 센터 장애는 정전, 네트워크 장애, 자연재해 등 다양한 이유로 발생하는데 데이터를 여러 데이터 센터에 다중화하여 한 데이터 센터가 망가지면 다른 데이터 센터를 이용할 수 있도록 구성한다.

 

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

• 아키텍처의 주된 기능
  • 클라이언트는 키-값 저장소가 제공하는 두가지 단순한 API, 즉 get(key) 및 put(key, value)와 통신
  • 중재자(coordinator)는 클라이언트에게 키-값 저장소에 대한 프록시(proxy)역할을 하는 노드
  • 노드는 안정해시(consistent hash)의 해시 링(hash ring)위에 분포

 

• 노드를 자동으로 추가 또는 삭제할 수 있도록 시스템은 완전히 분산된다 (decentralized).
• 데이터는 여러 노드에 다중화된다.
• 모든 노드가 같은 책임을 지므로 SPOP(Single Point of Failure)는 존재하지 않는다.
• 완전히 분산된 설계 채택 시 모든 노드에는 [클라이언트 API / 장애감지 / 데이터 충돌 해소 / 장애 복구 메커니즘 / 다중화 / 저장소 엔진 ... 등]의 기능을 전부 지원해야 한다.

 

쓰기 경로

• 쓰기 요청에 특정 노드에 전달되면 나타나는 현상

카산드라의 쓰기 사례 참고

① 쓰기 요청이 커밋 로그(commit log) 파일에 기록

② 데이터가 메모리 캐시에 기록

③ 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록

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

 

 

읽기 경로

• 읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지 살피고 있으면 해당 데이터를 클라이언트에게 반환

• 데이터가 메모리에 없는 경우에는 디스크에 가져와야 하는데 어느 SSTable에 찾는 키가 있는지 알아내는 효율적인 방법으로 블룸 필터 (Bloom filter)가 흔히 사용됨.
• 데이터가 메모리에 없을 때 읽기 연산이 처리되는 경로 (그림)

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

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

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

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

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

 

정리

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