Chandy–Lamport, 파일이 정상이어도 백업 상태가 틀리는 이유

여러 파일을 백업할 때 각 파일의 해시가 맞으면 전체 상태도 맞을까. 백업·복구 기능을 만드는 개발자에게는 파일이 손상되지 않았는지에 더해, 함께 복원해도 되는 시점의 상태인지가 필요하다. Chandy와 Lamport의 분산 스냅샷 논문은 프로세스를 같은 순간에 멈추지 않고도 그 관계를 보존하는 방법을 설명한다.

읽은 원문은 K. Mani Chandy와 Leslie Lamport의 Distributed Snapshots: Determining Global States of Distributed Systems다. 1985년 2월 ACM Transactions on Computer Systems 3권 1호에 발표된 판본을 기준으로 한다. 아래 송금 사례와 실행 예제는 원리를 설명하려고 독립적으로 구성했다.

정상인 두 잔액을 더했는데 돈이 늘었다

두 프로세스가 각각 계정 A와 B를 관리한다고 하자. 처음 잔액은 A가 100, B가 50이다. A에서 B로 10을 보낼 때 송신 프로세스는 A에서 먼저 차감하고 메시지를 전송한다. 수신 프로세스는 나중에 메시지를 받아 B에 더한다. 수수료·다른 거래·메시지 유실은 없는 가상 상황이다.

어느 단계에서도 합계는 150이다. 다만 중간 단계에서는 이동 중인 메시지까지 포함해야 한다.

백업이 A를 전송 전에 읽고 B를 수신 후에 읽으면 100 + 60 = 160이 된다. 두 잔액 파일은 각자 실제로 존재했던 값이지만, 합친 결과에는 송신 쪽 차감 없이 수신 쪽 입금만 들어 있다. 각 파일을 읽을 때 해시를 기록하고 복원 시 그대로 돌아왔는지 확인해도 이 시간 관계는 검사하지 못한다.

반대쪽 누락도 가능하다. A를 차감 후에 기록하고 B를 수신 전에 기록하면 잔액 합계는 140이다. 이것은 전송 중인 10을 함께 기록하면 올바른 중간 상태가 된다. 프로세스의 상태만 저장하면 빠지는 통신 채널의 상태가 있다는 뜻이다.

일관성은 같은 시각보다 인과관계에 있다

각 프로세스가 어디까지 실행했는지 경계를 하나씩 정하면, 전체 실행을 여러 지점에서 잘라 모은 상태를 생각할 수 있다. 이를 cut이라고 부른다. 일관된 cut에는 결과인 메시지 수신이 들어갔는데 원인인 송신이 빠진 경우가 없어야 한다.

송신은 포함했지만 수신은 아직 포함하지 않은 경우는 허용된다. 그 메시지가 이동 중이라고 기록하면 된다. 앞의 140과 160이 다른 이유다. 140에는 기록할 수 있는 전송 중 메시지가 있지만, 160에는 아직 보내지 않은 돈을 이미 받았다는 모순이 있다.

원문의 전체 상태는 프로세스의 상태와 채널에 남은 메시지를 함께 가진다. 같은 벽시계 시각에 읽었는지를 맞추는 대신, 각 채널에서 송신 쪽 경계 전에 보냈고 수신 쪽 경계 전에는 받지 않은 메시지를 보존한다. 원문의 채널 모델과 알고리즘이 필요한 이유다.

Marker가 메시지의 어느 쪽을 잘랐는지 알려 준다

Chandy–Lamport 알고리즘은 일반 메시지 사이에 marker라는 제어 메시지를 보낸다. Marker는 해당 송신자의 스냅샷 경계를 나타낸다. 처음 스냅샷을 시작한 프로세스는 자신의 상태를 기록하고, 이후 일반 메시지를 보내기 전에 모든 출력 채널로 marker를 보낸다.

다른 프로세스가 marker를 처음 받으면 자신의 상태를 기록한다. 그 marker가 온 입력 채널의 스냅샷은 비어 있다. 다른 입력 채널에서는 지금부터 해당 채널의 marker가 도착할 때까지 받는 일반 메시지를 별도로 기록한다. 자기 상태를 기록한 프로세스는 같은 송신 규칙에 따라 출력 채널에도 marker를 보낸다.

왜 처음 marker가 온 채널은 비어 있다고 할 수 있을까. 원문은 채널이 메시지를 보낸 순서대로 전달하는 FIFO라고 가정한다. 송신자가 자기 상태를 기록하기 전에 보낸 메시지는 marker보다 먼저 도착한다. 수신자는 첫 marker를 받은 순간 자기 상태를 기록하므로 그 이전 메시지의 효과가 이미 자기 상태에 들어 있다. 반대로 송신자의 기록 이후에 보낸 메시지는 marker를 앞지를 수 없다.

이미 자기 상태를 기록한 수신자에게는 그 사이가 남는다. 수신자는 아직 받지 않았지만 송신자는 이미 보낸 메시지다. 이 구간을 채널 상태로 기록하면 프로세스 잔액에서 빠진 10을 되찾는다.

앞의 송금에서 B가 먼저 스냅샷을 시작하는 순서를 따라가 보자. A에서 B로 가는 채널과 B에서 A로 가는 채널은 각각 FIFO다. 서로 다른 두 채널 사이의 전달 순서는 같을 필요가 없다.

스냅샷의 잔액은 A가 90, B가 50이고 채널에는 10이 남는다. 실제 B는 이미 60이 되었어도 기록해 둔 B의 잔액 50을 바꾸지 않는다. 그러면 90 + 50 + 10 = 150이다. 모두 동시에 저장하지 않았어도 송금의 원인과 결과가 맞는다.

FIFO 가정을 깨면 같은 규칙이 실패한다

이 순서는 네트워크 없이 작은 Python 예제로 확인할 수 있다. 송금 메시지와 marker의 전달 순서를 고정한 축소 모형이며 분산 스냅샷 서비스의 구현은 아니다. 예제에서는 B의 기록 이후 도착한 송금을 채널에 넣고 marker에서 기록을 끝낸다.

recorded_a, recorded_b = 90, 50
recorded_channel = []
for message in ("transfer", "marker"):
    if message == "marker":
        break
    recorded_channel.append(10)
total = recorded_a + recorded_b + sum(recorded_channel)
assert total == 150

Python 3.14.5에서 전체 예제와 자체 검사를 실행하면 다음 결과를 얻는다.

mixed local snapshots: 160
in-flight transfer omitted: 140
FIFO: A=90, B=50, channel=10, total=150
non-FIFO control: A=90, B=50, channel=0, total=140

마지막 줄은 일부러 FIFO를 어겨 marker가 앞선 송금 메시지를 추월하도록 한 대조다. 수신자는 marker에서 채널 기록을 닫으므로 늦게 온 10을 놓친다. 같은 코드가 실패한다는 사실이 FIFO 가정의 역할을 보여 준다. 여러 큐나 서로 다른 연결에 데이터를 나눠 보낸 시스템에 marker만 추가하면 원문의 보장을 그대로 얻을 수 없는 이유이기도 하다.

기록한 상태가 실제 한 순간과 같을 필요는 없다

원문은 기록한 전체 상태가 실제 실행 중 관측한 어느 한 순간과도 같지 않을 수 있다고 설명한다. 대신 프로세스 내부 순서와 메시지의 인과관계를 지키면서 독립적인 사건의 순서를 바꾼 실행에서는 그 상태에 도달할 수 있음을 보인다. 따라서 이 스냅샷을 “정확히 오후 세 시의 시스템”이라고 읽으면 보장보다 강한 해석이 된다. 원문의 기록 상태에 대한 성질

이 결과는 분산 교착이나 작업 종료처럼 한 번 참이 되면 이후에도 유지되는 성질을 탐지하는 데 쓰인다. 하지만 논문이 실제 저장 장치의 장애, 손상된 파일, 복구 후 부작용의 재실행까지 해결해 주는 것은 아니다. 채널의 무손실 전달과 FIFO, marker가 결국 처리된다는 조건이 필요하다. 모든 프로세스에 기록 시작이 전파되는 경로도 있어야 한다.

파일 백업으로 돌아오면 무엇을 선택할까

파일이나 DB를 복원할 때 메시지를 재생해야 한다면 그 재생의 중복 처리도 설계해야 한다. 앞 예제에서는 채널의 10을 B에 한 번 반영해야 잔액이 60이 된다. 이미 반영한 입금을 다시 처리하는 문제는 스냅샷의 일관성과 별도의 책임이다.

모든 백업 시스템에 분산 marker가 필요한 것은 아니다. 쓰기 주체와 저장소가 적다면, 새 변경을 잠깐 막고 진행 중인 변경을 끝낸 뒤 상태를 복사하는 방법이 더 작을 수 있다. 이때는 여러 파일을 차례로 고치는 작업 전체가 끝났는지가 중요하다. 파일 하나를 원자적으로 교체해도 첫 파일 교체와 두 번째 파일 교체 사이를 백업하면 서로 다른 단계가 섞인다.

읽기 전용 버전을 만드는 저장소라면 같은 버전의 데이터를 읽는 방법도 고려할 수 있다. 외부 저장소까지 포함하면 그 저장소도 같은 경계에 참여하는지 따져야 한다. 이 선택들은 논문의 파일 백업 구현이 아니라 일관성 조건을 실제 시스템에 옮긴 설계 판단이다.

다음 백업을 검토할 때는 파일 목록 옆에 한 변경이 어디에 걸쳐 반영되는지를 그려 보면 좋다. 두 저장소를 고치는 작업이 있다면 첫 반영 직후에 복사를 끼워 넣어 보자. 각 파일의 검사는 모두 성공해도 복원한 두 상태의 관계가 깨질 수 있다면, 더 강한 해시보다 먼저 맞춰야 할 것은 기록의 경계다.