[Concurrency Control] Optimistic Version Locking

버전 락, (대개) 낙관적 락(Optimistic Locking)이라고 부르는 locking 개념에 대해서 정리해보고자 한다.

진행하고 있는 연구 구현에서 최근에 이 친구를 추가했다 ㅎ__ㅎ

 

Main idea

---

어떤 데이터에 대해서 reader가 writer 보다 훨씬 많은 상황을 생각해 보자.

즉, 갱신이 자주 발생하지는 않으며, 읽기 연산은 많이 발생하는 데이터라는 것이다.

 

여기서 비관적 락(Pessimistic Lock)처럼, 연산을 진행하기 위해서는 무조건 lock을 잡아야 한다면 매우 큰 성능 저하가 발생할 수 있다. 읽기 연산은 여러 reader가 동시에 진행할 수 있는데, 그것을 아예 막아버렸기 때문이다.

 

 

따라서 버전 락(낙관적 락)은 '우선 그냥 읽어! → 읽는 동안 쓰기가 발생했다면, 다시 읽어!'의 방식을 취한다.

 

1. 동시에 진행할 수 있는 연산은 동시에, 그리하여 빠르게 진행해 버릴 수 있도록 열어두고,

2. 만약 데이터의 갱신이 발생했다면, 해당 갱신 시점에 읽기 연산을 진행하고 있었던 reader들에 대해서 처리를 진행해 주는 것이다.

 

 

비관적 락과 낙관적 락에 대해서 매우 매우 잘 설명해 놓은 글이 있어서 아래에 링크를 남긴다.

소프트웨어 개발에서의 낙관적 락과 비관적 락의 이해

 

 

How to implement this ??

---

그렇다면 이 lock을 실질적으로 어떻게 구현할 수 있을까?

 

아래 모든 코드는 HydraList의 코드를 참고하였다.

hydralist/hydralist/src/VersionedLock.h at master · cosmoss-jigu/hydralist

 

Version

lock의 버전 정보를 저장하는 integer 변수가 필요하다.

#include <atomic>

typedef unsigned long version_t;

class VersionLock {
    std::atomic<version_t> version;
    
    ...
    
};

 

해당 값의 상태에 따라서 현재 writer가 존재하는지, 존재하지 않는지를 알아낼 수 있다.

- version 값이 짝수인 경우 : 현재 writer는 존재하지 않는다.

- version 값이 홀수인 경우 : 현재 writer가 쓰기를 진행하고 있다.

 

따라서 아래 writerExists 메서드를 통해서 writer의 존재 유무를 알아낼 수 있고,

이를 통해 writer나 reader가 현재 연산을 진행할 수 있는지를 판단할 수 있게 된다.

    bool writerExists(version_t versionToCheck) {
        return (versionToCheck & 1);
    }

 

Writer

writer는 간단하게 다음과 같이 진행된다.

 

1. lock 획득을 시도한다.

    1-1. lock 획득에 실패했다면(한 번에 하나의 writer만이 쓰기를 진행할 수 있기 때문) retry 한다. 즉, 1번으로 되돌아간다.

    1-2. lock 획득에 성공했다면 쓰기 연산을 진행한다.

2. lock을 푼다.

restart:
Block *currentTail = tail.load(std::memory_order_acquire);

if (currentTail->versionLock.writeLock() == LOCK_ACQUIRE_FAILED) {
    goto restart;
}

currentTail->insert(keyToInsert, valueToInsert);
currentTail->versionLock.writeUnlock();

 

구체적인 내부 메서드 구현은 다음과 같다.

    version_t writeLock() {
        version_t currentVersion = version.load(std::memory_order_acquire);

        if (!writerExists(currentVersion) &&
            version.compare_exchange_weak(currentVersion, currentVersion + 1, std::memory_order_acq_rel)) {

            return currentVersion;
        }
        return LOCK_ACQUIRE_FAILED;
    }

    void writeUnlock() {
        ++version;
    }

 

writer는 쓰기를 진행하기 전에 writeLock 메서드를 불러서 version 값을 1 증가시키고,

쓰기를 모두 마친 후에 writeUnlock 메서드를 통해서 version 값을 1을 증가시킨다.

 

Reader

reader도 다음과 같은 흐름으로 진행된다.

 

1. 읽기 연산을 진행하기 전에 현재의 version 값을 가져온다.

2. 읽기 연산을 진행한다.

3. 읽기 연산을 모두 마친 후, 1번에서 가져온 version 정보와 현재의 version 값을 비교한다.

    3-1. 만약 version 정보가 변경되었다면, writer가 그동안 데이터를 변경했다는 의미이므로 1번으로 되돌아간다.

    3-2. 만약 version 정보가 변경되지 않았다면 종료한다.

restart:
version_t readVersion = block->versionLock.readLock();
                
uint64_t value = block->search(keyToSearch);
                
if (!block->versionLock.readUnlock(readVersion)) {
    goto restart;
}
return value;

 

구체적인 내부 메서드 구현은 다음과 같다.

    version_t readLock() {
        version_t currentVersion = version.load(std::memory_order_acquire);

        if (!writerExists(currentVersion)) {
            return currentVersion;
        }
        return LOCK_ACQUIRE_FAILED;
    }

    bool readUnlock(version_t oldVersion) {
        std::atomic_thread_fence(std::memory_order_acquire);
        return (oldVersion == version.load(std::memory_order_acquire));
    }

 

---

 

VersionLock에 대한 전체 코드는 다음과 같다. HydraList 코드에서 내 식대로 리팩터링을 진행한 것일 뿐이다.

#ifndef VERSION_LOCK_H
#define VERSION_LOCK_H

#include <atomic>

#define LOCK_ACQUIRE_FAILED 0

typedef unsigned long version_t;

class VersionLock {
    std::atomic<version_t> version;

public:
    VersionLock() : version(2) {}

    version_t readLock() {
        version_t currentVersion = version.load(std::memory_order_acquire);

        if (!writerExists(currentVersion)) {
            return currentVersion;
        }
        return LOCK_ACQUIRE_FAILED;
    }

    bool readUnlock(version_t oldVersion) {
        std::atomic_thread_fence(std::memory_order_acquire);
        return (oldVersion == version.load(std::memory_order_acquire));
    }

    version_t writeLock() {
        version_t currentVersion = version.load(std::memory_order_acquire);

        if (!writerExists(currentVersion) &&
            version.compare_exchange_weak(currentVersion, currentVersion + 1, std::memory_order_acq_rel)) {

            return currentVersion;
        }
        return LOCK_ACQUIRE_FAILED;
    }

    void writeUnlock() {
        ++version;
    }

private:
    bool writerExists(version_t versionToCheck) {
        return (versionToCheck & 1);
    }
};

#endif // VERSION_LOCK_H

 

 

정리

---

여기서 중요한 것은 적재적소에 알맞은 locking 방법을 사용해야 한다는 것이다.

writer가 많은 상황에서 낙관적 락을 사용한다면, reader들이 retry를 하는 횟수가 늘어나기 때문에 되기 때문에 오히려 성능이 저하되기 때문이다.

 

따라서 workload의 특성을 보고, 현재 적용하려는 locking scheme이 적절한지를 검증하는 절차가 필요하다.

 

 

추가로.. HydraList에서는 retry로 인한 자원 낭비를 줄이기 위한 최적화 기법이 존재한다.

retry 횟수가 특정 threshold를 넘어갔을 경우, 지정된 시간 동안 retry를 부르지 않고 그냥 wait 하도록 한 것이다.

 

구체적인 내용과 이를 통해서 어느 정도의 성능 향상이 있었는지가 궁금하다면 논문을 직접 읽어보는 것을 추천한다.

https://www.vldb.org/pvldb/vol13/p1332-mathew.pdf

(킹드라 리스트 !!)