Redlock 알고리즘

개요

이전에도 동시성 관련된 글을 몇개 포스팅한적이 있다. 실무에서도 redlock알고리즘의 구현체인 aioredlock을 활용하여 동시성 제어를 진행하고 있는데, redlock 알고리즘에 대해 조금 더 자세히 살펴봐야할 것 같아서 Redis 공식 문서를 찾아봤고 나에게 필요한 부분만 추려서 번역을 진행했다. 본문은 https://redis.io/docs/reference/patterns/distributed-locks/ 에서 확인할 수 있다.

Safety and Liveness Guarantees

Safety property: 상호배제. 어떤 순간에도 하나의 클라이언트만 락을 획득할 수 있어야 한다.

Liveness property A: 데드락이 발생하지 않는 것. 락을 획득한 클라이언트에 문제가 생겨 락을 풀지 못하더라도 결국에는 락을 획득할 수 있어야 한다.

Liveness property B: 내결함성. 특정 노드에 장애가 발생해도 클라이언트는 락을 획득하고 해제할 수 있어야 한다.

Correct Implementation with a Single Instance

위에서 설명한 단일 인스턴스의 한계에 대해 설명하기 전에 단일 인스턴스처럼 간단한 경우에 올바르게 분산락을 적용하는 방법에 대해 확인해본다. 이는 때때로 레이스컨디션이 발생할 수 있는 상황에 적용이 가능한 해법이 되기도 하고, 아래에서 설명할 분산락의 기본이 되기 때문이다.

락을 획득하기 위한 방법은 다음과 같다.

 SET resource_name my_random_value NX PX 30000

위 명령어는 락이 존재하지 않는 다면 키를 세팅하고 30000ms의 타임아웃 시간을 가진다. 값은 my_random_value로 세팅된다. 이 값은 모든 클라이언트와 모든 잠금 요청에서부터 유니크한 값이어야 한다.

기본적으로 랜덤 값은 레디스에 스크립트를 보내 안전하게 락을 해제하기 위해 사용된다. 키가 존재하고 키에 저장된 값이 예상하는것과 정확히 일치하는 경우에만 키를 삭제한다. 그리고 이는 아래의 Lua 스크립트를 통해 수행된다.

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

이것은 락을 생성하지 않은 클라이언트가 락을 삭제하는것을 방지할 수 있기에 굉장히 중요한 부분이다. 클라이언트는 락을 획득할 수 있고, 락 유효시간보다 긴 시간(락이 해제되는 시간)동안 일부 작업을 수행하는것이 차단된다. 그리고 락을 해제하게 되는데, 단순히 DEL명령어만을 사용하는 것은 타 클라이언트가 생성한 락을 삭제할 수 있기에 안전한 방법이 아니다. 위 스크립트를 사용하면 락에 저장된 랜덤 문자열값을 비교한 후 이후 작업을 진행하므로 오로지 락을 획득한 클라이언트만 락을 해제할 수 있다.

그렇다면 랜덤 문자열은 어떠한 값이 되야할까? 우리는 /dev/urandom에서 얻은 20byte짜리 값으로 가정하고 있지만 좀 더 쉬운 방법으로 유니크한 랜덤값을 얻을 수 있다면 그걸로 충분하다. 예를 들어 /dev/urandom을 seed로 하여 랜덤 값을 생성하는 방법도 있을 것 같다. 더 간단한 방법은 마이크로초의 정밀도를 가진 UNIX 타임스탬프와 클라이언트의 ID를 연결하는 것이다. 안전하지는 않지만 대부분의 환경에서는 이걸로도 충분할 것이다.

lock validity time은 락 유효시간으로써 타임아웃 시간을 뜻한다. 락이 자동으로 해제되는 시간이며 다른 클라이언트가 락을 다시 획득하기 전에 락을 설정한 클라이언트가 필요한 작업을 수행하는데 걸리는 시간이다. 

이제 우리는 락을 획득/해제하는 방법을 찾았다. 이 방법을 사용하면 분산 시스템이 아닌 단일 시스템의 대부분의 경우에서 안전하다. 이제는 분산 시스템에서 락을 다루는 방법에 대해 알아본다.

The Redlock Algorithm

예를 들어 N개의 레디스 노드가 있다고 가정해보자. 각 노드는 완전히 독립적이기 때문에 복제본을 사용하거나 기타 협력 시스템을 사용하지 않는다. 위에서 이미 싱글 인스턴스 상황에서의 락 획득 및 해제 과정을 설명했었다. 그리고 우리는 그 과정이 첫 번째에서 설명한 3가지 조건에 부합한다는 것을 알고 있다. 이번 예제에서는 각 상황에 맞춰 독립적인 실패 상황을 설명하기위해 총 5개의 인스턴스가 있다고 가정한다. 

락을 획득하기 위해 클라이언트는 아래의 순서대로 명령을 할 것이다.

1. 현재의 시간을 구한다.

2. 같은 키와 랜덤한 값을 통해 모든 인스턴스를 순차적으로 방문한다. 2단계에서 모든 인스턴스에 락을 설정할 때 클라이언트는 총 락 타임아웃보다 살짝 작은 타임아웃 시간을 사용한다. 예를 들어 타임아웃이 10초라면 시간 초과 범위는 5-50ms 정도가 될 것이다. 이것을 통해 다운된 인스턴스 때문에 발생할 수 있는 지연시간을 줄인다. 만약 인스턴스가 문제가 있는 상태라면 최대한 빠르게 다음 인스턴스로 넘어가야한다.

3. 클라이언트는 락을 획득하기 위해 (현재 시간 - 1단계에서 구했던 현재 시간)을 계산하여 경과한 시간을 구한다. 클라이언트가 대부분의 인스턴스(본 예제는 5개의 인스턴스를 사용하기 때문에 3개의 인스턴스)에서 락을 획득할 수 있고, 락을 획득하는데 경과된 총 시간이 락 유효시간보다 짧은 경우 락을 획득한 것으로 간주한다.

4. 락을 획득했다면 유효 시간은 3단계에서 계산된 초기 유효 시간에서 경과 시간을 뺀 것으로 간주한다. 

5. 만약 클라이언트가 락을 획득하는데 실패했다면(예를 들어, 인스턴스 개수/2+1 개의 인스턴스를 잠글 수 없거나 유효 시간이 음수라면) 인스턴스에 락이 걸려있지 않은 상황에서도 락이 있다고 생각하고 모든 인스턴스를 대상으로 락 해제를 시도한다.

Is the Algorithm Asynchronous?

본 알고리즘은 모든 프로세스간 동기화된 시간이 없다고 가정한다. 하지만 각 프로세스의 로컬 시간이 락 타임아웃 시간에 비해 거의 동일하다는 가정에 의존한다. 이 가정은 현실 세계의 컴퓨터와 거의 동일하다. 모든 컴퓨터는 로컬 시간을 가지고 있고 각 컴퓨터마다 약간의 시간 오차는 있겠지만 우리는 해당 시간을 믿고 사용하기 때문이다.

이 시점에서 상호 배제를 조금 더 잘 다뤄야 한다. 상호배제는 락을 보유하고 있는 클라이언트가 3단계에서 언급한 락 유효 시간에서 일정 시간을 뺀 시간내에 작업을 종료하는 동안에만 보장된다.