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에 키가 존재하는지 확인한 후 데이터를 가져온다.

Last updated