대규모 시스템 설계 기초 - 6. 키-값 저장소 설계

키-값 저장소는 키-값 DB라고도 불리는 비 관계형 DB이다.

키는 유일해야 하며, 키에 매달린 값은 키를 통해서만 접근할 수 있다.

키-값 저장소로 널리 알려진 것으로는 아마존 다이나모, memcached, Redis 같은 것들이 있다.

분산 키-값 저장소

분산 키-값 저장소를 설계하기 전에, 단일 키-값 저장소를 생각해보자. 단일 키-값 저장소는 간단하다. 키-값 쌍 전부를 메모리에 hash table로 저장하면 된다. 또한 2가지 개선책 1) 데이터 압축 2) 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장 을 이용하면 조금 더 나은 단일 키-값 저장소를 만들 수 있다. 하지만 한 대 서버로는 부족한 때가 찾아오며 결국은 분산 키-값 저장소를 활용할 수 밖에 없다.

먼저 분산 시스템을 설계할 때에는 CAP정리(Consistency, Availability, Partition Tolerance theorem)를 이해하고 있어야 한다.

• 일관성(Consistency) : 분산 시스템의 어떤 node에 접속했느냐와 무관하게 동일한 데이터를 봐야 한다
• 가용성(Availability) : 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다
• 파티션 감내 (Partition Tolerance) : 분산 시스템 내 node 사이 통신 장애가 발생하더라도 시스템은 계속 동작해야 한다

CAP 정리란, 어떤 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다는 의미이다.

💡 왜 희생되어야 하는가?

우선 분산환경에서 파티션 감내는 포기할 수 없는 요구사항이다. 분산 환경에서 파티션 감내를 포기하면, node가 하나라도 미동작했을때 전체 시스템의 장애가 일어나기 때문이다.

그렇다면 파티션 감내를 만족하는 분산시스템에서 일관성을 지킨다고 해보자. 3개의 노드 N1, N2, N3가 있다. N3에 장애가 일어나면, 일관성을 위해 N1과 N2에 대한 쓰기 연산을 중지할 수 밖에 없다. 중지하지 않는다면 노드 사이에 데이터 불일치가 생기고, 일관성이 어겨지기 때문이다. 쓰기 연산이 중지된다면 이는 가용성이 지켜지지 않는 것이다. 즉 일관성과 파티션 감내가 적용되는 시스템이다.

• CP 시스템 : 일관성과 파티션 감내를 지원하는 키-값 저장소. 가용성을 희생한다
• AP 시스템 : 가용성과 파티션 감내를 지원하는 키-값 저장소. 일관성을 희생한다.

이제 분산 키-값 저장소를 설계하기 위한 핵심 기술들을 살펴보자.

데이터 파티션

전체 데이터를 한 대 서버에 모두 넣는 것은 불가능하다. 때문에 데이터를 작은 파티션들로 분할한 후 여러 서버에 저장해야 하는데 다음과 같은 문제를 잘 생각해보아야 한다.

• 데이터를 여러 서버에 고르게 분산할 수 있는가
• 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가

데이터 다중화

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

1개씩의 서버에만 데이터를 저장하면 해당 서버에 장애가 났을 때 복구가 불가능해질 것이다.

데이터 일관성, 비일관성 해소

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

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

• N : 사본(노드) 개수
• W : 쓰기 연산에 대한 정족수 (W개의 서버로부터 쓰기 성공을 받으면 쓰기 연산을 성공으로 간주한다)
• R : 읽기 연산에 대한 정족수 (R개의 서버로부터 읽기 성공을 받으면 읽기 연산을 성공으로 간주한다)

중재자는 클라이언트와 노드 사이에서 proxy 역할을 한다

N, W, R 개수에 따른 구성 예시

• R = 1, W = N : 빠른 읽기 연산에 최적화된 시스템
  • 읽기연산에 대한 정족수가 1이므로 빠른 읽기 연산이 가능하다
• W = 1, R = N : 빠른 쓰기 연산에 최적화된 시스템
  • 마찬가지로 쓰기 연산에 대한 정족수가 1이므로 빠른 쓰기 연산이 가능하다
• W + R ≥ N : 강한 일관성이 보장됨 (보통 N = 3, W = R = 2)
  • 예시처럼 전체가 3개의 node로 구성되어 있는데 최신값이 두 곳의 node에 쓰여지고, 두 곳의 node로 부터 값을 읽는다면 비둘기집 원리에 의해 최신화된 값이 무조건 불려질 수 밖에 없음. 즉 강한 일관성이 보장되는 것
• W + R ≤ N : 강환 일관성이 보장되지 않음
  • 위와 반대되는 case

 

일관성 수준

• 강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환
• 약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수도 있음
• 최종 일관성 : 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영되는 모델

데이터를 다중화하면 가용성은 높아지지만, 사본 간 일관성이 깨질 가능성은 높아진다. 버저닝과 벡터 시계는 그 문제를 해소하기 위해 등장한 기술이다.

 

벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것이다. 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는데 쓰인다.

벡터시계는 D([S1, V1,], [S2, V2], ..., [Sn, Vn])과 같이 표현할 수 있다.

• D : 데이터
• S1 : 서버 번호
• V1 : 데이터 버전

벡터 시계를 사용해 충돌을 감지하고 해소하는 방법에는 두 가지 분명한 단점이 있다.

1. 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로, 클라이언트 구현이 복잡해진다
2. 서버-버전의 순서쌍 개수가 굉장히 빨리 늘어난다. 길이에 어떠한 threshold를 설정하고, 임계치 이상으로 길이가 길어지면 오래된 순서쌍을 베터 시계에서 제거하도록 해야 한다.

장애 감지

분산시스템에서는 보통 N대 이상의 서버가 똑같이 A 서버에 대한 장애를 보고해야 장애 발생으로 간주하게 된다.

모든 노드 사이에 멀티캐스팅 채널을 구축하는 것이 서버 장애를 감지하는 것이 가장 손쉬운 방법이지만, 서버가 많을 때는 분명 비효율적이다. 때문에 가십 프로토콜 같은 분산형 장애 강지 솔루션을 채택하는 편이 보다 효율적이다. 동작 원리는 다음과 같다.

• 각 노드는 멤버십 목록을 유지한다. 멤버십 목록은 각 멤버 id와 박동 카운터 쌍의 목록이다.
• 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다.
• 각 노드는 무작위적으로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다.
• 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신한다.
• 어떤 멤버의 박동 카운트 값이 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애인 것으로 간주한다.

(단방향 + 전체서버 → 일부서버 idea가 들어가 있는 솔루션이다)

일시적 장애 처리

네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리한다. 그동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영하여 데이터 일관성을 보존한다. 이를 위해 임시로 쓰기 연산을 처리한 서버에는 그에 관한 단서(hint)를 남겨둔다. 따라서 이런 장애 처리 방안을 단서 후 임시 위탁 기법이라 부른다.

영구 장애 처리

영구 장애 처리 상황에서는 anti-entropy 프로토콜을 구현하여 사본들을 동기화 해야 한다. anti-entropy 프로토콜은 사몬들을 비교하여 최신 버전으로 갱신하는 과정을 포함한다. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클 (Merkle) 트리를 사용할 것이다.

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

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

• 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, 즉 get(key) 및 put(key, value)와 통신한다.
• 중재자는 클라이언트에 키-값 저장소에 대한 proxy 역할을 하는 노드이다.
• 노드는 안정 해시와 해시 링 위에 분포한다.
• 노드를 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산된다.
• 데이터는 여러 노드에 다중화된다.
• 모든 노드가 같은 책임을 가지므로, SPOF는 존재하지 않는다

각 노드는 1) 메모리 캐시 2) 커밋 로그 (Disk) 3) SSTable 을 가지며, 읽기 요청이 들어올 때는 SSTable에서 값을 효율적으로 꺼내기 위해 Bloom Filter를 사용한다.