05. 복제

1. single leader
2. multi leader
3. leaderless

   리더와 팔로워

   • leader와 다중 복제서버 (replica)구조

     leader-based replication = active(능동) / passive(수동) = master/slave 복제

   • leader 노드에서는 write작업을 전담하여 변경을 로컬에 저장하고, replicationlog, change stream을 팔로워에게 전송하여 복제한다.

     동기 vs 비동기

     - 동기 : leader 변경작업시 follower의 변경을 보장
     

   • 동기 노드가 죽으면 write작업 불가.
   • 일관성 있는 데이터 복사본을 가질 수 있다. - 비동기 : leader는 변경작업 메세지를 follower에게 전송하지만, 응답을 기다리지는 않는다.
   • 약간의 지연이 발생. - 반동기식 : leader - sync replica (1) - async replica (n)
   • 한개의 동기노드가 리더가 죽었을때 대체가능하다

     새로운 팔로워 설정

     중단없이 추가하는방식

4. leader의 snapshot을 신규 팔로워 노드에 복제한다.
5. snapshot 이후 (binlog coordinate) 발생한 모든 데이터 변경을 복제한다.
6. 이제 다른 팔로워와 마찬가지로 동작 가능.

   노드 중단 처리

   팔로워 장애 : 따라잡기 복구

   • follower 에서 서버가 다운되기 전 마지막 트랜잭션을 기준으로 변경사항을 leader에게 요구하여 sync.

     리더 장애 : 장애 복구 (failover)

7. leader가 단순 타임아웃으로 끊어진것인지, 실제 서버장애인지 판단.
8. 새로운 leader 선출
   • 새로운 리더로 가장 적합한 노드는 이전 리더의 최신 데이터 변경사항을 가진 복제서버, 모든 노드에게 election(선출) 과정을 거친다.

     kafka leader electon 도 이런 과정을 거치는건가?

9. 새로운 리더 사용을 위해 시스템을 재설정 한다.
   • 비동기식 복제를 사용한다면, new leader와 old leader간의 불일치가 발생할 수 있다. (충돌하는 쓰기), 이때 사이의 간극을 폐기하는 방식이 간단한데, 다른 db와 sync되어야하는 경우 어려워질 수 있다.
   • ex) MySql Auto increment PK가 Redis의 key로 사용되고있는 경우, PK가 중복되어 데이터 정합성이 깨질 수 있다. - split brain : 특정 결함 시나리오에서 두 노드가 모두 자신이 리더라고 믿는 상황. 이때 데이터가 유실되거나 오염될 수 있어 위험한데, 둘중 한노드를 종료하는 매커니즘도 있다. -

     복제 로그 구현

     stagement-based replication 구문 기반 복제

     - 모든 statement를 기록하고, follower에게 전송한다. (insert/update,,)
     

   • now()나 rand()는 다른 값을 생성시킬 수 있다. > 고정값 반환으로 대체
   • 데이터에 의존하는 업데이트인경우, 순서가 보장되어야한다.
   • 부수효과 trigger등을 포함하는 구문은 각 복제서버에서 다른 부수효과가 생길 수 있따. - Mysql 5.1 이전버전에서는 사용되었지만, 위 문제들로 row-based replication으로 변경되었다.

     쓰기 전 로그 배송

     - 로그 기반 복제방식은 동일 한 구조의 데이터 복제본을 만들 수 있지만, 저장소 엔진과 밀접하게 엮이게 되어 리더와 팔로워가 다른 버전의 sw를 사용할 수 있다.
     

   • 다른 버전 사용이 허용된다면, 팔로워가 더 높은 버전을 사용하고, 리더가 나중에 업그레이드 하여 무중단 버전업이 가능하다.

     논리적 (row 기반) 로그 복제

     - 논리적 로그(logical log) = 저장소 엔진의 물리적 데이터 표현과 구별되는 로그
     

   • 여러 row를 수정하는 트랜잭션은 여러 로그로 레코드 생성후 트랜잭션 커밋됨을 레코드에 표시한다. - follower와 leader가 다른 버전의 엔진을 사용할 수 있고, 외부 애플리케이션이 파싱하기 쉬워서 change data capture에서 사용된다.

     트리거 기반 복제

     - 원하는 스크립트를 트리거 형식으로 실행가능, 유연성이 좋아 많이 사용됨. ### 복제지연 문제
     - read-scaling 아키텍처 : 팔로워간의 읽기요청을 분산하는 옵션
       - 최종적 일관성을 갖추기 전까지 아주잠시의 복제지연이 있을 수 있지만, 네트워크 문제가 있으면 수초로 늘어날 수도 있다. > 이벤트 기반으로 가면서, "키전달 -> 조회" 플로우 증가로 이른 이슈가 몇번 있었던걸로 기억.  > 우리 서버의 평균 복제지연시간은 어떻게 되는가? ## 자신이 쓴 내용 읽기  ### 쓰기 후 일관성 유지 방법
     

10. 데이터 소유자는 master, 그외 유저는 read => 소유자의 조회가 많아지면 비효율적
11. 최종 갱신 시각 1분후까지는 master
12. 클라이언트가 가장 최근 쓰기 타임스탬프/id를 기억하여, read에서 조회에 실패하는 경우 복제될때까지 대기한다.

    디바이스간 쓰기 읽관성 유지 방법

    • 위 3번 클라이언트가 키를 보관하는 방식을 사용할 수 없으므로, 이 키에 해당하는 메타데이터를 중앙집중식으로 관리한다.

      단조 읽기

    • 연속된 쿼리 두번이 각각 다른 follower에서 조회되는 경우, 첫번째 쿼리는 정상, 두번째 쿼리가 복제지연이 발생했다면 더 과거의 데이터를 읽게되는 역순이 발생할 수 있다. 이를 방지하는게 단조읽기.
13. 사용자의 읽기가 항상 같은 서버에서 수행되게끔 하는것.
    • 해당 서버가 고장나면 단조읽기를 보장할 수 없음.

      일관된 순서로 읽기

       - 쓰기가 특정 순서로 발생한다면, 읽기도 같은 순서로 읽음을 보장해야한다.
      

14. 인과성 있는 쓰기가 동일한 파티션에 기록되게하는 방법 (효율적이지 못할때도 있다.)
15. 이를 위한 알고리즘도 있다. (다음장에서 확인p.188)

    복제 지연을 위한 해결책

    • 트랜잭션

      트랜잭션이 복제 완료까지를 보장하는것인가??

      다중 리더 복제

    • 쓰기처리를 하는 각 노드는 다른 모든 노드에 변경사항을 전달해야한다.
    • master-master 복제, active/active 복제
    • 각 리더는 팔로워역할도 한다.
    • 쓰기충돌, AutoIncrement Key, trigger 등 문제가 될 소지가 많아 가능하면 피해야하는 영역으로 간주된다.

      다중 리더 복제의 사용 사례

    • 복잡도가 추가되어 단일 데이터센터에서는 적절하지 않다.

      다중 데이터센터 운영

    • 데이터센터마다 리더를 가지게 됨.
    • 사용자가 인지하는 쓰기 성능이 더 좋아짐.
    • 데이터 센터 중단 내성이 생김
    • 네트워크 문제 내성 : 데이터센터간의 네트워크는 비교적 느릴 수 있는데, 쓰기처리가 각 데이터센터에서 이루어짐으로써 약간의 내성을 가지게된다.

      오프라인 작업을 하는 클라이언트

    • 인터넷이 끊겨도 쓰기가 동작하고, 온라인일때 서버에 동기화되는 앱이라면, 각 디바이스가 리더 db를 가지고 있는 방식이다.

      협업 편집

    • 편집 충돌이 없음을 보장하려면, 잠금을 얻어야한다. 변경 단위를 매우 작게해서 잠금을 피할 수 있다.

쓰기 충돌 다루기

• 같은 내용을 동시에 수정할때
• 복제 완료를 대기하는 동기식이라면 해결가능하지만, 다중리더 복제의 장점인 각 서버가 독립적으로 쓰기를 허용하는 장점을 잃는다.

  충돌 회피

• 유저별로 특정 db서버만 사용하도록 라우팅하면 문제없다. 하지만 그 서버가 죽으면 충돌 회피 실패

  일관된 상태 수렴

• 단순히 서버별로 최종으로 받은 기록만 유지하면, 다중 리더간의 데이터 일관성이 깨질 수 있다.
  1. 최종 쓰기 승리(LWW : last write wins) : 각 쓰기에 고유id를 부여하여 우선순위를 따진다.
  • (ex_ timestamp, uuid)
  • 우선순위가 낮은 데이터는 유실될 수 있다. 2. 각 서버마다 우선순위를 두어, 우선순위가 높은 서버의 변경사항이 적용되도록 하는 방식 > 데이터 유실 가능 3. 어떻게든 병합한다 4. 명시적 데이터 구조에 충돌을 기록해 모든 정보를 보존하고, 애플리케이션으로 추후 충돌을 해소한다.

    사용자 정의 충돌 해소 로직

• 쓰기 수행중 충돌감지시 백그라운드에서 자동으로 해소로직이 동작할 수 있다.
• 읽기 수행중 충돌감지시, 애플리케이션이 충돌을 해소하여 다시 db를 업데이트한다.

  자동 충돌 해소

• 충돌 없는 복제 데이터타입 CRDT : set, map, 정렬목록, 카운터 등,,

  저 데이터타입이 왜 충돌이 없다는건지?.?

• 병합가능한 영속 데이터 구조 : git 처럼 명시적으로 히스토리를 추적하고, 삼중 병합 합수를 사용한다.
• 운영 변환 : 애플리케이션별 충돌해소 알고리즘.

Figma가 라이브 동시편집을 서빙하는 방법 (from chatGPT)

1. WebSocket : 클라이언트가 편집 > figma 서버로 전송 > 각 웹소켓으로 broadcast
2. 충돌 : 영상 참고

   다중 리더 복제 토폴로지

   • 복제 토폴로지는 쓰기를 한 노드에서 다른 노드로 전달하는 통신 경로
     • 리더가 두개라면 토폴로지는 A <-> B 한개이지만, 리더가 많은경우 토폴로지가 다양해진다.
3. 전체 연결 all to all : 모든 리더가 모든 리더에게 전송.
   • 단일 장애지점이 없어 내결함성이 높다.
   • 복제중에 쓰기충돌이 일어날 수있다.
     • LWW로 타임스탬프를 쓰는것은 서버간 동기화 보장을 할 수 없어 버전벡터를 사용할 수 있따. (p.186)
4. 원형 토폴로지 : mysql 방식, 한 리더는 다른 한 리더에게만 발송하고, 연쇄적으로 전송된다.
   • 단일 장애지점 가능성
5. 별모양 토폴로지 : 리더중의 리더가 변경사항을 수신하고, 다른 모든 노드에 전송한다.
   • 단일 장애지점 가능성

리더없는 복제

• dynamo 스타일
• 클라이언트는 각 쓰기를 여러 노드로 전송한다. 오래된 데이터를 감지하고 바로잡기위해 병렬로 여러 노드에서 읽는다.

  노드가 다운됐을때 데이터베이스에 쓰기

• n개의 복제서버중 한개가 다운되어 쓰기에 실패한 경우, 복구 후에 어떻게 읽어야 최신값을 보장할까

  읽기 복구와 안티 엔트로피

  1. 읽기복구 : 여러 노드가 병렬로 읽기를 수행하고, 최신버전을 탐지한 뒤 구버전을 리턴한 서버에 업데이트해준다.
  • 값읽기가 자주 있는 상황에서는 부적절
  • 읽히기전까지는 복구되지않음.
    1. 안티엔트로피 : 복제서버간 데이터차이를 감지하고 복구하는 별도 백그라운드 프로세스를 둔다.
  • 순서대로 쓰기복사가 이루어지기때문에 지연발생가능.

    읽기와 쓰기를 위한 정족수

• n : 복제서버수
• w : 쓰기 성공 필수 노드수
• r : 읽기 최소 노드 수
• w + r > n
  • 최소 한개의 노드에서 최신값을 읽을 수 있다.
• 일반적 설정값 : w = r = (n+1)/2 반올림
• 일반적으로 쓰기와 읽기는 n개 서버에 모두 전송되지만, w와 r은 응답을 기다리는 수이다.

  정족수 일관성의 한계

• w + r < n 이면 최신값 보장이 안될 수 있으나, 낮은 지연시간과 높은 가용성이 가능.
• w + r > n 이어도 오래된 값을 반환 할 수 있다. > 느슨한 정족수 p.184
  • 쓰기충돌인경우, 해결책이 timestamp 라면 서버간 시간차에 의해 쓰기가 유실될 수 있다. (clock skew)
  • w만족이 안되어 쓰기실패가 되어도 롤백이되지않는경우
• 복제지연시 발생할수있는 이슈들은 트랜잭션으로 합의가 필요하다.

  최신성 모니터링

• 복제지연지표 : 리더의 현재위치 - 팔로워의 현재위치 로 계산가능.
  • 리더없는복제에서 읽기복구만 사용한다면, 오래 읽히지않은 값은 얼마나 오래된 데이터인지 측정할 수 없다.
  • 최종적 일관성은 의도적으로 모호한 보장이지만, 운용성을 위해서는 ‘최종적’을 정량화할 수 있어야한다. > 복제지연

    느슨한 정족수와 암시된 핸드오프

• 적절히 설정된 정족수는 개별노드 장애/느린응답을 허용한다. 때문에 높은 가용성과 낮은 지연시간이 필요하다.
• 정족수는 내결함성이 없다. 네트워크중단으로 노드가 죽은것으로 판별되는경우, w + r > (live)n 이게되어 정족수 만족이 안될 수 있다.
  • 위 상황에서 트레이드오프
    1. 정족수를 만족하지 않으면 오류를 반환한다.
    2. 쓰기는 일단 받아서 w를 만족시키는 임시 대기노드에 기록한다. > 느슨한 정족수
• 암시된 핸드오프 : 느슨한 정족수 상황에서, n개 노드가 복구된 경우 임시대기노드의 변경사항을 원본노드로 복구하는것.
• 느슨한 정족수 상황에서는 암시된 핸드오프가 완료될때까지 r노드의 읽기가 최신성을 보장하지않는다.

  다중 데이터센터 운영

• 리더없는 복제에서도 다중데이터센터 운영이 가능하다.
  • 카산드라와 볼드모트는 보통 복제시 요청은 모든 데이터센터로 넣고, 로컬 데이터센터 안에서의 정족수 노드 확인응답을 기다리며, 다른 데이터센터간에는 대개 비동기로 발생하게끔 한다.

    동시쓰기

• 다이나모 스타일에서는 여러 클라이언트가 동시에 같은키에 쓰기를 허용하기때문에 정족수가 맞아도 충돌이 발생한다.
• ex) 클라이언트가 3개의 DB에 동시에 같은키를 쓰기작업하는경우.

  최종쓰기 승리 LWW

• 카산드라에서 유일한 충돌해소방법, 고유키를 가지고있어야하므로 UUID사용을 추천

  ‘이전 발생’ 관계와 동시성

• 이전발생 (happens-before) : 작업B가 작업A에 의존적이거나, A를 기반으로 하는것
• 어느 작업이 다른 작업에 대해 알지못한다면, 순서를 알수없으므로 동시작업이라 말한다.

  이전 발생 관계 파악하기 (?)

• 서버가 쓰기발생때마다 증가하는 버전번호를 관리한다.
• 클라이언트가 이전읽기의 버전번호를 포함하여 쓰기작업을 해야하고(인과성 컨텍스트), 이전읽기 값을 합쳐야한다.

  동시에 쓴 값 병합

• write작업은 합집합으로 병합할 수 있으나, delete작업이 유실될 수 있다.
• 툼스톤 : 버전번호에 특정 아이템이 제거되었음을 나타내는 표시

  버전벡터

• 리더없는 쓰기에서 다중복제본의 동시쓰기를 받아야할때는, 키당 버전번호 + 복제노드당 버전번호 = 버전벡터 가 필요하다.
• 버전 벡터와 버전 클락은 미묘하게 다른데, 복제본 상태비교에서 사용해야할 올바른 데이터구조는 버전 벡터이다. wiki
• 버전벡터 : 업데이트가 일어날때 버전 + 1,
  • V_{a}[x]=V_{b}[x]=max(V_{a}[x],V_{b}[x])
  • 최신버전으로 합쳐서 노드들이 동기화되는것이 목적.
• 버전 클락 : 이벤트가 있을때마다 버전 + 1
  • 모든 노드의 동기화가 목적이 아니라 이벤트 발생순서를 보는게 목적.