선형성

내결함성

• 분산 시스템에서 발생할 수 있는 결함은 크게 세 가지

  • 네트워크에 의한 패킷 손실, 순서 뒤섞임, 임의의 시간 동안 지연
  • 시간의 오류
  • 노드가 죽음(ex. GC)

• 이러한 결함이 발생하더라도 서비스는 올바르게 작동한다면, 이런 시스템은 내결함성(Fault Tolerance)를 지닌다고 말함

• 내결함성을 지닌 시스템을 만드는 가장 좋은 방법 중 하나는 범용적인 추상화를 찾아 구현하고 애플리케이션에서 이 보장에 의존하게 하는 것

• 이러한 추상화 중 하나로 합의가 있음. 즉, 모든 노드가 어떤 것에 동의하게 만드는 것

• 이를테면 단일 리더 복제를 하는 데이터베이스가 있을 때 리더가 죽어서 다른 노드로 복구해야 한다면 남은 노드들이 합의를 사용해서 새 리더를 뽑음

일관성 보장

• 복제 데이터베이스는 대부분 최종적 일관성을 보장. 즉, 데이터베이스에 쓰기를 멈추고 불특정 시간 동안 기다리면 결국 모든 읽기 요청이 같은 값을 반환한다는 의미

• 노드 간 불일치는 일시적인 것이며 결국 스스로 해소됨

• 하지만 이러한 보장은 매우 약한 보장의 형태임. 언제 복제본이 수렴될지에 대한 아무런 보장이 없기 때문

선형성

• 최종적 일관성을 지닌 데이터베이스에서 두 개의 다른 복제본에 같은 질문을 동시에 하면 두 가지 다른 응답을 받을 수도 있음

• 그렇다면, 데이터베이스가 복제본이 하나만 있다고 생각하도록 한다면 단순하게 처리할 수 있지 않을까?

• 선형성(원자적 일관성 atomic consistency)은 시스템에 데이터 복사본이 하나만 있고 그 데이터를 대상으로 수행하는 모든 연산은 원자적인 것처럼 보이게 만드는 것

• 여기서 x는 레지스터라고 불리며, 키-값 저장소의 키 하나, RDBMS의 로우 하나, 문서 데이터베이스의 문서 하나를 의미

• read(x)=>v는 클라이언트가 레지스터 x를 읽기 요청했고, 데이터베이스가 값 v를 반환하는 것을 의미

• write(x, v)=>r는 클라이언트가 레지스터 x의 값을 v로 설정하라고 요청, 데이터베이스가 응답 r(ok or error)을 반환했다는 것을 의미

• 쓰기 시점과 읽기 시점이 겹치는 구간에서는 0 or 1의 값을 반환해야하며, 쓰기가 끝난 시점에서는 1이 반환되어야 함

• 시스템이 선형적이라는 의미는 여기에 또 다른 제약 조건이 추가됨

• 읽기와 쓰기가 겹치는 시점에, 어떤 노드의 읽기 요청에 1이 반환됐다면, 이후의 다른 읽기 요청은 반드시 1이 반환되어야 함(쓰기 요청이 완전히 끝나지 않았더라도)

• 이것을 조금더 구체적으로 시각화해보자면 다음과 같음

• 선형성의 요구사항은 연산 표시를 모든 선들이 항상 시간순으로 진행되어야 하며, 결코 뒤로 가서는 안됨

• 또한, 새로운 값이 쓰여지거나 읽히면 이후 실행되는 모든 읽기는 값이 다시 덮어쓰여질 때까지 쓰여진 값을 읽어야 함

• 여기서 cas는 Compare And Set 연산을 의미하며, 다른 클라이언트가 동시에 값을 바꾸지 않았는지 확인하기 위한 원자적 연산임

• 즉, D의 cas연산은 성공하지 못함. 왜냐하면 D가 cas연산을 수행할 때는 이미 x의 값이 0이 아니라, 1이 때문임

선형성 vs 직렬성

• 선형성과 직렬성은 모두 순차적인 순서로 배열될 수 있는 무언가를 의미하지만, 구체적으로 살펴보면 서로 다름

• 직렬성

  • 모든 트랜잭션이 여러 객체를 읽고 쓸 수 있는 상황에서의 트랜잭션의 격리 속성임

  • 트랜잭션들이 어떤 순서에 따라 실행되는 것처럼 보장. 그 순서는 트랜잭션들이 실제로 실행되는 순서와 달라도 상관 없음

• 선형성

  • 레지스터(개별 객체)에 실행되는 읽기와 쓰기에 대한 최신성 보장

  • 선형성은 연산을 트랜잭션으로 묶지 않기때문에 쓰기 스큐 같은 문제를 막지 못함

• 데이터베이스는 직렬성과 선형을 모두 제공할 수 있으며, 이런 조합은 엄격한 직렬성(strict serializability)라고 함

선형성이 활용되는 분야

• 선형성은 언제 쓰이면 좋은가

  • 잠금과 리더 산출
  • 제약 조건과 유일성 보장
  • 채널 간 타이밍 의존성

• 잠금과 리더 산출

  • 단일 리더 복제를 사용하는 시스템은 리더가 여러 개(스플릿 브레인)가 아니라 진짜로 하나만 존재하도록 보장해야함

  • 모든 노드는 시작할 때 잠금 획득을 시도하고 성공한 노드가 리더가 되는 방식으로 이를 구현

  • 즉, 잠금을 어떻게 구현하든지 선형적이어야 하며, 모든 노드는 어떤 노드가 잠금을 소유하는지에 동의해야함

• 제약 조건과 유일성 보장

  • 유일성 제약 조건은 데이터베이스에서 흔한 제약 조건임

  • 사용자명이나 이메일 주소는 사용자 한 명을 유일하게 식별할 수 있어야 한다는 것

  • 데이터가 기록될 때 이 제약 조건을 강제하고 싶다면 선형성이 필요하며, 실제로 잠금과 비슷한 메커니즘으로 작동

• 채널 간 타이밍 의존성
  

  • 용자들이 사진을 올릴 수 있고 백그라운드 프로세스가 사진을 빨리 내려받을 수 있도록 저해상도로 크기를 바꾸는(썸네일) 웹사이트가 있다고 가정
  • 이미지 크기 변경 모듈은 크기 변경 작업을 하도록 명시적으로 지시받아야 하고 이 지시는 메시지 큐를 통해 웹 서버에서 크기 변경 모듈로 보내짐(메시지 큐는 대부분 작은 메시지용으로 설계됐기 때문에 사진은 파일시스템에 기록되고 기록이 완료되면 크기변경지시가 큐에 들어감)
  • 이때 파일 저장 서비스가 선형적이라면 이 시스템은 잘 동작함. 선형적이지 않다면 경쟁 조건의 위험이 있음
  • 위 그림에서 4단계가 5단계보다 빠르다면 이미지 크기 변경 모듈은 이미지의 과거 버전을 보거나 아무 것도 보지 못할 수 있음

선형성의 구현

• 단일 리더 복제(선형적일 수도 있음)

  • 단일 리더복제에서 리더는 쓰기에 사용되는 복사본을 갖고 있고, 팔로워는 다른 노드에 데이터의 백업 복사본을 바라봄

  • 하지만, 읽기에 리더를 사용하려면 누가 리더인지 확실히 안다고 가정해야 함. 즉, 스플릿브레인이 발생한다면, 선형성을 위반하게 됨

• 합의 알고리즘(선형적)

  • 합의 프로토콜은 단일 리더 복제와 비슷하지만, 스플릿 브레인과 복제본이 뒤처지는 문제를 막을 수 있음 (ex. Zookeeper)

• 다중 리더 복제(비선형적)

  • 여러 노드에서 동시에 쓰기를 처리하고 그렇게 쓰여진 내용을 비동기로 다른 노드에 복제하기 때문에 선형적이지 못함

• 리더없는 복제(비선형적)

  • 정족수 읽기와 쓰기를 요구함으로서 엄격한 일관성을 달성할 수 있다고 주장할 수 있지만, 엄격한 정족수를 사용하더라도 비선형적으로 동작할 수 있음

  • 아래 예시를 보자면, 정족수를 충족했지만 비선형적으로 작동함

선형성의 비용

• 위와 같이 다중 데이터센터가 있다면, 다중 리더 복제가 좋은 선택이 될 수 있음

• 다중 리더 복제를 사용한다면, 네트워크가 끊기더라도 데이터베이스는 정상적으로 동작함. 한 데이터센터에 쓰여진 내용은 비동기로 다른 데이터센터로 복제되므로 쓰기는 그냥 큐에 쌓였다가 네트워크 연결이 복구되면 전달됨

• 하지만 위에서 알아봤듯이 다중 리더 복제는 선형성을 보장하지 못함

• 반대로 단일 리더 복제는 선형성을 보장하지만 네트워크가 끊긴다면 가용성을 보장하지 못함

CAP 정리

• 이런 문제는 단일 리더 복제와 다중 리더 복제 사이의 것만은 아님

• 애플리케이션에서 선형성을 요구하고 네트워크 문제 때문에 일부 복제 서버가 다른 복제 서버와 연결이 끊기면 일부 복제서버는 연결이 끊긴 동안은 요청을 처리할 수 없음(가용성이 없음)

• 애플리케이션에서 선형성을 요구하지 않는다면 각 복제 서버가 다른 복제 서버(예를 들어 다중 리더)와 연결이 끊기더라도 독립적으로 요청을 처리하는 방식으로 쓰기를 처리할 수 있음

• 즉, 선형성이 필요 없는 애플리케이션은 네트워크 문제에 더 강인함

- 일관성(Consistency): 모든 노드가 같은 순간에 같은 데이터를 볼 수 있다.
- 가용성(Availability): 모든 요청이 성공 또는 실패 결과를 반환할 수 있다.
- 분할내성(Partition tolerance): 메시지 전달이 실패하거나 시스템 일부가 망가져도 시스템이 계속 동작할 수 있

• 위와 같은 표현은 오해의 소지가 있으므로, 사용하지 않는 것이 좋음

선형성과 네트워크 지연

• 선형성은 유용한 보장이지만 현실에서 실제로 선형적인 시스템은 놀랄만큼 드뭄

• 심지어 다중 코어 CPU의 램조차 선형적이지 않음

• 이렇게 동작하는 까닭은 모든 CPU 코어가 저마다 메모리 캐시와 저장 버퍼를 갖기 때문

• 메모리 접근은 기본적으로 캐시로 먼저 가고 변경은 메인 메모리에 비동기로 기록

• 이렇게 동작하는 이유는 캐시에 있는 데이터를 접근하는 게 메인 메모리로 가는 것보다 훨씬 더 빠르므로 좋은 성능을 내는 데 필수적이기 때문

• 좀 더 효율적인 선형 저장소 구현은 없을까?

• 이 문제에 대해서 아티야(Attiya)와 웰치(Welch)는 선형성을 원하면 읽기와 쓰기 요청의 응답 시간이 적어도 네트워크 지연의 불확실성에 비례해야 함을 증명함

• 대부분의 환경에서 네트워크 지연의 변동은 피할 수 없으므로 선형성 읽기와 쓰기의 응답시간은 필연적으로 높아질 수밖에 없음