동시성 시스템에서 널리 쓰이는 일관성 모델들의 함의 관계와 가용성 특성을 계층적으로 설명합니다. 시스템, 프로세스, 연산, 함수/인자/반환값, 호출/완료 시간, 동시성, 장애, 히스토리, 그리고 일관성 모델의 포함 관계를 개념적으로 소개합니다.
이 클릭 가능한 지도(Bailis, Davidson, Fekete et al, Viotti & Vukolic에서 각색)는 동시성 시스템의 일반적인 일관성 모델 간의 관계를 보여줍니다. 화살표는 일관성 모델들 간의 관계를 나타냅니다. 예를 들어, 엄격 직렬 가능(strict serializable)은 직렬 가능성(serializability)과 선형화 가능성(linearizability) 모두를 함의하고, 선형화 가능성은 순차적 일관성(sequential consistency)을 함의하는 식입니다. 색상은 비동기 네트워크 상의 분산 시스템에서 각 모델이 어느 정도 가용한지를 나타냅니다.
이 지도는 일관성 모델을 계층적으로 배치해 보여줍니다. 가장 강한 모델은 엄격 직렬 가능입니다. 엄격 직렬 가능은 두 부류의 일관성 모델(다중 객체 트랜잭션에 대한 모델과 단일 객체 연산에 대한 모델)을 통합합니다. 모델 x가 y를 함의한다는 말은, x가 성립하는 모든 히스토리에서 y도 성립한다는 뜻이며, 따라서 x가 y보다 “강하다”고 말합니다.
다중 객체 측면에서, 엄격 직렬 가능은 직렬 가능을 함의하고, 직렬 가능은 다시 반복 가능 읽기와 스냅샷 격리를 함의합니다. 스냅샷 격리(일반화된 정의를 가정)와 반복 가능 읽기는 모두 단조 원자적 뷰를 함의합니다. 반복 가능 읽기는 커서 안정성을 함의합니다. 커서 안정성과 단조 원자적 뷰는 모두 커밋된 읽기를 함의하며, 이는 다시 커밋되지 않은 읽기를 함의합니다.
단일 객체 모델의 경우, 엄격 직렬 가능은 선형화 가능을 함의하고, 선형화 가능은 순차적 일관성을, 순차적 일관성은 인과적 일관성을 함의합니다. 인과적 일관성은 읽기 이후 쓰기(Writes Follow Reads)와 PRAM을 함의합니다. PRAM은 단조 읽기, 단조 쓰기, 자신이 쓴 내용 읽기를 함의합니다.
커서 안정성, 스냅샷 격리, 순차적 일관성 이상(그들을 포함)의 모든 모델은 비동기 네트워크에서 완전 가용할 수 없습니다. 자신이 쓴 내용 읽기 이상(그들을 포함)의 모든 모델은 많아야 스티키 가용성에 그칩니다. 이보다 더 약한 모델들(여기 열거된 것들 중)은 완전 가용할 수 있습니다.
분산 시스템은 동시성 시스템의 한 종류이며, 동시성 제어에 관한 많은 문헌이 분산 시스템에도 그대로 적용됩니다. 실제로, 우리가 논의할 대부분의 개념은 원래 단일 노드 동시성 시스템을 위해 정식화된 것입니다. 다만, 가용성과 성능 면에서 중요한 차이가 있습니다.
시스템은 시간이 지남에 따라 변하는 논리적 상태를 가집니다. 예를 들어, 가장 단순한 시스템은 하나의 정수 변수일 수 있고, 상태는 0, 3, 42와 같을 수 있습니다. 뮤텍스는 잠김 또는 잠금 해제의 두 상태만을 가집니다. 키-값 저장소의 상태는 키에서 값으로의 매핑일 수 있으며, 예컨대 {cat: 1, dog: 1} 또는 {cat: 4}와 같은 형태입니다.
프로세스1는 연산을 실행하고 계산을 수행하는 논리적으로 단일 스레드인 프로그램입니다. 프로세스 자체는 결코 비동기가 아니며, 비동기 계산은 독립된 여러 프로세스로 모델링합니다. "논리적으로 단일 스레드"라고 하는 것은 프로세스가 한 번에 하나의 일만 수행한다는 점을 강조하기 위함이며, 그 구현이 여러 스레드, 운영체제 프로세스, 심지어 여러 물리 노드에 걸쳐 분산되어 있더라도, 그 구성 요소들이 일관된 단일 스레드 프로그램의 환영을 제공하기만 하면 된다는 뜻입니다.
연산은 한 상태에서 다른 상태로의 전이입니다. 예를 들어, 단일 변수 시스템에는 해당 변수의 값을 읽고 설정하는 read와 write 같은 연산이 있을 수 있습니다. 카운터에는 증가, 감소, 읽기 같은 연산이 있을 수 있습니다. SQL 저장소에서는 연산이 일정 수의 select, update, delete 등으로 구성된 _트랜잭션_일 수 있습니다.
이론적으로는, 모든 상태 전이에 고유한 이름을 부여할 수 있습니다. 락에는 정확히 두 개의 전이 lock과 unlock이 있습니다. 정수 레지스터에는 무한한 수의 읽기와 쓰기가 있으며, 예컨대 read-the-value-1, read-the-value-2, …, 그리고 write-1, write-2, …가 있을 수 있습니다.
이를 더 다루기 쉽게 만들기 위해, 우리는 이러한 전이를 read, write, cas, increment 등과 같은 _함수_와, 그 함수를 매개변수화하는 _값_으로 나눕니다. 단일 레지스터 시스템에서 1을 쓰는 연산은 다음과 같이 표현할 수 있습니다:
{:f :write, :value 1}
키-값 저장소에서 키 "a"의 값을 3만큼 증가시키고자 한다면 다음과 같습니다:
{:f :increment, :value ["a" 3]}
트랜잭션 저장소에서는 값이 복잡한 트랜잭션일 수 있습니다. 여기서는 a의 현재 값을 읽어 2를 얻고, b를 3으로 설정하는 것을 단일 상태 전이로 수행합니다:
{:f :txn, :value [[:read "a" 2] [:write "b" 3]]}
일반적으로 연산에는 시간이 걸립니다. 멀티스레드 프로그램에서는 연산이 함수 호출일 수 있습니다. 분산 시스템에서는 연산이 서버로 요청을 보내고 응답을 받는 것을 의미할 수 있습니다.
이를 모델링하기 위해, 각 연산에는 _호출 시각_과(완료한다면) 그보다 엄격히 큰 _완료 시각_이 있다고 가정합니다. 두 시각은 상상 속의2, 완벽하게 동기화되고 전역에서 접근 가능한 시계3에 의해 주어집니다. 우리는 이러한 시계가 실시간 순서를 제공한다고 부르며, 이는 인과적 순서만을 추적하는 시계4와 대조됩니다.
연산에는 시간이 걸리므로, 두 연산이 시간적으로 겹칠 수 있습니다. 예를 들어, 두 연산 A와 B가 있을 때, A가 시작하고 B가 시작한 뒤 A가 완료되고, 그 다음 B가 완료될 수 있습니다. 두 연산 A와 B가 어떤 시점에든 동시에 실행 중이라면, A와 B는 _동시_라고 말합니다.
프로세스는 단일 스레드이므로, 같은 프로세스가 실행한 두 연산이 동시에 실행되는 일은 결코 없습니다.
어떤 이유로든(예컨대 타임아웃이 발생했거나 중요한 구성 요소가 크래시함으로써) 연산이 완료되지 않으면, 그 연산은 완료 시각이 없으며, 일반적으로 호출 이후의 모든 연산과 동시라고 간주해야 합니다. 실제로 실행되었을 수도, 실행되지 않았을 수도 있습니다.
이런 상태의 연산을 가진 프로세스는 사실상 멈춘 것이며, 다시는 다른 연산을 호출할 수 없습니다. 만약 또 다른 연산을 호출한다면, 이는 단일 스레드 제약을 어기는 것이 됩니다. 프로세스는 한 번에 한 가지 일만 합니다.
_히스토리_는 연산들의 모음이며, 그들의 동시성 구조를 포함합니다.
일부 논문은 이를 연산들의 집합으로 표현하며, 각 연산은 호출 시각과 완료 시각을 나타내는 두 개의 숫자를 포함합니다. 동시성 구조는 프로세스 간 시간 창을 비교하여 유추합니다.
Jepsen은 히스토리를 표현할 때 호출과 완료 연산의 정렬된 목록으로 나타내며, 사실상 각 연산을 둘로 쪼갭니다. 이 표현은 히스토리를 순회하면서 동시 연산과 가능한 상태를 추적하는 알고리즘에 더 편리합니다.
_일관성 모델_은 히스토리들의 집합입니다. 우리는 일관성 모델을 사용하여 어떤 히스토리가 시스템에서 “좋은”, 혹은 “합법적인” 것인지를 정의합니다. 히스토리가 “직렬 가능성을 위반한다”거나 “직렬 가능하지 않다”고 말할 때, 그 히스토리가 직렬 가능한 히스토리들의 집합에 속하지 않는다는 뜻입니다.
일관성 모델 A가 모델 B를 함의한다는 것은 A가 B의 부분집합이라는 뜻입니다. 예컨대, 선형화 가능성은 선차적 일관성을 함의하는데, 이는 선형화 가능한 모든 히스토리가 순차적으로도 일관적이기 때문입니다. 이를 통해 일관성 모델들을 계층적으로 관련지을 수 있습니다.
비공식적으로 말해, 더 작고 제한적인 일관성 모델을 “더 강한” 모델이라 부르고, 더 크고 허용적인 모델을 “더 약한” 모델이라 부릅니다.
모든 일관성 모델이 직접 비교 가능한 것은 아닙니다. 흔히 두 모델은 서로 다른 동작을 허용하지만, 어느 한 쪽이 다른 한 쪽을 포함하지 않습니다. 예를 들어, 스냅샷 격리는 A5B(Write Skew)라는 현상을 허용하지만, 이는 반복 가능 읽기에서 금지됩니다. 그러나 반복 가능 읽기는 스냅샷 격리에서 금지되는 조건(predicate) 기반의 G-single을 허용합니다. 어느 쪽도 다른 쪽보다 엄밀히 더 강하지 않으며, 스냅샷 격리와 반복 가능 읽기는 _상호 비교 불가(incomparable)_하다고 말합니다.