대규모 분산 환경 key-value 저장소 설계

https://bytebytego.com/courses/system-design-interview/design-a-key-value-store

ByteByteGo | Technical Interview Prep

 

전통적인 관계형 DB와 다르게 상황에 따라 key-value 형태로 저장이 필요한 경우가 있다. 대표적인 서비스로는 AWS DynamoDB, Memcached, Redis 같은 것들이 있으며 큰 틀에서는 아래와 같은 특징을 가진다.

• key: 유일한 값이어야한다. 값의 종류는 상관없다. 숫자형, 해쉬값, 의미있는 텍스트등.
• value: 관계형 DB와는 다르게 문자열, 리스트, 객체 무엇이든 될 수 있다.

Redis에서 지원하는 value 값의 형태

 

 

세상에 완벽한 설계는 없다. 우린 언제나 데이터의 일관성과 가용성 사이에 적절하게 트레이드 오프를 고려해야한다. 이 글에서도 아래와 같이 실제 대규모 비즈니스에서 사용가능할 정도의 제약을 두고 시작하고자 한다.

• key-value 쌍의 크기는 10KB 이하
• 수백만 이상의 사용자가 만들어내는 대용량 데이터를 처리할 수 있어야 한다.
• 높은 가용성 (High Availablity): 시스템의 응답은 빨라야한다. 설령 장애가 발생했더라도.
• 높은 확장성 (High Scalabilty): 트래픽 양이 늘었을 때 손쉽게 서버를 확장할 수 있어야 한다.
• 자동 스케일링(Automatic scaling): 트래픽 양이 증가함에 따라 서버의 증설/삭제가 자동으로 이루어질 수 있어야한다.
• 데이터의 일관성을 조절할 수 있어야 한다. (Tunable consistency)
• 응답 지연시간이 짧아야 한다. (Low latency)

 

1️⃣ 단일 서버 key-value 저장소

서버가 한 대라면 설계는 매우 간단하다. 그냥 전부 해시 테이블로 저장하면 된다. 메모리를 최대한 활용하기 위해 아래 방법을 사용한다.

• 데이터를 압축해서 사용하기
• 자주 쓰이는 데이터만 우선적으로 메모리에 두기

 

2️⃣ 분산 서버 key-value 저장소

단일 서버를 아무리 scale-up해서 사용한다해도 언젠가 부족한 때가 찾아오기 마련이다. 이 때는 서버를 분산시켜 사용해야한다.

이는 분산 해시테이블이라고도 불리는데 이를 설계할 때는 트레이드 오프의 기본인 CAP(Consitency, Availabilty, Partition Tolerance ) 를 고려해야한다.

서버를 구성할 때 세가지중 두 가지 속성만 충족할 수 있다. 나머지 하나는 희생될 수 밖에 없다. (* 그중 실 비즈니스에서 분단 내성은 필수)

 * P의 정확한 정의는 분산 네트워크간 통신과정에서 일어나는 메시지 손실을 얼마나 허용할지 규칙을 정하는 것이다.

• CP 시스템: 일관성, 파티션 감내를 지원
• AP 시스템: 가용성과 파티션 감내를 지원
• CA 시스템: 일관성과 가용성을 지원하는 저장소. 다만 대부분의 분산 환경 비즈니스에서 분단 내성을 포기하는건 불가능하다.

 

실제 서비스 운영에서 특정 파티션의 장애는 피할 수 없다. 이 때 일관성과 가용성 중 어떤 것을 우선적으로 챙겨야할지 고민해야한다.

• 일관성(CP)이 중요하다면 쓰기 연산을 중지시키면 파티션간 데이터 불일치를 막을 수 있다. 단 서비스 가용성은 많이 낮아진다. 
  온라인 뱅킹 같이 계좌의 최신정보를 출력하지 못하는 경우를 생각해보자. 이 때는 가용성보다 일관성이 훨씬 중요하다.
• 가용성(AP)이 중요하다면 옛날 데이터를 잘못 반환하더라도 쓰기 및 읽기를 계속 허용해야한다.
  페이스북 같은 커뮤니티 서비스라면 댓글이 잠깐 잘못나오더라도 서비스 가용성과 사용자 경험을 챙기는게 훨씬 중요하다. 

 

이러한 분산환경 key-value 저장소를 구현할 때에는 여러 가지 요소를 고려해야하는데, 각 요소들을 하나씩 살펴보자.

• Data partition (데이터 파티션)
• Data replication (데이터 다중화)
• Data consistency (데이터 일관성, 일관성 모델)
• Inconsistency resolution (일관성 불일치 해소)
• Handling failures (장애 처리, 장애 감지)
• System architecture diagram (아키텍처 다이어그램 설계)

 

# Data partition (데이터 파티션)

대규모 서비스의 경우, 한 대에 모든 데이터를 넣는건 불가능하다. 전체 데이터를 작은 파티션으로 분할하여 여러 대에 나눠 저장해야한다. 이 때 아래의 요소들을 고려해야한다.

• 데이터를 각 서버에 고르게 분산할 수 있는가
• 서버(노드)가 추가, 삭제되더라도 데이터를 많이 이동하지 않아도 되는가

이는 앞에서 배운 안정해시를 통해 해결할 수 있다. 안정해시를 사용하면 추가적으로 자동 확장(Auto Scaling)이 쉬워지고 각 서버의 용량에 맞게 설정을 다양화(heterogeneity) 할 수 있다. 2024.02.18 - [👀기본 지식/CS 기본지식] - 안정 해시(Consistent Hashing)

안정 해시(Consistent Hashing)

 

 

# Data replication (데이터 다중화)

하나의 서버를 아무리 철저하게 관리한다고 해도 높은 가용성과 안정성을 얻긴 어렵다. 이를 확보하려면 비동기적인 다중화가 필요하다.

안정해시를 사용하는 예를 들어본다면 시계 방향으로 원을 순회하면서 중복되지 않는 첫 N개 서버에 데이터 사본을 보관하면 된다. 또한 정전, 네트워크 이슈, 자연재해등을 방지하기위해 각 물리서버는 다른 데이터 센터에 보관하도록 구성하면 된다. (이는 AWS 같은 클라우드를 사용한다면 쉽게 구성 가능하다.)

 

 

# Data consistency (데이터 일관성)

여러 서버에 데이터를 다중화하기 때문에 적절한 로직을 사용해 데이터가 동기화가 되어야한다.

예를 들어 Quorum Consensus(정족수 합의) 프로토콜을 사용하면 읽기/쓰기 연산에 아래와 같이 일관성을 보장할 수 있다.

• N: 사본개수
• W: 쓰기 연산에 대한 서버 정족수(* 완료처리를 위한 최소 성공 수)
• R: 읽기 연산에 대한 서버 정족수(* 완료처리를 위한 최소 성공 수)

클라이언트 요청은 중재자(coordinator)가 받아서 프록시처럼 처리한다.

W,R,N 을 따로 정의한 이유는 응답 레이턴시와 데이터 일관성 사이에 트레이드 오프를 고려해야하기 때문이다.

• W,R 이 몇 개 안되는 경우 응답 레이턴시는 매우 빠를 것이다. 대신 데이터 일관성은 잠깐 일치하지 않을 수 있다.
• W,R 이 전체 개수와 비슷하다면 응답 레이턴시는 느릴 것이다. 하지만 데이터 일관성은 언제나 같을 것이다.

정답은 없다. 서비스에 맞춰서 결정해야한다.

 

프로토콜만 고려했다고 끝은 아니다. 서비스의 특성에 따라 일관성 모델을 정해서 구현해야한다.

• 강한 일관성(Strong Consistency) : 모든 읽기는 최신 데이터이다. 낡은 데이터를 반환하는 경우는 없다.
• 약한 일관성(Weak Consistency) : 읽기 연산은 최신 데이터가 아닐 수 있다. 어느정도 일관성 손실을 감수한다.
• 최종 일관성(Eventual Consistency) : 읽기 연산은 최신 데이터가 아닐 수 있으나 시간이 지나면 모든 사본에 일관성이 맞춰진다.

DB 같은 경우엔 강한 일관성을, 동영상 스트리밍서비스는 약한 일관성을, key-value 인 다이나모, 카산드라 같은경우에는 최종 일관성 모델을 선택하고 있다.

최종 일관성등에서 일관성을 해소하는 방법 중 하나는, 데이터 버저닝(versioning)과 벡터 시계(vector clock)을 사용하는 방법이 있다.

• 버저닝은 데이터 변경 시마다 데이터의 새로운 버전을 만드는 것이다. 각 버전의 데이터는 불변하다
• 벡터 시계는 [서버, 버전]의 순서쌍을 시간 값처럼 데이터에 달아두는 것이다. 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는데 쓰인다.

충돌나면 그 다음 요청자(클라이언트)가 이를 직접 git merge 해서 해결하는 것과 비슷한 원리

 

물론 이 방법도 만능은 아니다. 아래의 단점들을 보고 트레이드 오프를 고려해야한다.

• 사용자(클라이언트)가 충돌을 감지하고 해소해야한다. 클라이언트 구현이 복잡해진다
  Last Write Wins  같은 규칙을 정하고 timestamp에 기반해서 충돌을 해결하는 로직을 구현해야한다.
• 수정이 잦을 경우, 이론상 [서버:버전]의 쌍이 엄청나게 많이 늘어날 수 있다.
  다행히 AWS 다이나모 문헌에 따르면 실제 서비스에서 [서버:버전]쌍이 많아져서 문제가 된 적은 없다고 한다.

 

 

# Handling failures (장애 감지, 처리)

대규모 시스템에서 장애는 그저 불가피하기만 한 것이 아니라 아주 흔하게 벌어지는 사건이다. 먼저 장애 감지 기법을 살펴보고 뒤에서 장애 해소에 대해 알아보도록 하자.

 

분산 환경에서 가장 단순한 방법은 전부 다 연결해 멀티캐스팅(multicasting) 으로 장애를 감지하는 것이다. 당연히 이는 비효율적이다.

 

더 나은 방법으로는 가십 프로토콜(gossip protocol)같은 분산형 장애 감지 솔루션을 사용할 수 있다. 이는 아래와 같이 동작한다.

• 각 노드는 멤버십 목록을 유지한다. 멤버십 목록은 각 [memberId, Heartbeat counter] 쌍의 목록이다.
• 각 노드는 주기적으로 자신의 Heartbeat counter 증가시킨다.
• 각 노드는 무작위로 선정된 노드들에게 주기적으로 자신의 Heartbeat counter 목록을 보낸다.
• Heartbeat counter 목록을 받은 노드는 멤버십 목록을 최신값으로 갱신한다.
• 어떤 멤버의 Heartbeat counter 값이 지정된 시간동안 갱신되지 않으면 (= 특정 서버의 counter 리스트를 어디에도 받지 못했다면) 해당 멤버는 장애 상태인 것으로 간주된다.

counter가 오랫동안 증가되지않으면, 이를 발견한 모든 노드는 해당ID를 장애 노드로 표시한다.

 

1️⃣ 가십 프로토콜로 발견 -> 일시적인 장애 처리

만약 위 과정을 통해 장애를 발견했다면 가용성 보장을 위해 적절한 조치를 취해야한다.

• 엄격한 정족수(strict quorum): 전체 읽기/쓰기 연산을 금지시켜버린다. 장애 발생시 가용성은 최악이 된다.
• 느슨한 정족수(sloppy quorum): 쓰기 연산용 W개의 정상노드, 읽기 연산용 R개의 정상노드만 사용한다. 나머지 서버는 무시한다.
  이후 장애 서버가 복구되었을 때 변경사항(hint)을 일괄 반영하여 데이터 정합성을 보장한다.

장애 해결이후 데이터를 옮길 수 있게 별도로 기록(hint)한다.

 

2️⃣ 가십 프로토콜로 발견 -> 영구적인 장애 처리

해당 서버가 잠깐 문제였다면 위 방법으로 처리하면 된다. 다만 자연재해나 어떠한 이유로 영구적인 장애상황이라면 어떻게 처리할까?

반-엔트로피 프로토콜 (anti-entropy protocol) 을 사용할 수 있다. 이는 사본을 비교하여 최신 버전으로 갱신하는 방법이다.

 

단순 무식하게 모든 걸 비교해서 사본을 찾을수도 있겠지만 대용량 데이터를 처리할 때에는 성능이 매우 느려진다. 대신 해시를 사용하는 머클트리를 구성하면 데이터 총량과 무관하게 이를 구현할 수 있다.

1. 아래와 같이 머클트리(자식 노드들의 레이블로부터 계산된 해시값을 테이블로 붙여두는 트리)를 구성한다.
2. 이후 왼쪽 자식->오른쪽 자식으로 BFS 탐색을 하며 root 노드 해시와 비교한다.
3. 해쉬값이 같다면 데이터가 같으니 넘어가면 되고, 다르다면 그 버킷을 동기화해주면 된다.

머클 트리: https://en.wikipedia.org/wiki/Merkle_tree

카산드라 아키텍처: https://cassandra.apache.org/doc/latest/architecture/

SStable: https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

블룸 필터 https://en.wikipedia.org/wiki/Bloom_filter

 

 

 

3️⃣ 특정 데이터센터의 장애

이는 자연재해에 가까우므로 프로토콜로 극복할 수 없다. 초기 설계부터 데이터 센터를 다중화하여 서버를 구성하는 것이 좋다.

 

 

 

# System architecture diagram (아키텍처 다이어그램 설계)

위에서 여러가지를 고려해보았으니 이제 시스템을 구현하기위해 큰그림, 즉 아키텍처를 그릴 수 있을 것이다.

• 클라이언트는 키-값 저장소가 제공하는 API get(key)와 put(key, value)로 통신한다.
• 중재자는 클라이언트에게 키-값 저장소에 대한 프락시 역할을 하는 노드다.
• 노드는 안정해시의 해시링 위에 분포한다.
• Client API 진입점 및 분산 환경에서 필요한 언급한 요소( 장애감지, 데이터 정합성, 다중화, 복구..)를 다 지원해야한다.

 

예를 들어 key-value 저장소중 하나인 카산드라는 아래와 같이 쓰기와 읽기를 구현한다.

 

 

 

🍀 부록 - AWS Dynamo DB 가 설계된 과정

AWS에서 전세계적인 서비스를 운영할 때 필요한 고가용성의 분산 key-value 저장소가 필요했고 이를 구현하기 위한 논문(Dynamo: Amazon’s Highly Available Key-value Store)을 게제 후 만든 서비스가 DynamoDB이다. 실제로 오픈소스인 카산드라도 이 논문의 영향을 받았다고 한다.

 

물론 심심해서 Dynomo를 만든 건 아니다. AWS는 기존에는 Oracle DB로 운영하였으나, 서비스가 전세계적으로 확장되며 더 이상 관계형DB로는 감당할 수가 없었기에 직접 분산환경에 적절한 고가용성 DB를 설계하고 유지보수하기로 결정하였다고 한다.

 

# 어떤 과정을 거쳐 만들어졌을까 

분산 환경 Key-Value 저장소인 Dynomo가 탄생하게 된 배경은 아래와 같다.

• Oracle 데이터베이스 사용 패턴을 조사 -> 스케일 아웃 처리를 위해 JOIN 자체를 사용하지 않는 경우가 많았다.
• 즉 복수의 데이터를 가져오는 경우, 한 쿼리가 하나의 테이블에서만 데이터를 가져오는 형태였다.
• 그 외에는 인덱스를 통한 단일 데이터 검색이 대부분이었다.

https://changhoi.kim/posts/database/dynamodb-internals-1/

 

 

# 어떤 고민들이 있었을까

Dynomo는 네트워크 장애가 발생할 것이라는 가정 아래 가용성을 최대록 높이도록 디자인되었다.

즉 데이터는 비동기적으로 전파되지만 이에 따른 데이터 충돌 문제 (한 데이터가 다른 수정으로 여러 버전으로 분기) 발생할 수 있다.

읽기 시점의 해결은, 일단 쓰기는 허용하고 이후 복구하는 과정을 거치게된다.

 

분산 저장소에서는 DB 트랜잭션처럼 쓰기를 막을 수 없다. 그래서 "항상 쓰기가 가능한" key-value 저장소를 목표로 하게된다.

• 언제 해결할 것인가?
  쓰기 작업의 가용성을 위해 읽기 작업에서 충돌을 해결한다.
• 누가 해결할 것인가?
  DB가 아닌 서버 로직을 구현하여 이를 처리한다.

여기에 있어 아래의 요소들을 같이 고려했다고 한다.

• 노드를 추가/삭제할 때 운영 및 시스템에 최소한의 영향만을 주어야한다.
• 단일 노드의 장애가 전파되서는 안된다. 모든 노드가 동일한 역할을 수행해야한다.
• 중앙 시스템이 장애로 마비되더라도 P2P 를 통한 분산 컨트롤이 가능한 시스템을 설계해야한다.
• 각 노드들은 상황에 따라 효율적으로 다양하게(Heterogeneitry) 구성될 수 있다.

파티셔닝 ( 노드 추가 / 제거)	안정해시 사용	트래픽에 따른 서버 증설, 즉 증분 확장성을 쉽게 보장할 수 있음.
쓰기 고가용성(HA) 구성	vector clock 사용 데이터 충돌은 클라이언트가 해결	데이터 전파는 Eventual Consistency를 선택함. 쓰기 가용성을 보장받을 수 있음.
일시적 실패	quorum 프로토콜과 Hinted Handoff(복구를 위한 기록) 사용	범용적인 시스템을 위한 일시적인 실패 복구 방법
멤버십, 장애 탐지	gossip 프로토콜 사용	각 노드의 동일성을 유지하면서 탈 중앙화 시스템을 구현

 

Dynomo는 안정 해시에 의해 모든 노드에서 쓰기가 가능하다. 즉 Leader 노드라는 개념 자체가 모호하다.

쓰기를 실패하는 것은 느슨한 정족수 (sloppy quorum)를 이용해 읽기/쓰기가 성공했는지를 판단한다. 

 

 

위에서 설명한 quorum과는 조금 다른게 Dynamo는 요청을 받아 노드에게 전파해주는 중개자(Coordinator)가 따로 없다. 요청을 보내는 key에 따라 안정해시에서 해당 데이터를 저장해야하는 첫번째 노드가 중개자 역할을 하도록 구현되어있다.

 

요청을 받아 중개자가 된 노드는 복제해야하는 노드 수 만큼 다른 노드(preference list)에 데이터를 전파해야한다. 이 과정 속에서 실패 여부는 언급한대로 느슨한 정족수(Sloppy Quorum)를 사용해서 성공 응답을 클라이언트에게 반환한다. 느슨한 정족수를 사용해서 일부 장애가 발생하더라도 서비스 가용성을 보장한다.

 

 

 

이 내용들을 읽어보면 앞에서 언급한 내용들과 비슷한 부분이 많다는 걸 느낄 것이다.

당장은 필요없을 수 있는 지식이지만 분산 환경 서비스를 만들게 된다면 지금 배웠던 내용들을 알차게 써먹을 수 있다.

앞에서 배운 내용들

 

애초에 Dynomo도 천재 개발자가 짠하고 만들어낸 것이 아니라 전부터 논의되어오던 여러 방법들을 최적화한 결과이기 때문이기도 하다.