6장_키-값_저장소_설계.md

6장 키-값 저장소 설계

• 키-값 저장소(데이터베이스)는 비 관계형 데이터베이스
  • 이 저장소에 저장되는 값은 고유 식별자를 키로 가져야 함
  • 키 값 사이의 연결관계를 '키-값' 쌍 이라고 지칭함
• 키-값 쌍에서의 키는 유일해야 하며, 해당 키에 매달린 값은 키를 통해서만 접근할 수 있음
  • 키는 일반 텍스트이거나 해시값일 수 있음
  • 성능상의 이유로 키는 짧을수록 좋음
• 키-값 쌍에서의 값은 문자열, 리스트, 객체일 수 있음 (무엇이 오든 상관하지 않음)
• 대표적인 키-값 저장소: 아마존 다이나모, memcached, 레디스
• 다음 연산을 지원하는 키-값 저장소를 설계해 볼 것
  • put(key, value): 키-값 쌍을 저장소에 저장
  • get(key): 인자로 주어진 키에 매달린 값을 꺼냄

문제 이해 및 설계 범위 확정

• 완벽한 설계는 없다
• 읽기, 쓰기, 메모리 사용량 사이에 어떤 균형을 찾고, 데이터의 일관성과 가용성 사이에서 타협적 결정을 내린 설계를 하면 쓸만한 답안
• 다음 특성을 갖는 키-값 저장소를 설계해 볼 것
  • 키-값 쌍의 크기는 10KB 이하
  • 큰 데이터를 저장할 수 있어야 함
  • 높은 가용성을 제공해야 함 (시스템 장애가 있더라도 빨리 응답해야 함)
  • 높은 규모 확장성을 제공 (트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 함)
  • 데이터 일관성 수준은 조정이 가능해야 함
  • 응답 지연시간이 짧아야 함

단일 서버 키-값 저장소

• 한 서버만 사용하는 경우 가장 직관적인 방법은 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것
  • 빠른 속도가 가능하지만 모든 데이터를 메모리 안에 두는 것이 불가능함
    • 이 문제를 해결하기 위해서는 데이터 압축 혹은 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장
    • 그러나 이렇게 해도 한대로는 부족한 때가 곧 찾아옴
    • 많은 데이터를 저장하기 위해서는 분산 키-값 저장소를 만들 필요가 있음

분산 키-값 저장소

• 키-값 쌍을 여러 서버에 분산시키기 때문에 분산 해시 테이블이라고도 불림
• 분산 시스템을 설계할 때는 CAP 정리를 이해하고 있어야 함

CAP 정리

• 데이터 일관성(consistency), 가용성(availability), 파티션 감내(partition tolerance) 세가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리
• 데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다
• 가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
• 파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크 사이에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다.
• CAP 정리는 이들 한 가운데 어떤 두가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다
• 키 값 저장소는 세가지 요구사항 가운데 어느 두 가지를 만족하느냐에 따라 달라진다
  • CP 시스템: 일관성과 파티션 감내를 지원하는 키-값 저장소. 가용성을 희생
  • AP 시스템: 가용성과 파티션 감내를 지원하는 키-값 저장소. 데이터 일관성을 희생
  • CA 시스템: 일관성과 가용성을 지원하는 키-값 저장소. 파티션 감내는 지원하지 않음.
    • 그러나 네트워크 장애는 피할 수 없는 일이므로, 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 함
    • 따라서 실세계에 CA 시스템은 존재하지 않음

구체적인 사례 살펴보기

• 분산 시스템에서 데이터는 보통 여러 노드에 복제되어 보관됨.
• 세대의 복제 노드 n1, n2, n3에 데이터를 복제하여 보관하는 상황
• 이상적 상태: 네트워크가 파티션되는 상황은 절대로 일어나지 않음
  • n1에 기록된 데이터는 자동적으로 n2와 n3에 복제됨. 데이터 일관성과 가용성도 만족됨
• 실세계의 분산시스템
  • 분산 시스템은 파티션 문제를 피할 수 없음
  • 파티션 문제가 발생하면 일관성과 가용성 사이에서 하나를 선택해야 함
  • n3에 장애가 발생하여 n1 및 n2와 통신할 수 없는 경우 클라이언트가 n1 또는 n2에 기록한 데이터는 n3에 전달되지 않음
  • n3에 기록되었으나 아직 n1 및 n2로 전달되지 않은 데이터가 있다면 n1과 n2는 오래된 사본을 갖고 있을 것
  • CP시스템의 경우: 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1과 n2에 대해 쓰기 연산을 중단시켜야 함
    • 은행권 시스템의 경우 데이터 일관성을 양보하지 않음
    • 온라인 뱅킹 시스템이 계좌 최신 정보를 출력하지 못한다면 큰 문제
    • 네트워크 파티션 때문에 일관성이 깨질 수 있는 상황이 발생하면 이런 시스템은 상황이 해결될 때까지는 오류를 반환해야 함
  • AP시스템의 경우: 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용해야 함
    • n1과 n2는 계속 쓰기 연산을 허용할 것이고, 파티션 문제가 해결된 뒤에 새 데이터를 n3에 전송할 것
• 분산 키-값 저장소를 만들 때는 그 요구사항에 맞도록 CAP 정리를 적용해야 함

시스템 컴포넌트

• 키-값 저장소 구현에 사용될 핵심 컴포넌트들 및 기술들을 살펴볼 것. 다이나모, 카산드라, 빅테이블의 사례를 참고

데이터 파티션

• 대규모 애플리케이션의 경우 전체 데이터를 한 대 서버에 욱여넣는 것은 불가능하기 때문에, 데이터를 작은 파티션들로 분할한 다음 여러대 서버에 저장해야 함
• 데이터를 파티션 단위로 나눌 때는 데이터를 여러 서버에 고르게 분산할 수 있는지, 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화 할 수 있는지를 중요하게 따져봐야 함
• 5장에서 다룬 안정 해시 문제는 위의 문제를 푸는데 적합한 기술
  • 서버를 해시 링에 배치한다. 해시 링에는 s0, s1, ..., s7 여덟 개 서버가 배치되어 있다.
  • 어떤 키-값 쌍을 어떤 서버에 저장할지 결정하려면 우선 해당 키를 같은 링 위에 배치한다.
  • 그 지점으로부터 링을 시계 방향으로 순회하다 만나는 첫 번째 서버가 바로 해당 키-값 쌍을 저장할 서버다.
  • 따라서 key0은 s1에 저장된다
• 안정 해시를 사용하여 데이터를 파티션하면 좋은 점
  • 규모 확장 자동화: 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있음
  • 다양성: 각 서버의 용량에 맞게 가상 노드의 수를 조절할 수 있음. 고성능 서버는 더 많은 가상 노드를 갖도록 설정할 수 있음

데이터 다중화

• 높은 가용성과 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화할 필요가 있다.
• N은 튜닝 가능한 값으로, 어떤 키를 해시 링 위에 배치한 후 그 지점으로부터 시계 방향으로 링을 순회하면서 만나는 첫 N개 서버에 데이터 사본을 보관하는 것.
  
  • N3으로 설정하면 key0은 s1, s2, s3에 저장된다.
• 가상노드를 사용하는 경우 선택한 N개의 노드가 대응될 실제 물리 서버의 개수가 N보다 작아질 수 있다.
  • 노드를 선택할 때 같은 물리 서버를 중복 선택하지 않도록 해야 한다.
• 같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등의 문제를 동시에 겪을 가능성이 있다.
  • 안전성을 담보하기 위해서는 데이터의 사본은 다른 센터의 서버에 보관하고, 센터들은 고속 네트워크로 연결한다.

데이터 일관성

• 여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 한다.
• 정족수 합의 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.
• N = 사본 개수
• W = 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 한다.
• R - 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야 한다.
• N = 3의 경우: 데이터가 s0, s1, s2에 다중화되는 상황
  • W=1인 경우 쓰기 연산이 성공했다고 판단하기 위해 중재자는 최소 한 대 서버로부터 쓰기 응답을 받아야 함
    • s1으로부터 성공 응답을 받았다면, s0, s2로부터의 응답은 기다릴 필요가 없음
• W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정
  • W =1 또는 R = 1 인 경우 한 대 서버로부터의 응답만 받으면 되니 응답 속도는 빠를 것
  • W나 R의 값이 1보다 큰 경우에는 시스템이 보여주는 데이터 일관성의 수준은 향상될 테지만, 응답 속도는 가장 느린 서버로부터의 응답을 기다려야 하므로 느려질 것
  • W + R > N 인 경우에는 강한 일관성이 보장됨. 일관성을 보증할 최신 데이터를 가진 노드가 최소 하나는 겹칠 것이기 때문
• N, W, R 값을 정할 몇 가지 구성을 제시 (요구되는 일관성 수준에 따라 값을 조정하면 됨)
  • R =1, W = N : 빠른 읽기 연산에 최적화된 시스템
  • W = 1, R = N : 빠른 쓰기 연산에 최적화된 시스템
  • W + R > N : 강한 일관성이 보장됨 (보통 N = 3, W = R = 2)
  • W + R <= N : 강한 일관성이 보장되지 않음

• 일관성 모델 : 종류가 다양함. 데이터의 일관성 수준을 결정함
  • 강한 일관성: 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환. 절대로 낡은 데이터를 보지 못함
  • 약한 일관성: 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
  • 최종 일관성: 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(동기화)되는 모델
• 강한 일관성을 달성하는 일반적인 방법은 모든 사본에 현재 쓰기 연솬의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것
  • 새로운 요청의 처리가 중단되기 때문에 고가용성 시스템에는 적합하지 않음
• 다이나모 또는 카산드라는 최종 일관성 모델을 택하고 있음
  • 쓰기 연산적이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있는데, 이 문제는 클라이언트가 해결해야 함

• 비 일관성 해소 기법: 데이터 버저닝
  • 데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성은 높아짐
  • 버저닝과 벡터 시계는 일관성이 깨지는 문제를 해소하기 위해 등장한 기술
  • 버저닝은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미. 따라서 각 버전의 데이터는 변경 불가능
  • 일관성이 어떻게 깨지게 될까?
    • 데이터의 사본이 노드 n1과 n2에 보관되어있는 경우
    • 데이터를 가져오려는 서버 1과 서버 2는 get("name") 연산의 결과로 같은 값을 얻음
    • 서버 1은 "name"에 매달린 값을 "johnSanFrancisco"로 바꾸고 서버 2는 "johnNewYork"로 동시에 바꾸는 경우 충돌하는 v1, v2 두 값을 가지게 됨
    • 이 변경이 이루어진 이후에, 변경이 끝난 옛날 값이기 때문에 원래 값은 무시할 수 있음
    • 하지만 마지막 두 버전 v1과 v2 사이의 충돌은 해결하기 어려워 보임
    • 문제를 해결하기 위해서 충돌을 발견하고 자동으로 해결해 낼 버저닝 시스템이 필요함 (백터 시계가 사용됨)
  • 백터 시계: 서버, 버전 의 순서쌍을 데이터에 매단 것. 어떤 버전이 선행 버전인지, 후행 버전인지, 다른 버전과 충돌이 있는지 판별하는데 쓰임
    • 백터 시계는 D([S1, v1], [S2, v2], ... , [Sn, vn])과 같이 표현한다고 가정
      • D는 데이터, vi는 버전 카운터, si는 서버 번호
      • 데이터 D를 서버 Si에 기록하면, 시스템은 [Si, vi]가 있으면 vi를 증가하거나 없는 경우 새 항목[Si, 1]을 만들어야 함
    • 구체적인 사례
      1. 클라이언트가 데이터 D1을 시스템에 기록. 쓰기 연산을 처리한 서버는 Sx 이므로 벡터 시계는 D1[(Sx, 1)]
      2. 다른 클라이언트가 데이터 D1을 읽고 D2로 업데이트 한 다음 기록. D2는 D1에 대한 변경이므로 D1을 덮어씀. 쓰기 연산은 같은 서버인 Sx가 처리한다고 가정. 벡터 시계는 D2([Sx, 2])로 바뀜
      3. 다른 클라이언트가 D2를 읽어 D3로 갱신한 다음 기록. 이 쓰기 연산은 Sy가 처리한다고 가정. 백터 시계 상태는 D3([Sx, 2], [Sy, 1])로 바뀜
      4. 또 다른 클라이언트가 D2를 읽고 D4로 갱신한 다음 기록. 이 쓰기 연산은 Sz가 처리한다고 가정. 백터 시계는 D4([Sx, 2], [Sz, 1])로 바뀜
      5. 어떤 클라이언트가 D3과 D4를 읽으면 데이터 간 충돌이 있다는 것을 알게 됨. D2를 Sy와 Sz가 각기 다른 값으로 바꾸었기 때문. 이 충돌은 클라이언트가 해소한 후에 서버에 기록. 이 쓰기 연산을 처리한 서버는 Sx였다면 벡터 시계는 D5([Sx, 3], [Sy, 1], [Sz, 1])로 바뀜
    • 벡터 시계를 사용하면 어떤 버전 X가 버전 Y의 이전 버전인지 쉽게 판단 가능
      • 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 모든 구성요소 값보다 같거나 큰지만 보면 됨.
        • 예를 들어 벡터 시계 D([s0, 1], [s1, 1])은 D([s0, 1], [s1, 2])의 이전 버전이므로 두 데이터 사이에 충돌은 없음
      • 어떤 버전 X와 Y 사이에 충돌이 있는지 보려면 Y의 벡터 시계 구성 요소 가운데 X의 벡터 시계 동일 서버 구성요소보다 작은 값을 갖는 것이 있는지 보면 됨
        • 예를 들어 D([S0, 1], [s1, 2])와 D([S0, 2], [S1, 1])는 서로 충돌
    • 벡터 시계를 사용해 충돌을 감지하고 해소하는 방법에는 두가지 단점이 있음
      • 충돌 감지 및 해소 로직이 클라이언트에 들어가야 해서 클라이언트 구현이 복잡해짐
      • [서버: 버전]의 순서쌍 개수가 굉장이 빨리 늘어나기 때문에 길이에 임계치를 설정하고 이상으로 길어지면 오래된 순서쌍을 벡터 시계에서 제거하도록 해야 함.
        • 그러나 이렇게 하면 버전 간 선후 관계가 정확하게 결정될 수 없기 때문에 충돌 해소 과정의 효율성이 낮아지나, 다이나모 데이터베이스에 관계된 문헌에 따르면 아마존은 실제 서비스에서 그런 문제가 벌어지는 것을 발견한 적이 없기 때문에 대부분의 기업에서는 백터 시계는 적용해도 될 것.

장애 처리

• 대다수 규모 시스템에서는 장애는 아주 흔하게 벌어지는 것이므로 장애를 어떻게 처리할 것인지는 중요한 문제
• 장애 감지
  • 한 대의 서버가 죽었다고 해서 바로 서버 A를 장애 처리하지 않음. 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 실제로 장애가 발생했다고 간주
  • 모든 노드 사이에 멀티캐스팅 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법이나, 서버가 많을때는 비효율적
  • 가십 프로토콜 같은 분산형 장애 감지 솔루션이 보다 효율적
    • 각 노드는 멤버십 목록을 유지. 멤버십 목록은 각 멤버 ID와 박동 카운터 쌍의 목록
    • 각 노드는 주기적으로 자신의 박동 카운터를 증가
    • 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보냄
    • 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
    • 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주
  • 예제
    • 노드 s0은 그림 좌측의 테이블과 같은 멤버십 목록을 가짐
    • 노드 s0은 노드 s2(멤버 ID=2)의 박동 카운터가 오랫동안 증가되지 않았다는 것을 발견
    • 노드 s0은 노드 s2를 포함하는 박동 카운터 목록을 무작위로 선택된 다른 노드에게 전달
    • 노드 s2의 박동 카운터가 오랫동안 증가되지 않았음을 발견한 모든 노드는 해당 노드를 장애 노드로 표시
• 일시적 장애 처리
  • 가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해 필요한 조치를 해야함
  • 엄격한 정족수 접근법을 쓴다면 읽기와 쓰기 연산을 금지해야 할 것
  • 느슨한 정족수 접근법은 이 조건을 완화하여 가용성을 높임
    • 정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행한 R개의 건강한 서버를 해시 링에서 고른다. 이때 장애 상태인 서버는 무시함
  • 네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리함
    • 그동안 발생한 변경사항은 해당 서버가 복구되었을때 일괄 반영하여 데이터 일관성을 보존함
    • 이를 위해 임시로 쓰기 연산을 처리한 서버에는 그에 관한 단서를 남겨둠
    • 이런 장애 처리 방안을 단서 후 임시 위탁 기법이라 부름
  • 예제
    • 장애 상태인 노드 s2에 대한 읽기 및 쓰기 연산은 일시적으로 노드 s3가 처리한다
    • s2가 복구되면 s3은 갱신된 데이터를 s2로 인계할 것
• 영구 장애 처리
  • 단서 후 임시 위탁 기법은 일시적 장애를 처리하기 위한 것.
  • 영구적인 노드의 장애 상태를 처리하기 위해 반 엔트로피 프로토콜을 구현하여 사본들을 동기화 것.
    • 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함함
  • 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클 트리를 사용할 것
    • 해시 트리 라고도 불리는 머클 트리는 각 노드에 그 자식 노드들에 보관된 해시, 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리.
    • 해시 트리를 사용하면 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증할 수 있음
  • 키 공간이 1부터 12까지일 때 머클 트리를 만드는 예제 (일관성이 망가진 데이터가 위치한 상자는 다른 색으로 표시해 둠)
    1. 키 공간을 4개의 버킷으로 나눈다
    2. 버킷에 포함된 각각의 키에 균등 분포 해시 함수를 적용하여 해시 값을 계산한다
    3. 버킷별로 해시값을 계산한 후 해당 해시 값을 레이블로 갖는 노드를 만든다.
    4. 자식 노드의 레이블로부터 새로운 해시 값을 계산하여 이진 트리를 상향식으로 구성해 나간다.
  • 두 머클 트리의 비교는 루트 노드의 해시값을 비교하는 것으로 시작. 루트 노드의 해시 값이 일치한다면 두 서버는 같은 데이터를 갖는 것.
    • 루트 노드 값이 다르면 왼쪽 자식 노드의 해시 값을 비교하고, 그 다음으로 오른쪽 자식 노드의 해시 값을 비교함.
    • 아래쪽으로 계속 탐색해 나가다 보면 다른 데이터를 갖는 버킷을 찾을 수 있으므로 그 버킷들만 동기화하면 됨
  • 머클 트리를 사용하면 동기화해야하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터의 총량과는 무관해짐.
    • 하지만 실제로 쓰이는 시스템의 경우 버킷 하나의 크기가 꽤 크다.
      • 가능한 구성 가운데 하나를 예로 들면 10억(1B)개의 키를 백만(1M)개의 버킷으로 관리하는 것인데, 그 경우 하나의 버킷은 1000개의 키를 관리하게 됨
• 데이터 센터 장애 처리
  • 데이터 센터 장애는 정전, 네트워크 장애, 자연재해 등 다양한 이유로 발생할 수 있음
  • 데이터 센터 장애에 대응할 수 있는 시스템을 만들려면 데이터를 여러 데이터 센터에 다중화하는 것이 중요
  • 한 데이터센터가 완전히 망가져도 다른 사용자는 다른 데이터 센터에 보관된 데이터를 이용할 수 있음

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

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

쓰기 경로

• 쓰기 요청이 특정 노드에 전달되는 경우 (카산드라의 사례를 참고함)
  1. 쓰기 요청이 커밋 로그 파일에 기록됨
  2. 데이터가 메모리 캐시에 기록됨
  3. 메모리 캐시가 가득차거나 사전에 정의된 임계치에 도달하면 데이터는 디스크에 있는 SSTable(Sorted-String Table, 키-값 순서쌍을 정렬된 리스트 형태로 관리하는 테이블)에 기록됨

읽기 경로

• 읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지 살피고, 있는 경우 해당 데이터를 클라이언트에게 반환
  • 데이터가 메모리에 없는 경우에는 디스크에서 가져와야 함.
  • 어느 SSTable에 찾는 키가 있는지 알아낼 효율적인 방법이 필요함 (흔히 블룸 필터가 사용됨)
• 데이터가 메모리에 없는 경우 읽기 연산이 처리되는 경로
  1. 데이터가 메모리에 있는지 검사
  2. 데이터가 메모리에 없으므로 블룸 필터를 검사
  3. 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아냄
  4. SSTable에서 데이터를 가져옴
  5. 해당 데이터를 클라이언트에게 반환

요약

• 분산 키-값 저장소가 가져야 하는 기능과 그 기능 구현에 이용되는 기술들