키-값 저장소

• 고유 식별자인 키에 값을 할당하는 데이터베이스를 키-값 저장소라고 부른다.
• 키-값 저장소의 대표적인 시스템은 레디스가 있다.

단일 서버 키-값 저장소

• 한 대 서버만 사용하는 키-값 저장소에서는 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 게 제일 간단한 설계이다.
• 해시 테이블로 저장하는 방법은 O(1) 이어서 매우 빠르지만 시스템이 확장될 수록 모든 데이터를 메모리에 두는 것은 어렵다. 그나마 할 수 있는 방법은 두 가지다.
  1. 데이터 압축
  2. 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장

분산 키-값 저장소

분산 시스템을 설계할 때는 CAP 정리를 이해해야 한다.

CAP 정리

• 데이터 일관성(consistency): 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 상관없이 언제나 같은 데이터를 보아야 한다.
  - 모든 노드 전체가 동일한 데이터를 가진다는 게 아니라 해당 데이터가 저장되어야 하는 노드 집합(=샤드 + 그 샤드의 replica) 내에서 일관성을 유지하는 것
• 가용성(availability): 분산 시스템에 접속하느 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
• 파티션 감내(partition tolerance): 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다.

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

• CP 시스템: 일관성 & 파티션 감내를 지원하는 키-값 저장소 (가용성 희생)
• AP 시스템: 가용성 & 파티션 감내를 지원하는 키-값 저장소 (일관성 희생)
• CA 시스템: 파태션 감내를 희생하는 키-값 저장소. 그러나 통상 네트워크 장애는 피할 수 없는 일로 여겨지므로, 분산 시스템은 파티션 감내를 무적권 지원하도록 설계해야 한다. 따라서 CA 시스템은 없다.

CP, AP, CA 시스템은 왜 하나를 희생하라고 하지? 셋 다 충족시키면 안되나?

CAP 정리는 셋을 동시에 만족할 수 없는 것이 아니라, ‘네트워크 파티션이 발생한 상황’에서는 셋을 동시에 만족할 수 없다는 이론이다. 네트워크가 나뉘는 장애 상황에서는 Consistency와 Availability를 동시에 만족할 수 없기 때문이다.

실 세계의 분산 시스템

세 대의 복제(replica) 노드 n1, n2, n3에 데이터를 복제하여 보관하는 상황을 예시로 들어본다.

n3에 장애가 발생하여 n1 및 n2와 통신할 수 없는 상황이 발생했다고 가정하면 아래와 같은 일들이 일어난다.

• 클라이언트가 n1이나 n2에 저장한 데이터는 n3에 전달 X
• n3에 저장되었으나 아지 n1이나 n2에 전달되지 않은 데이터가 존재

이 상황에서는 가용성 또는 일관성을 선택해야 한다.

일관성을 선택

• 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1과 n2에 대해 쓰기 연산을 중단 -> 가용성 깨짐
• 은행권에서는 데이터 일관성을 양보하지 않는다.

가용성

• 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용한다.
• n1과 n2는 계속 쓰기 연산을 허용하고, 파티션 문제가 해결된 뒤에 새 데이터를 n3에 전송한다.
• 커뮤니티 사이트, 이커머스(결제 도메인은 모르겠지만)에서는 일관성 보다 가용성을 택하는게 더 옳은 선택이라고 생각

데이터 파티션

대규모 어플리케이션에서 엄청난 양의 데이터를 저장하는 좋은 방법은 데이터를 작은 파티션들로 분할한 다음 여러 대 서버에 저장하는 것이다.
데이터를 파티션 단위로 나눌 때 중요한 문제는 다음 두 가지이다.

• 데이터를 여러 서버에 고르게 분산할 수 있는가
• 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가
  이 문제를 해결하기 위한 좋은 방법은 안정 해시이다.

데이터 다중화

높은 가용성과 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화할 필요가 있다. 안정 해시를 활용한 데이터 다중화 방법은 다음과 같다.

• 안정 해시 링에서 시계방향으로 순회하며 만나는 첫 N개 서버에 데이터 사본을 보관한다.
• 안정 해시 링에 가상 노드를 사용하고 있는 경우 중복된 서버에 데이터를 보관하지 않도록 한다.

데이터 일관성

여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 한다. 정족수 합의 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.

정족수 합의 프로토콜

• N = 사본 개수
• W = 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 한다.
• R = 읽기 연산에 대한 정족수.

중재자가 데이터를 읽기/쓰기를 하면서 각 노드에서 연산에 대한 성공 응답을 받고, 정해진 프로토콜에 따라 일정 수의 성공 응답을 받아야 해당 연산은 성공했다고 판단한다.

N, W, R 구하는 예시

• R=1, W=N: 빠른 읽기 연산에 최적화된 시스템
• W=1, R=N: 빠른 쓰기 연산에 최적화된 시스템
• W+R > N: 강한 일관성이 보장됨
• W+R <= N: 강한 일관성이 보장되지 않음.

중재자란

중재자(Coordinator): 여러 노드(혹은 서비스)들이 서로 충돌 없이, 일관성 있는 상태로 동작하도록 조율하는 역할
중재자의 3가지 핵심 역할
1. 요청을 올바른 노드로 라우팅: 분산 서비스는 데이터가 여러 노드로 나뉘어 저장됨(샤딩).이때 클라이언트가 직접 노드를 선택하게 하면 혼란이 생김. 그래서 중재자가 대신 해준다.
2. 일관성 유지: 중재자는 다음을 담당한다:
- 복제 요청을 모든 replica에 전달
- 복제가 완료됐는지 확인
- 실패 시 롤백 또는 재시도
- 읽기/쓰기 일관성 보장
3. 동시성/경쟁 상태 해결: 여러 노드가 같은 자원에 접근하면 충돌이 발생할 수 있다. 중재자는 “누가 먼저 처리할지”를 결정한다.

일관성 모델

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

결과적 일관성 모델

강한 일관성을 달성하는 일반적인 방법은 모든 사본에 현재 쓰기 연산의 결과가 반영될 때 까지 읽기/쓰기를 금지하는 것. 이 방법은 고가용성 시스템에서는 적합하지 않다. 그래서 다이나모 또는 카산드라 같은 저장소는 결과적 일관성 모델을 택하고 있다.

결과적 일관성 모델은 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있어서 이 문제는 클라이언트가 해결해야한다. 해결 방법으로 데이터 버저닝 기법이 있다.

데이터버저닝

• 데이터를 업데이트할 때마다 “이 값이 몇 번째 버전인지” 번호를 붙여서 충돌을 감지하고 해결하는 방법
• 클라이언트에서 쓰기 연산 시 데이터의 버전을 함께 보낸다. 저장소에 저장할 때 버전이 겹치면 쓰기 연산에 실패하고, 클라이언트에서는 이에 대한 후속 처리를 한다.

벡터 클럭

• 각 노드 마다 데이터 업데이트에 참여한 버전과 메타데이터(타임 스탬프)를 관리한다.
• 주기적으로 노드 별로 버전이 다른 데이터를 찾아서 메타데이터를 확인하여 모든 노드에 최신 데이터가 입력될 수 있도록 하여 일관성을 맞출 수 있다.
• 단일 버전 번호는 “어느 업데이트가 최신인지”만 알려주지만, Vector Clock은 업데이트가 ‘원인-결과’ 관계인지 ‘충돌’인지까지 알려준다.

장애 감지

분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버에 실제로 장애가 발생했다고 간주한다.

가십 프로토콜 같은 분산형 장애 감지 솔루션을 채택하는 편이 장애 감지를 하기에 좋다.
가십 프로토콜의 동작 원리는 다음과 같다.

• 1) 각 노드는 주기적으로 랜덤한 다른 노드를 하나 선택한다.
  • “오늘 누구한테 소문을 퍼뜨릴까?” 하는 느낌.
• 2) 선택된 노드에게 자기 상태 정보를 전달한다.
  • 예: 최신 데이터 버전 정보, 헬스 체크 정보, 멤버십 정보 등.
• 3) 상대 노드는 전달받은 정보를 자신의 정보와 비교한다.
  • 더 최신이면 반영하고,
  • 뒤쳐졌으면 상대에게 요청해서 최신 정보를 받아옴.
• 4) 그리고 그 노드도 다시 랜덤한 노드에게 같은 정보를 전파한다.
  • 마치 소문이 퍼지는 방식 그대로임.
• 5) 이런 소문 퍼뜨리기가 반복되면 전체 클러스터에 정보가 퍼지게 된다.
  • O(log N) ~ O(N) 정도의 시간 안에 사실상 모든 노드가 동기화됨.
• 6) 일부 노드가 실패해도 전체 정보는 계속 퍼지므로 매우 높은 내결함성을 가짐.
  • 노드 몇 개가 죽어도 소문은 계속 퍼진다.

시스템 아키텍쳐

쓰기 경로

1. 쓰기 요청이 커밋 로그 파일에 기록된다.
2. 데이터가 메모리 캐시에 기록된다.
3. 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록된다.

읽기 경로

1. 읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지부터 살핀다. 있으면 반환한다.
2. 캐시에 없으면 블룸 필터를 검사한다.
3. 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아낸다.
4. SSTable에서 데이터를 가져온다.
5. 해당 데이터를 클라이언트에게 반환한다.