designing-data-intensive-applications

Part2 - 분산 데이터

분산된 데이터베이스를 필요로 하는 이유

• 확장성
  • 데이터 볼륨, 읽기 부하, 쓰기 부하가 단일 장비에서 다룰 수 있는 양보다 커지면 부하를 여러 장비로 분배할 수 있다.
• 내결함성 / 고가용성
  • 장비 하나가 죽더라도 애플리케이션이 계속 동작해야 한다면 여러 장비를 사용해 중복성을 제공할 수 있다.
• 지연 시간
  • 전 세계에 사용자가 있다면 사용자와 지리적으로 가까운 곳의 데이터센터에서 서비스를 제공하기 위해서 사용할 수 있다.

고부하로 확장

Scale Up

• 확장이 필요하다면 더 강력한 장비를 구매하는 것이 가장 간단한 방법이다.
• 수직 확장
• 용량 확장

해당 방식의 문제점은 비용이 선형적인 추세보다 훨씬 빠르게 증가한다는 것이다. 또한 병목 현상 때문에 두 배 크기의 장비가 반드시 두 배의 부하를 처리할 수 있는 것은 아니다.

• 네트워크 대역폭과 같은 문제 그리고 하나의 지리적인 위치로 제한되게 된다.

공유 디스크 아키텍처

• 독립적인 CPU와 RAM을 탑재한 여러 장비가 데이터 저장은 장비 간 공유하는 디스크 배열
• 장비는 고속 네트워크로 연결된다.
• 잠금 경합과 오버헤드가 확장성을 제한한다.

비공유 아키텍처(shared-nothing)

Scale Out 각 장비나 가상 장비를 노드라고 부른다.

• 각 노드는 cpu, ram, disk를 독립적으로 사용한다.
• 노드 간 코디네이션은 일반적인 네트워크를 사용해 소프트웨어 수준에서 수행한다.

특별한 하드웨어를 필요로 하지 않으므로 가격 대비 성능이 가장 좋은 시스템을 사용할 수 있다. 또한 여러 지리적인 영역에 걸쳐 데이터를 분산해 지연 시간을 줄일 수 있다. 최근엔 클라우드 배포를 활용하여 소규모 회사라도 다중 지역 분산 아키텍처가 실현 가능하다.

복제 대 파티셔닝

복제

• 같은 데이터의 복사본을 잠재적으로 다른 위치에 있는 여러 노드에 유지한다.
• 즉 중복성을 제공한다. 파티셔닝
• 큰 데이터베이스를 파티션이라는 작은 서브셋으로 나누고, 각 파티션은 각기 다른 노드에 할당(샤딩)

Part5 - 복제

복제란

• 여러 장비에 동일한 데이터의 복사본을 유지함.

복제가 필요한 이유

• 지리적으로 사용자와 가깝게 데이터를 유지해 지연 시간을 줄임
• 시스템의 일부에 장애가 발생해도 지속적으로 동작할 수 있음
• 읽기 질의를 제공하는 장비의 수를 확장해 읽기 처리량을 늘림

복제중인 데이터가 시간이 지나도 변하지 않는다면 복제는 쉽지만, 데이터는 변경 될 가능성이 있기 매우 높다.

변경 데이터를 복제하기 위한 세 가지 알고리즘을 이번 장에서 얘기한다.

• 단일 리더(single-leader)
• 다중 리더(multi-leader)
• 리더 X(leaderless)

복제에는 동기식 복제와 비동기식 복제 중 어떤 것을 사용할지, 잘못된 복제본을 어떻게 처리할 지 고려해야 한다. 이러한 트레이드 오프는 데이트베이스의 설정 옵션이다.

리더와 팔로워

모든 쓰기는 모든 복제 서버에서 처리되어야 한다. 그렇지 않으면 복제 서버는 더 이상 동일한 데이터를 유지할 수 없다. 이 문제를 해결하기 위한 가장 일반적인 해결책은 리더 기반 복제(leader-based replication) 이다.

서버 중 하나를 마스터로 지정한다.

1. 클라이언트가 데이터베이스에 쓰기를 할 때 요청을 리더에게 보낸다.
2. 리더는 먼저 로컬 저장소에 새로운 데이터를 기록한다.
3. 새로운 데이터를 기록할 때 마다 복제 로그(replication log)나 변경 스트림(change stream) 을 팔로워에게 전달한다.
4. 팔로워가 리더로부터 로그를 받으면 동일한 순서로 모든 쓰기를 적용하여 복사본을 갱신한다.

읽기를 할 땐 리더 혹은 팔로워에게 질의할 수 있다. 단, 쓰기는 리더에게만 허용된다.

동기식 vs 비동기식 복제

ex) 프로필 이미지를 갱신하는 상황

1. 클라이언트가 리더에게 갱신 요청을 전송한다.
2. 리더는 요청을 받은 후 데이터 변경을 팔로워에게 전달한다.
3. 리더는 클라이언트에게 갱신이 성공했음을 알려준다.

복제는 매우 빠르지만 얼마 정도의 시간이 걸릴지는 보장할 수 없다. 팔로워가 수 분 이상 리더와 떨어질 수 있다.

동기식 장점

• 팔로워와 리더가 일관성 있게 데이터를 유지하는 것을 보장.
• 리더가 작동하지 않아도 팔로워에서 계속 사용 가능 동기식 단점
• 동기 팔로워가 응답하지 않는다면 쓰기가 처리될 수 없다.
• 모든 쓰기를 차단하고 동기 복제 서버가 다시 사용할 수 있을 때까지 기다려야 한다.

만약 여러 노드를 사용 중일 때 하나의 노드만 장애를 발생해도 전체 시스템을 멈추게한다. 그래서 동기식 복제를 사용하려면 하나만 동기식 복제를 사용하고 나머지는 비동기식으로 하는 것을 의미한다. 이렇게 하면 적어도 두 노드에 데이터의 최신 복사본이 있는 것을 보장한다. 이러한 설정을 반동기식(semi-synchronous) 라고 한다.

리더 기반 복제는 비동기식으로 구성한다. 리더가 잘못되고 복구할 수 없을 경우 팔로워에 아직 복제되지 않은 모든 쓰기는 유실된다. 쓰기가 클라이언트에게 확인된 경우에도 지속성을 보장하지 않는다. 장점

• 팔로워가 잘못되더라도 리더는 쓰기 처리를 계속 할 수 있다.

새로운 팔로워 설정

클라이언트는 지속적으로 데이터베이스에 기록하고 데이터는 항상 유동적이기 때문에 표준 파일 복사본은 다른 시점에 데이터베이스의 다른 부분을 보게 된다.

새로운 팔로워 노드 설정은 대개 중단시간 없이 수행할 수 있다.

1. 데이터베이스를 잠그지 않고, 리더의 데이터베이스 스냅숏을 일정 시점에 가져온다.
2. 스냅숏을 팔로워 노드에 복사한다.
3. 팔로워는 리더에 연결해 스냅숏 이후 발생한 모든 데이터 변경을 요청한다.
   • 스냅숏이 리더의 복제 로그의 정확한 위치와 연관되어야 한다.
     • postgresql : 로그 일련번호(log sequence number)
     • MySQL : 이진로그 좌표(binlog coordinate)
4. 팔로워가 스냅숏 이후 데이터 변경의 미처리분을 모두 처리했을 때 따라잡았다고 말한다.
   • 리더에 발생하는 데이터 변화를 이어서 처리할 수 있다.

노드 중단 처리

모든 노드는 중단 시간이 발생할 수 있다.

• 예기치 않은 오류
• 보안 패치를 위한 리부팅

중단시간 없이 개별 노드를 재부팅할 수 있다는 점은 운영과 유지보수에 큰 장점이다. 리더 기반 복제에서 HA는 어떻게 달성 할까?

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

팔로워는 리더로부터 수신한 데이터 변경 로그를 로컬 디스크에 보관한다. 이렇게 하게되면 복구를 쉽게 진행할 수 있다.

1. 보관된 로그에서 결함이 발생하기 전에 처리한 마지막 트랜잭션을 확인한다.
2. 팔로워는 리더에 연결해 연결이 끊어진 동안 발생한 데이터 변경을 모두 요청한다.
3. 변경이 다 적용되면 데이터 변경의 스트림을 계속 받을 수 있다.

리더 장애: 장애 복구

1. 리더가 장애인지 판단한다.
   1. 대부분 시스템은 TimeOut을 통해 판별한다.
2. 새로운 리더를 선택한다.
   1. 선출 과정을 통해 이전에 선출된 제어 노드에 의해 새로운 리더가 임명될 수 있다.
3. 새로운 리더 사용을 위해 시스템을 재설정 한다.
   1. 새로운 쓰기 요청을 새로운 리더에게 보내야 한다.

장애 복구 과정은 잘못될 수 있는 것 투성이다.

• 비동기식 복제를 사용한다면 새로운 리더는 이전 리더가 실패하기 전에 이전 리더의 쓰기를 일부 수신하지 못할 수 있다. 이러한 경우 충돌하는 쓰기를 발생시킬 수 있다. 가장 일반적인 해결책은 이전 리더의 복제되지 않은 쓰기를 단순히 폐기하는 것이다. 이러한 방식은 클라이언트의 기대를 저버리게 된다.
• 노드가 모두 자신이 리더라고 믿을 수 있다.(스플릿 브레인(Split Brain))
  • 두 리더가 쓰기를 받으면서 충돌을 해소하는 과정을 거치지 않으면 데이터가 유실되거나 오염된다.
• 리더가 죽었다고 판단하기 위한 적절한 타임아웃을 설정해야한다.

복제 로그 구현

구문 기반 복제

리더는 모든 쓰기 요청을 기록하고 쓰기를 실행한 다음 구문 로그를 팔로워에게 전송한다. 관계형 데이터베이스는 모든 INSERT, UPDATE, DELETE 구문을 팔로워에게 전달하고, 팔로워는 클라이언트에게 직접 받은 것처럼 SQL 구문을 파싱하고 실행한다.

하지만 이 방법엔 복제가 깨질 수 있다.

• 시간을 얻기 위한 NOW()나 임의의 숫자를 얻기 위한 RAND()와 같은 비결정적 함수를 호출하는 구문은 각 복제 서버마다 다른값을 생성할 가능성이 있다.
• 자동증가 컬럼을 사용하는 구문이나 데이터베이스에 잇는 데이터에 의존한다면 모두 정확히 같은 순서로 실행되어야 한다.
• 부수 효과를 가진 구문(ex. 트리거, 프로시저)은 부수 효과가 완벽하게 결정적이지 않으면 각 복제 서버에서 다른 부수효과가 발생할 수 있다.

해결책

• 모든 비결정적 함수 호출은 고정 값을 반환하게끔 대체
• 하지만 다른 문제도 있기에 다른 복제방법을 선호한다.

쓰기 전 로그 배송

• 로그 구조화 저장소 엔진에선 로그 자체가 저장소의 중요한 주요 부분이다.
  • 로그 세그먼트는 작게 유지되고 백그라운드로 가비지 컬렉션을 한다.
• 개별 디스크 블록에 덮어쓰는 B 트리의 경우 모든 변경은 쓰기 전 로그(Write-ahead log, WAL)에 쓰기 때문에 일관성 있는 상태로 색인을 복원할 수 있다.

로그는 데이터베이스의 모든 쓰기를 포함하는 추가 전용(append-only) 바이트 열이다. 완전히 동일한 로그를 사용해 다른 노드에서 복제 서버를 구축할 수 있다. 리더는 디스크에 로그를 기록하는 일 외에도 팔로워에게 네트워크로 로그를 전송한다.

팔로워가 이 로그를 처리하게 되면 정확히 동일한 데이터 구조의 복제본이 만들어진다.

큰 단점 로그가 제일 저수준의 데이터를 기술한다. WAL은 어떤 디스크 블록에서 어떤 바이트를 변경했는지와 같은 상세 정보를 포함한다. 이렇게 하면 복제가 저장소 엔진과 밀접하게 엮인다. 다른 버전으로 변경한다면 리더와 팔로워의 데이터베이스 소프트웨어 버전을 다르게 실행할 수 없다.

만약 이것이 허용된다면 팔로워를 먼저 업그레이드 하고 레이드함으로써 중단시간 없이 데이터베이스 소프트웨어 업그레이드 수행이 가능하다. WAL배송과 같이 복제 프로토콜이 버전의 불일치를 허용하지 않는다면 중단시간이 필요하다.

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

다른 로그 형식을 사용하는 방법이다. 복제 로그를 저장소 엔진의 데이터 표현과 구별하기 위해 논리적 로그(logical log)라고 부른다.

• 삽입된 로우의 로그는 모든 컬럼의 새로운 값을 포함.
• 삭제된 로우의 로그는 로우를 교유하게 식별하는 정보를 포함
  • 대부분 Primary Key지만, 없다면 모든 컬럼의 예전 값을 로깅해야 한다.
• 갱신된 로우의 로그는 로우를 고유하게 식별하는 데 필요한 정보와 모든 컬럼의 새로운 값을 포함한다.

여러 로우를 수정하는 트랜잭션은 여러 로그 레코드를 생성한 다음 트랜잭션이 커밋됐음을 레코드에 표시한다.

논리적 로그를 내부와 분리했기 때문에 호환성을 더 쉽게 유지할 수 있고, 다른 버전의 데이터베이스 소프트웨어나 다 른 저장소 엔진을 실행할 수 있다.

또한 논리적 로그 형식은 외부 애플리케이션이 파싱하기 더 쉽다. 이런 측면은 외부 시스템에 데이터베이스 내용을 전송하고자 할 때 유용하다.

트리거 기반 복제

조금 더 유연한 상황이 필요할 때 트리거나 프로시저를 사용하여 복제할 수 있다.

트리거는 애플리케이션 코드를 등록할 수 있게 하여 데이터가 변경되면 자동으로 실행된다. 데이터 변경을 분리된 테이블에 로깅할 수 있는 기회를 가진다.

그러나 많은 오버헤드가 있다. 하지만 유연성이 미쳐서 많이 사용한다.

복제 지연 문제

복제는 내결함성 뿐만 아니라 확장성과 지연시간 때문에 한다.

리더 기반 복제는 모든 쓰기가 단일 노드를 거쳐야 하지만, 읽기 전용 질의는 어떤 복제 서버에서도 가능하다. 대부분이 읽기 요청이고 쓰기가 작은 비율로 구성된 작업부하라면 많은 팔로워를 만들어 읽기 요청을 분산시킨다.

읽기 확장(read-sacling) 아키텍처는 팔로워를 더 추가함으로써 읽기 전용 요청을 처리하기 위한 용량을 늘릴 수 있다. 이러한 것은 비동기식 복제에서만 동작한다. 동기식에서 한다면 단일 노드 장애나 네트워크 중단으로 전체 시스템의 쓰기가 불가능해진다.

하지만 비동기 팔로워에서 데이터를 읽을 때 이전 데이터를 읽어올 수도 있다. 동일한 질의를 수행하면 모든 쓰기가 반영되지 않았을 때 다른 결과를 얻을 수 있다. 하지만 이러한 상태는 일시적인 상태에 불과하다. 쓰기를 멈추고 잠시 기다리면 결국 따라잡게 되고 리더와 일치하게 된다. 이런 효과를 최종적 일관성이라고 한다.

하지만 지연 시간이 얼마나 길어질 지 확신할 수 없기 때문에 이러할 경우 큰 문제가 될 수 있다.

자신이 쓴 내용 읽기

데이터가 제출되면 리더에게 전송해야 하지만, 데이터를 볼 때는 팔로워에서 읽을 수 있다.

사용자가 쓰기를 수행한 직후 데이터를 본다면 복제 서버에 반영되지 않았을 수 있다. 이러할 경우 유실된 것처럼 보이기 때문에 당연히 불만족스러운 동작이다.

이런 상황에서는 읽기 일관성 이 필요하다. 페이지를 재로딩 했을 때 모든 갱신을 볼 수 있음을 보장하며 다른 사용자에 대해서는 보장하지 않는다.

• 사용자가 수정한 내용을 읽을 때는 리더에서 읽는다.
  • 그 외에는 팔로워에서 읽는다.
  • 예를 들어 사용자 소유의 프로필은 리더에서 읽고, 다른 사용자의 프로필은 팔로워에서 읽는 규칙을 설정한다.
• 쓰기가 많을 경우 효율적이지 않다.
  • 마지막 갱신 시각을 찾아서 마지막 갱신 후 1분동안은 리더에서 모든 읽기를 수행한다.
  • 복제 지연 모니터링해 리더보다 1분 이상 늦은 모든 팔로워에 대한 질의를 금지할 수 있다.
• 가장 최근 쓰기의 타임스탬프를 기록하여 갱신한다.
  • 최신 내용이 아닌 경우엔 다른 복제 서버가 읽기를 처리하거나 복제 서버가 따라잡을 때까지 대기시킨다.
• 모든 요청은 리더가 포함된 데이터센터로 라우팅되어야 한다.(?)

동일한 사용자가 여러 디바이스로 접근할 시엔 또 다른 문제가 발생한다. 이러한 경우엔 디바이스 간 쓰기 후 읽기 일관성이 제공되어야 한다.

• 마지막 갱신 타임스탬프를 기억해야 하는 방식을 어렵다.
• 동일한 데이터센터로 라우팅 된다는 보장이 없다.

단조 읽기

시간이 거꾸로 흐르는 현상이 있을 수 있다.

단조 읽기(monotonic read) 는 이상 현상이 발생하지 않음을 보장한다. 강한 일관성보단 덜 하지만 최종적 일관성보다는 더 강한 보장이다. 새로운 데이터를 읽은 후에는 예전 데이터를 읽지 않는다.

사용자의 읽기가 항상 동일한 복제 서버에서 수행되게끔 하는 방법이다. 예를 들어 임의 선택보다는 사용자 ID의 해시를 기반으로 복제 서버를 선택한다. 그러나 복제 서버가 고장 나면 질의를 다른 복제서버로 재라우팅 할 필요가 있다.

일관된 순서로 읽기

B는 지연없이 바로 전달되더라도 A는 지연이 발생할 수 있다. 이러하면 B -> A 순서로 화면에 보여질 수 있다.

https://www.notion.so

이러한 현상은 일관된 순서로 읽기(Consistent Prefix Read) 와 같은 다른 유형의 보장이 필요하다. 일련의 쓰기가 특정 순서로 발생한다면 쓰기를 읽는 모든 사용자는 같은 순서로 쓰여진 내용을 보게 됨을 보장한다.

파티셔닝된 데이터베이스에서 발생하는 특징적인 문제다. 같은 순서로 쓰기를 적용한다면 읽기 또한 일관된 순서를 보기 때문에 이러한 현상은 일어나지 않는다.

복제 지연을 위한 해결책

최종적 일관성 시스템으로 작업할 때 지연이 몇 분이나 몇 시간으로 증가한다면 문제가 생긴다. 이러한 상황이 중요하다면 쓰기 후 읽기와 같은 강한 보장을 제공하게끔 설계해야 한다.

또한 복제가 비동기식으로 동작하지만 동기식으로 동작하는 척 하는 것도 문제 해결 방안이다.

이러한 이유로 트랜잭션을 사용한다,

다중 리더 복제

• 다중 리더 복제(마스터 마스터 또는 액티브/액티브 복제)
  • 리더 기반 복제 모델에서 쓰기를 허용하는 노드를 하나 이상 두는 것으로 확장
  • 쓰기 처리를 하는 각 노드는 데이터 변경을 다른 모든 노드에 전달
  • 각 리더는 동시에 다른 리더의 팔로워 역할

다중 리더 복제의 사용 사례

1. 다중 데이터센터 운영

• 여러 다른 데이터센터에 데이터베이스 복제 서버가 존재
• 각 데이터센터마다 리더가 존재
• 각 데이터센터 내에서는 보통의 리더 팔로워 복제를 사용
• 데이터센터 간에는 각 데이터센터의 리더가 다른 데이터센터의 리더에게 변경 사항을 복제
• 다중 데이터센터 배포에서 단일 리더 설정과 다중 리더 설정 비교
  • 성능
    • 단일 리더에서 모든 쓰기는 리더가 있는 데이터센터로 이동 → 쓰기 지연시간 증가
    • 다중 리더에서 모든 쓰기는 로컬 데이터센터에서 처리 후 비동기 방식으로 다른 데이터센터로 복제 → 데이터센터 간 네트워크 지연이 숨겨짐
  • 데이터센터 중단 내성
    • 단일 리더에서 리더가 있는 데이터센터가 고장 나면 장애 복구를 위해 다른 데이터센터에서 한 팔로워를 리더로 승진
    • 다중 리더에서 각 데이터센터는 서로 독립적으로 동작 → 고장난 데이터센터가 온라인으로 돌아왔을 때 복제 따라잡기
  • 네트워크 문제 내성
    • 데이터센터 간 트래픽은 보통 공개 인터넷을 통해 처리 → 데이터센터 내 로컬 네트워크보다 안정성이 떨어짐
    • 단일 리더에서 데이터센터 내 연결의 쓰기는 동기식 → 데이터센터 내 연결 문제에 매우 민감
    • 다중 리더는 비동기 복제를 사용하기 때문에 네트워크 문제에 보다 잘 견디고, 일시적인 네트워크 중단에도 쓰기 처리는 진행 가능
• 다중 리더 복제의 단점
  • 동일한 데이터를 다른 두 개의 데이터센터에서 동시에 변경 가능 → 반드시 “쓰기 충돌”을 해소해야 함
    1. 오프라인 작업을 하는 클라이언트
• 인터넷 연결이 끊어진 동안 애플리케이션이 계속 동작하는 상황
  • 예시) 휴대전화, 노트북, 기타 디바이스의 캘린더 앱
    • 디바이스가 현재 인터넷에 연결됐는지 여부와 관계없이 언제든지 읽기/요청이 가능
    • 오프라인 상태에서 데이터를 변경하면 디바이스가 다음에 온라인 상태가 됐을 때 서버와 다른 디바이스를 동기화해야 함
• 모든 디바이스는 리더처럼 동작하는 로컬 데이터베이스가 존재(쓰기 요청 처리)
• 캘린더의 복제 서버 간 다중 리더 복제를 비동기 방식으로 진행하는 프로세스(동기화) 존재
  • 복제 지연은 인터넷 접근이 가능해진 시점에 따라 다름
• 아키텍처 관점에서는 데이터센터 간 다중 리더 복제와 근본적으로 동일
  • 극단적으로 각 디바이스는 “데이터센터”가 되고 디바이스 간 네트워크 연결은 극히 신뢰할 수 없음
• 예시) 카우치DB → 이런 종류의 다중 리더 설정을 쉽게 하기 위한 도구
  1. 협업 편집
• 실시간 협업 편집 애플리케이션
  • 동시에 여러 사람이 문서를 편집할 수 있는 애플리케이션
    • 예시) 이더패드(Etherpad) 또는 구글 독스 → 텍스트 문서나 스프레드 시트를 동시 편집 가능
• 한 사용자가 문서를 편집할 때 변경 내용을 즉시 로컬 복제 서버에 적용
• 동일한 문서를 편집하는 다른 사용자와 서버에 비동기 방식으로 복제
• 편집 충돌이 없음을 보장하려면 애플리케이션은 사용자가 편집하기 전에 문서의 잠금을 얻어야 함
• 다른 사용자는 같은 문서를 편집하려면 첫 번째 사용자의 변경이 커밋되고 잠금이 해제될 때까지 기다려야 함
• 더 빠른 협업을 위해 변경 단위를 매우 작게(예를 들어 단일 키 입력) 해서 잠금을 피할 수 있음

쓰기 충돌 다루기

다중 리더 복제에서 제일 큰 문제는 쓰기 충돌이 발생한다는 점 → 충돌 해소가 필요하다

동기 대 비동기 충돌 감지

• 단일 리더
  • 첫 번째 쓰기가 완료될 때까지 두 번째 쓰기를 차단
  • 두 번째 쓰기 트랜잭션을 중단해 사용자가 쓰기를 재시도
• 다중 리더
  • 두 쓰기가 모두 성공하고 충돌은 이후 특정 시점에서 비동기로만 감지 가능
• 이론적으로 충돌 감지를 동기식으로 만들 수 있지만(쓰기가 성공한 사실을 사용자에게 알리기 전에 모든 복제 서버가 쓰기를 복제하기를 기다린다), 다중 리더 복제의 주요 장점(각 복제 서버가 독립적으로 쓰기를 허용)이 상쇄됨

충돌 회피

• 특정 레코드의 모든 쓰기가 동일한 리더를 거치도록 애플리케이션이 보장하면 충돌은 발생 X
  • 예시) 특정 사용자의 요청을 동일한 데이터센터로 항상 라우팅 → 해당 데이터센터 내 리더를 사용해 읽기와 쓰기를 하게끔 보장
    • 사용자마다 서로 다른 “홈” 데이터센터를 갖는 구조
    • 사용자 입장에서 보면 단일 리더 구성
    • 한 데이터센터가 고장 나서 트래픽을 다른 데이터센터로 다시 라우팅하거나 사용자가 다른 지역으로 이동해 현재는 다른 데이터센터와 더 가깝다면 → 리더를 변경해야 하고 충돌 회피는 실패!

일관된 상태 수렴

• 단일 리더 데이터베이스는 순차적인 순서로 쓰기를 적용 → 동일한 필드를 여러 번 갱신한다면 마지막 쓰기가 필드의 최종값으로 결정
• 다중 리더 설정에서는 순서가 정해지지 않아 최종값이 명확하지 X
  • 단순하게 각 복제 서버가 쓰기를 본 순서대로 적용한다면 데이터베이스는 결국 일관성 없는 상태가 됨
    • [그림 5-7] 리더1의 최종값은 C, 리더2의 최종값은 B
• 모든 복제 서버가 최종적으로는 동일하다는 사실을 보장하기 위해서 데이터센터는 수렴(convergent) 방식으로 충돌을 해소해야
• 수렴 충돌 해소를 달성하는 방법
  • 각 쓰기에 고유 ID를 부여하고 가장 높은 ID를 가진 쓰기를 선택
    • 타임스탬프를 사용하는 경우 최종 쓰기 승리(LWW, last write wins)라고 함
    • 대중적이지만 데이터 유실 위험 존재
  • 각 복제 서버에 고유 ID를 부여하고 높은 숫자의 복제 서버에서 생긴 쓰기가 항상 우선적으로 적용
    • 역시 데이터 유실 가능성 있음
  • 값을 병합
    • 예를 들어 사전 순으로 정렬한 후 연결
    • [그림 5-7] “B/C”
  • 명시적 데이터 구조에 충돌을 기록 → 모든 정보를 보존
    • 나중에 충돌을 해소하는 애플리케이션 코드를 작성

사용자 정의 충돌 해소 로직

• 애플리케이션 코드를 사용해 충돌 해소 로직을 작성
  • 쓰기 수행 중
    • 복제된 변경 사항 로그에서 데이터베이스 시스템이 충돌을 감지하자마자 충돌 핸들러를 호출
    • 일반적으로 사용자에게 충돌 내용을 표시하지 않음
    • 백그라운드 프로세스에서 빠르게 실행
  • 읽기 수행 중
    • 충돌을 감지하면 모든 충돌 쓰기를 저장
    • 다음 번 데이터를 읽을 때 여러 버전의 데이터가 애플리케이션에 반환
    • 애플리케이션은 사용자에게 충돌을 보여주거나 자동으로 충돌을 해소 → 충돌 해소 결과를 다시 데이터베이스에 기록
• 자동 충돌 해소를 위한 연구
  • 충돌 없는 복제 데이터타입(conflict-free replicated datatype, CRDT) : 셋(set), 맵(map), 정렬 목록, 카운터 등을 위한 데이터 구조의 집합 → 동시에 여러 사용자가 편집할 수 있고 합리적인 방법으로 충돌을 자동 해소
    • 리악(Riak) 2.0에서 CRDT가 일부 구현
  • 병합 가능한 영속 데이터 구조 : 깃(Git) 버전 제어 시스템과 유사하게 명시적으로 히스토리를 추적, 삼중 병합 함수를 사용
  • 운영 변환 : 이더패드와 구글 독스와 같은 협업 편집 애플리케이션의 충돌 해소 알고리즘. 텍스트 문서를 구성하는 문자 목록과 같은 정렬된 항목 목록의 동시 편집을 위해 설계됨

다중 리더 복제 토폴로지

• 복제 토폴로지
  • 쓰기를 한 노드에서 다른 노드로 전달하는 통신 경로

• 전체 연결(all-to-all)
  • 모든 리더가 각자의 쓰기를 다른 모든 리더에게 전송
• 원형 토폴로지(circular topology)
  • 각 노드가 하나의 노드로부터 쓰기를 받고, 이 쓰기(자신의 쓰기도 추가)를 다른 한 노드에 전달하는 방식
  • 마이SQL이 기본적으로 제공하는 방식
• 별 모양 토폴로지
  • 지정된 루트 노드 하나가 다른 모든 노드에 쓰기를 전달
  • 트리로 일반화할 수 있음
• 원형과 별 모양 토폴로지 특징
  • 쓰기는 모든 복제 서버에 도달하기 전에 여러 노드를 거친다
  • 노드들은 다른 노드로부터 받은 데이터 변경사항을 전달
  • 무한 복제 루프를 방지하기 위해 각 노드에서 고유 식별자가 있고 복제 로그에서 각 쓰기는 거치는 모든 노드의 식별자가 태깅 → 노드가 데이터 변경 사항을 받았을 때 자신의 식별자가 태깅된 경우 해당 변경 사항을 무시
  • 문제점
    • 하나의 노드에 장애가 발생하면 다른 노드 간 복제 메세지 흐름에 방해를 준다
    • 해당 노드가 복구될 때까지 통신 불가능
    • 장애 노드를 회피하게끔 토폴로지를 재설정할 수 있으나 수동으로 수행
    • 메시지가 여러 경로를 따라 이동할 수 있으면 단일 장애점을 피할 수 있어 내결함성은 전체 연결 같이 빽빽하게 연결한 토폴로지가 더 좋음
• 전체 연결 토폴로지의 문제점
  • 일부 네트워크 연결이 다른 연결보다 빠르다면 일부 복제 메시지가 다른 메시지를 “추월”할 수 있음

  

  • 갱신은 이전 삽입에 종속적이라 모든 노드에서 삽입을 먼저 처리한 다음 갱신을 처리해야 → 이런 이벤트를 올바르게 정렬하기 위해 버전 벡터(version vector) 기법을 사용 가능

리더 없는 복제

• 리더 없는 복제
  • 모든 복제 서버가 클라이언트로부터 쓰기를 직접 받을 수 있게 허용하는 접근 방식
• 다이나모 스타일
  • 아마존이 내부 다이나모(Dynamo) 시스템에서 사용한 후 다시 데이터베이스용 아키텍처로 유행
  • 리악, 카산드라, 볼드모드 → 다이나모에서 영감을 얻은 오픈 소스 데이터스토어
• 일부 리더 없는 복제 구현에서는 코디네이터 노드가 클라이언트를 대신해 여러 복제 서버에 쓰기를 전송하기도 한다
  • 코디네이터 노드는 특정 순서로 쓰기를 수행하지 않음
  • 이러한 설계의 차이는 데이터베이스 사용 방식에 중대한 영향을 미침

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

• 세 개의 복제 서버를 가진 데이터베이스에 한 개의 복제 서버를 사용할 수 없다고 가정
  • 클라이언트는 쓰기를 모든 복제 서버에 병렬로 전송
    • 사용 불가능한 복제 서버는 쓰기를 놓침
    • 클라이언트는 두 개의 ok 응답을 받아 쓰기가 성공한 것으로 간주
  • 사용할 수 없었던 노드가 다시 온라인 상태에서 읽기를 시작
    • 노드가 다운된 동안 발생한 모든 쓰기는 누락된 상태
    • 클라이언트가 해당 노드에서 데이터를 읽으면 outdated 상태인 값을 얻음
• 해결책
  • 클라이언트가 데이터베이스를 읽을 때 읽기 요청을 여러 노드에 병렬로 전송
    • 여러 노드에서 다른 응답을 받을 수 있는데, 이때 버전 숫자를 사용해 어떤 값이 최신 내용인지 결정

읽기 복구와 안티 엔트로피

사용 불가능한 노드가 온라인 상태가 된 후 누락된 쓰기를 따라잡는데 주로 사용하는 두 가지 메커니즘

• 읽기 복구
  • 클라이언트가 병렬 읽기를 수행하여 오래된 응답을 감지
  • 버전 정보를 통해 오래된 값을 감지하고 해당 복제 서버에 새로운 값을 다시 기록
  • 값을 자주 읽는 상황에서 적합
• 안티 엔트로피 처리
  • 백그라운드 프로세스를 두고 복제 서버 간 데이터 차이를 지속적으로 찾아 누락된 데이터를 복사
  • 특정 순서로 쓰기를 복사하기 때문에 데이터가 복사되기까지 상당한 지연이 발생
  • 볼드모드의 경우 안티 엔트로피 처리를 X → 읽기를 거의 하지 않는 데이터의 값이 복제에서 누락돼 내구성이 떨어짐

읽기와 쓰기를 위한 정족수

• 정족수 읽기와 쓰기
  • r과 w를 따르는 읽기와 쓰기
  • 유효한 읽기와 쓰기를 위해 필요한 최소 투표수가 r과 w로 생각
• n : 복제 서버의 개수
• w : 성공적인 쓰기 정족수
• r : 성공적인 읽기 정족수
• w + r > n 이면 읽기 요청을 할 때 최신 값을 얻을 것으로 기대
  • 최소한 r개의 노드 중 하나에서 최신 값을 읽을 수 있기 때문
  • 일반적으로는 n을 홀수(보통 3이나 5)로 하고 w = r = (n + 1) / 2(반올림)으로 설정
    • 파라미터들은 대개 설정 가능
  • w < n이면 노드 하나를 사용할 수 없어도 여전히 쓰기 처리 가능
  • r < n이면 노드 하나를 사용할 수 없어도 여전히 읽기 처리 가능
  • 필요한 w나 r개 노드보다 사용 가능한 노드가 적다면 쓰기나 읽기는 에러를 반환

정족수 일관성의 한계

• n개의 복제 서버가 있고 w + r > n이 되게끔 w와 r을 선택하면 일반적으로 모든 읽기는 최신 값을 반환할 것을 기대
  • 쓰기를 하는 노드 셋과 읽기를 하는 노드 셋이 겹치기 때문
  • 즉, 읽은 노드 중에는 최신 값을 가진 노드가 하나 이상 있어야
• 보통 r과 w의 값으로 노드의 과반수(n/2 초과) 선택
  • n/2 노드 장애까지 허용해도 w + r > n이 보장되기 때문
• w와 r이 작을수록 오래된 값을 읽을 확률이 높음
  • 최신 값을 가진 노드가 읽을 노드에 포함되지 않을 가능성이 높기 때문
• w + r > n 인 경우에도 오래된 값을 반환하는 에지 케이스
  • 느슨한 정족수를 사용한다면 w개의 쓰기는 r개의 읽기와 다른 노드에서 수행 가능 → w개의 노드와 r개의 노드가 겹치는 것을 보장 X
  • 두 개의 쓰기가 동시에 발생하면 어떤 쓰기가 먼저인지 불분명 → 해결책은 동시 쓰기를 합치는 방법밖에 없음
    • 승자가 타임스탬프 기반으로 결정되면 시계 스큐에 의해 쓰기 유실 가능성
  • 쓰기가 읽기와 동시에 발생하면 쓰기는 일부 복제 서버에만 반영 → 읽기가 예전 값 또는 최신 값을 반환하는지 여부가 불분명
  • 쓰기가 일부 복제 서버에서는 성공했지만 다른 복제 서버에서는 실패해 전체에서 성공한 서버가 w 복제 서버보다 작다면 성공한 복제 서버는 롤백하지 X → 쓰기가 실패한 것으로 보고되면 이어지는 읽기에 해당 쓰기 값이 반환될 수도 있고 아닐 수도 있다는 의미
  • 새 값을 전달하는 노드가 고장나면 예전 값을 가진 다른 복제 서버에서 해당 데이터가 복원되고 새로운 값을 저장한 복제 서버 수가 w보다 낮아져 정족수 조건이 깨짐
  • 시점 문제
• 다이나모 스타일 데이터베이스는 일반적으로 최종적 일관성을 허용하는 사용 사례에 맞게 최적화
  • 매개변수 w와 r로 오래된 값을 읽을 확률을 조정할 수는 있지만 절대적 보장은 불가능

최신성 모니터링

• 최신성 모니터링
  • 데이터베이스가 최신 결과를 반환하는지 여부를 모니터링
  • 복제가 명확히 뒤처진다면 원인을 조사할 수 있게 해줘야 함
• 리더 기반 복제
  • 복제 지연에 대한 지표를 노출 → 모니터링 시스템에 제공
  • 리더에 적용된 쓰기가 동일한 순서로 팔로워에도 적용되고, 각 노드가 복제 로그의 위치(로컬에 적용된 쓰기 수)를 가지기 때문에 가능
  • 리더의 현재 위치에서 팔로워의 현재 위치를 빼면 복제 지연량을 측정
• 리더 없는 복제 시스템
  • 쓰기가 적용된 순서를 고정할 수 없음 → 모니터링이 조금 더 어려움
  • 데이터베이스가 읽기 복구만 사용한다면 자주 읽히지 않는 값이 얼마나 오래된 것인지에 대한 제한이 X
  • 복제 서버의 오래됨(staleness)를 측정하고 매개변수 n, w, r에 따라 오래된 값을 읽는 비율을 예측하는 연구 존재 → 운용을 위해서 최종적 일관성에서 “최종적”을 정량화할 수 있어야 함

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

• 느슨한 정족수
  • 네트워크 중단 등의 이유로 응답 가능한 노드가 w나 r보다 적어 더이상 정족수 충족이 불가능한 상황
  • 일단 쓰기를 받아들이고 보통 저장되는 n개의 노드에 속하지는 않지만 연결할 수 있는 다른 노드에 연결해서 기록하는 것
    • 쓰기와 읽기는 여전히 w와 r의 성공 응답이 필요
    • 지정된 n개의 “홈” 노드에 없는 노드가 포함될 수 있음
    • 내 집 문이 잠겨 들어갈 수 없다면 이웃집 문을 두드려 소파에 잠시 머물 수 있는지 묻는 상황
  • 장점
    • 쓰기 가용성을 높이는데 매우 유용
  • 제한
    • w + r > n인 경우에도 키의 최신값을 읽는다고 보장할 수 없음
      • 최신 값이 일시적으로 n 이외의 일부 노드에 기록될 수 있기 때문
• 암시된 핸드오프
  • 네트워크 장애 상황이 해제되면 한 노드가 다른 노드를 위해 일시적으로 수용한 모든 쓰기를 해당 “홈” 노드로 전송하는 것

다중 데이터센터 운영

• 리더 없는 복제도 동시 쓰기 충돌, 네트워크 중단, 지연 시간 급증 등을 허용하기 때문에 다중 데이터센터 운영에 적합
• 카산드라와 볼드모트
  • n개의 복제 서버 수에는 모든 데이터센터의 노드가 포함
    • 각 데이터센터마다 n개의 복제 서버 중 몇 개를 보유할지 지정
  • 클라이언트의 쓰기는 데이터센터 상관없이 모든 복제 서버에 전송
    • 보통 로컬 데이터센터 안에서 정족수 노드의 확인 응답을 기다리기 때문에 데이터센터 간 연결의 지연과 중단에 영향을 받지 X
• 리악
  • 클라이언트와 데이터베이스 간 모든 연결이 하나의 데이터센터의 로컬에서 이뤄짐
    • n은 하나의 데이터센터 안에 있는 복제 서버 수를 나타냄
    • 데이터센터 간 복제는 백그라운드에서 비동기로 일어나며 다중 리더 복제와 유사함

동시 쓰기 감지

• 다이나모 스타일 데이터베이스는 여러 클라이언트가 동시에 같은 키에 쓰는 것을 허용

  → 엄격한 정족수를 사용하더라도 충돌이 발생

• 네트워크 지연과 장애 때문에 이벤트가 다른 노드에 다른 순서로 도착할 수 있음
• 각 노드가 클라이언트로부터 쓰기 요청을 받을 때마다 키의 값을 단순하게 덮어 쓴다면 마지막 얻기(get) 요청처럼 노드들은 영구적으로 일관성이 깨짐

최종 쓰기 승리(동시 쓰기 버리기)

• 최종 쓰기 승리(LWW)
  • 각 복제본이 가진 “예전” 값을 버리고 가장 “최신” 값으로 덮어쓰는 방법
    • 이벤트 순서가 정해지지 않았기 때문에 임의로 쓰기 순서를 결정
    • 예를 들어 쓰기에 타임스탬프를 붙여 제일 큰 타임스탬프를 “최신”으로 간주
  • 어떤 쓰기가 “최신”인지 결정할 수 있는 한 복제본은 최종적으로 동일한 값으로 수렴
    • 최종적 수렴 달성이 목표
  • 단점
    • 지속성을 희생 → 동일한 키에 여러 번의 동시 쓰기가 있다면 클라이언트에게는 모두 성공으로 보고될지라도 쓰기는 하나는 남고 다른 쓰기는 무시된다
  • LWW로 데이터베이스를 안전하게 사용하는 유일한 방법은 키를 한번만 쓰고 이후에는 불변값으로 다루는 것 → 같은 키를 동시에 갱신하는 상황을 방지

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

• 이전 발생
  • 작업 B가 작업 A에 대해서 알거나 A에 의존적이거나 어떤 방식으로든 A를 기반으로 한다면 작업 A는 작업 B의 이전 발생(happens before)
    • B는 A에 인과성이 있다(casually dependent)
  • 나중 작업은 이전 작업을 덮어쓸 수 있음
• 동시 작업
  • 한 작업이 다른 작업 이전에 발생했는지가 동시성의 의미를 정의하는 핵심
  • 작업이 다른 작업보다 먼저 발생하지 않으면, 즉 어느 작업도 다른 작업에 대해 알지 못한다면) 단순히 동시작업 → 두 작업이 발생한 물리적 시각보다 각 작업이 서로 알지 못하는지 여부로 판단
  • 값을 덮어쓸 수 없고 충돌을 해소해야 함

이전 발생 관계 파악하기

1. 클라이언트 1은 장바구니에 우유를 추가. 버전 1을 할당받는다.
2. 클라이언트 2는 우유에 대해 모르고 달걀을 추가. 버전 2을 할당하고 [우유], [달걀]을 반환받는다.
3. 클라이언트 1은 달걀에 대해 모르고 밀가루를 추가. 버전 1과 함께 데이터를 전송하면 이 버전 번호로 [우유]를 , [우유, 밀가루]로 대체. 버전 3을 할당받는다. 서버는 [우유, 밀가루]와 [달걀]이 동시라는 사실을 안다. [우유, 밀가루]와 [달걀]을 반환받는다.
4. 클라이언트 2는 클라이언트 1의 작업을 모른 채 햄을 추가. [달걀, 우유, 햄]으로 데이터를 합쳐 버전 2를 가지고 서버에 전송. 서버는 버전 2로 [달걀]을 덮어쓰고, [달걀, 우유, 햄]에 버전 4를 할당한다.
5. 마지막으로 클라이언트 1이 베이컨을 추가. 이전에 버전 3을 받았으므로 그 데이터에 베이컨을 추가해 버전 3으로 전송. 이 값은 [우유, 밀가루]를 덮어쓰지만 [달걀, 우유, 햄]은 동시에 수행됐기 때문에 서버는 이 두개의 동시 수행된 값을 유지한다.

⇒ 전체적으로 이해가 잘 안됨

• 동작 방식
  • 서버가 모든 키에 대한 버전 번호를 유지, 키를 기록할 때마다 버전 번호를 증가시킴
  • 클라이언트가 키를 읽을 때는 최신 버전뿐만 아니라 덮어쓰지 않은 모든 값을 반환
  • 클라이언트가 키를 기록할 때는 이전 읽기의 버전 번호를 포함 + 이전 읽기에서 받은 모든 값을 함께 합쳐야 함
  • 서버가 특정 버전 번호를 가진 쓰기를 받을 때 해당 버전 이하 모든 값을 덮어쓸 수 있음
    • 높은 버전 번호의 모든 값은 유지해야 함
  • 쓰기가 이전 읽기의 버전 번호를 포함하면 쓰기가 수행되기 이전 상태를 알 수 있음
  • 버전 번호를 포함하지 않은 쓰기는 다른 쓰기와 동시에 수행된 것이므로 아무것도 덮어쓰지 않음

동시에 쓴 값 병합

• 형제(sibling) 값
  • 여러 작업이 동시에 발생하면 클라이언트는 동시에 쓴 값을 합쳐 정리해야 하는데, 이런 동시값을 리악은 형제값이라고 부름
  • 병합
    • 간단한 접근 방식으로 버전 번호나 타임스탬프 기반으로 하나의 값을 선택하는 방법이 있지만 데이터 손실이 발생할 수 있음
    • 장바구니 예제에서 형제를 병합하는 방식은 합집합을 취하는 것
      • 형제의 합집합은 데이터 제거하는 상황에서는 올바른 결과를 얻을 수 없다
      • 두 형제 바구니를 합치고 그 중 하나만 제거하면 제거한 값이 다시 나타남
        • 이 문제를 방지하려면 제거할 때 상품을 제거했음을 나타내기 위해 해당 버전 번호를 표시 → 툼스톤이라 한다

버전 벡터

• 버전 벡터
  • 모든 복제본의 버전 번호 모음
  • 각 복제본은 쓰기를 처리할 때 자체 버전 번호를 증가시키고 각기 다른 복제본의 버전 번호도 계속 추적해야 함
    • 이 정보는 덮어쓸 값과 형제로 유지할 값을 나타냄
  • 사례) 리악 2.0에서 사용하는 도티드 버전 벡터(dotted version vector)
    • 버전 벡터를 인과성 컨텍스트(casual context)라 부르는 문자열로 부호화
  • 버전 벡터를 통해 데이터베이스는 덮어쓰기와 동시 쓰기를 구분할 수 있음