[System Design Interview] 6장 키-값 저장소 설계

키-값 저장소(key-value store)는 키-값 데이터베이스라고도 불리는 비 관계형(non-relational) 데이터베이스

문제 이해 및 설계 범위 확정

다음 연산을 지원하는 키-값 저장소를 설계

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

다음 특성을 갖는 키-값 저장소를 설계

• 키-값 쌍의 크기는 10KB 이하
• 큰 데이터를 저장할 수 있어야 함
• 높은 가용성을 제공해야 함
• 높은 규모 확장성을 제공해야 함
• 데이터 일관성 수준은 조정 가능해야 함
• 응답 지연시간(latency)이 짧아야 함

단일 서버 키-값 저장소

데이터 압축과 캐싱을 이용해도 한 대 서버로 부족한 때가 찾아옴. 많은 데이터를 저장하려면 분산 키-값 저장소(distributed key-value store)를 만들 필요가 있음

분산 키-값 저장소

분산 키-값 저장소(분산 해시 테이블): 키-값 쌍을 여러 서버에 분산시킴

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

CAP 정리

CAP(Consistency, Availability, Partition Tolerance theorem): 데이터 일관성(consistency), 가용성(availability), 파티션 감내(aprtition tolerance)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리

• 데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 함
• 가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 함
• 파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미함. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 함

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

• CP 시스템: 일관성과 파티션 감내를 지원. 가용성을 희생함 (은행권 시스템)
• AP 시스템: 가용성과 파티션 감내를 지원. 데이터 일관성을 희생함
• CA 시스템: 일관성과 가용성을 지원. 파티션 남내는 지원하지 않음. 하지만 네트워크 장애는 피할 수 없는 일로 여겨지므로, 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 함 → 따라서 실세계에 CA 시스템은 존재하지 않음

요구사항에 맞도록 CAP 정리를 적용해야 함

시스템 컴포넌트

데이터 파티션

전체 데이터를 한 대 서버에 넣는 것은 불가 → 데이터를 파티션들로 분할한 다음 여러 서버에 분산하여 저장 → 안정 해시 사용

데이터 다중화(replication)

데이터를 N개의 서버에 비동기적으로 다중화 → 해시 링 위에서 시계 방향으로 순회하며 만나는 N개의 서버에 사본 저장

일관성(consistency)

다중화된 데이터는 동기화가 되어야 함 → 정족수 합(Quorum Consensus) 프로토콜 사용

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

• 강한 일관성(strong consistency): 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환해야 함
• 약한 일관성(weak consistency): 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있음
• 최종 일관성(eventual consistency): 약한 일관성의 한 형태로, 갱신 결과가 결국에서 모든 사본에 반영(즉, 동기화)되는 모델

→ 고가용성 시스템에서는 최종 일관성 모델을 택함 → 일관성이 깨어질 수 있음 → 비 일관성 해소 기법: 데이터 버저닝 → 버저닝(versioning)과 벡터 시계(vector clock) 사용

장애 처리

장애 감지

• 장애를 감지한 시스템은 가용성을 보장하기 위해 엄격한 정족수(strict quorum), 또는 느슨한 정족수(sloppy quorum) 접근법을 사용

장애 처리

• 가십 프로토콜(Gossip protocol)과 같은 분산형 장애 감지(decentralized failure detection) 사용
• 일시적 장애 처리: 느슨한 정족수(sloppy quorum) → 임시 위탁(hinted handoff) 기법 사용
• 영구 장애 처리: 반-엔트로피(anti-entropy) 프로토콜과 머클(Merktle) 트리 사용
• 데이터 센터 장애 처리: 데이터를 여러 데이터 센터에 다중화

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

아키텍처의 주요 기능

• 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, 즉 get(key) 및 put(key, value)와 통신함
• 중재자(coordinator)는 클라리언트에게 키-값 저장소에 대한 프록시(proxy) 역할을 하는 노드
• 노드는 안정 해시(consistent hash)의 해시 링(hash ring) 위에 분포함
• 노드를 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산됨(decentralized)d
• 데이터는 여러 노드에 다중화됨
• 모든 노드가 같은 책임을 지므로, SPOF(Single Point of Failure)는 존재하지 않음
• 모든 노드는 기능 전부를 지원해야 함

쓰기 경로(write path)

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

읽기 경로(read path)

1. 데이터가 메모리에 있는지 검사한다. 없으면 2로 감
2. 데이터가 메모리에 없으므로 블룸 필터(Bloom filter)를 검사함
3. 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아냄
4. SSTable에서 데이터를 가져옴
5. 해당 데이터를 클라이언트에게 반환함

요약

분산 키-값 저장소가 가져야 하는 기능/기능 구현에 필요한 기술

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

 

Reference: http://www.yes24.com/Product/Goods/102819435

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - YES24