Design Key-Value Store

키-값 저장소는 키-값 데이터베이스라고도 불리는 비 관계형 데이터베이스다.

• key

  • 데이터를 식별하는 데 사용되는 유일한 값

  • 일반 텍스트, 숫자, UUID, 해시 등이 될 수 있음

  • 성능상 키 길이는 짧을수록 좋음

• value

  • 보통 무슨 값이든 될 수 있음

  • key를 통해서만 접근 가능

키-값 저장소를 설계할 때는 다음과 같은 요구사항을 고려해볼 수 있다.

• 키-값 쌍의 크기

• 큰 데이터 저장 가능

• 높은 가용성 제공

• 높은 규모 확장성(자동적으로 서버 증설/삭제 가능)

• 데이터 일관성 수준 조정 가능

• 짧은 응답 시간

하나의 서버만 사용하는 키-값 저장소는 데이터 전부를 메모리에 해시 테이블로 저장하는 등 간단한 방법으로 구현 가능하다. 하지만 이 방법은 데이터가 많아지면 모든 데이터를 메모리 안에 두는 것이 불가능하여 아래의 방법으로 개선해볼 수 있다.

• 데이터 압축

• 자주 쓰이는 데이터만 메모리에 저장(나머지는 디스크에 저장)

하지만 이 방법도 하나의 서버로 부족해질 수 있기 때문에, 더 많은 데이터를 저장하기 위해선 분산 키-값 저장소를 사용해야 한다.

분산 키-값 저장소

분산 키-값 저장소에 구현에 필요한 핵심 컴포넌트와 기술들은 다음과 같다.

1. 데이터 파티션

모든 데이터를 한 대의 서버에 넣는 것은 불가능하므로, 데이터를 여러 파티션들로 나누어 저장해야 한다. 안정 해시 기법을 사용해서 데이터를 여러 서버에 고르게 분산하고, 노드 추가 삭제 시 데이터 재배치 최적화를 할 수 있다.

2. 데이터 다중화(replication)

N개의 서버에 비동기적으로 다중화하여 높은 가용성과 안정성을 확보할 수 있다.(N은 튜닝 가능한 값)

3. 데이터 일관성(consistency)

정족수 합의(Quorum Consensus) 프로토콜을 사용하여 다중화된 데이터 일관성을 보장할 수 있다. 아래의 값을 조정하여 쓰기와 읽기 연산의 일관성 수준을 조절할 수 있다.

• W: 쓰기 연산 성공 응답 필요 수, 설정한 개수 이상의 서버가 쓰기 성공하면 쓰기 연산을 성공한 것으로 간주(나머지 서버에 저장을 하지 않는 다는 것은 아님)

• R: 읽기 연산 응답 성공 필요 수, 설정한 개수 이상의 서버에서 읽기 성공하면 읽기 연산을 성공한 것으로 간주

W, R, N 세 가지 값에 따라 다음과 같은 시스템을 구성할 수 있다.(N=사본 수)

• R=1, W=N: 빠른 읽기 연산에 최적화된 시스템

• W=1, R=N: 빠른 쓰기 연산에 최적화된 시스템

• W+R > N: 강한 데이터 일관성을 보장하는 시스템

• W+R <= N: 강한 데이터 일관성을 보장하지 않는 시스템

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

일관성 모델은 키-값 저장소를 설계할 때 고려해야할 중요한 요소 중 하나인데, 그 종류는 다음과 같다.

• 강한 알관성: 모든 읽기 연산이 가장 최근에 갱신된 결과 반환

• 약한 일관성: 모든 읽기 연산이 최근에 갱신된 결과를 반환하지 않을 수 있음

• 최종 일관성: 약관 일관성의 한 형태로, 갱신 결과가 결국 모든 사본에 반영되는 모델

고가용성 시스템을 제공하기 위해 최종 일관성 모델을 택하는 경우가 많은데, 데이터 버저닝을 사용해 일관성 불일치 해소를 하고 있다. (벡터 시계 참고)

5. 장애 감지

분산 시스템에서는 하나의 서버가 다른 서버의 장애 진단을 하지 않고, 두 대 이상의 서버가 똑같이 장애를 감지해야 한다. 모든 노드 사이를 연결하여 장애를 감지하는 방법도 있지만, 이 방법은 네트워크 비용이 많이 들기 때문에 효율적이지 않다. 분산형 장애 감지 솔루션인 가십 프로토콜을 사용할 수 있는데, 다음과 같은 방식으로 동작한다.

1. 각 노드마다 멤버십 정보 유지

2. 각 노드는 주기적으로 다른 노드에게 주기적으로 메시지 전송

3. 메시지를 받은 노드는 자신의 멤버십 정보를 최신 값으로 갱신

4. 멤버십 노드 중 지정된 시간 이상 갱신되지 않으면 장애로 간주

5. 장애를 발견한 노드는 다른 노드에게 멤버십 정보 전달

6. 갱신되지 않은 것을 확인한 노드는 해당 노드를 장애 노드로 표시

6. 장애 처리

장애를 감지하면 해당 노드 대신 다른 노드가 잠시 맡아 처리하고, 복구가 됐을 때 변경사항을 일괄 반영하여 일관성을 보존할 수 있도록 한다.(=임시 위탁 기법) 하지만 이 방법은 일시적인 장애만 처리할 수 있고, 영구적인 장애를 처리하기 위해선 반-엔트로피 프로토콜을 구현하여 사본들을 동기화하여 처리할 수 있다.

참고자료

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