Distributed Transactions

Distributed Transactions

0. Overview

이 장에서는 Distributed transaction들이 필요하다. 이것들은 하나 이상의 server에서 야기되어 지는 것을 말한다. 

Dirtributed transaction들은 flat이거나 nested인 것을 말한다.

2단게로 구성되어진 아토믹한 커밋 프로토콜을 배운다.

분산환경에서 어떻게 컨커런시를 컨트롤하는지를 배운다.

어떻게 분산황경에서의 데드락을 찾아내는지에 대한것을 다룬다. 이것을 찾아내는 알고리즘도 배운다.

서버가 실패 했을때 어떻게 복구하는지에 대해서도 배운다. 

1. Introduction

트렌젝션은 모두 원자성을 띄면서 처리가 되어져야 한다. 

이러한 것을 모두 달성하기 위해서, 서버들 중에 하나가 coordinator 규칙을 따라야 한다. 이 cordinator 룰을 반영하는 서버는 모든 서버들의 결과가 동일할것임을 보장하게 된다.

이러한 방법론은 프로토콜에 의존되어 진다.

현재 많이 알려진 프로토콜이 Two-Phase commit protocol이다.

14.2 Flat and nested distributed transactions

2개의 서로다른 구조가 존재한다. Flat과 nested이다.

Flat transaction이란, 클라이언트가 요청을 하나 이상의 서버로 보내는것을 말한다. 17.1의 예제를 보면, 클라이언트에서 T 트렌젝션이 서버 X,Y,Z로 가는것을 볼 수 있다. 주목할것은, flat transaction은 순차적으로 완료된다는 것이다. 즉, 서버 X로 간 transaction이 완료되어야 서버 Y로 가게된다. 따라서 어떤 서버가 locking을 하고 있다면, 그것에 대한 트렌젝션은 그 오브젝트가 완료될때까지 대기하게된다.

Nested transcation이란, Top-level transaction은 서브 트렌젝션을 오픈 할 수 있다. 그리고 각각의 서브 트렌젝션은 자기보다 더 낮은 서브 트렌젝션을 오픈 할 수 있다. 17.1의 예제를 보면, 트렌젝션 T가 2개의 트렌젝션 t1,t2를 오픈하는것을 볼수 있다. 이 두 트렌젝션은 서버 X와 Y의 오브젝트들을 엑세스 하게 된다. 그 다음, T1,T2의 서브트렌젝션은  T11,T12,T21,T22에 대한 트렌젝션을 오픈하게 된다.그리고 이 새롭게 오픈된 서브 트렌젝션들은 다시 M N P 서버들의 오브젝트들을 접근하게 된다. 

이러한 네스티드 에서는 같은 레벨에서의 서브 트렌젝션들은 컨커런시 할 수 있다. 그리고 서로 다른 서버에서 각기다른 오브젝트를 접근한다.

즉, T1,T2가 동시성 발생, T11,T12,T21,T22가 동시성이 발생한다.

우리는 분산 트렌젝션을 다음과 같이 고려해 본다. 그림 17.2와 같이 10달러를 계좌 A와 C에 대해서 발생 시키고, 20달러를 B와 D에 대해서 발생 시킨다. 그리고 A와 B는 서로다른 서버이고 C,D는 같은 서버이다. 

위와 같은 작업을 하나의 셋으로 구성된 4개의 Nested 트렌젝션으로 구성하면그림 17.2와 같다.

여기서 주목할것은, 네스티드이기 떄문에 4개의 트렌젝션이 모두 컨커런트하게 실행되어 질수 있고 심플 트렌젝션보다 성능이 좋다는것이다. 왜냐하면 심플의 경우 4개의 오퍼레이션들이 모두 순차적으로 발생되어지기 때문이다.

14.2.1 The coordinator of a distributed transaction.

아래의 그림 17.3은 하나의 서버가 조정자가 되는것이다

뭔가 작업이 이뤄지는 서버들은 항상 조정자 서버와의 통신이 필요하다. 즉, 커밋을 할려면 항상 조정자 서버에게 허락을 받아야 하는것이다.

그림 17.3을 보면 우선 클라이언트는 조정자로 openTransaction을 요청 한다. 그다음 조정자는 트렌젝션 구분자를 리턴하게 된다. 이 트렌젝션 구분자는 분산 시스템에서 유일한 값을 가지는 것이다. 이것을 위해서 TID는 2가지 부분으로 구성되어질 수 있다. 1) Server identifier (for example, an IP address)와 2) 서버내에서 생선한 unique한 number를 조합해서 사용할 수 있다.

이렇게 조정자가 해당 트렌젝션을 오픈을 허가 했을경우에, 조정자는 앞으로 분산환경에서 발생하게될 해당 트렌젝션에 대한 커미팅과 어볼팅을 모두 책임지게 된다. 즉 반환받은 T를 이용해서 항상 클라이언트는 작업을 요청하게된다. 

participant: 이제 각각의 서버들은 트렌젝션에 참여를 할 것이다. 그리고 이 트렌젝션에 참여한 오브젝트들은 서버마다 각기 다를것이다. 이렇게 트렌젝션에 참여를한 오브젝트들의 집합을 participant라고 정의한다.

participant는 모든 recoverable object들에 대한 유지를 책임진다.

participant는 조정자가 커밋 프로토콜에서 케리아웃 하는것에 대한 협조를 책임진다.

트렌젝션이 진행되어지는 동안, 조정자는 기록 한다. 참조 리스트를 participant들로 가는 그리고 각각의 participant 기록들을 coordinator들에 대한 참조를.

조정자의 인터페이스는 아래와 같이 4개가 있다.

openTransaction() -> trans;

closeTransaction() -> (commit, abort);

abortTransaction()

join(Trans, reference to participant) // 새로운 participant가 transaction에 합류 했는지를 확인 한다.

그림 17.3에 대해서 설명을 한다.

본 구조는 flat banking 구조를 따른다. Branch X, Branch Y, Branch Z.는 각각의 서버를 나타낸다.

하나의 예로 클라이언트에서 b.withdraw를 하게된다면, 조정자에게 해당 작업을 요청한다. 이때 해당 트렌젝션에 필요로한 participant가 있다면 그냥 그걸 실행 하면 되고, 없다면 join을 발생시켜서 조정자가 해당 reference를 트렌젝션에 인가한다. 이렇게해서 작업을 모두 처리하고 나면, closeTransaction을 해서 모든 reference를 제거한다.

주목할 것은, abortTransaction을 이용해서 조정자는 participant를 transaction에서 제거 할 수 있다.

14.3 Atomic commit protocols.

분산환경에서의 transaction은 atomic 해야한다. 즉 모든 트렌젝션이 실행 되거나, 아니면 실행이 아에 안되야 한다. 그 사이의 상태는 있을수 없다.

이것을 구현하기위한 간단한 방법은, 조정자가 커밋과 어볼트를 모든 참여자에 대해서 처리하는 것이다. 이러한 방법을 on-phase atomic commit protocol. 이라고 한다

단점: 이 방법은 서버 스스로 트렌젝션에 대한 어보트와 커밋을 결정할 수 없기 때문에 문제가 된다. 왜냐하면, 리소스에대한 락킹 매커니즘을 사용했을때, 데드락이 발생할 수 있고, 그경우 서버는 클라이언트가 인지하지 못하는 상태에서도, 스스로가 트렌젝션을 어보트 해야한다. 하지만 이 방법은 서버 스스로가 어보트를 시킬수 없기 때문에 데드락을 해결할 수가 없다. 이것을 조정자가 처리해주기에는 조정자는 가각의 서버들이 언제 크래쉬 되었는지를 알아내기 어렵다.

Two-phase commit protocol.

이 개념이 나온 이유는, participant 스스로가 트렌젝션의 일부분을 abort 시키기 위함이다. 이렇게해야 데드락 문제를 발생 시키지 않는다. 하지만 트렌젝션은 atomic해야 하기 때문에 트렌젝션의 일부분이 어보트 되더라도 트렌젝션 전체가 다시 롤백해야한다. 이 문제를 다시 해결 해야한다.

첫 번째 phase에서는, 각각의 participant가 트렌젝션에 대해서 commit인지 abort인지를 투표하게 된다. 일단 하나의 participant라도 commit을 투표한다면, 절대로 abort 되어질 수 없다. 따라서 참여자의 커밋은 신중해야하며, 궁극적으론 어떠한 문제조 발생 시키지 않는다는것을 보장해야 한다. 

그리고 이것을 위해서 준비단계에서 모든 오브젝트를 트로지에 저장하게 된다.

두 번째 phase에서는, 모든 참여자들은 joint decision을 싱행하게 된다. 만약 어떤 하나의 참여자가 어보트를 투표하게 된다면, 그때 반드시 트렌젝션 전체가 어보트 되어저여햔다. 

모든 참여자가 커밋을 요청 했을 때마 트렌젝션은 커밋 되어 질수 있다. 

문제점: 모든 참여자들의 투표를 검증하는 것이 문제이다. 즉 실패해대한 처리가 어렵다.

14.3.1 The two-phase commit protocol

결국 핵심 알고리즘은 17.5와 같다.

2개의 Phase는 voting과 vote 결과에 따르는 완료로 구성되어진다.

2단계 끝 부분에서, 조정자와 모든 참여자들은 Yes를 투표하면 즉시 영송적인 저장 장치에 해당 트렌젝션을 저장해서 커밋을 위한 준비를 한다. 만약 No라고 하면 즉시 버린다.

3을 보면 조정자는 투표들을 수집하게 된다.

3-a) 모든 투표가 Yes 라면. 조정자는 커밋을 결정한다. 그리고 doCommit 요청을 각각의 참여자들에게 보낸다.

3-b) 달느 한편으로, 조정자는 트렌젝션의 어보트와 doAbort 요청을 투표시 yes를한 모든 참여자들에게 보낸다. No라고 한 참여자들은 스스로 알아서 어보트 했기 때문에 보낼 필요가 없다.

4에서는 yes를 투표한 참여자들은 조정자로부터 doCommit 또는 doAbort 요청 메시지를 받을때 까지 기다리게 된다. 만약 참여자가 이 두 메시지중 1개를 받는다면, 그것에따라서 동작하게 된다. 그리고 만약 commit의 경우 haveCommitted를 호출해서 조정자에게 정상저으로 커밋 했다는것을 최종적으로 알리게 된다.

14.3.2 Two-phase commit protocol for nested transactions

가장 바깥쪽의 transaction T가 서브 트렌젝션은 t1,t2,t11,t12,t21,t22는 서브트렌젝션.

각각의 서브 트렌젝션은 그것의 부모 이후에 시작하게 된다. 그리고 그것 이전에 끝나게 된다.

따라서, t11과 t12가 t1 이후에 시작하게대고, 끝나는것은 t1 이전에 끝나게 된다.

서브트렌젹센이 완료되었을때, 그것은 독립적으로 결정하게 된다. 일시적인 커밋과 abort를 

일시적인 commit은 prepared commit과는 다르다. 그것은 permanent storage에 back-up하는것과는 다르다.

만약 서버가 커밋이후에 crash되어 진다면, 커밋 교체는 가능하지 않다. 왜냐면 영속적인 저장 장치에 백업을 하지 않았기 때문이다. 

따라서 Two-phase commit 프로토콜을 사용해서 nested transaction을 수행하는것이 올바르다.

서브 트렌젝션을 위한 조정자는 서브 트렌젝션을 오픈하는 operation을 제공한다. 그것은 Top-level 트렌젝션을 위한 구분자를 리턴한다. 클라이언트는 서브 트렌젝션을 시작한다. openSubTransaction 오퍼레인션을 실행 시켜서, 이것에 대한 동의는 부모 트렌젝션이 승인하게 된다. 새로운 서브트렌젝션들은 자동으로 parent 트렌젝션들에게로 조인하게 된다 그리고 서브트렌젝션을 위한 트렌젝션 구분자들은 리턴된다.

서브트렌젝션을 위한 구분자는 반드시 부모 트렌젝션의 TID를 확장해서 만들어 져야한다. 즉, 모든 시스템에서 유니크한 정보를 담고 있어야한다. 클라이언트는 최종적으로 트렌젝션을 완료하게 되면, closeTransaction 또는 abortTransaction을 탑 레벨 트렌젝션 조정자에서 실행 시켜서 끝내게 된다.

nested transaction들이 그것의 오퍼레이션들에 의해서 실행되어 지게 된다. 그리고 그것들이 완료 되었을 때, 서버는 서브트렌젝션들이 일시적으로 committed 되었는지 아니면 aborted 되었는지를 기록하게 된다. 

주목할것은, 만약 부모의 트렌젝션이 abort되었다면 반드시 서브트렌젝션들은 강제로 abort 되어야 한다.

탑 레벨 트렌젝션 T와 그곳의 서브트렌젝션은 그림 17.8과 같다. 이 그림은 17.1을 기반으로 새롭게 작성한것이다. 각각의 서브트렌젝션들은 임시적으로 committed 또는 aborted를 실행하게 된다. 예를들면, T12는 임시적으로 커밋을 수행 했다. 그리고 T11은 abort를 실행 했다. 

T12는 부모 트렌젝션인 T1에 의해서 자신의 운명이 결정되어지며, 궁극적으로 top-level 트렌젝션 T에 의해서 모든 서브트렌젝션들이 결정되어 진다. 

즉, T21과 T22가 둘다 잠정적으로 커밋했더라도 T2가 어보트 할경우 이 두개는 반드시 어보트 되어진다. 

(분산 트렌젝션의 원자성의 원리에 근거해서)

T는 비록 T2가 aborted이지만 커밋일 수 있다. 또한 T1은 커밋을 결정할 수 있다 비록 T11이 어보트일지라도.

최상위 레벨 트렌젝션이 완료되었을 때, 그것의 조정자는 Two-phase commit protocol을 실행하게 된다.  

오직한가지 이유가 있다. 참여자의 서브트렌젝션이 완료되어지지 못하는 경우는, 만약 crashed되어지는 시점이 임시 커밋이 이뤄진다음일 경우이다.

조정자는 parent와 서브 트렌젝션들에대한 모든 상태들을 알고 있어야 한다. 모든 서브트렌젝션은 어보트할경우 부모 트렌젝션에게 반드시 이를 보고한다. 따라서 최상위 수준의 트렌젝션은 모두 하위 서브트렌젝션의 상태에 대해서 알 수 있다. 그리고 조정자는 이 최상위 수준의 트렌젝션이 가지고 있는 정보만 참조하면 되는 것이다.

17.8을 기반으로 각각의 조정자가 가지고 있는 정보를 표현한 것이 그림 17.9이다. 

주목할것은, T12,T21은 조정자의 정보를 공유한것이다. 왜냐하면 같은 서버 N에서 동작하기 때문이다.

서브트렌젝션 T2가 어보트 되었을때, 그 사실은 부모인 T 트렌젝션에게로 보고 된다. 하지만 T21, T22 서브트렌젝션들에 대한 정보는 전달하지 않는다. 왜냐하면 T2가 어보트했기때문에 그 자식인 두 서브트렌젝션의 정보는 무엇이 되었는 상관이 없기 때문이다.

서브트렌젝션의 고아현상(orphan)은 다음과 같다.만약 조상중에 하나가 어보트 되었거나, 그것의 조정자가 crash 되었기 때문이다. 

우리의 예제에서는, T21과 T22가 고아이다. 왜냐하면, 그들의 부모가 탑 레벨 트렌젝션에 자신들의 정보를 넘기지않고 어버트 되어졌기 때문이다. 하지만 조정자는 그들의 parent의 상태를 조사하게된다. getStatus operation을 사용해서. T21과 T22는 모두 provisionally committed 이지만 그냥 aborted 되어 진다. 최상위 레벨 트렌젝션이 커밋 되어지더라고 상관없이, 왜냐하면 자신의 부모가 어보트 되어졌기 때문이다.

이제 TPC(Two phase commit)을 수행한다. 투표를 하게될 참여자 들은 T, T1, T12 이다. 다른것들은 모두 어보트 되었거나 고아이기 때문에 투표를 하지 않는다. 

phase 1: 커밋을 투표한다면, 반드시 그들의 트렌젝션 내용은 영속적인 저장장치에 저장이 되어야 한다.

phase 2: 조정자는 투표결과를 수집하고 참여자들의 결과에 대해서 확인 한다.

이때 phase2에서의 동작방식은 non nested case일때와 동일하다.

그렇게 해서 최종적으로 참여자들의 투표 결과에 따라 aborted 인지 커밋인지를 결정한다.

이제 TPC protocol을 2가지 방식으로 수행한다. hierarchic or flat 방법이다.

Hierarchic two-phase commit protocol: 

이 접근법은, two-phase commit protocol은 멀티레벨 네스티드 프로토콜이 된다. 

최상위 레벨 트렌젝션 조정자는 서브 트렌젝션 조정자와 통신을 한다. 이렇게 연결된 각각의 조정자들은 canCommit?이라는 메시지를 보내서 확인을 한다. 이것은 트리구조로써 점점 하위로가면서 처리가 되어지는 형태이다. 각각의 참여자들은 그들의 부모에게 보고하기전에 자손들의 응답을 모두 받은다음에 부모에게 최종적으로 응답하게 된다. 

우리의 예제를 통해서 설명을 하면 다음과 같다.

T는 canCommit? 이라는 메시지를 조정자 T1에게 보낸다. 그리고 T1은 canCommit? 이라는 메시지를 T1의 자식인 T12에게 전송한다. T2는 어보트 했기 때문에 투표에 참여하지 않는다.

canCommit의 아규먼트에 대해서 알아보자.

첫 번 째 아규먼트인 TID는 최상위 레벨 트렌젝션의 것이다. 이것은 데이터를 준비할때 사용한다.

두번째 아규먼트는 참여자에 대한 TID이다. 이 두번쨰 아규먼트를 통해서 호출에 대한 결과값 구분을 하게 된다.

예를들어서 조정자 T12와 T21은 서로 같다. 왜냐하면 이것은 같은 서버에서 동작하는 서브 트렌젝션이기 때문이다. 하지만 canCommit? 콜에대한 리턴을 받을때, 두번째 아규먼트는 T1 이고 그것은 T12로 다뤄 질 것이다.

canCommit? (trans,subTrans) -> Yes/No

Flat two-phase commit protocol: 

canCommit? (trans,abortList) -> Yes/No

조종자가 모든 임시적으로 커밋을한 참여자들에 대해서 투표를 요청하게 된다. 그러면 참여자들은 Yes/No를 투표하게 된다.

이것의 핵심은 최상위 레벨 조정자가 canCommit을 보낸다는 것이다. 모든 provisional list에 있는 서브트렌젝션의 조정자들에게 말이다.

 

3. Concurrency Control in Distributed Transactions

컨커런시한 트렌젝션이 실행 될수 있으므로, 각각의 서버들은 이것을 메니지 해줘야한다.

즉, 트렌젝션 U와 T가 같은 서버에서 실행되고 공통의 자원에 대해서 엑세스를 한다면, 그것의 순서를 반드시 메니지 해줘야 한다는 것이다.

14.4.1 Locking

락은 같은 서버에서 지역적으로만 유지가 된다.

로컬 락의 매니지먼트 방법은 다음과 같다.

락의 승인을 요청허가나 그것이 안되면 문제가 발생한 트렌젝션이 끝날때가지 기다려야한다.

분산에서 데드락이 발생하는 상황은 아래와 같다.

이 문제는 트렌젝션의 어보트를 통해서 해결할 수 있다. 결국 이래서 TPC를 사용해야 하는것이다.

14.4.2 Timestamp Ordering Concurrency Control

싱글 서버 트렌젝션은 유니크한 타임스템프를 가진다.

14.5 Distributed deadlocks

분산에서는 wait-for graph을 그려서 찾을 수가 있다. 분산환경에서의 데드락을

Wait-for graph

1) Node: transactions and data item

2) Edges: a data item that held or waited by a transaction 

위 그림 17.2는 분산 데드락이 있는 트렌젝션들이다.

우선 트렌젝션은 U,V,W가 있다 이 3개는 상호 작용을 하면서 동작을 한다.

오브젝트 A는 서버 X

오브젝트 B는 서버 Y

오브젝트 C와 D는 서버 Z

위 관계를 wait-for graph으로 그린것은 그림 17.3과 같다.

그림 중 (a)는 모든 에지들로 구성된 데드락 사이클을 보여준다. 트렌젝션 때문에 기다리는 오브젝트와 그리고 트렌젝션을 유지하고 있는 오브젝트를 나타내고 있다. 단순히 기다리고 있는 오브젝트들에 대해서만 그림을 그린것이 (b)이다.

결국 이러한 분산 데드락을 발견해 내기 위해서는, local wait for graph을 그려야한다. 이것을 각각의 서버에 대해서 생성을 하면 아래와 같다.

Server Y: U-> V (added when U requests b.withdraw(30))

Server Z: V->W (added when V requests c.withdraw(20))

Server C: W->U (added when W.requests a.withdraw(2))

그리고 위와 같은 local deadlock을 합쳐서 global wait for graph을 생성하면 된다.

Centralized deadlock detection 

이러한 deadlock을 찾아내는 간단한 솔루션은  Centralized deadlock detection 기술이다.

각각의 서버들이 자신들의 local-wait-graph을 중앙서버로 전송을 하고, 그것을 합병해서 global wait-for graph을 생성하게 된다. 그 다음, global deadlock detector는 각각의 사이클을 체크해서 분산 데드락을 찾게 된다.

데드락을 찾으면 해당 서버에게 트렌젝션을 어보트 시켜서 해결을 할것인지를 확인하게 된다.

단점: 

하지만 이것은 좋은 생각이 아니다. 이러한 방식은 싱글서버로 전달해야하는 문제점이 있다.

이러한 문제점은 다음과 같은 단점을 야기 시킨다,.

1) 접근성이 떨어진다.

2) 고장 허용이 약해진다.

3) 확장성이 떨어진다.

4) 주기적으로 local wait for graphs를 전송하는것은 비용이 많이 든다. 주기를 떨어 틀이면 데드락 디텍션 시간이 길어지기 때문에 주기를 마냥 길게할 수도 없다.

Phantom deadlocks: 데드락을 찾았지만 실제 데드락이 아닌것을 부르는 말이다. 

즉, 데드락을 찾기위해서 정보를 병합하는 과정에 데드락이 이미 해결되었는데, 그 정보가 제대로 반영이 되지 않았을 경우에 발생하는 문제이다.

잘이해가 안가니 예제를 들어서 설명하도록 하겠다.

X와 Y로 부터 Local wait for graph를 받았다고 치자. 

T->U (at X)

V->T (at Y)

이상태인대 이제 T->U이게 바뀌여서 U->V를 한다고 치자.

그럼 U->V->T가 된다.

그런데 여기서 global detector가 서버 X에 대한 local wait for graph을 갱신받지 않았다면,

T->U는 이미 존재하지도 않은 트렌젝션이지만 이걸 반영해서

T->U->V->T 라는 global wait for graph을 생성하게 되어서, deadlock이 있다고 판단해 버린다. 이러한 경우를 팬텀 데드락이라고 한다. 

Edge chasing (Path Pushing)

이방법은 global wait for graph를 구성하지 않는다. 각각의 서버들은 그것의 edge들에 대해서 알고 있는 지식을들 전송한다. 서버들은 사이클들을 찾으려고 노력한다. 서로 probe을 전송하면서, 

probe는 분산 시스템 전반에 걸친 edge들에 대한 내용이다. 

prob 메시지는  트레젠셕의 관계들로 구성되어 진다.

즉 이것은 서버들의 전체적인 에지를 말하게된다.

첫번째 질문: 서버는 언제 probe를 전송 하는가?

이 알고리즘은 3가지 스탭을 가진다.

initiation, detection and resolution

initiation: 서버 T 트렌젝션이 시작하자마자 다른 트렌젝션 U 때문에 웨이팅 되어지는 것을 인지하게 된다. 이러한 관계를 초기에 발견하고 edge를 생성하게 된다 그것이 T->U 이다. 그리고 U는 블럭 되어져 있는 상태이다. 

detection: 

이 단계는 probes의 receiving과 deadlock 발생의 구분, probe의 포워드로 구성된다.

예를들어서, 서버는 probe <T->U>를 받았다고 치자. <T->U>는 T는 트린젝션 U에 대해서 기다리고 있는 것을 나타낸다. 왜냐하면 U는 local object를 홀드하고 있기 때문이다.

그곳은 U 또한 기다리고 있는 상태인지를 체크하게 된다. 만약 그 U 트렌젝션 또한 V 라는 트렌젝션에 의해서 대기중이라면, probe를 추가한다. ( making it <T->U->V>

이렇게하여서, global wait for graph의 path들을 통과하는 하나의 edge가 생성되게 되어진다. 

resolution: 

사이클을 찾아냈을떄 사이클 내의 트렌젝션을 오버트해서 데드락을 제거한다.

그림 17.5의 예제를 들어서 Edge chasing 방법을 설명하도록 하겠다.

• 서버 X는 초기 발견을 해서 probe< W->U >을 B의 서버(Server Y)로 전송 한다.

• 서버 Y는  probe< W->U >을 받는다. 주목할것은 B는 트렌젝션 V에 의해서 홀드되어지고 있다. 따라서 V는  probe< W->U >에 추가되어지고  probe< W->U->V >가 되어진다. 그리고 V가 기다리고 있는 C의 서버 Z에게 이 probe를 포워드 한다.

• 서버 Z은 probe< W->U->V >을 받는다. 그리고 Z는 자신의 객체 C가 트렌젝션 W에 의해서 홀드되어져 있기 때문에 이것은 현재 전송받은 probe에 추가한다. 최종적으로 probe< W->U->V ->W >가 생성 된다.