분산 키-값 저장소 설계

[가상 면접 사례로 배우는 대규모 시스템 설계]를 읽고 작성하는 포스트입니다. 

틀린 내용이 있을 수도 있습니다! 

틀린 내용이 있다면 댓글로 달아주시면 감사하겠습니다!

 

 

이번 챕터에서는 키-값 저장소 설계에 대해서 공부한 내용을 정리했다. 

 

키 값 저장소란?

키 값 저장소는 비 관계형 데이터베이스로 키-값 데이터 쌍을 저장하며,

내부의 데이터는 키를 통해서만 접근할 수 있기 때문에 키를 고유 식별자로 가져야 한다.

키는 일반 텍스트 일수도 있고, 해시 값일 수도 있다. 

키는 성능상의 이유로 짧을수록 좋으며, 값은 문자열, 객체, 리스트 등 어떤 값도 가능하다. 

대표적인 키 값 저장소로 다이나모 DB, Memcached, Redis 등이 있다. 

 

 

어떠한 특징을 갖는 키-값 저장소를 살펴볼 것인가?

 해당 챕터에서는 다음과 같은 특징을 갖는 키-값 저장소를 살펴본다. 

1. 키 값 쌍의 크기는 10 kb 이하

2. 큰 데이터를 저장할 수 있어야 함

3. HA를 제공

4. Scaling을 제공

5. 데이터 Consistency를 조절 가능해야 함

6. Latency가 짧아야 함 

 

 

단일 서버 형태의 키 값 저장소는 어떻게 설계할까?

한 대의 서버만 사용하는 경우, 간단하다. 

해시 테이블 형태로 키-값 쌍 전부를 메모리에 저장한다. 

메모리에 저장하기 때문에 용량의 한계에 부딪칠 수도 있는데, 이때는 다음과 같은 방식으로 개선할 수 있다.

1. 데이터 압축

2. 자주 쓰이는 데이터만 메모리에 적재하고, 잘 쓰지 않는 데이터는 디스크에 저장 

 

하지만 서버 한대만 사용하는 것은 어느 순간부터 한계가 올 수 있다.

따라서 분산 키-값 저장소를 사용할 필요가 있다. 

 

 

분산 키-값 저장소란?

키-값 쌍을 단일 서버가 아닌 여러 서버에 걸쳐서 분산시켜 저장하는 방식이다. 

분산 설계를 할때는 CAP 정리를 알 필요가 있다. 

 

CAP 정리란?

CAP 정리는 다음과 같은 사항들을 모두 만족하는 분산 시스템 설계는 불가능하다는 정리다.

 

1. Consistency(일관성): 모든 노드들은 같은 데이터를 들고 있어야 한다.  

2. Availablity(가용성): 일부 노드에 장애가 발생해도 항상 응답을 받을 수 있어야 한다. 

3. Partion Tolerance(파티션 감내): 네트워크 장애가 발생해도 시스템은 동작해야 한다. 

 

위 3가지 조건 중 최대 두 가지만 만족시킬 수 있다. 

그리고 실제 환경에서는 네트워크 장애는 피할 수 없는 장애로 간주되기 때문에, Partition Tolerance는 반드시 만족해야 한다. 

따라서 분산 시스템을 설계할 때 일관성과 가용성 중에서 하나만 고를 수 있다. 

일관성을 선택하면 CP 시스템, 가용성을 선택하면 AP 시스템이 된다.

참고로 실세계에서는 CA 시스템은 존재하지 않는다

 

예를 들면, 은행과 같이 일관성을 중요시하는 환경에서는 CP 시스템을 선택한다.

온라인 뱅킹 시스템에서 계좌의 최신 정보를 출력하지 못한다면 큰 문제가 될 수 있기 때문이다. 

 

 

분산 키-값 저장소 설계를 위한 핵심 컴포넌트 기술

1. 데이터 파티션

대규모 애플리케이션의 경우 모든 데이터를 한 대의 서버에 몰아서 넣은 것은 불가능하다.

따라서 여러 서버에 데이터를 고르게 분산시켜서 저장을 해야 하는데,

이때 서버가 추가되거나 삭제될 때 데이터의 이동을 최소화해야 한다. 

그래서 이를 위해 안정 해시라는 방법을 사용하며, 자세한 내용은 다음 글을 참고하자. 

안정 해시 설계

 

결론적으로 안정 해시를 이용하면 서버를 증설하거나 제거했을 때의 키 재배치 문제를 해결할 수 있게 된다.  

즉, 규모 확장 자동화가 가능해진다.

 

또한 가상 노드를 이용하여, 사양이 서로 다른 서버에 맞게 데이터를 고루 분산시킬 수 있다.

예를 들면, 고성능 서버에 더 많은 가상 노드를 할당하여 해당 노드에 데이터를 더 많이 저장할 수 있다. 

 

2. 데이터 다중화

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

 

안정 해시를 이용하면 데이터 다중화 또한 다음과 같이 해결할 수 있다. 

어떤 키가 해시 링위에 배치되어 있을 때, 해당 키에서 시계방향으로 N개의 서버에 데이터 사본을 보관한다. 

 

주의해야 할 점은 가상 노드를 사용하게 되면 같은 서버에 키를 중복해서 저장하는 상황이 생길 수도 있다.

또한 같은 데이터센터에 있는 서버에만 키를 저장하게 되면,

정전, 네트워크 이슈, 자연재해 등의 문제를 동시에 겪을 수도 있기 때문에 가능하다면 여러 데이터 센터에 걸쳐 다중화를 해야 한다.

 

3. 데이터 일관성

데이터가 다중화되어 있을 때, 원본 데이터는 사본 데이터와 적절하게 동기화가 되어야 한다. 

데이터 동기화에는 주로 정족수 합의 알고리즘을 사용하여 읽기/쓰기 연산 모두에 일관성을 보장한다. 

 

정족수 합의에 대한 자세한 내용은 다음 글을 참고한다. 

 

정족수 합의 알고리즘

 

4. 일관성 불일치 해소

데이터를 다중화하면 가용성은 높아지지만, 일관성이 깨질 가능성은 높아진다. 

versioning과 벡터 시계를 통해서 이를 해소할 수 있다. 

 

벡터 시계는 D([s1, v1], [s2, v2], [s3, v3]...) 와 같이 표현한다고 가정한다.

D는 데이터이고, vi는 버전 카운터, si는 서버 번호이다. 

만약 데이터 D를 si에 기록하면 다음과 같은 작업 중 하나를 수행한다.

- [si, vi]가 있으면, vi를 증가시킨다.

- [si, vi]가 없다면, [si, 1]을 새로 만든다. 

 

다음과 구체적 사례를 통해서 알아보자. 

벡터 시계를 이용해서 위와 같은 규칙을 통해 어떤 버전 x가 버전 Y의 이전 버전인지 쉽게 판단할 수 있다. 

주목할 부분이 있다면, 마지막 5번에서는 클라이언트가 D3과 D4를 읽으면 데이터 간 충돌이 있다는 것을 알게 되고, 

이 충돌은 클라이언트가 해소한 후, 서버에 기록한다. 

 

정리하다가 개인적으로 잘 이해가 안 되는 부분이 있는데, 

3번과 4번 과정에서 쓰기 한 내용들은 무시한 후, 기존의 데이터에 쓰기 작업을 해도 되는지에 대해서는 잘 모르겠다. 

 

위와 같이 벡터 시계와 버저닝을 이용해서 충돌을 감지하고 해소할 수 있지만, 이 또한 다음과 같은 단점을 지닌다.  

1. 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하기 때문에 클라이언트 구현이 복잡해진다. 

2. 서버: 버전 순서쌍의 개수가 굉장히 빨리 늘어나기 때문에 임계치를 두어 순서쌍을 관리해야 한다. 

그런데 임계치를 넘어 오래된 순서쌍을 제거하게 된다면, 버전 간 선후 관계를 정화하게 결정할 수 없기 때문에 충돌 해소 과정의 효율성이 낮아지게 된다. 하지만 아마존의 다이나모 DB에 의하면 실제 서비스에서 그런 문제가 벌어지는 것을 발견한 적이 없다고 한다. 

 

5. 장애 감지 

분산 시스템에서는 한 대의 서버가 A 서버 한대가 죽었다고 해서 바로 장애처리를 하지 않는다. 

보통 두대 이상의 서버가 A 서버가 죽었다고 해야 장애처리를 한다. 

 

모든 노드 사이에 멀티 캐스팅 채널을 구축하는 것은 서버 장애를 감지하는 쉬운 방법이지만,

노드의 수가 늘어난다면 이 방법은 비효율적이다. 

 

그래서 분산 환경에서는 다음과 같이 gossip 프로토콜과 솔루션을 채택하여 장애를 감지한다. 

분산 환경에서의 장애감지: Gossip Protocol

 

6. 장애처리

gossip protocol로 서버의 장애를 감지한 후, 시스템은 가용성을 보장하기 위해 필요한 조치를 해야 한다. 

 

1. 일시적 장애 처리

 

정족수를 느슨하게 구성하여 가용성을 높인 후, 임시로 다른 서버가 장애 난 서버를 대신해서 일을 처리 

이를 위해 임시로 쓰기 연산을 처리한 서버에는 그에 관한 Hint를 남겨둠

장애가 발생한 서버가 복구되었을 때, 그동안 발생한 변경사항을 일괄 반영하여 데이터 일관성을 보존한다. 

이를 단서 후 임시 위탁(hinted handoff) 기법이라 한다. 

 

2. 영구 장애 처리

반엔트로피 프로토콜을 이용하여 사본들을 동기화하고, 사본 간의 일관성이 깨진 부분을 탐지하여 전송 데이터 양을 줄일 수 있다.  

이 반엔트로피 프로토콜은 Merkle 트리를 이용한다. 

머클 트리는 해시 트리라고도 불리는데,

해시 트리는 각 노드에 자식 노드들에 보관된 값에 대한 해시 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여 놓은 트리다.  

 

머클 트리에 대한 자세한 내용은 다음 내용을 참고하면 좋을 듯하다.

https://steemit.com/kr/@brownbears/merkle-tree

1-2. 머클트리(merkle tree)란? — Steemit

 

3. 데이터 센터 장애 처리

데이터 센터에서는 정전, 네트워크 장애, 자연재해 등 다양한 원인에 의해서 장애가 발생할 수 있다.

이에 대한 대안으로 여러 데이터 센터에 걸쳐서 데이터를 다중화하는 방법을 사용할 수 있다. 

사용자는 한 데이터 센터에 문제가 발생해도 다른 데이터 센터에 보관된 데이터를 통해서 데이터를 제공받을 수 있을 것이다.

 

 

노드 내부에서 일어나는 일 

1. 쓰기 요청이 들어왔을 때 

1) 제일 먼저 쓰기 요청은 커밋 로그 파일(디스크)에 기록된다.  

2) 데이터가 메모리 캐시에 기록된다. 

3) 메모리 캐시가 가득 차거나 임계치에 도달하면 데이터는 SSTable(Sorted-string table)(디스크)에 저장된다. 

  여기서 SSTable은 키-값 쌍을 정렬된 리스트 형태로 관리하는 테이블이다. 

 

2. 읽기 요청이 들어왔을 때 

1) 제일 먼저 데이터가 메모리에 있는지 검사한다.  

2) 데이터가 메모리에 없으면 블룸 필터를 검사한다.

  여기서 블룸 필터는 어떤 SSTable에 원하는 키가 있는지 효율적으로 찾아낼 수 있다. 

3) 블룸 필터를 통해 어떤 SSTable에서 원하는 데이터가 있는지 알아낸다.

4) SSTable에서 데이터를 가져와 클라이언트에게 반환 

 

 

요약  

1. 읽기 연산에 있어 고가용성을 보장하기 위해, 데이터 다중화를 이용한다. 

2. 쓰기 연산에 있어 고가용성을 보장하기 위해, 버저닝 및 벡터 시계를 이용하여 데이터 충돌 문제를 해소한다. 

3. 안정 해시를 통해서 대규모 데이터 저장, 데이터 파티션, 규모 확장성 등을 제공할 수 있다. 

4. 정족수 합의를 통해서 일관성 수준을 조절할 수 있다. 

5. 일시적 장애에 대응하기 위해 느슨한 정족수 프로토콜 + 단서 후 임시 위탁 기법을 사용한다.

6. 영구적 장애에 대응하기 위해 머클 트리를 이용한다. 

7. 데이터 센터 장애에 대응하기 위해선 여러 데이터 센터에 걸쳐서 다중화하는 방식을 이용한다.