[Chapter 06] Q&A

[travelbeeee]

[Chapter 06] 키-값 저장소 설계

• 궁금한 점 혹은 이야기하고 싶은 주제 코멘트로 정리
• 추가로 같이 보면 좋을 것 같은 기술 블로그, 아티클 등 공유

[zziri]

지훈

• 정족수?? (Quorum Consensus)
  • 의사 결정하는데에 필요한 최소한의 출석 인원...
• 모든 노드가 같은 책임을 지므로, SPOF는 존재하지 않는다
  • SPOF(Single Point Of Failure)
    • https://www.techtarget.com/searchdatacenter/definition/Single-point-of-failure-SPOF
    • A single point of failure (SPOF) is a potential risk posed by a flaw in the design, implementation or configuration of a circuit or system.
    • 하나의 오류로 인해서 시스템 전체 장애가 되지 않는다
    • 책임을 나누게 되면 하나의 오류로 시스템 전체 장애로 이어질 수 있으나, 동일한 책임을 가지게 되면 그렇지 않음
• SSTable
  • https://velog.io/@yunhongmin/SSTable-data-storage
• Bloom Filter
  • https://steemit.com/kr-dev/@heejin/bloom-filter

[travelbeeee]

현석

• CAP 추가 정리 및 궁금증
  • ❓ CAP를 동시에 만족할 수 없는 이유
  • AP를 만족하려면 동일한 데이터를 한 노드가 아니라 여러 노드에서 저장하고 있어야 된다. ( 네트워크에 파티션이 생기더라도 시스템은 계속 동작하고, 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 되므로 )
  • --> 1번 노드에서 데이터를 수정하고, 다른 여러 노드로 전달하는 과정에서 2,3,4번 노드에는 수정한 데이터가 전달되고, 5,6번 노드에는 전달되지 못한 상태로 1번 노드가 죽는다.
  • => C (데이터 일관성) 이 깨지게 된다.
  • Brewer's Theorem
  • P ( 파티션 감내 ) 는 실제 네트워크 상황에서 무조건 발생한다고 가정
  • P는 발생한다 --> 발생했을 때, C / A 둘 중에 어떤 조건을 만족하냐에 따라 CP, AP 시스템
  • CA 를 유지하려면 서로 다른 노드에서 통신이 필요 --> P 가 무조건 필요하게 된다.

[easyfordev]

이지

Question

• 성능 상의 이유로 Key의 길이는 짧을수록 좋다고 하는데, 구체적으로 왜 그렇게 되는것인지 아시나요?
  • RDB의 원리를 참고해보면 : key의 용량 커지면 -> 용량이 한정되어 있기 때문에, page의 갯수와 key의 사이즈가 반비례하기 때문에,,, -> 디스크 접근을 많이 하면 느려짐
    • 이거랑 비슷하지 않을까?
  • 메모리 관점 : https://mozi.tistory.com/522
• 벡터시계... 어렵네요! (쉽게 설명해주실분 구합니다)
• 머클트리도 ... 어렵네요
• bloom filter(블룸필터)란? 더 찾아보자

Comment

• 확실히 알고가자! 데이터 일관성 <----> 가용성, latency
• 파티션(Partition)이라는 것이 내가 기존에 알고있던 의미와 달랐다
  • 알고있던 파티션 : 데이터를 분산 저장하는 것. 분산 키가 파티션 키(생각해보니 이건 파티셔닝 인듯..?)
  • 책에서 나온 파티션 감내, 파티션 : 두 노드 사이에 통신 장애가 발생한 것
• 안정 해시에서 고성능 서버는 더 많은 가상 노드를 갖도록 설정할 수 있다고 한다.
  • 드디어 지난주에 이해가 안됐던 부분이 완전히 이해가 되었다! 가상 노드가 하나의 찐 노드를 여러개의 가상노드로 쓰는 개념이었구나. 그래서 가상노드가 너무 많으면 (당연히) 메모리 부족이 있을 수 있는거...
• Quorum Consensus
  • 정족수라는 번역이 조금 마음에 안든다.
  • 보통 쿼럼을 구성할 때 서버는 홀수대로 구성해야 한다. (과반수를 정확하게 판단할 수 있어야 해서)
  • 참고) Apache Zookeeper
• 데이터 일관성에서 W, R 의 예시 : Kafka producer의 acks 옵션
• 장애 감지 기법 중 가십 프로토콜(gossip protocol)
  • 박동 카운터 ㅋㅋ그냥 heartbeat가 말이 더 쉽다

[kihyun-yang]

기현

CAP 이론의 한계

• CAP 이론에 따르면 분산 시스템은 CP이거나 AP여야 한다.
  • P는 네트워크 장애가 있을 수 있다는 것을 인정하느냐의 문제이고 이는 인정 할 수밖에 없는 문제이므로 처음부터 선택되어 있다는 것.
• 결국 CAP 이론은 분산 시스템에서 네트워크 장애 상황일 때 일관성과 가용성 중 하나만 선택할 수 있다는 것.
  • 즉, CAP 이론은 네트워크 장애가 없는 정상 상황에 대해 설명하지 못한다.

PACELC 이론

• PACELC 이론은 CAP 이론으로 부족한 부분을 보완하기 위해 네트워크 장애 상황과 정상 상황으로 나누어 설명하는 이론.
• 네트워크 분할이 발생했다면 CAP 이론에서 제시한 가용성과 일관성 사이의 trade-off가, 그렇지 않다면 지연시간과 일관성 사이의 trade-off가 있음을 의미

참고

• http://eincs.com/2013/07/misleading-and-truth-of-cap-theorem/
• http://happinessoncode.com/2017/07/29/cap-theorem-and-pacelc-theorem/

[janeljs]

지선

• partition tolerance = 네트워크에 파티션이 생기더라도 시스템은 계속 동작해야 한다는 것
• 두 노드 사이의 통신 장애를 왜 partition이라고 부를까?
  • https://en.wikipedia.org/wiki/Network_partition
• 데이터 일관성 보장을 위해 Quorum Consensus protocol을 사용하면 응답은 어떤 형태로 올까?
  • 왜 W+R>N인 경우에는 strong consistency가 보장되는가? W>N && R>N이 아니라?
    • 두 개의 트랜잭션에 의해 동시에 read & write가 일어나고 있지 않음을 보장해주기 때문
    • 또한 read quorum 중 최소한 1개는 최신본 보장함
    • https://en.wikipedia.org/wiki/Quorum_(distributed_computing)

      In a distributed database system, a transaction could execute its operations at multiple sites. Since atomicity requires every distributed transaction to be atomic, the transaction must have the same fate (commit or abort) at every site. In case of network partitioning, sites are partitioned and the partitions may not be able to communicate with each other. This is where a quorum-based technique comes in. The fundamental idea is that a transaction is executed if the majority of sites vote to execute it.

  • one response==one quorum. yes가 여러개면 commit, 아니면 rollback
  • abort quorum과 commit quorum을 던지는 것.
• vector clock는 어떻게 구현되는가? 클라이언트는 충돌을 어떻게 해소?
  • 아마존 Dynamo도 eventual consistency 지원 위해 vector clock 사용
  • https://www.cl.cam.ac.uk/teaching/1819/FJava/workbook5.html
  • 채팅 클라이언트
  • https://github.com/dhruvdeveloper/Distributed-System-Vector-Clock
• multicasting은 서버가 많을 때 왜 비효율적일까?
  • https://ko.wikipedia.org/wiki/%EB%A9%80%ED%8B%B0%EC%BA%90%EC%8A%A4%ED%8A%B8
  • https://www.sciencedirect.com/topics/computer-science/multicast-problem

    However, this kind of multicast tree may be inefficient in multi-channel CRAHNs, since the dynamically changing links and network topology can result in frequent update of the multicast tree, which incurs unacceptable cost.

• 머클트리
  • http://wiki.hash.kr/index.php/%EB%A8%B8%ED%81%B4%ED%8A%B8%EB%A6%AC
• uniform hash는 SUHA(Simple Uniform Hashing Assumption)랑 다른것?
• 블룸필터
  • https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0

[meloncha]

민석

CAP 정리 in database

SSTable

• 데이터는 key, value로 구성되며 key 기준으로 데이터가 정렬된다
• 중복되는 key를 가진 데이터는 없어야 한다
• 장점
  • merge가 쉽고 빠르다 (데이터는 키 기준으로 정렬이 되어 있으므로 merge sort 알고리즘을 사용하여 O(n)으로 병합가능)
  • 순서가 보장되므로 모든 데이터에 대한 index를 생성할 필요가 없다. 특정 포인트에 대해서만 index를 생성해둔 sparse index 만으로도 속도 개선이 된다

참고) https://velog.io/@yunhongmin/SSTable-data-storage

Bloom filter

• 어느 SSTable에 찾는 키가 있는지 알아낼 수 있는 효율적인 방법
• membership query : 어떤 원소 x가 어떤 집합 A에 포함되는지를 묻는 것 (자바 Set 인터페이스의 contains 메소드와 비슷)
• Bloom filter : 어떤 원소 x가 어떤 집합 A의 원소인지 확률적으로 판단하는 표시함수
• Bloom filter를 이용한 membership query 결과 값 : '아마도 해당 집합의 원소인 것 같다' or '확실히 해당 집합에 포함된 원소가 아니다'
• 주 목적 : 키가 존재하지 않는다는 것을 파악하는 데 소모되는 자원의 낭비를 줄이는 것 (해시 테이블에 비해 공간 효율이 매우 높다)

참고) https://d2.naver.com/helloworld/749531

카산드라(cassandra)에서 데이터 조회 과정

• 하나의 노드는 여러 개의 SSTable이 존재하므로 찾을 데이터가 어느 SSTable에 있는지 아는 것이 매우 중요
• 블룸 필터는 해당 데이터가 있는 SSTable의 위치를 찾는데 도움을 준다
• 조회하려는 키에 해당하는 파티션 키가 캐시에 없는 경우 파티션 인덱스를 통해 SSTable에 접근

참고) https://nosqldb.tistory.com/entry/%EC%B9%B4%EC%82%B0%EB%93%9C%EB%9D%BCcassandra-%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%A5%BC-%EC%9D%BD%EB%8A%94-%EA%B3%BC%EC%A0%95-%EC%8B%AC%ED%99%94

vector clock

• 벡터 클락은 노드와 count의 쌍을 의미
• D1 : +1 증가 요청. Sx 서버가 처리. 값은 1 (1, 0, 0)
• D2 : +2 증가 요청. Sx 서버가 처리. 값은 3 (2, 0, 0)
• D3 : +3 증가 요청. Sy 서버가 처리. 값은 6 (2, 1, 0)
• D4 : -1 감소 요청. Sz 서버가 처리. 값은 2 (2, 0, 1)
• D5 : 값 조회 요청. Sx 서버가 처리. (Sx -> 3, Sy -> +3, Sz -> -1) 값은 5 (3, 1, 1)
• 버전 충돌 여부 확인법 : 두 벡터 시계의 구성요소끼리 비교할때 대소관계가 바뀌는 것이 있으면 충돌 (예 [1,3,3], [2,2,2])

정족수 합의(Quorum Consensus)

W + R > N

• 강한 일관성
• N이 3인 경우 R+W는 4이상이어야 한다. Write, Read 할 때 0개의 서버에 작업을 할 수는 없다
• R : 1, W : 3 인 경우 (빠른 읽기 연산에 최적화)
  • Write 할 때 모든 서버에 작업을 하는 경우 Write시 모든 서버에 쓰기 연산을 함 (일관성 유지)
  • 그러므로 1개의 서버의 값만 읽어와도 일관성이 유지됨
• R : 2, W : 2 인 경우
  • Write시 2개 서버에서 작업을 했으므로 나머지 하나의 서버에는 작업이 없는 상태
  • 제대로된 값을 읽어오려면 최소 2개 서버에서 값을 읽어와야 한다. 그 중 한 서버는 최신 값을 가지고 있다
  • 두 서버 중 최신 값 판단은 vector clock으로 가능하다
• R : 3, W : 1 인 경우 (빠른 쓰기 연산에 최적화)
  • Write 시 1개의 서버에만 작업을 하는 경우 Read 시 모든 서버에서 값을 읽어와야 최신 값을 찾아서 일관성 유지 가능
  • 2개의 서버에서 값을 읽어온다면 작업한 서버가 포함된다면 vector clock으로 해결할 수 있지만 둘 다 작업하지 않은 서버의 경우 낡은 데이터가 조회된다

W + R = N

• 강한 일관성 보장되지 않음
• N이 3인 경우 R = 1, W = 2 or R = 2, W = 1 의 조합을 가진다
• 위의 예시처럼 문제가 생긴다

참고) https://darkstart.tistory.com/144