리더 없는 복제

리더 없는 복제란

• 단일 리더와 다중 리더 복제는 클라이언트가 쓰기 요청을 한 노드(리더)에게 전송한 뒤 데이터베이스 시스템이 쓰기를 다른 복제 서버에 복사하는 아이디어를 기반으로 함

• 일부 시스템은 리더의 개념을 버리고 클라이언트에게 모든 복제 서버로의 쓰기 요청을 허용하는 방식을 적용

• 아마존이 다이나모(Dynamo) 시스템에서 사용하며 유명해져 이런 종류의 데이터베이스를 다이나모 스타일이라고 부름(카산드라, 리악, 볼드모트 등)

노드가 다운되었을 때

• 세 개의 복제 서버를 가진 데이터베이스 중 복제 서버 하나가 다운되었다고 가정

• 리더 기반 설정에서 쓰기 처리를 계속하기 위해선 장애 복구를 처리해야 함

• 반면, 리더 없는 설정에서는 장애 복구가 필요하지 않음. 단순히 복제 서버 중 하나가 쓰기를 놓친 사실을 단순히 무시함

• 이때 다시 다운된 복제 서버가 살아난다면, 클라이언트의 읽기 요청에 오래된(outdated) 값을 반환할 수 있음

• 이를 해결하기 위해 읽기 요청을 병렬로 여러 노드에 전송하는 방식을 취함. 두 리턴 값에 대한 버전 숫자를 활용해 최신값을 반환

읽기 복구

• 살아난 복제 서버에서는 누락된 쓰기를 따라잡기 위해 어떤 두 가지 방식을 사용

• 읽기 복구

  • 클라이언트의 읽기 요청이 왔을 때 버전 값을 통해 해당 복제 서버의 쓰기가 누락되었다는 사실을 감지하고, 해당 복제 서버에 새로운 값을 기록 → 읽기 요청을 많을 때 적합

• 안티 엔트로피 처리

  • 백그라운드 프로세스를 두어 복제 서버 간 데이터 차이를 지속적으로 찾아 누락된 데이터를 복제 서버로 복사하는 방식. 하지만, 이는 특정 쓰기 순서를 토대로 쓰기를 복사하기 때문에 데이터가 복사되기까지 상당한 지연이 존재할 수 있음

정족수

• n개의 복제서버가 있을 때 모든 쓰기는 w개의 노드에서 성공해야 쓰기가 확정되고, 모든 읽기는 최소한 r개의 노드에 질의해야 한다

• w + r > n 이면 읽을 때 최신 값을 얻을 것으로 기대할 수 있음

• 다이나모 스타일 데이터베이스에선 n, w, r 파라미터를 대개 설정할 수 있으며, 보통 n을 홀수(3, 5)로 설정하고 w = r = (n + 1) / 2 (반올림) 으로 설정

• 여러 CASE

  • w < n : 노드 하나를 사용할 수 없어도 여전히 쓰기를 처리할 수 있음

  • r < n : 노드 하나를 사용할 수 없어도 여전히 읽기를 처리할 수 있음

  • n = 3, w = 2, r = 2이면 사용 불가능한 노드 하나를 용인

  • n = 5, w = 3, r =3이면 사용 불가능한 노드 둘을 용인

정족수의 한계

• n개의 복제 서버가 있고, w + r > n을 만족한다면 일반적으로 모든 읽기는 키의 최신 값을 반환할 것을 기대할 수 있음

• 이에 대한 선행 조건은 읽은 노드 중에는 최신 값을 가진 노드가 하나 이상 존재해야 함

  • 느슨한 정족수를 사용한다면, w개의 쓰기는 r개의 읽기와 다른 노드에서 수행될 수 있으므로 r개의 노드와 w개의 노드가 겹치는 것을 보장하지 않음

  • 두 개의 쓰기가 동시에 발생해 어떤 쓰기가 먼저 일어났는지 분명하지 않은 경우

  • 쓰기와 읽기가 동시에 발생해 쓰기가 일부 복제 서버에만 반영된 경우

  • 쓰기가 일부 복제 서버에서는 성공했지만, 다른 복제 서버에서는 실패한 경우(예를 들어 일부 노드의 디스크가 가득 참)

  • 새 값을 전달하는 노드가 고장나, 예전 값을 가진 다른 복제 서버에서 해당 데이터가 복원되고 새로운 값을 저장한 복제 서버 수가 w보다 낮아져 정족수 조건이 깨지는 경우

• 여기서 말하고자 하는 건, 일반적으로 정족수를 통해 최종적 일관성을 보장할 수 있지만, 이를 절대적으로 보장할 수는 없다는 것

느슨한 정족수

• 위의 예시처럼 정족수에는 한계가 존재 이를 처리하기 위한 방법은 크게 두 가지

  • w나 r 노드 정족수를 만족하지 못하는 모든 요청에 오류를 반환

  • 일단 쓰기를 받아들이고 값이 저장되는 n개 노드에는 속하지 않지만, 연결할 수 있는 노드에 기록

• 후자를 느슨한 정족수라고 부름

• 일단 임시 노드에 값을 저장하고, 네트워크 장애 등이 해소되면 임시 노드에서 수용한 모든 쓰기를 다른 노드로 전달하는 방식

• 느슨한 정족수는 쓰기 가용성을 높이는 데 유용하지만, 이는 w + r > n 인 경우에도 최신 키 값을 읽는다고 보장하지 못할 수 있음을 의미

동시 쓰기 문제

• 다이나모 스타일 데이터베이스는 여러 클라이언트가 동시에 같은 키에 쓰는 것을 허용 → 엄격한 정족수를 사용하더라도 충돌이 발생할 수 있다는 의미

• 위 그림과 같은 상황에서 쓰기 요청을 받을 때마다 키의 값을 단순히 덮어쓴다면, 영구적으로 일관성이 깨질 수 있음

• 대부분의 데이터베이스에서 이러한 충돌을 자동으로 처리해주지 않음

• 최종 쓰기 승리

  • 한 가지 방법은 각 복제본이 가진 예전 값을 버리고 가장 최신인 값으로 덮어쓰는 것

  • 쓰기는 자연적인 순서가 없기 때문에 예를 들어 타임스탬프를 붙여 제일 큰 타임스탬프를 선택하는 방식으로 사용 가능

  • 최종 쓰기 승리(LWW)라고 부르는 충돌 해소 알고리즘은 카산드라에서 제공하는 방식

  • 하지만 이는 최종적 수렴 달성은 가능하지만, 같은 키에 여러 쓰기가 발생할 경우 하나만 남고(클라이언트에겐 모두 성공으로 표시될테지만) 다른 쓰기는 무시된다는 단점이 존재

  • LWW로 데이터베이스를 안전하게 사용하는 방법은 키를 한번만 쓰고 이후에는 불변값으로 다루는 것.