리스

리스는 정해진 기간 동안만 유효한 권리입니다. 기간이 지나면 준 쪽이 따로 묻지 않고 거둬 갑니다. 계속 쓰려면 기간이 끝나기 전에 다시 받아야 합니다. 상대가 응답을 멈춰도 기다릴 시간이 미리 정해져 있습니다.

상세

원 논문은 리스를 계약으로 정의합니다. 한정된 기간 동안 그 소유자에게 대상에 대한 명시된 권리를 주는 계약입니다. 캐싱 맥락에서 그 권리는 쓰기 통제권입니다. 리스가 덮고 있는 데이터를 서버가 쓰려면 먼저 리스 소유자의 승인을 받아야 합니다. 리스 소유자가 쓰기를 승인하면 자기 로컬 복사본을 무효화합니다.

리스를 쓰는 캐시는 데이터를 들고 있는 것만으로는 부족합니다. 읽기에 응답하거나 쓰기를 반영하려면 그 데이터에 대한 유효한 리스가 같이 있어야 합니다. 데이터를 서버에서 받아올 때 서버가 리스도 같이 돌려줍니다. 그 리스는 기간 동안 서버가 이 소유자의 승인 없이는 어떤 클라이언트의 쓰기도 허용하지 않는다는 보장입니다.

sequenceDiagram
    participant 캐시
    participant 서버
    캐시->>서버: 데이터 요청
    서버-->>캐시: 데이터 + 리스
    Note over 캐시: 기간 안의 읽기는 서버에 묻지 않는다
    캐시->>서버: 기간이 지난 뒤의 읽기
    서버-->>캐시: 리스 연장 · 바뀌었으면 새 데이터

기간 안에 같은 데이터를 다시 읽으면 캐시가 서버와 통신하지 않고 바로 돌려줍니다. 캐시에 데이터가 아직 남아 있을 때 이야기입니다. 기간이 지난 뒤의 읽기는 캐시가 먼저 그 데이터의 리스를 연장하게 만듭니다. 만료된 사이에 데이터가 바뀌었으면 그때 캐시를 갱신합니다.

기간이 붙어 있다는 것이 고장을 다루는 방식이기도 합니다. 원 논문은 리스를 시간 기반 메커니즘으로 제안합니다. 비잔틴이 아닌 고장은 정확성이 아니라 성능에 영향을 준다고 적습니다. 그 영향은 짧은 리스로 최소화된다고 적습니다.

대가

리스를 쓰기로 하면 기간이라는 값을 하나 정해야 합니다. 원 논문은 리스 기간의 선택이 리스 연장 오버헤드를 줄이는 것과 거짓 공유를 줄이는 것 사이의 맞바꿈에 근거한다고 적습니다. 어느 쪽으로 잡아도 다른 쪽을 내줍니다.

거짓 공유는 파일 접근에 실제 충돌이 없는데도 리스 충돌이 나는 것을 말합니다. 다른 클라이언트가 리스로 덮어 둔 파일에 어떤 클라이언트가 쓰려 하는데, 정작 그 다른 클라이언트는 그 파일을 지금 쓰고 있지 않은 경우입니다.

고장 난 상대를 기다리는 시간도 리스를 쓰기로 한 순간 확정됩니다. 서버가 어떤 클라이언트와 통신할 수 없게 되면, 그 클라이언트가 리스를 쥐고 있는 파일에 대한 쓰기를 리스가 만료될 때까지 미뤄야 합니다. 클라이언트가 이미 죽었더라도 그렇습니다. 서버는 그 사실을 모릅니다.

서버는 자기가 내준 리스를 기록으로 들고 있어야 합니다. 원 논문은 그 저장 오버헤드가 크지 않다고 적습니다. 리스 소유자마다 신원 기록 하나와 그가 쥔 리스 목록이 필요하고, 리스 하나는 포인터 두어 개면 된다고 적습니다.

양쪽 시계가 제대로 도는 것도 전제로 삼게 됩니다. 리스는 시계에 기대는 메커니즘이라, 시계가 어긋나면 무엇이 무너지는지가 따로 있습니다. 그건 아래 실패 절이 받습니다.

이름의 출처

이 이름을 붙인 사람은 Cary G. Gray 와 David R. Cheriton 입니다. 두 사람은 스탠퍼드 대학교 컴퓨터과학과 소속으로 「Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency」를 썼습니다. 이 논문이 원전입니다.

논문은 1989년 12월 3일부터 6일까지 미국 애리조나 리치필드파크에서 열린 제12회 ACM(Association for Computing Machinery) 운영체제 원리 심포지엄에 실렸습니다. 이 학회의 줄임말이 SOSP(Symposium on Operating Systems Principles)입니다. 쪽수는 202쪽부터 210쪽까지이고 DOI(Digital Object Identifier)는 10.1145/74850.74870 입니다. 같은 논문이 스탠퍼드 테크리포트 STAN-CS-90-1298 로도 나와 있고, 전문은 http://i.stanford.edu/pub/cstr/reports/cs/tr/90/1298/CS-TR-90-1298.pdf 에 있습니다.

이름이 어디서 왔는지는 논문이 고른 정의 문장에 그대로 드러납니다. 재산에 대한 명시된 권리를 한정된 기간 동안 소유자에게 주는 계약, 곧 임대차 계약의 말을 그대로 가져다 캐시 일관성에 붙였습니다.

예시

Kubernetes 의 Lease 오브젝트

Kubernetes 공식 문서는 리스 개념이 coordination.k8s.io API(Application Programming Interface) 그룹의 Lease 오브젝트로 표현된다고 적습니다. 노드 하트비트와 컴포넌트 수준 리더 선출 같은 시스템 필수 기능이 이것을 씁니다.

apiVersion: coordination.k8s.io/v1
kind: Lease
metadata:
  name: apiserver-07a5ea9b9b072c4a5f3d1c3702
  namespace: kube-system
spec:
  holderIdentity: apiserver-07a5ea9b9b072c4a5f3d1c3702_0c8914f7-0f35-440e-8676-7844977d3a05
  leaseDurationSeconds: 3600
  renewTime: "2023-07-04T21:58:48.065888Z"

holderIdentity 가 지금 이 리스를 쥔 쪽의 신원입니다. leaseDurationSeconds 가 기간이고 이 예에서는 3600 입니다. renewTime 이 마지막으로 갱신한 시각입니다. 문서는 더 이상 존재하지 않는 kube-apiserver 의 만료된 리스가 한 시간 뒤에 새 kube-apiserver 들에 의해 수거된다고 적습니다.

노드 하트비트도 같은 오브젝트로 오갑니다. 노드마다 이름이 같은 Lease 오브젝트가 kube-node-lease 네임스페이스에 하나씩 있습니다. kubelet 의 하트비트는 그 Lease 오브젝트의 spec.renewTime 필드를 갱신하는 요청입니다.

etcd 의 Lease API

etcd 공식 문서는 리스를 클라이언트 생존을 검출하는 메커니즘이라고 적습니다. 클러스터가 TTL(Time To Live)을 붙여 리스를 발급합니다. 정해진 TTL 안에 클러스터가 킵얼라이브를 받지 못하면 리스가 만료됩니다.

message LeaseGrantRequest {
  int64 TTL = 1;   // TTL - the advisory time-to-live, in seconds.
  int64 ID = 2;    // ID - the requested ID for the lease. If ID is set to 0, etcd will choose an ID.
}
message LeaseGrantResponse {
  ResponseHeader header = 1;
  int64 ID = 2;    // ID - the lease ID for the granted lease.
  int64 TTL = 3;   // TTL - is the server selected time-to-live, in seconds, for the lease.
}

요청에 담는 TTL 은 권고 값이고, 실제로 적용되는 값은 응답이 돌려주는 서버가 고른 TTL 입니다. 갱신은 LeaseKeepAlive 호출로 만든 양방향 스트림으로 합니다. 클라이언트가 리스 아이디만 담은 LeaseKeepAliveRequest 를 보내면, 응답으로 그 리스에 남은 새 TTL 이 돌아옵니다.

리스가 키에 붙는다는 점이 이 구현의 형태를 정합니다. 키 하나에는 리스가 많아야 하나 붙습니다. 리스가 만료되거나 LeaseRevoke 로 회수되면 거기 붙어 있던 키가 전부 삭제됩니다.

Chubby 의 세션 리스

Chubby 는 클라이언트와 셀 사이의 관계를 세션으로 부르고, 세션마다 리스를 하나씩 답니다. 그 리스는 마스터가 세션을 일방적으로 끝내지 않겠다고 보장하는 미래의 한 구간입니다. 그 구간의 끝을 세션 리스 타임아웃이라고 부릅니다. 마스터는 이 시각을 미래로 더 밀 수 있지만 과거로 되돌릴 수는 없습니다.

마스터가 시각을 미는 자리는 셋입니다. 세션을 만들 때, 마스터 페일오버가 일어날 때, 그리고 클라이언트의 KeepAlive RPC(Remote Procedure Call)에 응답할 때입니다. 논문은 마스터가 원하는 만큼 늘릴 수 있다고 적고, 기본 연장 폭은 12초라고 적습니다. 부하가 걸린 마스터는 처리해야 할 KeepAlive 호출 수를 줄이려고 더 큰 값을 쓸 수도 있습니다.

실패

리스가 서 있는 전제는 시계입니다. 원 논문은 리스가 잘 도는 시계에 의존한다고 적고, 어긋나는 방향마다 무엇이 벌어지는지를 갈라 놓았습니다.

논문은 이런 시계 고장이 크래시나 통신 고장보다 훨씬 드물다고 적습니다. 동기화 프로토콜을 쓰거나 리스 관련 메시지에 명시적 타임스탬프를 넣으면 빠르게 검출할 수 있다고도 적습니다. 보장의 범위도 같은 자리에 그어 두었습니다. 리스는 호스트와 네트워크가 시계 고장을 포함한 특정 비잔틴 고장을 겪지 않는 한 일관성을 지킵니다. 분단을 포함한 메시지 손실과 클라이언트나 서버의 고장에는 견딥니다. 서버 쪽 쓰기가 크래시를 넘어 지속된다는 가정이 붙습니다.

리스를 쥔 쪽이 만료 시점을 확신하지 못하는 구간도 생깁니다. Chubby 논문이 그 구간을 이름 붙여 다룹니다. 클라이언트의 로컬 리스 타임아웃이 만료되면 클라이언트는 마스터가 자기 세션을 끝냈는지 알 수 없게 됩니다. 그러면 캐시를 비우고 꺼 버립니다. 이 상태를 세션이 위태롭다고 부릅니다. 클라이언트는 유예 기간을 더 기다리고 기본값은 45초입니다. 그 안에 KeepAlive 를 한 번 성공시키면 캐시를 다시 켭니다. 못 하면 세션이 만료됐다고 간주합니다.

마스터가 바뀌는 동안에도 같은 구간이 열립니다. 마스터는 마스터 자격을 잃으면 세션과 핸들과 락에 대한 메모리 상태를 버립니다. 세션 리스의 권위 있는 타이머가 마스터에서 돌기 때문에 새 마스터가 뽑힐 때까지 그 타이머는 멈춥니다. 논문은 이것이 클라이언트의 리스를 연장하는 것과 같으므로 정당하다고 적습니다. 선출이 오래 걸리면 클라이언트는 캐시를 비우고 유예 기간 동안 새 마스터를 찾습니다. 이 동안 클라이언트는 자기 리스가 마스터 쪽에서 만료됐는지 확신할 수 없습니다. 세션을 허물지는 않되 자기 API 위의 애플리케이션 호출을 전부 막습니다. 애플리케이션이 일관되지 않은 데이터를 보는 것을 막으려는 것입니다.

관련 항목

리스 기간을 나타내는 값

TTL · 타임아웃 · 유예 기간

리스 상태를 확인·연장하는 신호

하트비트 · KeepAlive · 타임스탬프 · RPC

리스 갱신에 관여하는 참여자

kubelet · 클러스터 · 마스터

마스터가 페일오버 때 버리는 상태

세션 · 락 · 핸들

리스가 발생시키는 비용

캐시 무효화 · 거짓 공유 · 지연

리스를 활용하는 분산 조정 기법

리더 선출 · 락 서비스 · 시퀀서

리스가 정확성의 전제로 삼는 조건

시계 · 네트워크 · 비잔틴 고장

리스를 실제로 구현·채택한 시스템

Chubby · etcd · Kubernetes

이 논문의 서지를 이루는 이름

ACM · SOSP · DOI