알고리즘 3️⃣ : 리더 없는 복제

모든 복제 서버가 클라이언트로부터 쓰기를 직접 받을 수 있게 허용하는 방식 → 다이나모 스타일이라고도 한다.

리더가 있는 방식에서 하나의 노드에서 장애가 일어나면 장애를 복구하고 다시 다른 노드와 데이터를 동기화 해야한다. 하지만 리더없는복제서버 에서는 장애복구과정이 필요하지 않다.

3개의 복제서버중 하나가 고장이 났다. 3개의 복제 서버 중 2개의 복제서버가 쓰기를 받으면 쓰기처리가 된다고 가정해보자. 사용자가 3개의 복제서버에 쓰기를 병렬로 전송한다. 이 중에 2개의 복제서버에서 ok응답을 받는다.(쓰기가 성공한다) 클라이언트는 복제 서버중 하나가 쓰기를 놓친 사실을 단순히 무시한다.

사용할 수 없었던 노드가 다시 온라인 상태가 되고 노드가 다운된 동안 발생한 모든 쓰기가 누락됐다. 이 문제를 해결하기 위해 클라이언트는 데이터베이스에서 읽을 때 하나의 복제 서버로 요청을 보내지 않고 읽기 요청을 병렬로 여러 노드에 전송한다. 그러면 여러 노드에서 다른 응답을 받을 수 있다. 이때 버전 숫자를 이용해 어떤 값이 최신 내용인지 결정한다.

읽기 복구와 안티 엔트로피

누락된 쓰기를 따라잡을 때 두 가지 메커니즘을 주로 사용한다

읽기복구

• 병렬로 여러 노드에 읽기 요청을 수행하면 오래된 응답을 감지할 수 있다.

• 이 때 버전 값을 비교해 오래된 DB에 새로운 값을 다시 기록한다.

• 값을 자주 읽는 상황에 적합

안티 엔트로피 처리

• 백그라운드 프로세스로 복제 서버 간 데이터 차이를 지속적으로 찾아 누락된 데이터를 없애는 방식.

• 복제 로그로 복구하는 것과 달리 안티 엔트로피 처리는 특정 순서로 쓰기를 복사하기 때문에 데이터가 복사되기 까지 상당한 지연이 있을 수 있음

읽기와 쓰기를 위한 정족수

3개중 2개만 처리해도 성공한것으로 간주했던 위의 예시. 근데 이걸 어느 범위까지 허용해야 할까?

자세한 내용은 책에서.. [p.181~183]

<aside> 🔔 n개의 복제서버가 있을 때 모든 쓰기는 w개의 노드에서 성공해야하고 모든 읽기는 최소한 r개의 노드에 질의해야 한다. w+r > n이면 최신 값을 얻을 것으로 기대한다. (보통 n을 홀수로 하고 w=r=(n+1)/2로 설정)

</aside>

동시 쓰기 감지

다인모 스타일 데이터베이스는 동시에 같은 키에 쓰는 것을 허용하기 때문에 충돌이 발생한다. 문제는 다양한 네트워크 지연과 장애 때문에 노드에 요청이 다른 순서로 도착하는 것.

이를 처리하는 방법 몇가지가 있음.

최종 쓰기 승리(LWW)

• 예전 값을 버리고 가장 최신 값으로 덮어 쓰는 방법

• 어떤 쓰기가 최신인지 명확하게 결정할 수 있는 한 복제본은 최종적으로 동일한 값으로 수렴

  • 예를들어 타임스탬프로 어떤게 최신인지 선택하고 이전것은 모두 무시하는 방법

• 동일한 키에 여러 번의 동시쓰기가 있다면 클라이언트에게는 모두 성공으로 보고될지라도 쓰기 중에 하나만 남고 다른 쓰기는 모두 무시된다.

“이전 발생” 관계와 동시성

• 두 가지 작업이 동시에 수행된건지 순서가 있는지 여부를 어떻게 결정할지 알아야함

• 어떤 작업이 이전의 작업을 기반으로 한다면 이전발생

• 작업 A와 B가 있다면 3가지 가능성이 있음

  • A가 B보다 먼저

  • B가 A보다 먼저

  • 동시

• 순서가 있다면 버전을 부여해 덮어씌우면 되지만 동시에 발생한 작업은 충돌을 해소해야함

이전 발생 관계 파악하기

동시에 쓴 값 병합

• 여러 작업이 동시에 발생하면 동시에 쓴 값들을 형제값이라 부른다

• 형제 값의 병합은 버전 번호나 타임스탬프 기반으로 하나의 값을 선택할 수도 있지만 데이터 손실이 생길 수 있다

• 합리적인 방법은 합집합을 취하는 것

  • 위의 그림 예시로 보면 최종적인 형제값은 [우유, 밀가루, 달걀, 베이컨], [달걀, 우유 햄] 이다 여기서 합집합을 취하면 [우유, 밀가루, 달걀, 베이컨, 햄] 이다.

  • 하지만 장바구니에서 상품 추가 외에 제거도 할 수 있게 하려면 합집합으로는 올바른 결과를 얻을 수 없음

  • 두 형제 장바구니중 하나에서만 우유를 제거하면 합집합을 취할 때 다시 나타난다.

  • 따라서 상품을 제거할 때 DB에 단순히 삭제만 하는 것이 아니라 상품을 제거했음을 버전번호에 나타내야한다. 이런 삭제 표시를 툼스톤 이라고 함

• 형제 병합은 복잡하고 오류가 발생하기 쉬움

🔚정리

복제의 목적

• 고가용성

• 오프라인에서도 작업

• 지연 최소화

• 확장성

복제의 세 가지 알고리즘

• 단일 리더 복제

• 다중 리더 복제

• 리더 없는 복제

복제가 이뤄질 때

• 동기

• 비동기

  • 빠르지만 복제 지연이 증가하고 장애 파악이 중요함

  • 리더가 고장 나고 비동기로 갱신된 팔로워를 새로운 리더로 승격하면 최근에 커밋된 데이터를 잃을 수 있음

복제 지연으로 발생할 수 있는 이상현상에 도움되는 일관성 모델

• 쓰기 후 읽기 일관성 : 사용자는 자신이 제출한 데이터를 항상 볼 수 있어야 한다.

• 단조 읽기 : 사용자가 어떤 시점에 데이터를 본 후에는 예전 시점의 데이터는 나중에 볼 수 없다

• 일관된 순서로 읽기 : 사용자는 인과성이 있는 상태의 데이터를 봐야 한다.

  • 예를 들어 질문과 그에 대한 답을 순서에 맞게 봐야한