서로 다른 컴퓨터의 기록에서, 무엇이 먼저였는지 어떻게 알까요?

맞습니다. 여기서는 한 서버가 기록하는 행동 하나를 사건으로 정합니다. A는 신청 내용 작성 a₁, 요청 전송 a₂, 응답 수신 a₃를 차례대로 처리합니다. B는 좌석 목록 확인 b₁, 요청 수신 b₂, 응답 전송 b₃를 차례대로 처리합니다. A와 B를 각각 하나의 과정, 영어로 프로세스(process, 순서대로 진행되는 계산 과정)라고 부르겠습니다.

한 서버 내부에서는 우리가 정한 사건 순서가 명확합니다. A에서는 a₁이 a₂에 앞서고 a₂가 a₃에 앞섭니다. B에서는 b₁, b₂, b₃ 순서입니다. 실제 큰 서버에 여러 작업이 동시에 돌아간다면 작업 흐름을 더 잘게 나누어 모델을 만들 수 있습니다. 이번 사례는 서버별 작업 한 줄씩을 관찰하는 단순한 모형입니다.

서버 사이에는 메시지 두 개만 오갑니다. m₁은 a₂에서 보내 b₂에서 받는 예약 요청이며, m₂는 b₃에서 보내 a₃에서 받는 응답입니다. 아래 여섯 사건을 끝까지 같은 뜻으로 사용하겠습니다. 도식의 줄 간격이나 화면에서의 높이는 실제 몇 초가 흘렀는지를 나타내지 않습니다.

a→b는 이 모형의 기록을 따라 a가 b에 앞선다는 뜻입니다. 램포트가 정의한 해픈드 비포(happened-before, 사건의 선행 관계)는 세 가지로 정해집니다. 같은 과정에서 먼저 기록된 사건에서 나중 사건으로 이어집니다. 같은 메시지의 전송에서 수신으로 이어집니다. 이미 a→b와 b→c가 있으면 a→c도 이어집니다.

마지막 규칙을 추이성이라고 합니다. a에서 b로 갔고 b에서 c로 갈 수 있다면 a에서 c까지 연결된 길이 있다는 뜻입니다. 다만 반대 방향을 새로 만들지는 않습니다. a₂에서 b₂로 요청이 갔다는 사실만으로 b₂에서 a₂로 되돌아가는 선을 그리면, 요청을 받기 전에 보냈다는 기록과 충돌합니다.

따라서 직접 주어진 선은 A 내부 두 개, B 내부 두 개, 메시지 두 개입니다. 그 여섯 선을 따라 앞으로 갈 수 있는 모든 쌍을 찾아 선행 관계를 완성합니다. 아무 근거 없이 선을 덧붙이지 않는다는 점이 중요합니다. 자신에서 출발해 자신으로 돌아오는 선행 경로가 생긴다면 이 사건 모형부터 다시 확인해야 합니다.

예약 요청 m₁을 따라 a₂에서 b₂로 갑니다. B는 요청을 받은 다음 응답을 보내므로 b₂에서 b₃로 갑니다. 응답 m₂를 따라 b₃에서 a₃로 갑니다. 세 번 이동한 경로는 a₂→b₂→b₃→a₃입니다. 각 구간에 메시지 전송·수신 또는 같은 과정의 순서라는 근거가 붙어 있습니다.

추이성을 한 번 적용하면 a₂→b₃를 얻습니다. 여기에 b₃→a₃를 이어 붙이면 a₂→a₃를 얻습니다. 신청 내용을 작성한 a₁도 a₂에 앞서므로 a₁→a₃까지 따라옵니다. 중간 사건을 지웠다는 뜻은 아닙니다. 긴 경로를 짧게 요약한 관계를 추가한 것입니다.

이 과정을 실제 장애 기록에 대입한다면, 메시지 식별자를 통해 어느 전송과 어느 수신이 한 쌍인지 확인해야 합니다. 서로 다른 요청을 같은 m₁로 묶으면 없던 경로가 생깁니다. 이번 모형은 두 메시지의 짝이 정확히 확인되어 있다는 전제에서 계산합니다.

우리가 적은 기록에서는 b₁에서 a₂로 가는 길이 없고 a₂에서 b₁로 가는 길도 없습니다. 이런 두 사건을 이 관계에 대해 동시적이라고 부릅니다. 이 말은 벽시계의 같은 초에 일어났다는 뜻으로 사용하지 않습니다. 현재 모형에 포함된 과정과 메시지로 두 사건의 선후를 정할 수 없다는 뜻입니다.

b₁은 b₂보다 앞서고 a₂도 b₂보다 앞섭니다. 그렇다고 b₁과 a₂ 사이의 순서까지 정해지지는 않습니다. 두 길이 나중에 b₂에서 만난다는 사실은 각각의 출발점이 어떤 순서였는지 알려 주지 않습니다. ‘같은 결과보다 먼저’라는 두 조건을 ‘둘 사이에도 먼저와 나중이 있다’로 바꾸면 추론이 한 단계 더 나가 버립니다.

만약 B가 b₁ 뒤에 별도 메시지를 보내고 A가 그 메시지를 받은 뒤 a₂를 수행했다는 기록이 추가되면, 새 모형에서는 b₁→a₂를 얻을 수 있습니다. 우리는 실제로 포함된 기록의 범위에서 판단합니다. 지금 모형의 동시성만으로 세상의 모든 전달 경로까지 부정할 수는 없습니다.

여기서는 사건의 순서를 지키기 위한 정수를 적습니다. 각 서버에 숫자를 담는 칸을 하나씩 두고 처음 값을 0으로 정하겠습니다. 서버가 일반 내부 사건이나 전송 사건을 처리할 때 값을 1 올린 뒤 그 사건에 붙입니다. A의 첫 사건 a₁에는 1, 다음 전송 사건 a₂에는 2를 붙입니다. B의 첫 사건 b₁에도 1을 붙입니다.

이렇게 사건에 숫자를 대응시키는 장치를 논리시계(logical clock, 사건의 선후를 보존하도록 붙이는 시각값)라고 합니다. C(a₂)=2는 사건 a₂의 논리시계 값이 2라는 뜻입니다. 숫자가 같다는 사실만으로 두 컴퓨터의 실제 동작 시간이 같았다고 읽을 수는 없습니다. 실제 경과 시간을 재는 단위가 붙어 있지 않기 때문입니다.

이번 계산에서는 항상 1씩 올리는 구체적인 구현을 사용합니다. 원전의 조건은 한 과정의 뒤 사건이 앞 사건보다 큰 값을 갖도록 하는 것입니다. 따라서 어떤 구현이 1에서 3으로 더 크게 올라가더라도 필요한 순서를 지킬 수 있습니다. 실험에서는 계산 과정을 비교하기 쉽도록 증가 폭을 1로 고정합니다.

수신 사건에는 전송 사건보다 큰 값이 필요합니다. B가 2라고 적으면 전송 a₂와 수신 b₂의 값이 같아져, 우리가 지키려는 a₂→b₂의 엄격한 선후를 숫자로 표현하지 못합니다. 이번 구현에서는 자기 직전 값과 받은 메시지의 값을 비교해 큰 값을 고른 뒤 1을 더합니다.

식으로 쓰면 ‘수신 값 = max(자기 직전 값, 메시지 값)+1’입니다. max는 괄호 안 값 가운데 가장 큰 것을 고른다는 뜻입니다. 지금은 max(1,2)+1=3이므로 b₂에는 3을 붙입니다. B의 직전 값 1에도, 메시지의 값 2에도 뒤따르는 숫자가 됩니다.

반대로 B가 이미 8까지 진행한 상태에서 값 2인 오래된 메시지를 받는 경우도 생각해 보세요. 계산은 max(8,2)+1=9입니다. 메시지가 오래됐다는 이유로 B의 값을 3으로 되돌리면 B가 이미 처리한 사건들의 순서가 깨집니다. 두 값을 함께 확인하는 이유를 여기서 볼 수 있습니다.

B가 응답을 보내는 b₃는 전송 사건이므로 자기 값 3에 1을 더합니다. b₃의 값은 4이고, 응답 메시지 m₂에도 4를 적습니다. A는 요청을 보낸 a₂ 이후 다음 사건을 아직 처리하지 않았으므로 직전 값이 2입니다. m₂를 받는 a₃에서는 max(2,4)+1=5를 계산합니다.

따라서 A의 세 값은 1, 2, 5이고 B의 세 값은 1, 3, 4입니다. A에서 3과 4가 빠졌다고 오류가 생기지는 않습니다. A는 메시지에 적힌 값 4를 확인했으므로 자기 다음 사건에 더 큰 값 5를 붙였습니다. 같은 서버의 연속 사건마다 값이 꼭 이어지는 정수일 필요는 없습니다.

이제 요청의 왕복 경로만 골라 읽어 보겠습니다. a₂의 2, b₂의 3, b₃의 4, a₃의 5가 차례로 증가합니다. 앞에서 직접 확인했던 a₂→b₂→b₃→a₃와 숫자의 증가 방향이 일치합니다. 아래 실험에서도 바로 이 규칙으로 값을 다시 계산합니다.

확인할 대상은 직접 연결된 두 종류의 선입니다. 같은 서버의 다음 사건에서는 값을 올리므로 앞 값이 뒤 값보다 작습니다. 메시지의 수신에서는 메시지 값보다 큰 수를 적으므로 전송 값도 수신 값보다 작습니다. 따라서 직접 그은 모든 선 u→v에 대해 C(u)<C(v)가 성립합니다.

이제 길이가 두 구간인 경로 u→v→w를 생각합시다. 앞의 확인으로 C(u)<C(v), C(v)<C(w)를 얻습니다. 수의 크기 관계도 추이적이므로 C(u)<C(w)입니다. 경로에 구간 하나가 더 붙을 때마다 같은 방법을 반복할 수 있습니다. 유한한 선행 경로 전체에서 값이 증가하는 이유가 여기 있습니다.

이것이 시계 조건 ‘a→b이면 C(a)<C(b)’를 읽는 방법입니다. 여섯 사건의 숫자를 나열한 것은 예시 검산이고, 임의의 길이에 적용되는 이유는 직접 선 두 종류와 경로 연결에 관한 논증입니다. 표본 계산과 일반적인 이유를 함께 두면 어디까지 확인했는지 명확해집니다.

그 역방향은 별도로 확인해야 합니다. b₁의 값은 1이고 a₂의 값은 2입니다. 1<2는 참입니다. 그러나 5번 질문에서 확인했듯 b₁에서 a₂로 가는 경로도, a₂에서 b₁로 가는 경로도 없습니다. 바로 우리 여섯 사건 안에 ‘숫자는 더 작지만 선행 관계는 없는’ 반례가 있습니다.

같은 사례로 조건문의 방향을 살펴볼 수 있습니다. ‘선행하면 값이 작다’는 규칙은 선행 관계가 발견됐을 때 숫자를 점검하게 해 줍니다. 숫자가 작다는 이유만으로 빠져 있는 선행 관계를 새로 만들 수는 없습니다. 이런 잘못은 p이면 q라는 전제에서 q만 보고 p를 단정하는 추론과 같은 구조를 가집니다.

유효한 시계라는 전제를 유지하면 다른 판단은 가능합니다. C(a)≥C(b)라면 a→b는 성립할 수 없습니다. 성립한다면 시계 조건이 요구하는 C(a)<C(b)와 충돌하기 때문입니다. 특히 서로 다른 두 사건의 값이 같으면 양방향 선행이 모두 배제됩니다. 반대로 값이 다르더라도 두 사건이 동시적일 수 있습니다.

논리시계 값이 작은 사건부터 놓고, 값이 같을 때 사용할 서버 순서를 미리 약속하면 됩니다. 여기서는 A를 B보다 앞에 놓는다고 정하겠습니다. 사건마다 ‘시계 값, 서버 이름’이라는 두 정보를 붙이고 앞의 숫자를 먼저 비교합니다. 숫자가 같을 때만 서버 이름의 약속을 사용합니다.

a₁의 표지는 (1,A), b₁의 표지는 (1,B)이므로 a₁을 먼저 놓습니다. 그다음 (2,A), (3,B), (4,B), (5,A)를 놓으면 a₁, b₁, a₂, b₂, b₃, a₃라는 한 줄을 얻습니다. 이미 존재하는 선행 관계는 시계 값의 엄격한 증가 때문에 그대로 보존됩니다. 같은 과정 안에서는 값이 증가하므로 같은 숫자와 같은 서버 이름의 사건 둘이 생기지도 않습니다.

이 한 줄은 처리 순서를 결정하는 약속입니다. a₁이 b₁보다 실제로 먼저 일어났다는 새로운 관찰을 얻은 것은 아닙니다. 동률일 때 B를 먼저 놓기로 바꾸면 b₁, a₁부터 시작하는 줄도 가능합니다. 어느 약속을 쓰든 확실한 선행 관계를 뒤집지 않는지 확인하는 것이 이번 계산의 기준입니다.

이번 질문만 세 과정 A, B, S를 둔 새 사례를 사용하겠습니다. A가 요청 Rₐ를 S로 보낸 뒤, B에게 ‘요청을 보냈다’는 알림 H를 보냅니다. B는 H를 받은 다음 요청 Rᵦ를 S로 보냅니다. 이 기록에는 Rₐ 전송→H 전송→H 수신→Rᵦ 전송이라는 선행 경로가 있습니다.

전송 구간마다 지연이 다르면 Rₐ가 S로 가는 동안 H가 B에 도착하고, 이어 Rᵦ가 S에 먼저 도착할 수 있습니다. A에서 S로 가는 길과 B에서 S로 가는 길이 다르므로, 보내는 순서와 중앙 접수처의 도착 순서가 달라질 수 있는 것입니다. 이것은 같은 발신자·수신자 사이의 메시지 순서를 보존한다는 조건과도 양립합니다.

요청에 붙은 논리시계 값을 예로 Rₐ=1, H 전송=2, H 수신=3, Rᵦ=4로 정하면 원래 선행 관계가 숫자에 남습니다. S가 Rᵦ를 먼저 받았다고 해서 Rₐ보다 먼저 발행된 요청이라고 판단하면 이 경로를 놓칩니다. 어떤 순서의 공정성을 지킬 것인지 먼저 정하고, 그 순서를 판단할 기록을 보관해야 합니다.

마지막 한 자리를 두 서버가 함께 내주지 않으려면, 한 번에 한 과정만 그 자원을 다루도록 정할 수 있습니다. 이를 상호배제라고 합니다. 자기 대기표만 보고 시작하면 아직 전달되지 않은 더 앞선 요청을 놓칠 수 있습니다. 원전의 절차는 자기 요청이 자기 대기열에서 가장 앞선다는 조건에, 다른 모든 과정으로부터 자기 요청 시각보다 나중인 메시지를 받았다는 조건을 함께 둡니다.

이 설명에서는 고정된 참여자들이 서로 직접 통신하고, 같은 두 과정 사이에서 메시지가 전송 순서대로 도착하며, 전송한 메시지는 결국 도착한다고 가정합니다. 요청·응답·해제 메시지를 주고받아 각자의 대기열을 갱신하는 원전 절차의 일부를 살펴보는 것입니다. 이 글의 점검은 그중 진입 조건 두 개에 초점을 맞춥니다.

교육용 점검 사례를 하나 보겠습니다. 참여자는 A, B, C이며 동률 약속은 A<B<C입니다. A의 요청은 (5,A)이고, A가 확인한 대기열에는 (5,A), (5,B)가 있습니다. A의 요청은 맨 앞입니다. B에서 마지막으로 받은 메시지의 값은 6이지만, C에서 받은 값은 아직 4입니다. C가 값 5보다 앞선 요청을 보냈는데 A가 아직 받지 못했을 가능성을 이 기록만으로 닫을 수 없으므로 기다립니다.

C에서 값 6인 메시지를 받았고 그 앞 메시지도 순서대로 모두 받았다면, 이 점검의 두 조건을 만족합니다. 반대로 C의 값이 6이어도 대기열 앞에 (4,B)가 남아 있으면 기다립니다. 아래 세 번째 실험은 이 두 조건을 계산하는 도구입니다. 실제 네트워크의 전체 상호배제 절차를 구현하거나 장애 복구까지 검증하는 도구로 표시하지 않습니다.

서버 A에서 접수한 사람이 접수증을 들고 B의 담당자에게 가서 다음 신청을 부탁했다고 해 봅시다. 서버 사이의 메시지만 모은 기록에는 사람이 종이를 전달한 사건이 빠져 있을 수 있습니다. 그 좁은 모형에서 두 신청 사이의 길을 찾지 못했다고 해서, 현실에서도 아무 전달이 없었다고 결론내리면 안 됩니다. 모형에 어떤 사건과 전달을 포함했는지가 판단의 범위를 결정합니다.

그 선행 관계를 서비스가 지켜야 한다면 접수증의 식별자나 앞선 요청의 값을 다음 신청에 함께 전달하는 방법을 생각할 수 있습니다. 새 기록이 들어오면 후속 사건이 앞선 값 뒤에 놓이도록 계산해야 합니다. 관찰하지 않은 경로를 추측으로 채우는 대신, 필요한 정보를 실제로 기록하는 설계입니다.

또한 13번의 기다리기 조건은 모든 참여자의 응답을 필요로 합니다. 한 과정이 계속 응답하지 않으면 다음 처리가 멈출 수 있습니다. 안전한 순서를 지킨다는 성질과, 어떤 장애가 생겨도 계속 진행한다는 성질은 각각의 조건을 확인해야 합니다. 이번 실험은 메시지 값과 대기열 조건을 다루며, 임의의 고장 속에서도 진행을 보장하지 않습니다.

첫째, a₂가 a₃에 선행하는가? 그렇습니다. 같은 과정의 기록으로도 알 수 있고, a₂→b₂→b₃→a₃라는 왕복 메시지 경로로도 확인합니다. 그 길에 붙은 값은 2<3<4<5입니다. 사건 경로와 숫자 계산이 같은 방향을 지킵니다.

둘째, 값 1인 b₁이 값 2인 a₂에 선행하는가? 현재 모형에서는 양방향 경로가 모두 없습니다. 수의 크기 관계 1<2를 선행 관계로 바꿀 근거가 없습니다. 셋째, a₁과 b₁을 한 줄로 정렬할 수 있는가? A<B라는 동률 약속을 쓰면 a₁을 앞에 놓을 수 있습니다. 그 결과는 우리가 정한 처리 순서이며 두 사건의 벽시계 순서를 새로 알아낸 결과로 해석하지 않습니다.

이렇게 읽으면 기록에서 얻은 관계, 관계를 보존하는 숫자, 업무 처리를 위해 덧붙인 약속이 각각 어떤 일을 하는지 드러납니다. 원전의 정의를 실제 여섯 사건에 적용하고, 가능한 추론과 성립하지 않는 역추론을 하나씩 확인한 것입니다. 세 실험에서 사건 쌍과 수신 값을 바꾸어 같은 이유가 계속 성립하는지 확인할 수 있습니다.