Table of Contents
If you are more familiar with English than Korean, please see the below.
References)
https://martinfowler.com/articles/patterns-of-distributed-systems/two-phase-commit.html
1. What is 2 Pahse Commit?
여러 노드(클러스터)에서 하나의 동작처럼 리소스를 업데이트하는 방법이다. 잠깐 예시를 빌려 설명하면, 서버가 데이터를 저장하려 시도한다. 이 때, 여러 서버, DB를 가지고 있다면, 이를 문제없이 성공했다는 것을 증명하기 위한 방법론이다.
시작 하기 전, 시스템을 구성하는 단어에 대해 정의를 하자.
- coordinator: 여러 노드를 중재하는 조정자
- participant: 이 시스템에 연관된 노드들을 의미한다. 서버나 데이터베이스
2. Problem
여러 개의 노드에서 데이터가 자동적으로 저장되어야 할 때, 다른 노드들의 결정을 알기 전에 노드들은 데이터가 클라이언트에게 접근가능하도록 만들 수 없다. 각 노드들은 데이터를 성공적으로 저장했는지 실패했는지 알아야만 한다.
3. Solution
2 Phase commit의 2단계로 구성되어 있다.
prepare, 각 노드들에게 업데이트가 가능한 상태로 변경할 수 있는지 확인한다.commit, 실제 반영한다.prepare단계에서, 트랜잭션에 들어가는 각 노드들은 commit(2번째 단계)에 필요한 것들을 모조리 획득한다. 예를 들면, 잠금 상태가 필요할 수 있다. 일단 각 노드들은 commit이 가능한 것을 확신하게 되면,coordinator(조정자)에게 알리고,commit할 것이라고 약속한다. 만약 어떤 노드가 진행이 불가능한 상황이라면, 그 때 coordinator는 모든 노드에게 되돌리라고 전달한다. 그리고 모든 잠금 상태를 해지하며, transaction는 중단된다. 만약 모든 노드가 진행할 것을 동의한다면, 2번째 단계가 시작되며, 그 때 성공적으로 업데이트를 하게 된다.
간단한 분산 key-value 스토어를 구현을 고려하는 것, 2 Phase commit 프로토콜은 위의 절차를 따라 동작한다.
transactional client는 transaction 구분자를 UID(Unique Identifier)로 만든다. client는 transaction의 시작 시간과 같은 추가 정보들 역시 보호한다. 이것은 뒤에서 locking mechanism에 의해 기술 될 deadlock을 막기위하여 사용된다. client가 추적하는 UID는 시작 시간과 같은 추가 정보와 함께 노드 간 transaction을 참조하는데 사용되곤 한다. client는 client에서 다른 노드들로 모든 request와 함께 전달하는 transaction reference를 유지한다.
아래는 이를 직접 구현해보기 위한 예시이다.
class TransactionRef…
private UUID txnId;
private long startTimestamp;
public TransactionRef(long startTimestamp) {
this.txnId = UUID.randomUUID();
this.startTimestamp = startTimestamp;
}
class TransactionClient…
TransactionRef transactionRef;
public TransactionClient(ReplicaMapper replicaMapper, SystemClock systemClock) {
this.clock = systemClock;
this.transactionRef = new TransactionRef(clock.now());
this.replicaMapper = replicaMapper;
}노드 중 하나는 client를 대신하여 transaction 상태를 추적하는 coordinator 처럼 동작한다. key-value 스토어에서, 일반적으로 노드를 키 중 하나를 대해 데이터를 갖는 것이다. 이는 일반적으로 클라이언트에 의해 사용되는 첫 번째 키를 위한 데이터를 저장하는 노드로써 선택된다.
값을 저장하기 전에, client는 트랜잭션이 시작한다는 것을 알리려고 coordinator와 통신한다. 왜냐하면 coordinator는 값을 저장하는 노드 중 하나이기 때문에, client가 특정 키를 갖고 get이나 put을 시작할 때 동적으로 선택되어진다.
class TransactionClient…
private TransactionalKVStore coordinator;
private void maybeBeginTransaction(String key) {
if (coordinator == null) {
coordinator = replicaMapper.serverFor(key);
coordinator.begin(transactionRef);
}
}transaction coordinator 는 transaction 상태를 추적한다. 충돌 발생한 경우에 세부정보를 볼 수 있도록 하기 위해서 Write-Ahead Log에 모든 변화를 기록한다.
class TransactionCoordinator…
Map<TransactionRef, TransactionMetadata> transactions = new ConcurrentHashMap<>();
WriteAheadLog transactionLog;
public void begin(TransactionRef transactionRef) {
TransactionMetadata txnMetadata = new TransactionMetadata(transactionRef, systemClock, transactionTimeoutMs);
transactionLog.writeEntry(txnMetadata.serialize());
transactions.put(transactionRef, txnMetadata);
}
class TransactionMetadata…
private TransactionRef txn;
private List<String> participatingKeys = new ArrayList<>();
private TransactionStatus transactionStatus;client는 transaction의 일부분인 각 키들을 coordinator로 보낸다. coordinator가 transaction의 일부분인 모든 키들을 추적하기위한 방법이다. coordinator는 transaction 메타데이터에서 transaction의 일부분인 키들을 기록한다. 키는 트랜잭션에 관여되어있는 모든 노드들을 알기위해 사용된다. 각 key-value 는 일반적으로 Replicated Log에 복제되기 때문에, 개별의 키들을 위한 request를 제어하는 리더 서버는 transaction의 생애주기 동안 변경될 수도 있고, 그래서 실제 서버 주소 대신에 키를 추적한다. client는 이 때 put 또는 get 요청을 키 데이터를 보유한 서버로 보낸다. partitioning strategy에 의해 서버를 선택한다.
주목해야할 점은 클라이언트는 coordinator를 통하지 않고 직접 서버와 소통한다. 이는 client에서 coordinator로 coordinator에서 각 서버로 두번 데이터 전송하는 것을 피할 수 있게 된다.
class TransactionClient…
public CompletableFuture<String> get(String key) {
maybeBeginTransaction(key);
coordinator.addKeyToTransaction(transactionRef, key);
TransactionalKVStore kvStore = replicaMapper.serverFor(key);
return kvStore.get(transactionRef, key);
}
public void put(String key, String value) {
maybeBeginTransaction(key);
coordinator.addKeyToTransaction(transactionRef, key);
replicaMapper.serverFor(key).put(transactionRef, key, value);
}
class TransactionCoordinator…
public synchronized void addKeyToTransaction(TransactionRef transactionRef, String key) {
TransactionMetadata metadata = transactions.get(transactionRef);
if (!metadata.getParticipatingKeys().contains(key)) {
metadata.addKey(key);
transactionLog.writeEntry(metadata.serialize());
}
}request를 다루는 노드는 transaction id로 transaction의 일부분인 request를 탐지한다. 해당 request에서 key-value를 저장하는 transaction의 상태를 관리한다. key-value들은 직접적으로 key-value store에서 사용할 수 없지만, 저장은 분산되어야 한다.
class TransactionalKVStore…
public void put(TransactionRef transactionRef, String key, String value) {
TransactionState state = getOrCreateTransactionState(transactionRef);
state.addPendingUpdates(key, value);
}3.1. Locks and Transaction Isolation
request들이 key를 통해 잠그도록 하는 방식이다. get request의 경우 read lock을 하고, put request의 경우 write lock을 한다.
class TransactionalKVStore…
public CompletableFuture<String> get(TransactionRef txn, String key) {
CompletableFuture<TransactionRef> lockFuture
= lockManager.acquire(txn, key, LockMode.READ);
return lockFuture.thenApply(transactionRef -> {
getOrCreateTransactionState(transactionRef);
return kv.get(key);
});
}
synchronized TransactionState getOrCreateTransactionState(TransactionRef txnRef) {
TransactionState state = this.ongoingTransactions.get(txnRef);
if (state == null) {
state = new TransactionState();
this.ongoingTransactions.put(txnRef, state);
}
return state;
}write lock은 transaction이 commit되려고 하고 값이 key-value store에 표시되어야 할 때만 얻을 수 있다. 그때까지 노드는 수정된 값을 보류 중인 작업으로 추적할 수 있다.
잠금을 잠깐 연기함으로써 trnsaction 충돌 가능성을 낮춰준다.
class TransactionalKVStore…
public void put(TransactionRef transactionRef, String key, String value) {
TransactionState state = getOrCreateTransactionState(transactionRef);
state.addPendingUpdates(key, value);
}lock이 장시간동안 지속되며 완료될 때 해제되지 않는 다는 것을 주목하자. 이 put request는 transaction commit이 될 때만 해제된다. transaction 기간 동안 잠금을 유지하는 이 기술 그리고 transaction이 commit되거나 rollback될 때만 해제되는 이것을 two-phase-locking이라 부른다. two-phase locking은 serializable isolation level(직렬화 가능한 독립 레벨)을 제공하는 것에서 중요하다. serializable(직렬화 가능)은 transaction이 마치 한 번에 하나씩 실행되는 것처럼 보여지는 것을 의미한다.
3.1.1. Deadlock Prevention
lock의 예시는 두 transaction이 lock을 해제하기 위해 서로가 기다릴 때 deadlock을 발생할 수 있다. 충돌이 감지 될 때 트랜잭션이 대기 및 중단되어도록 허락되지않으면 deadlock을 피할 수 있다. 중단된 transaction과 계속할 수 있는 transaction을 결정하는 데 사용되는 다양한 전략이 있습니다.
lock manager는 WaitPolicy들을 따라 하기와 같이 구현한다.
class LockManager…
WaitPolicy waitPolicy;WaitPolicy는 request가 충돌할 때 무엇을 할지 결정한다.
public enum WaitPolicy {
WoundWait,
WaitDie,
Error
}lock은 현재 lock 을 소유하고 있는 transaction과 lock을 기다리는 transactions을 추적하는 오브젝트이다.
class Lock…
Queue<LockRequest> waitQueue = new LinkedList<>();
List<TransactionRef> owners = new ArrayList<>();
LockMode lockMode;transaction이 lock을 취득하기위해 요청할 때, lock manager는 이미 lock을 가져서 충돌하는 transaction이 없다면 즉시 lock을 부여한다.
class LockManager…
public synchronized CompletableFuture<TransactionRef> acquire(TransactionRef txn, String key, LockMode lockMode) {
return acquire(txn, key, lockMode, new CompletableFuture<>());
}
CompletableFuture<TransactionRef> acquire(TransactionRef txnRef,
String key,
LockMode askedLockMode,
CompletableFuture<TransactionRef> lockFuture) {
Lock lock = getOrCreateLock(key);
logger.debug("acquiring lock for = " + txnRef + " on key = " + key + " with lock mode = " + askedLockMode);
if (lock.isCompatible(txnRef, askedLockMode)) {
lock.addOwner(txnRef, askedLockMode);
lockFuture.complete(txnRef);
logger.debug("acquired lock for = " + txnRef);
return lockFuture;
}
class Lock…
public boolean isCompatible(TransactionRef txnRef, LockMode lockMode) {
if(hasOwner()) {
return (inReadMode() && lockMode == LockMode.READ)
|| isUpgrade(txnRef, lockMode);
}
return true;
}만약 conflict가 발생하면, lock manager는 wait policy에 의거하여 동작하게 된다.
3.1.2. Commit and Rollback
클라이언트가 충돌 없이 성공적으로 읽고 모든 키 값을 기록하면 코디네이터에 커밋 요청을 전송하여 커밋 요청을 시작한다.
class TransactionClient…
public CompletableFuture<Boolean> commit() {
return coordinator.commit(transactionRef);
}이외 더 다양한 방법론에 대한 설명이 있으나, 개념정리 정도가 목표라 일단 여기까지만 작성
': Back-end' 카테고리의 다른 글
| RabbitMQ vs Apache Kafka 비교 (2) | 2023.03.06 |
|---|---|
| 공부하면서 정리가 필요한 목록 (0) | 2022.01.18 |
| [Node.js] Stream (0) | 2021.11.22 |