분산락은 여러 프로세스가 공유 자원에 접근할 때 락을 취득한 프로세스만 공유 자원에 접근하게 하는 방법이다.
분산락이 올바르게 작동하기 위해서는다음과 같은 속성을 만족해야 한다.
- 상호 배제: 오직 클라이언트 하나만 락을 보유해야 한다.
- Deadlock free: 락을 획득한 클라이언트에 문제가 발생해도, 궁극적으로 다른 클라이언트가 락을 획득할 수 있어야 한다.
- Fault Tolerance: 대다수의 레디스 노드가 동작하는 한, 클라이언트는 락을 획득하고 해제할 수 있어야 한다 .

1. 단일 인스턴스를 사용한 분산락 구현

단일 인스턴스 사용 사 다음과 같이 락을 획득할 수 있다.

# NX 는 아직 키가 없을 때만 키를 생성하는 옵션
# TTL은 키의 유효 기간. TTL은 락 유효 기간임과 동시에 클라이언트가 필요 작업을 수행할 수 있는 시간이다.
# 때문에 필요 작업 수행 시간을 고려해 TTL을 정해야 한다.
SET key random_value NX PX TTL

key는 모든 클라이언트의 락 요청에서 고유해야 한다.
random_value는 락을 획득한 클라이언트만 락을 해제할 수 있게 해주는 값이다. 레디스 분산락 해제는 키가 존재하고, 저장된 값이 같을 때만 이루어진다. 해제는 lua script로 이루어진다.

# 분산락 해제
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

레디스는 TTL을 가진 키를 생성해서 분산락에서 필요한 속성을 모두 만족할 수 있다. 다만, 레디스가 싱글 인스턴스 환경이라면 레디스는 SPOF가 된다. 복제를 사용한다고 해도 상호 배제를 완벽히 구현할 수 없다.
- 문제: 레디스 복제 시 비동기 복제로 인한 race condition 존재.
  - client A가 마스터에서 락을 획득한다.
  - 마스터에서 replica에게 키를 전송하기 전에 마스터가 다운된다.
  - replica가 마스터로 승격된다.
  - client B가 client A가 가진 락과 같은 리소스에 대한 락을 획득한다.

2. 레드락(RedLock) 알고리즘

위 문제를 해결하기 위해 레디스는 분산락에 레드락 알고리즘을 사용한다.
레드락 알고리즘은 N개의 레디스 마스터가 서로 다른 머신에서 독립적으로 실행되는 환경에서 동작한다.
레드락 알고리즘은 다음과 같다.
- 현재 시간을 밀리초 단위로 얻는다.
- N개 레디스 마스터에 대해 동일 키, 동일 랜던 값으로 락을 획득하려 시도한다.
  - 이 때 타임 아웃 시간은 락 자동 해제 시간에 비해 적게 설정해야 한다. 이를 통해 다운된 노드와 오랫 동안 통신 시도하는 것을 막는다.
- 클라이언트가 락을 획득하기 까지 경과된 총 시간(현재 시간에서 1번에서 얻은 시간을 뺀다)을 계산한다. 과반수 이상 인스턴스에서 락을 획득했고, 락 획득에 경과한 시간이 락 유효시간보다 적은 경우 락을 획득한 것으로 간주한다.
- 락을 획득했다면, 락의 유효 시간은 위에서 계산한 경과된 시간을 TTL에서 뺀 만큼이 된다. (TTL - (T2 - T1) - CLOCK_DRIFT)
  - T2, T1은 인스턴스에 락이 설정된 시간이다.
    - T1은 가장 첫 인스턴스에 락이 설정된 시간.
    - T2는 가장 마지막 인스턴스에 락이 설정된 시간.
  - CLOCK_DRIFT 값은 시계오차 가능성 만큼의 시간이다.
  - 레드락은 클럭 동기화 대신 로컬 시간이 거의 동일하게 갱신된다는 가정하에 욺직인다. 하지만, 로컬 시간은 하드웨어상의 이유로 오차가 발생한다. 이 오차를 미리 상정해서 CLOCK_DRIFT 만큼의 시간을 추가로 빼서 보수적으로 시간을 계산한다.
- 클라이언트가 락 획득에 실패했다면, 락 해제를 위해 모든 인스턴스에서 잠금 해제를 시도한다.
클라이언트는 락 획득에 실패했을 때, 동일 자원에 대해 모든 클라이언트가 모두 실패하는 현상(split brain)을 방지하기 위해 랜덤한 지연 시간을 두고 다시 시도한다. 클라이언트는 최대한 빨리 SET 명령읆 보내기 위해 멀티플랙싱을 사용하는 것이 좋다.
락 해제는 모든 인스턴스에게 해제 스크립트를 보내면 된다.

3. 레드락이 가진 문제점들과 해결책

3.1 노드 재시작

클라이언트가 과반수 노드로부터 락을 얻은 후, 해당 노드들 중 일부가 재시작되어 락 정보가 사라진다. 그러면 다른 클라이언트가 또 다른 락을 획득할 수 있다.
이 문제는 AOF 방식을 사용해도 fsync=everysec라면 1초 이내의 쓰기 손실이 발생한다. fsync=always로 한다면 성능 저하가 발생한다.
이를 해결하기 위해서는 인스턴스 충돌 후 재시작 시 TTL 최댓값보다 더 긴 시간동안 재시작한 인스턴스를 사용하지 못하게 하면 된다. 그러면 해당 인스턴스들은 인스턴스가 죽기 전에 생성된 모든 락이 만료된 후에 레드락 알고리즘에 참여하게 되어서, 영속성 설정 없이도 안전성을 유지할 수 있다.

3.2 락 연장

락을 취득한 작업이 오래걸린다면, 락을 연장해야한다. 클라이언트는 루아 스크립트를 보내 TTL을 연장하는데 과반수 인스턴스가 연장에 성공해야한다.
락 연장 스크립트 예시는 다음과 같다

-- KEYS[1]: 락의 키 이름 (예: "my_resource_lock")
-- ARGV[1]: 클라이언트가 보유한 고유 랜덤 값 (Token)
-- ARGV[2]: 새로 연장할 밀리초(ms) 단위의 시간 (TTL)

if redis.call("get", KEYS[1]) == ARGV[1] then
    -- 값이 일치하면 만료 시간을 새롭게 설정 (성공 시 1 반환)
    return redis.call("pexpire", KEYS[1], ARGV[2])
else
    -- 키가 없거나 값이 일치하지 않으면 연장 실패 (0 반환)
    return 0
end

3.3 일관성에 대한 주의 사항

분산락은 단일 물리적인 인스턴스 내에서 실행되면 뮤텍스 같은 락보다 훨씬 복잡하다. 서로 다른 노드들과 네트워크에서 다양한 실패 원인이 존재하기 때문이다.
다음과 같이 락을 획득한 뒤 파일 쓰기 작업을 하는 코드가 여러 클라이언트에서 동작한다고 해보자.

// 파일은 네트워크를 통해 읽어온다.
function writeData(filename, data) {
    var lock = lockService.acquireLock(filename);
    if (!lock) {
        throw 'Failed to acquire lock';
    }

    try {
        var file = storage.readFile(filename);
        var updated = updateContents(file, data);
        storage.writeFile(filename, updated);
    } finally {
        lock.release();
    }
}

위 코드는 다음과 같은 상황으로 인해 여러 클라이언트가 동시에 파일을 읽고, 쓰기를 진행할 수 있다.
- client1이 락을 획득한다 → client1 에서 파일을 읽어오는 도중 네트워크 지연 또는 Stop The World 등으로 락 TTL을 넘긴다 → client2가 락을 획득한다 → client1, client2가 모두 쓰기 작업을 진행한다.

fencing token1

3.3.1 펜싱 토큰(Fencing Token)을 사용해 락을 안전하게 만들기

모든 쓰기 요청에 펜싱 토큰을 포함하면 안전하게 락을 획득할 수 있다.
- 펜싱 토큰은 클라이언트가 락을 획득할 때마다 증가하는 숫자이다.
펜싱 토큰을 사용한다면, 다음과 같이 client1에 딜레이가 발생해도 최종 펜싱 토큰 값이 자신것 보다 크기 때문에, client1의 쓰기는 무산된다.
하지만 레드락 알고리즘은 자체적으로 펜싱토큰을 발급하고 관리하는 기능이 없다. 레드락 알고리즘은 랜덤한 값을 사용하는데, 이는 펜싱 토큰이 요구하는 단조성을 제공하지 못한다.

3.3.2 레디스 키 만료 기준

레디스는 키 만료를 판단할 때 monotonic clock 이 아니라 gettimeofday를 사용한다. 그런데, gettimeofday는 시간이 불연속적으로 점프해 과거나 미래로 이동할 수 있다.
레드락 알고리즘은 다음과 같은 시간 가정에 의존한다.
- 모든 레디스 노드가 키를 올바른 시간만큼 유지한다
- 네트워크 지연이 만료 시간보다 충분히 짧다
- 프로세스 중단이 만료 시간보다 짧다
이는 다음과 같은 상황에서 두 클라이언트가 락을 획득하는 상황을 야기한다.
- 클라이언트 1이 A, B, C 노드에서 락을 획득한다. 네트워크 문제로 D와 E에는 접근하지 못한다.
- C 노드의 시계가 앞으로 점프하여 락이 만료된다.
- 클라이언트 2가 C, D, E 노드에서 락을 획득한다. 네트워크 문제로 A와 B에는 접근하지 못한다.
- 이제 클라이언트 1과 2는 모두 자신이 락을 보유하고 있다고 믿는다.

3.3.3 결론

레드락 알고리즘은 위와 같은 이유로 제대로된 락을 구현하지 못하는 문제가 있다. 때문에 중복 작업이 생겨도 괜찮은 경우에만 레드락을 사용하는 것이 적절하다.
정확성이 중요한 분산락 구현이 필요하다면 주키퍼를 사용하는 것이 적절하다.

참고자료

분산락과 레드락 알고리즘

1. 단일 인스턴스를 사용한 분산락 구현

2. 레드락(RedLock) 알고리즘

3. 레드락이 가진 문제점들과 해결책

3.1 노드 재시작

3.2 락 연장

3.3 일관성에 대한 주의 사항

3.3.1 펜싱 토큰(Fencing Token)을 사용해 락을 안전하게 만들기

3.3.2 레디스 키 만료 기준

3.3.3 결론

FEATURED TAGS