9 | Notion

용어
- consensus: 여러 node가 특정 주제에 대해 동의하도록 함
- FLP result: node crash의 가능성이 있다면 consensus 보장은 불가
  - timeout, crash node identifying으로 일부 해결 가능
- weak guarantee: eventual consistency를 포함하는 개념
  - limitation 파악이 중요
  - fault-tolerant 관점에서는 유리
- linearizability: single copy, 모든 operation이 atomic한 경우
  - 모든 req, res의 timestamp를 수집했을 때 이를 시간 순으로 정렬 가능한 경우
  - atomic, strong ,immediate, external consistency
  - write skew 등과는 무관
- serializability: transaction 별로 순서 정리가 가능한 경우
  - 실제 순서와는 무관
- register: 특히 linearizable 상황에서 추적중인 key
- compare-and-set: compare 시 인지하는 값과 db 값이 다르면 error
- read repair: write 시 version 명시, replica lag에 대한 대비책
- CAP theorem: consistency, availability, partition를 모두 만족할 수 없음
  - consistency는 linearizability만, fault로는 network partition만을 고려한다는 한계
- casual dependency: 질문-답변처럼 논리 구조 상의 dependency. event order 정의
  - consistent with casualty: answer를 포함하면 이에 대한 question도 포함해야 함
  - read skew: casuality가 깨진 data를 읽는 상황
  - casually consistent: casualty가 정의한 order를 따르는 경우
- total order: 논리 구조와 별개로 모든 두 단위의 순서 비교 가능
- state machine replication: 모든 replica가 같은 순서, process로 write
- XA transactions: heterogeneous 상황의 2PC를 위한 표준
  - 기본적으로 C이나 JTA, JDBC, JMS 등 java api 도입
  - deadlock across different system은 감지 불가
    - SSI와 연동 불가
  - PostgreSQL, MySQL, DB2, SQL Server, Oracle
  - ActiveMQ, HornetQ, MSMQ, IBM MQ
- coordinator: multi node db transaction의 관리자
  - library, 별도 process로 적용 가능
  - DB의 일종이며 stateful
  - Narayana, JOTM, BTM, MSDTC
- participants: multi node db transaction 상황에서 각 node
- epoch: leader의 세대
Linearizability: 가장 강력한 consistency model 중 하나
- write 직후 모든 client에서 write된 내용 열람 가능해야 함
- concurrent한 read 요청: 한 번 new value가 return되면 이후에는 모두 new value return
- 사용 사례: lock이 사용되는 경우라고 보면 됨
  - leader election situation
  - uniqueness for db: 같은 email로 두 user가 동시에 register하는 경우
- 오류 사례
  - read repair와 lww의 조합으로 문제 발생 가능
  - leaderless의 경우 linear하지 않다고 보는 것이 안전
- 성능과 fault tolerance 측면에서 불리
  - network problem 상황에서 linearize하기 위해 process stop
  - casualty만 만족하도록 조정
Casualty
- 사례
  - Serializable snapshot isolation
  - read repair에서의 version number
- sequence number나 timestamp 활용
  - timestamp는 logical clock 활용이 일반적
  - node 별로 sequence number에 규칙 지정해 concurrency 조절
    - inter node process에 불리
  - 충분히 높은 resolution을 갖는 clock 참고
- lamport timestamp: counter, node ID pair 활용. total ordering
  - node간 counter sync: total order broadcast의 일종
    - sync에 걸리는 시간이 있으므로 real time 어려움
- total order broadcast: reliable, totally ordered
  - fault 상황에서 무한 retry
  - fencing token에도 사용 가능
  - linearizability와 달리 stale 상황 존재 가능
  - 연속적인 consensus algorithm 적용 필요
consensus algorithms: 여러 node의 제안 값 중 선택하는 algorithm
- zookeeper(Zab), etcd(Raft), VSR, Paxos
- 특성
  - Uniform agreement: 모든 node의 동의
  - Integrity: 결정 수정 불가
  - Validity: 최초 제안된 값들 중 선택
  - Termination: 모든 node는 결국 하나의 값을 결정해야 함
    - fault-tolerant. in doubt 상태로 무한 대기해서는 안 됨
    - 재해 상황 등 영구 failure도 고려
- atommic commit
  - single db node
    - make transaction durable: wal
    - disk에 commit log 남김: 핵심 step
      - log 남기는 중에 crash: node restarts 후 recover
      - log 남긴 후 crash: commit 완료
      - log 남기기 전 crash: abort
  - multi nodes: commit success 여부가 node 간 동일해야 함
    - commit은 기본적으로 무를 수 없음
- 2 Phase Commit: atommic commit에 특화
  - prepare phase와 commit phase
  - coordinator의 prepare request 결과가 모두 yes면 commit 진행
  - 절차
    - coordinator가 transaction ID 발행
    - 각 participants가 transaction ID 부착한 채로 transaction 진행
    - coordinator가 transaction ID tag해서 prepare request send
    - commit point: coordinator commit/abort 결정
    - commit/abort request send: 무한 재시도
  - 3 phase commit: bounded delay, perfect failure detector 필요
Distributed transaction in practice