선형화 가능성

여러 요청이 동시에 겹쳐 돌아도 각 요청이 어느 한 순간에 통째로 일어난 것처럼 보이는 성질입니다. 겹쳐 돈 것들을 한 줄로 세울 수 있습니다. 그 줄은 실제로 벌어진 앞뒤 순서를 어기지 않습니다.

상세

방에 전등 스위치가 하나 있습니다. 여러 사람이 같은 순간에 손을 뻗어도 불은 어느 한 순간에 켜지고 어느 한 순간에 꺼집니다. 반쯤 켜진 불을 보는 사람은 없습니다.

동시 객체는 여러 프로세스가 함께 쓰는 데이터 객체입니다. 선형화 가능성은 그런 객체를 위한 정확성 조건입니다. 이 조건은 순서를 미리 정하라고 요구하지 않습니다. 이미 벌어진 일을 나중에 한 줄로 세울 수 있느냐를 묻습니다. 원 논문은 이 조건이 무엇을 주는지를 이렇게 적습니다. 동시에 도는 프로세스들이 적용한 각 연산이 그 호출과 반환 사이 어느 한 지점에서 순간적으로 효력을 갖는 것처럼 보이게 한다는 것입니다. 조건은 직관적으로 말이 되는 두 요구에서 나왔습니다. 첫째, 각 연산이 순간적으로 효력을 갖는 것처럼 보여야 합니다. 둘째, 겹치지 않은 연산들의 순서는 보존돼야 합니다.

sequenceDiagram
    participant 프로세스A
    participant 객체
    participant 프로세스B
    프로세스A->>객체: 호출
    프로세스B->>객체: 호출
    Note over 객체: 프로세스A 의 연산이 효력을 갖는 순간
    Note over 객체: 프로세스B 의 연산이 효력을 갖는 순간
    객체-->>프로세스A: 반환
    객체-->>프로세스B: 반환

형식은 이력을 다시 세우는 꼴입니다. 이력은 프로세스들이 객체에 건 호출과 받은 반환을 늘어놓은 기록입니다. 먼저 원래 이력을 확장합니다. 아직 반환이 돌아가지 않았지만 이미 효력을 가진 호출에는 반환을 붙입니다. 효력을 갖지 못한 나머지 호출은 덜어냅니다. 그렇게 남은 완결된 이력이 어떤 순차 이력과 같아지면 첫째 조건이 섭니다. 프로세스들이 완결된 연산 단위로 서로 끼워 넣어진 것처럼 행동한다는 뜻입니다. 그 순차 이력이 원래 이력의 실시간 선행 순서를 지키면 둘째 조건이 섭니다. 이렇게 세운 순차 이력을 원래 이력의 선형화라고 부릅니다.

비결정성이 이 개념에 처음부터 들어 있습니다. 하나의 이력에 두 조건을 만족하는 확장이 여럿일 수 있습니다. 확장 하나에 선형화가 또 여럿일 수 있습니다. 선형화 가능한 객체는 그 동시 이력들이 어떤 순차 명세에 대해 선형화 가능한 객체입니다.

배경

동시 객체가 맞게 도는지 잴 잣대가 필요했습니다. 그 자리에 이미 두 조건이 있었습니다. 순차 일관성은 이력이 적법한 순차 이력과 동등할 것을 요구합니다. 원래 이력의 선행 순서가 보존될 것은 요구하지 않습니다. 그래서 먼저 끝난 연산이 나중에 시작한 연산 뒤로 밀려도 순차 일관합니다. 게다가 순차 일관성은 지역적 성질이 아닙니다. 큐 객체 두 개를 각각 떼어 보면 둘 다 순차 일관합니다. 그런데도 전체 이력은 순차 일관하지 않은 경우가 있습니다. 다른 쪽 조건인 직렬성은 단위가 트랜잭션입니다. 트랜잭션은 다른 트랜잭션과 공유하는 객체 집합에 유한한 원시 연산 수열을 적용하는 제어 흐름입니다. 직렬성도 엄격 직렬성도 지역적 성질이 아닙니다. 그리고 직렬성은 본질적으로 블로킹 성질입니다. 어떤 상황에서는 완전히 정의된 연산이라도 직렬성을 어기지 않고는 끝낼 수 없습니다. 그런 트랜잭션은 되돌려 다시 시작해야 합니다. 그러려면 그 목적의 장치가 따로 있어야 합니다.

필요했던 것은 셋이었습니다. 객체마다 따로 만족시키면 전체가 성립하는 조건, 실시간 순서를 보존하는 조건, 프로세스를 기다리게 만들지 않는 조건입니다.

flowchart TD
    P["객체 p 의 이력이 선형화 가능"] --> W["전체 이력이 선형화 가능"]
    Q["객체 q 의 이력이 선형화 가능"] --> W

선형화 가능성은 셋을 다 갖습니다. 먼저 지역적 성질입니다. 정리는 이력이 선형화 가능한 것이 각 객체 x 에 대해 그 객체로 사영한 이력이 선형화 가능할 때, 그리고 오직 그때뿐이라고 말합니다. 그래서 객체를 따로 구현하고 따로 검증할 수 있습니다. 실행 시점 스케줄링도 완전히 분산할 수 있습니다. 다음으로 논블로킹 성질입니다. 완전히 정의된 연산을 호출한 프로세스는 기다리도록 강요받지 않습니다. 막힘이나 교착이 생기더라도 그것은 이 성질을 구현한 특정 방식의 부산물입니다. 정확성 조건 자체에 내재한 것이 아닙니다. 이름은 Herlihy 와 Wing 이 1990년 논문에서 붙였습니다. 조건을 만족하도록 세운 순차 이력을 원래 이력의 선형화라고 부른 데서 온 말입니다.

예시

FIFO 큐

FIFO(First-In-First-Out) 큐는 연산 두 개를 주는 자료형입니다. Enq 는 항목을 큐에 넣습니다. Deq 는 가장 오래된 항목을 돌려주고 큐에서 지웁니다. 원 논문은 동시에 도는 프로세스들이 이 큐를 만졌을 때 나올 수 있는 동작 네 가지를 그림 하나에 늘어놓습니다. 시간 축은 왼쪽에서 오른쪽으로 흐릅니다. 연산마다 구간이 하나씩 붙습니다. 구간이 겹치면 동시 연산입니다. 표기는 E(x) A 와 D(x) A 입니다. 프로세스 A 가 항목 x 를 넣는 연산과 빼는 연산을 가리킵니다.

H1 은 동시 FIFO 큐가 어떻게 돌아야 하는지에 대한 직관과 맞아떨어집니다. 프로세스 A 와 B 가 x 와 y 를 동시에 넣습니다. 뒤에 B 가 x 를 뺍니다. 그다음 A 가 y 를 빼고 z 를 넣기 시작합니다. x 를 빼는 연산이 y 를 빼는 연산보다 앞섭니다. FIFO 성질에 따르면 두 넣기도 같은 순서로 효력을 가졌어야 합니다. 실제로 두 넣기는 동시였습니다. 그러니 정말 그 순서로 효력을 가졌을 수 있습니다.

H2 는 직관적으로 받아들일 수 없습니다. 외부 관찰자가 보기에 x 가 y 보다 먼저 들어간 것이 분명합니다. 그런데 x 가 빠지지 않은 채 y 가 빠집니다. A 는 x 를 뺐어야 합니다.

H3 은 받아들일 수 있습니다. x 를 넣는 연산이 반환되기 전에 x 가 빠집니다. 직관적으로 보면 x 를 넣는 연산이 완료되기 전에 효력을 가진 것입니다. H4 는 분명히 받아들일 수 없습니다. y 가 두 번 빠집니다.

판정에는 객체가 의도한 의미가 필요합니다. FIFO 큐에 받아들여지는 동시 동작이 스택이나 집합, 디렉터리에는 받아들여지지 않습니다.

etcd

etcd 공식 문서는 모든 키-값 API(Application Programming Interface) 호출에 지속성과 엄격 직렬성을 보장한다고 적습니다. 엄격 직렬성은 이해하기 더 쉬운 약한 보장들을 함의합니다. 선형화 가능성이 그중 하나입니다. 문서는 원 논문의 정의 문장을 그대로 인용해 그 뜻을 밝힙니다.

문서가 드는 예는 이렇습니다. 클라이언트가 시점 t1 에 쓰기를 마칩니다. t1 보다 뒤인 t2 에 읽기를 겁니다. 그 읽기는 t1 에 끝난 쓰기만큼은 최신인 값을 받아야 합니다. 다만 읽기는 t3 이 되어서야 끝날 수도 있습니다. 선형화 가능성은 그 읽기가 가장 최신 값을 돌려주는 것을 보장합니다. 이 보장이 없으면 읽기가 시작된 t2 시점에 최신이던 값이 t3 에는 낡은 값일 수 있습니다. t2 와 t3 사이에 동시 쓰기가 일어날 수 있기 때문입니다.

etcd 는 watch 를 뺀 모든 연산에 기본으로 선형화 가능성을 보장합니다. 값이 따라옵니다. 선형화된 요청은 Raft 합의 과정을 거쳐야 합니다. 읽기 요청의 지연을 낮추려면 요청의 일관성 모드를 serializable 로 잡을 수 있습니다. 그러면 쿼럼 기준으로 낡은 데이터에 접근할 수 있습니다. 대신 살아 있는 합의에 기대는 선형화 접근의 성능 부담이 사라집니다. 실제 값은 RangeRequest 메시지의 bool serializable 필드입니다. watch 연산에는 선형화 가능성을 보장하지 않습니다. 사용자가 watch 이벤트의 리비전을 확인해 다른 연산과의 순서를 맞춰야 합니다.

MongoDB

MongoDB 공식 문서는 읽기 관심사 수준 하나를 linearizable 로 둡니다. 실제 값은 이렇게 들어갑니다.

JavaScript

db.runCommand({
  find: "restaurants",
  filter: { _id: 5 },
  readConcern: { level: "linearizable" },
  maxTimeMS: 10000
})

이 수준으로 건 질의는 읽기 연산이 시작되기 전에 끝난, 과반이 확인한 성공한 쓰기를 전부 반영한 데이터를 돌려줍니다. 질의는 동시에 실행 중인 쓰기가 복제 셋 멤버 과반에 전파될 때까지 기다릴 수 있습니다.

제약이 붙습니다. 이 수준의 보장은 단일 문서를 유일하게 식별하는 질의 필터를 준 읽기에만 걸립니다. 위 예의 filter: { _id: 5 } 가 그런 필터입니다. 아무 질의에나 이 수준을 걸었다고 해서 서는 보장이 아닙니다. 이 수준은 프라이머리에서 도는 읽기에만 지정할 수 있습니다. 문서는 maxTimeMS 를 항상 같이 쓰라고 권합니다. 데이터를 가진 멤버의 과반이 사용 불가일 때를 대비하는 것입니다. maxTimeMS 는 연산이 무한정 막히지 않게 합니다. 읽기 관심사를 채울 수 없으면 오류를 돌려줍니다. 인과 일관성 세션과는 같이 쓸 수 없습니다.

majority 와 무엇이 다른지도 문서에 적혀 있습니다. linearizable 은 세컨더리 멤버들에게 확인을 받습니다. 지금 읽고 있는 프라이머리가 { w: "majority" } 쓰기 관심사로 쓰기를 확인해 줄 수 있는 프라이머리인지 확인하는 것입니다. 그래서 이 수준의 읽기는 majority 나 local 로 읽는 것보다 눈에 띄게 느릴 수 있습니다.

Google Cloud Spanner

Spanner 공식 문서의 자주 묻는 질문은 이 성질을 정면으로 묻습니다. Spanner 가 선형화 가능성을 제공하느냐는 물음에 그렇다고 답합니다. 그리고 기본으로는 외부 일관성을 제공한다고 덧붙입니다. 외부 일관성이 선형화 가능성보다 강한 성질이라는 것이 이유입니다. 선형화 가능성은 트랜잭션의 동작에 대해서는 아무것도 말하지 않기 때문입니다.

문서는 두 성질의 대상 단위를 이렇게 가릅니다. 선형화 가능성은 원자적 읽기·쓰기 연산을 지원하는 동시 객체의 성질입니다. 데이터베이스에서 그 객체는 보통 행 하나나 셀 하나입니다. 외부 일관성은 트랜잭션 처리 시스템의 성질입니다. 클라이언트가 임의의 객체들에 대한 읽기와 쓰기 여럿을 담은 트랜잭션을 그때그때 만들어 내는 시스템입니다. 선형화 가능성은 트랜잭션이 객체 하나에 대한 읽기나 쓰기 하나만 담을 수 있는 특수한 경우로 볼 수 있습니다.

같은 문서가 강한 일관성도 이 성질로 정의합니다. 복제 프로토콜이 강한 일관성을 보인다는 것은 복제된 객체들이 선형화 가능하다는 뜻입니다.

경계

선형화 가능한 시스템이면 여러 객체에 걸친 트랜잭션도 한 줄로 서는가. 아닙니다. 원 논문은 이 성질을 엄격 직렬성의 특수한 경우로 봅니다. 트랜잭션이 객체 하나에 적용되는 연산 하나로 제한된 경우입니다. 그리고 이 한 연산 제한이 실무와 형식 양쪽에 멀리 미치는 결과를 낳는다고 덧붙입니다. Spanner 공식 문서도 같은 자리를 짚습니다. 선형화 가능성은 트랜잭션의 동작에 대해 아무것도 말하지 않는다는 것입니다. 그래서 데이터베이스에서 이 성질이 걸리는 객체는 보통 행 하나나 셀 하나입니다.

읽고 쓰기 여럿을 담은 트랜잭션의 순서까지 요구하려면 트랜잭션을 단위로 삼는 조건이 따로 있어야 합니다. 엄격 직렬성과 외부 일관성이 그 이름입니다. 선형화 가능성은 거기까지 보장하지 않습니다.

선형화 가능성

상세

배경

예시

FIFO 큐

etcd

MongoDB

Google Cloud Spanner

경계

관련 항목

이 성질과 강도를 겨루는 다른 정확성 조건

이 성질을 형식으로 세우고 증명하는 데 쓰는 개념

선형화 가능성이 재는 동시 객체의 예

이 성질을 떠받치는 장치

일관성 강도와 맞바꾸는 대가

복제 구조에서 읽기가 걸리는 역할

이 성질을 실제로 구현·채택한 제품

이 성질이 실제로 걸리는 인터페이스 단위