선형 가능성: 겹친 연산도 한 순간에 일어난 것처럼 보기
선형 가능성은 동시 실행된 객체의 연산들이 마치 하나씩 순서대로 수행된 것처럼 설명될 수 있는 조건이다. 각 연산은 실제 호출과 응답 사이 어느 한 순간에 효과가 생긴 것으로 볼 수 있어야 한다. 이 가상의 순간을 선형화 지점이라고 부른다.
선형 가능성은 겹치지 않는 연산의 실시간 선후 관계까지 보존한다.
완료와 다음 호출 사이의 순서를 지킨다
초기 값 0인 레지스터에 A가 1을 쓰고 완료한 뒤 B가 읽기를 시작했다면, 그 사이 다른 쓰기가 없는 한 B는 1을 읽어야 한다. B가 0을 읽으면 이미 끝난 쓰기를 뒤로 밀어 설명할 수 없으므로 선형 가능하지 않다.
반면 A의 쓰기와 B의 읽기 구간이 겹치면 B가 0 또는 1을 얻는 두 결과 모두 가능할 수 있다. 읽기의 선형화 지점을 쓰기보다 앞이나 뒤에 둘 수 있기 때문이다. 모든 연산에 대해 서로 모순 없는 하나의 순서를 만들 수 있어야 한다.
Case 1: nonoverlapping operations
A: [ write(1) ----- success ]
B: [ read -> 1 ]
The read must follow the completed write.
Case 2: overlapping operations
A: [ write(1) ---------------- success ]
B: [ read -> 0 ]
A legal linearization may place the read before the write.
기록에서 호출과 반환을 함께 보아야 하는 이유가 이 구간 조건이다. 서버 처리 시각 하나나 클라이언트의 불완전한 벽시계 순서만으로 결과를 판정하면 겹침을 잘못 해석할 수 있다.
물리적 구현은 동시에 움직여도 된다
선형 가능성을 만족한다고 실제 내부 작업이 모두 직렬 실행되는 것은 아니다. 여러 요청이 겹쳐 계산해도 관찰 결과가 적법한 순서로 설명되면 된다. 공유 메모리 자료구조에서 원자적 CAS를 선형화 지점으로 삼는 설계가 대표적인 예다.
복제 저장소에서는 이전 리더가 아직 자신을 리더라고 믿는 상황이 어렵다. 최신 정보를 확인하지 않고 읽기에 응답하면 새 리더의 완료된 쓰기를 놓칠 수 있다. 합의 로그와 함께 읽기 권한 확인, 쿼럼 확인 또는 정확한 시간 가정을 가진 임대 방식이 필요하다.
트랜잭션 직렬 가능성은 여러 연산을 묶은 트랜잭션들이 직렬 실행과 동등한지를 묻는다. 일반 직렬 가능성은 실시간 순서까지 요구하지 않으며, 선형 가능성은 보통 개별 객체 연산의 호출·응답을 기준으로 한다. 실시간 순서도 포함하는 엄격 직렬 가능성과도 범위를 구분해야 한다.
하나의 객체가 선형 가능해도 여러 객체를 묶은 읽기·쓰기 전체가 원자적 트랜잭션이 되는 것은 아니다. 개별 키 보장과 여러 키의 불변식은 별도 설계 과제다.
선형 가능성은 완료된 변경을 다음 사용자가 즉시 반영된 것처럼 생각할 수 있게 한다. 대신 통신이 끊겼을 때 무조건 응답하는 정책과 충돌할 수 있다. 어떤 연산의 어느 상태가 외부에 보이는지 먼저 명세하면 구현과 장애 실험을 정확히 평가할 수 있다.