6. 키-값 저장소

💬 키-값 저장소

비 관계형 데이터베이스이다.
키는 유일한 고유식별자여야 하며 짧을수록 성능에 좋다.
값은 문자열, 리스트, 객체 등 어떤 값이든 가능하다.
아마존 다이나모, memcached, redis 등이 이에 해당한다.

단일 서버

모든 데이터를 하나의 메모리 내에 두는 것은 사실 상 불가능하다.
단일 서버를 사용하려면 데이터를 압축해 저장하거나 자주쓰는 데이터만 메모리에 두고 나머지는 디스크에 저장해야 한다.

분산 서버

key-value 쌍을 여러 서버에 분산시키는 형태이다.

CAP 정리

Consistency, Availability, Partition Tolerance theorem
데이터 일관성, 가용성, 파티션 감내를 모두 만족하는 분산 시스템 설계는 불가능하다는 정리이다. 두 가지를 충족하려면 반드시 나머지 하나는 희생된다.
- 데이터 일관성: 어느 서버에 접속하든 항상 같은 데이터를 얻어야 한다.
- 가용성: 일부 서버에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
- 파티션 감내: 두 노드 사이에 통신 장애가 발생했음을 의미하는 파티션이 생기더라도 시스템은 동작해야 한다.
통신 장애는 막을 수 없으므로 파티션 감내는 반드시 충족되어야 한다.
CP 시스템: 가용성을 희생하고 일관성, 파티션 감내를 지원하는 시스템
AP 시스템: 일관성을 희생하고 가용성과 파티션 감내를 지원하는 시스템
일관성 vs 가용성
- 은행권 시스템의 경우 일관성이 더욱 중요 (계좌 정보 등등)
- 가용성을 선택한 시스템(ex 블로그, 카페 등) 은 예전 데이터를 반환할 가능성이 있더라도 끊김 없이 읽기 연산을 허용해야 한다.

💬 분산 키-값 저장소를 위한 컴포넌트 및 기술

데이터 파티션

안정 해시를 사용해 데이터를 파티션하여 다음과 같은 이점을 얻을 수 있다.
- 규모 확장 자동화
  - 시스템 부하에 따라 쉽게 서버를 scale-out, scale-in할 수 있다.
- 다양성
  - 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다. 고성능 서버의 경우 가상 노드를 더 배치하도록 하면 더 많은 데이터가 저장될 것이다.

데이터 다중화

높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 복제해야 한다.
데이터를 여러 서버에 중복 저장해두기 위한 방법으로 해시링에서 시계 방향으로 돌며 N개의 서버에 저장할 수 있으나, 가상 노드를 사용하는 경우 같은 물리 서버를 여러 번 선택하지 않도록 주의해야 한다.
같은 데이터 센터에 속한 서버 노드들은 정전, 네트워크 이슈, 자연재해 등 문제를 동시에 겪을 수 있으므로, 안정성을 위해 데이터 사본은 다른 데이터 센터의 서버에 보관하고 데이터 센터들은 고속 네트워크로 연결해야 한다.

데이터 일관성

Quorum Consensus 프로토콜
- 읽기/쓰기 연산 모두에 일관성을 보장하기 위한 방법이다.
- N개 서버에 사본이 있고, W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 하고, R개의 서버로부터 읽기 연산이 성공했다는 응답을 받아야 한다.
- 중재자
  - 읽기/쓰기 연산이 성공했다는 것을 판단하기 위해 W, R 값을 사용한다. 모든 조건이 만족되는 경우에만 클라이언트로 응답을 보낸다.
  - 클라이언트와 노드 사이에서 프록시 역할을 한다.
  - W, R 값이 1보다 큰 경우 비교적 응답 속도가 느린 두번째 ~ W번째 응답까지 받아야 하므로 전체 응답 속도가 느려질 것이다.
- 강한 일관성 보장을 위해서는 W+R > N 이 되어야 한다. (보통 N=3 , W=R=2)

일관성 모델

종류
- 강한 일관성
  - 읽기 요청 시에 절대로 옛날 데이터를 절대 반환하지 않는다.
  - 모든 사본에 쓰기 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지시켜야 달성 가능하다.
  - 일시적으로 반응하지 않을 수 있어 고가용성 시스템에 적합하지 않다.
- 약한 일관성
  - 읽기 요청 시에 옛날 데이터를 반환할 수도 있다.
- 최종 일관성
  - 최종적으로는 모든 사본에 최신 데이터가 반영되지만, 동기화 과정이 완료되기 전에는 옛날 데이터를 반환할 수 있다.
  - 다이나모, 카산드라 등은 최종 일관성 모델을 택하고 있다.
  - 쓰기 연산이 병렬적으로 발생하면 사본마다 시스템에 저장된 값의 일관성이 깨질 수 있다. 따라서 클라이언트 측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 해야 한다.

비 일관성 해소 모델

데이터 버저닝
- 데이터를 변경할 때마다 데이터의 새로운 버전을 생성하는 방식
- 각 버전의 데이터는 변경 불가능하다.
- 여러 서버에 걸쳐 존재하는 동일 데이터에 동시에 수정이 가해지는 경우, 각 서버 데이터의 마지막 버전이 다를 수 있다.
벡터 시계
- 서버, 버전 순서쌍을 [server1, version1] 형태로 데이터에 매달아둔다. 이 때 서버는 WAS 등을 의미한다.
- 조회 시에 데이터 충돌이 발생했음을 확인하면 직접 해소한 후 서버에 기록한다.
- Data1([Server0, v1], [server1, v1])은 Data1([Server0, v2], [server1, v1]) 의 이전 버전이다.
- Data1([Server0, v1], [server1, v2])과 Data1([Server0, v2], [server1, v1]) 은 충돌이 일어난 상태이다.
- 단점
  - 충돌 감지 및 해소 로직이 서버에 들어가므로 구현이 복잡해진다.
  - 보통 순서쌍 개수가 빠르게 증가하기 때문에, threshold를 설정하여 threshold 이상으로 늘어나면 오래된 순서쌍을 벡터 시계에서 제거해야 한다. 하지만 이렇게 하면 버전 간 선후 관계가 모호해져 충돌 해소 과정의 효율성이 낮아진다.
- 다음은 벡터 시계를 활용한 충돌 해소 플로우이다.
  - 3~4번 과정에서 동시에 쓰기 연산이 처리되어 버전이 충돌된 상태가 된다.
  - 클라이언트가 데이터를 요청하면, 서버 측에서는 버전 충돌이 있다는 정보들을 전달한다.
  - 클라이언트는 서버로부터 받은 정보들을 기반으로 버전 충돌을 해소한 데이터를 서버에 보내 쓰기 연산을 처리하도록 한다.

장애 처리

장애 감지 기법

모든 노드 사이에 multicasting 채널을 구축하는 방법이 있으나, 서버가 많을 경우 연결이 많아져 비효율적이다.

분산형 장애 감지

각 노드마다 heartbeat counter 를 가지며, 주기적으로 증가시킨다.
각 노드마다 membership list가 있고, 그 리스트에는 다른 노드들의 heartbeat counter를 저장해둔다.
각 노드는 무작위로 선정된 노드들에게 heartbeat counter들을 저장해둔 목록을 주기적으로 전송한다.
heartbeat가 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주한다.

일시적 장애 처리

sloppy quorum
- 쓰기 연산을 수행할 정상 서버와 읽기 연산을 수행할 정상 서버를 각각 해시 링에서 고른다.
- 장애가 발생한 노드에 저장되었어야 할 것을 임시로 다른 서버에 저장해두게 된다. 이 때 임시 데이터에는 hint를 남겨두어야 한다. (hinted handoff)
- 장애 발생하였던 서버가 복구되면 그동안 발생한 변경사항들을 일괄 반영받는다.

영구 장애 처리

anti entropy 프로토콜을 통해 사본들을 비교한 후 최신 버전으로 갱신하여 사본들을 동기화해야 한다.
사본들끼리 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 머클 트리를 사용할 수 있다.
머클 트리란 자식 노드들에 보관된 값의 해시 / 자식 노드들의 레이블로부터 계산된 해시 값을 부모 노드의 레이블로 붙여두는 트리이다.
머클 트리 만드는 과정
- 키 공간을 버킷 단위로 나누고 키에 uniform hash 함수를 적용한다.
- 버킷 단위로 해시 값을 계산하여 해시 값을 레이블로 갖는 노드를 만든다.
- 자식 노드의 레이블로부터 해시 값을 계산해 이진 트리를 만들어나간다.
머클 트리를 비교할 때에는 부모 노드에서 자식 노드로 이동하며 값이 동등한지 확인한다. 만약 값이 다르다면 일관성이 깨진 상황이므로 해당 버킷들에 존재하는 데이터를 동기화해주어야 한다.

💬 데이터 쓰기/읽기

쓰기 경로

쓰기 요청이 먼저 커밋 로그에 기록되고, 그 다음 메모리 캐시에 저장한다.
메모리 캐시가 가득 차거나 특정 조건이 되면 데이터가 디스크의 SSTable(Sorted String Table)에 기록된다.

읽기 경로

데이터가 메모리 캐시에 있으면 바로 반환한다.
데이터가 메모리 캐시에 없다면 블룸 필터를 검사하여 어떤 SSTable에 키가 존재하는지 확인한 후 데이터를 가져온다.

Previous5. 안정 해시 Next7. 유일한 ID 생성기

Last updated 22 days ago

6. 키-값 저장소

💬 키-값 저장소

비 관계형 데이터베이스이다.
키는 유일한 고유식별자여야 하며 짧을수록 성능에 좋다.
값은 문자열, 리스트, 객체 등 어떤 값이든 가능하다.
아마존 다이나모, memcached, redis 등이 이에 해당한다.

단일 서버

모든 데이터를 하나의 메모리 내에 두는 것은 사실 상 불가능하다.
단일 서버를 사용하려면 데이터를 압축해 저장하거나 자주쓰는 데이터만 메모리에 두고 나머지는 디스크에 저장해야 한다.

분산 서버

key-value 쌍을 여러 서버에 분산시키는 형태이다.

CAP 정리

Consistency, Availability, Partition Tolerance theorem
데이터 일관성, 가용성, 파티션 감내를 모두 만족하는 분산 시스템 설계는 불가능하다는 정리이다. 두 가지를 충족하려면 반드시 나머지 하나는 희생된다.
- 데이터 일관성: 어느 서버에 접속하든 항상 같은 데이터를 얻어야 한다.
- 가용성: 일부 서버에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
- 파티션 감내: 두 노드 사이에 통신 장애가 발생했음을 의미하는 파티션이 생기더라도 시스템은 동작해야 한다.
통신 장애는 막을 수 없으므로 파티션 감내는 반드시 충족되어야 한다.
CP 시스템: 가용성을 희생하고 일관성, 파티션 감내를 지원하는 시스템
AP 시스템: 일관성을 희생하고 가용성과 파티션 감내를 지원하는 시스템
일관성 vs 가용성
- 은행권 시스템의 경우 일관성이 더욱 중요 (계좌 정보 등등)
- 가용성을 선택한 시스템(ex 블로그, 카페 등) 은 예전 데이터를 반환할 가능성이 있더라도 끊김 없이 읽기 연산을 허용해야 한다.

💬 분산 키-값 저장소를 위한 컴포넌트 및 기술

데이터 파티션

안정 해시를 사용해 데이터를 파티션하여 다음과 같은 이점을 얻을 수 있다.
- 규모 확장 자동화
  - 시스템 부하에 따라 쉽게 서버를 scale-out, scale-in할 수 있다.
- 다양성
  - 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다. 고성능 서버의 경우 가상 노드를 더 배치하도록 하면 더 많은 데이터가 저장될 것이다.

데이터 다중화

높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 복제해야 한다.
데이터를 여러 서버에 중복 저장해두기 위한 방법으로 해시링에서 시계 방향으로 돌며 N개의 서버에 저장할 수 있으나, 가상 노드를 사용하는 경우 같은 물리 서버를 여러 번 선택하지 않도록 주의해야 한다.
같은 데이터 센터에 속한 서버 노드들은 정전, 네트워크 이슈, 자연재해 등 문제를 동시에 겪을 수 있으므로, 안정성을 위해 데이터 사본은 다른 데이터 센터의 서버에 보관하고 데이터 센터들은 고속 네트워크로 연결해야 한다.

데이터 일관성

Quorum Consensus 프로토콜
- 읽기/쓰기 연산 모두에 일관성을 보장하기 위한 방법이다.
- N개 서버에 사본이 있고, W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 하고, R개의 서버로부터 읽기 연산이 성공했다는 응답을 받아야 한다.
- 중재자
  - 읽기/쓰기 연산이 성공했다는 것을 판단하기 위해 W, R 값을 사용한다. 모든 조건이 만족되는 경우에만 클라이언트로 응답을 보낸다.
  - 클라이언트와 노드 사이에서 프록시 역할을 한다.
  - W, R 값이 1보다 큰 경우 비교적 응답 속도가 느린 두번째 ~ W번째 응답까지 받아야 하므로 전체 응답 속도가 느려질 것이다.
- 강한 일관성 보장을 위해서는 W+R > N 이 되어야 한다. (보통 N=3 , W=R=2)

일관성 모델

종류
- 강한 일관성
  - 읽기 요청 시에 절대로 옛날 데이터를 절대 반환하지 않는다.
  - 모든 사본에 쓰기 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지시켜야 달성 가능하다.
  - 일시적으로 반응하지 않을 수 있어 고가용성 시스템에 적합하지 않다.
- 약한 일관성
  - 읽기 요청 시에 옛날 데이터를 반환할 수도 있다.
- 최종 일관성
  - 최종적으로는 모든 사본에 최신 데이터가 반영되지만, 동기화 과정이 완료되기 전에는 옛날 데이터를 반환할 수 있다.
  - 다이나모, 카산드라 등은 최종 일관성 모델을 택하고 있다.
  - 쓰기 연산이 병렬적으로 발생하면 사본마다 시스템에 저장된 값의 일관성이 깨질 수 있다. 따라서 클라이언트 측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 해야 한다.

비 일관성 해소 모델

데이터 버저닝
- 데이터를 변경할 때마다 데이터의 새로운 버전을 생성하는 방식
- 각 버전의 데이터는 변경 불가능하다.
- 여러 서버에 걸쳐 존재하는 동일 데이터에 동시에 수정이 가해지는 경우, 각 서버 데이터의 마지막 버전이 다를 수 있다.
벡터 시계
- 서버, 버전 순서쌍을 [server1, version1] 형태로 데이터에 매달아둔다. 이 때 서버는 WAS 등을 의미한다.
- 조회 시에 데이터 충돌이 발생했음을 확인하면 직접 해소한 후 서버에 기록한다.
- Data1([Server0, v1], [server1, v1])은 Data1([Server0, v2], [server1, v1]) 의 이전 버전이다.
- Data1([Server0, v1], [server1, v2])과 Data1([Server0, v2], [server1, v1]) 은 충돌이 일어난 상태이다.
- 단점
  - 충돌 감지 및 해소 로직이 서버에 들어가므로 구현이 복잡해진다.
  - 보통 순서쌍 개수가 빠르게 증가하기 때문에, threshold를 설정하여 threshold 이상으로 늘어나면 오래된 순서쌍을 벡터 시계에서 제거해야 한다. 하지만 이렇게 하면 버전 간 선후 관계가 모호해져 충돌 해소 과정의 효율성이 낮아진다.
- 다음은 벡터 시계를 활용한 충돌 해소 플로우이다.
  - 3~4번 과정에서 동시에 쓰기 연산이 처리되어 버전이 충돌된 상태가 된다.
  - 클라이언트가 데이터를 요청하면, 서버 측에서는 버전 충돌이 있다는 정보들을 전달한다.
  - 클라이언트는 서버로부터 받은 정보들을 기반으로 버전 충돌을 해소한 데이터를 서버에 보내 쓰기 연산을 처리하도록 한다.

장애 처리

장애 감지 기법

모든 노드 사이에 multicasting 채널을 구축하는 방법이 있으나, 서버가 많을 경우 연결이 많아져 비효율적이다.

분산형 장애 감지

각 노드마다 heartbeat counter 를 가지며, 주기적으로 증가시킨다.
각 노드마다 membership list가 있고, 그 리스트에는 다른 노드들의 heartbeat counter를 저장해둔다.
각 노드는 무작위로 선정된 노드들에게 heartbeat counter들을 저장해둔 목록을 주기적으로 전송한다.
heartbeat가 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주한다.

일시적 장애 처리

sloppy quorum
- 쓰기 연산을 수행할 정상 서버와 읽기 연산을 수행할 정상 서버를 각각 해시 링에서 고른다.
- 장애가 발생한 노드에 저장되었어야 할 것을 임시로 다른 서버에 저장해두게 된다. 이 때 임시 데이터에는 hint를 남겨두어야 한다. (hinted handoff)
- 장애 발생하였던 서버가 복구되면 그동안 발생한 변경사항들을 일괄 반영받는다.

영구 장애 처리

anti entropy 프로토콜을 통해 사본들을 비교한 후 최신 버전으로 갱신하여 사본들을 동기화해야 한다.
사본들끼리 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 머클 트리를 사용할 수 있다.
머클 트리란 자식 노드들에 보관된 값의 해시 / 자식 노드들의 레이블로부터 계산된 해시 값을 부모 노드의 레이블로 붙여두는 트리이다.
머클 트리 만드는 과정
- 키 공간을 버킷 단위로 나누고 키에 uniform hash 함수를 적용한다.
- 버킷 단위로 해시 값을 계산하여 해시 값을 레이블로 갖는 노드를 만든다.
- 자식 노드의 레이블로부터 해시 값을 계산해 이진 트리를 만들어나간다.
머클 트리를 비교할 때에는 부모 노드에서 자식 노드로 이동하며 값이 동등한지 확인한다. 만약 값이 다르다면 일관성이 깨진 상황이므로 해당 버킷들에 존재하는 데이터를 동기화해주어야 한다.

💬 데이터 쓰기/읽기

쓰기 경로

쓰기 요청이 먼저 커밋 로그에 기록되고, 그 다음 메모리 캐시에 저장한다.
메모리 캐시가 가득 차거나 특정 조건이 되면 데이터가 디스크의 SSTable(Sorted String Table)에 기록된다.

읽기 경로

데이터가 메모리 캐시에 있으면 바로 반환한다.
데이터가 메모리 캐시에 없다면 블룸 필터를 검사하여 어떤 SSTable에 키가 존재하는지 확인한 후 데이터를 가져온다.

Previous5. 안정 해시 Next7. 유일한 ID 생성기

Last updated 22 days ago