Redis 분산락 알고리즘 Redlock의 특징과 한계

아래 Redis 문서를 참고했습니다.
https://redis.io/docs/manual/patterns/distributed-locks/

싱글 인스턴스로 구성된 Redis에서의 올바른 분산 락 구현

락을 획득하기 위해 사용하는 Redis 명령어는 다음과 같다.

SET resource_name my_random_value NX PX 30000

이 명령어는 키가 아직 존재하지 않을 경우에만(NX옵션) 키를 설정하고, 30초 동안 expires 시간을 설정한다. my_random_value(key)는 락을 안전하게 해제하기 위해 사용되며 이 값은 모든 클라이언트와 락 요청에서 고유해야 한다.

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

만약 아무런 검증없이 락 해제 요청을 허용하면 락을 획득하지도 않은 클라이언트가 락을 해제할 수 있으므로 안전하지 않다. 따라서 Lua 스크립트를 사용하여 키가 존재하고, 키에 저장된 값이 기대하는 값과 일치하는 경우에만 키를 제거한다. 즉, my_random_value는 다른 클라이언트에 의해 생성된 락을 제거하는 것을 방지한다. 하지만 단일 Redis 노드는 SPOF이 될 수 있으므로 Master-Slave모드로 Redis 서버를 구축하기도 한다.

Redis 분산 락이 보장해야 하는 세 가지 속성

공식 페이지를 살펴보면 분산 락은 아래 세가지 속성을 보장해야 한다고 한다.

1. Safety Property : Mutual Exclusion
어떤 순간에도 단 하나의 클라이언트만이 특정 리소스에 대한 락을 보유할 수 있다는 것을 의미한다. 상호 배제성(Mutual Exclusion)은 동시성 제어의 가장 기본적인 원칙 중 하나로, 분산 시스템에서 이를 보장하기 위해, 락 획득 시도를 성공한 클라이언트만이 해당 리소스에 대한 접근 권한을 갖게 된다.

2. Liveness Property A : Deadlock Free
만약 락을 획득한 클라이언트에 장애가 발생해 정상적으로 락을 반납하지 못했을 때 영영 다른 클라이언트들이 락을 획득할 수 없는 데드락이 발생해서는 안된다는 것을 의미한다. 이는 락에 타임아웃을 설정하거나, 락을 획득한 클라이언트가 실패할 경우 자동으로 락을 해제하는 메커니즘을 통해 다른 클라이언트에게 락을 제공할 수 있어야한다는 뜻이다.

3. Liveness Property B : Fault Tolerance
여러 Redis 노드가 존재하는 경우, 일부 노드에 장애가 발생하더라도 클라이언트는 정상적으로 락을 획득하고 반납할 수 있어야 한다는 것을 의미한다. 결함 허용은 분산 시스템에서 중요한 특성으로, 개별 컴포넌트의 실패가 전체 시스템의 기능에 미치는 영향을 최소화 해야한다.

왜 분산 락 라이브러리의 장애 조치 구현만으로 충분하지 않은지?

공식문서에서는 현재 Redis의 분산 락 라이브러리의 한계점과 왜 장애 조치 구현만으로는 충분하지 않은지 설명하고 있다. Redis를 사용해 락을 구현하는 가장 간단한 방법은 인스턴스 내의 키를 생성하는 것이다. 이 키는 Redis의 expires 기능을 통해 제한된 시간동안만 존재하고, 클라이언트가 락을 해제하고 싶을 때 키를 삭제한다.

이 방식의 문제는 단일 실패 지점(single point of failure)이 될 수 있다는 점이다. Redis의 Master가 다운되면 Slave가 Master 역할을 하기위해 데이터 복제(Replication) 작업을 수행하게 된다. 이때 Redis는 기본적으로 비동기 복제 방식이기 때문에 아래와 같은 시나리오에서 데이터의 경쟁 상태 문제가 발생할 수 있다.

1. 클라이언트 A가 마스터에서 락을 획득한다.
2. 키에 대한 쓰기가 슬레이브 노드로 전송되기 전에 마스터가 다운된다.
3. 슬레이브 노드가 마스터로 승격된다.
4. 클라이언트 B는 A가 이미 잠금을 보유하고 있는 동일한 리소스에 대한 잠금을 획득한다.

즉, 새로운 마스터 노드는 클라이언트 A에 의해 설정된 락 정보를 가지고 있지 않기 때문에, 클라이언트 B는 동일한 리소스에 대한 잠금을 획득하게 되어 경쟁 상태가 발생할 수 있다.

Redis가 제공하는 분산 락 Redlock 알고리즘

Redis는 분산 락 알고리즘의 구현으로 Redlock 알고리즘을 제안한다. Redlock은 N개의 독립적인 Redis 마스터 노드들을 이용하여, 과반수 이상의 노드에서 락을 획득하면 분산 락을 획득한 것으로 판단한다. 클라이언트는 분산 환경에서 락을 획득하기 위해 다음 작업을 수행한다.

1. 현재 시간을 ms 단위로 가져온다.
   
   
2. 클라이언트는 모든 N개의 Redis 인스턴스에서 순차적으로 락 획득을 시도한다. 각 인스턴스에서 락을 설정할 때, 클라이언트는 전체 잠금 자동-해제 시간(락이 자동으로 해제되기까지의 시간)에 비해 작은 타임아웃(락 획득 시도에 대해 응답을 기다리는 최대 시간)을 사용하여 잠금을 획득한다. 예를 들어 자동-해제 시간이 10s인 경우, 타임 아웃은 5~50ms가 될 수 있다. 이를 통해 특정 Redis 노드가 다운되어 있을 때 클라이언트가 오랫동안 블로킹되는 것을 방지할 수 있다.
   
   
3. 클라이언트는 (현재 시간 - 1단계에서 얻은 timestamp)를 통해 락을 획득하기 위해 경과한 시간을 계산한다. 만약 클라이언트가 과반이 넘는 (N/2 + 1)인스턴스에서 락을 획득했고, 총 경과 시간이 락 유효 시간보다 짧은 경우에만 락을 성공적으로 획득한 것으로 간주한다. 과반수 이상의 인스턴스에서 락을 획득하도록 요구함으로써, SPOF로 이어지지 않도록 한다. 과반수 이상의 인스턴스에서 락을 획득함으로써, 두 개 이상의 클라인언트가 동일 리소스에 대해 동시에 락 획득하는 것을 방지하고, 어떤 단일 인스턴스의 실패가 전체 시스템의 락 획득을 영향을 주지 않는다는 것이다.
   
   
4. 분산 락을 획득한 경우, 락의 유효 시간을 조정한다. 이는 초기 설정된 락의 유효 시간에서 락 획득에 실제로 걸린 시간을 빼서 계산한다. 이렇게 조정된 유효 시간은 클라이언트가 리소스를 사용할 수 있는 남은 시간을 나타낸다.
   
   
5. 분산 락을 획득하지 못한 경우(과반이 넘는 인스턴스를 잠글 수 없거나 유효 시간이 음수인 경우), 클라이언트는 모든 인스턴스에서 잠금을 해제하려고 시도한다.

실패 시 재시도

클라이언트가 잠금을 획득할 수 없는 경우 동시에 동일한 리소스에 대한 잠금을 획득하려는 여러 클라이언트의 동기화를 해제하기 위해 무작위 지연 후 재시도 해야 한다. 이를 통해 클라이언트 간의 시도를 비동기화하여 경쟁 상황을 줄인다. 몰론 이로 인해 어떠한 클라이언트도 잠금을 획득하지 못하는 split brain condition 문제가 발생할 수 있다.

이를 위해 클라이언트는 가능한 동시에 여러 Redis 인스턴스에 대해 'SET' 명령을 보내려고 시도해야 한다. 이는 multiplexing 같은 기술을 사용하여 구현할 수 있으며, 이 방식은 동시에 여러 Redis 인스턴스에 명령을 보내어, 락 획득 과정의 시간을 최소화하고, split brain condition 가능성을 줄인다. 재시도 노력에도 불구하고 클라이언트가 분산락을 획득하지 못했다면 락을 최대한 빨리 해제함으로써 다른 클라이언트가 잠금을 다시 획득해 키 만료를 기다리지 않고도 리소스에 대한 접근 권한을 회복할 수 있게 해야 한다.

Redlock 안정성은 어떨까?

클라이언트가 다수의 Redis 인스턴스에서 락을 획득할 수 있으면, 모든 인스턴스에는 동일한 TTL을 가진 키가 설정된다. 그러나 키는 서로 다른 시간에 설정되므로 만료 시간도 다를 것이다. 첫 번째 키가 T1 시간에 설정되고, 마지막 키가 T2(모든 락 설정 시도가 완료된 시간) 시간에 설정된다면, 첫 번째 키의 만료까지 남은 시간은 최소 MIN_VALIDITY = TTL-(T2-T1)-CLOCK_DRIFT가 된다. 이는 모든 키가 최소 이 시간 동안 동시에 설정될 것임을 보장한다.

대부분의 키가 설정되는 동안 다른 클라이언트는 N/2+1 인스턴스에서 SET NX연산을 성공시킬 수 없으므로, 락이 이미 획득되었다면 동시에 다시 획득할 수 없을 것이므로 상호 배제 원칙을 보장한다.

Redlock 활성 인수

모든 키는 설정된 TTL 후에 자동으로 만료되므로, 결국에는 다시 락을 획득할 수 있게 된다. 일반적으로 클라이언트는 락을 성공적으로 획득하지 못하거나, 락을 획득한 후 작업을 마쳤을 때 락을 해제한다. 이는 키가 만료되기를 기다리지 않고도 락을 재획득할 수 있게 해준다. 클라이언트가 락 획득을 시도할 때, split brain condition 확률을 낮추기 위해 다수의 락을 획득하는 데 필요한 시간보다 상대적으로 긴 대기 시간을 가진다.

Redlock 성능 및 지속성

Redis를 락 서버로 사용하는 많은 사용자는 락을 획득하고 해제 시의 지연 시간과 초당 수행 가능한 획득/해제 연산 수 측면에서 높은 성능을 요구한다.

1. 멀티 플렉싱과 비동기 소켓
Redis와의 통신에서 지연 시간을 줄이기 위해 멀티플렉싱이 사용된다. 멀티플렉싱은 소켓을 비동기 모드로 설정하고, 모든 명령을 한 번에 보낸 후 나중에 모든 응답을 읽는 방식이다.

2. 충돌 복구
Redis를 지속성 없이 구성할 경우, 특정 인스턴스가 재시작되면 그 인스턴스에서 락이 사라져 다른 클라이언트가 동일한 리소스에 대해 락을 다시 획득할 수 없게 되어, 락의 배타성이 침해될 수 있다. 이때 AOF 지속성을 활성화하면 상황이 크게 개선된다. Redis는 서버가 꺼져 있을 때도 시간이 흐르는 것처럼 만료를 처리하기 때문이다.

Redlock 알고리즘의 한계

1. Clock Drift로 인한 문제
Redlock 알고리즘은 노드들 간에 동기화된 시계(synchronized clock)는 없지만, 로컬 시간이 거의 동일한 속도로 갱신된다는 가정에 의존한다. 하지만 현실에서는 클럭이 정확한 속도로 동작하지 않는 클럭 드리프트(Clock Drift)현상으로 시스템 내부 시계가 실제 시간과 어긋날 수 있다. 분산 시스템에서 각 노드의 시간 동기화는 매우 중요한데, 노드 간 시간이 일치하지 않으면 락 메커니즘에서 split brain condition을 발생시킬 수 있다. 예를 들어, 노드 간 시간 차이로 인해 한 노드에서는 락이 유효하다고 판단하는 반면, 다른 노드에서는 해당 락이 이미 만료되었다고 판단할 수 있다.

2. 애플리케이션 중단 또는 네트워크 지연으로 인한 문제
예시로, 클라이언트가 공유 저장소(HDFS, S3)에 있는 파일을 업데이트한다고 가정한다. 클라이언트는 아래와 같이 먼저 락을 획득한 후 파일을 읽고, 변경사항을 저장한 다음, 수정된 파일을 다시쓰고 마지막으로 락을 해제한다.

// THIS CODE IS BROKEN
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();
    }
}

하지만 위 코드는 문제가 있다. 클라이언트가 락을 획득한 상태에서 가비지 컬렉터(GC)에 의해 장시간 일시 정지되는 경우가 발생할 수 있다. 일반적으로 GC 시간은 매우 짧지만, stop-the-world GC는 락의 유효시간이 만료될 수 있을 만큼 오래 지속될 수 있다. 만약 GC 일시 정지로 인해 락의 유효시간이 만료되고, 클라이언트가 이를 인지하지 못한 채로 데이터 변경 작업을 계속한다면, 아래 시나리오와 같이 데이터 무결성이 손상될 수 있다.

위 문제를 해결하기 위해 펜싱 토큰(Fencing Token)을 포함시킬 수 있다. 펜싱 토큰은 클라이언트가 락을 획득할 때마다 증가하는 숫자로, 아래 시나리오대로 각각의 쓰기 요청에 포함되어 스토리지 서비스로 전송된다. 이 방식은 스토리지 서버가 토큰은 확인하고, 이전 토큰의 요청은 거부한다.

하지만 Redlock은 펜싱 토큰을 생성하는 기능이 없다. 즉, 알고리즘이 그 외에 완벽하더라도 클라이언트가 일시 중지되거나 해당 패킷이 지연되는 경우 클라이언트 간의 race condition이 발생할 수 있다.

결론

Redlock은 여러 Redis 인스턴스를 사용하여 분산 환경에서 SPOF을 방지하며, 높은 가용성을 제공한다는 장점이 있다. 또한 자바에서는 Redisson 라이브러리로 제공된다. 하지만 clock drift 현상이나 펜싱 토큰 부재 등의 단점을 고려할 때 모든 사용 사례에 적합하지는 않다.

효율성 최적화가 주 목적인 경우, Redis의 단일 노드 락 알고리즘을 사용하는 것을 권장하고, 완전한 정확성이 필요하다면 ZooKeeper와 같은 적절한 합의 시스템을 사용하는 것이 좋은 선택이 될 수 있다.

Ref

https://dev.to/lazypro/explain-redlock-in-depth-31jj

https://mangkyu.tistory.com/311

https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html