Redis가 제안한 분산락(feat.Redlock)

서론

자바에서 레디스를 통해 분산락을 구현해야 하는 상황이 생겼습니다. 자바에서는 Redisson이라는 라이브러리가 대표적으로 사용되는데, 이 라이브러리가 어떤 방법을 통해 분산락을 구현하는지 궁금해졌습니다. 이에 따라, 레디스 공식 문서를 참조하여 구현 방법을 분석해보았습니다.

분산락을 위한 최소 조건

레디스는 락의 안전 및 생존 보장을 위해 최소 3가지 조건이 보장되어야 한다고 합니다. 세 가지 조건이란 상호 배제, 생명 주기 A, 생명 주기 B입니다.

1. 상호배제: 락은 한 명의 사용자만 점유해야 한다.
2. 생명 주기 A: 락은 반드시 release가 되어야 한다.
3. 생명 주기 B: 다수의 레디스 노드가 동작 중이면, 락을 획득하고 해제할 수 있어야 한다.

단일인스턴스에서 LOCK 획득 과정

사용자는 락을 획득하기 위해서 아래의 명령어를 레디스 서버에게 보내게 됩니다. 이 명령어는 리소스에 락이 없을 경우에만 락을 걸고(NX옵션), TTL(Time To Live)을 설정하여 일정 시간이 지나면 자동으로 해제되도록 합니다. 이를 통해서 상호배제 조건과 생명주기 B조건을 만족시킬 수 있습니다.

SET resource_key my_random_value NX PX 30000

//resource_key: 락을 걸고자 하는 리소스의 키입니다.
//my_random_value: 락의 소유자를 식별하기 위해 사용되는 고유한 값입니다.
//NX: 키가 존재하지 않을 때만 설정합니다. 즉, 리소스에 락이 이미 걸려있다면 아무 동작도 하지 않습니다.
//PX 30000: 락의 TTL을 밀리초 단위로 설정합니다. 이 경우 30000 밀리초(30초)입니다. 이 시간이 지나면 락이 자동으로 해제됩니다.

 

그 후 리소스에 LOCK을 해제하기 위해 아래의 명령어가 작동하게 됩니다. 여기선 저장되어 있는 KEY와 사용자가 전달한 KEY가 일치할 때 락을 해제할 수 있습니다. 이는 무분별한 사용자가 LOCK을 해제하는 것을 방지하기 위함입니다.

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

 

 

단일 인스턴스의 동작이 중요한 이유는 분산 알고리즘이 단일 인스턴스의 동작 방법을 기초로 동작하기 때문입니다.

 

단일 인스턴의 문제점

레디스를 단일 인스턴스로 둔다면 SPOF(Single Point Of Failure)지점이 생겨나게 됩니다. 이를 해결하기 위해서 사용자는 master와 slave를 생성하여 failover정책을 실행할 수 있습니다.

 

하지만 master와 slave사이에는 동기화 과정이 필요함으로 레디스의 최소한의 락 보장조건을 만족할 수 있을지는 조금 더 생각해봐야 하는 문제입니다.

 

아래와 같은 상황이 있다고 가정했을 때 Client1이 획득한 락이 slave에 동기화 되면서 master가 다운되도 최소한의 조건은 모두 만족될 것입니다.

 

하지만 아래의 그림과 같이 Master가 동기화 전에 죽어버린다면 상호배제 조건을 지키지 못하게 됩니다. 아래의 그림과 같이 Client 1은 Master에서 Lock을 획득했지만, 해당 내용이 동기화되지 않고, master가 죽어벼렸고, Slave 중 하나가 Master로 승격됩니다.

그 후 Client2가 같은 자원에 Lock을 요청하게 되면 상호배제 조건이 성립하지 않게 됨으로써 시스템에는 결함이 발생하게 됩니다.

RedLock 알고리즘

레디스는 이러한 문제를 해결하기 위해 Redlock 알고리즘을 이용할 것을 제안합니다. 앞서 단일 인스턴스에서 어떻게 하면 세 가지 조건들이 지켜지면서 Lock 획득 및 소멸이 가능한지 알아봤습니다. 이 알고리즘은 5개의 노드들이 독립적인 구조임을 가정함으로 단일 인스턴스에서 락을 획득하는 방법을 사용해도 무방할 것입니다.

 

이 과정에서는 제안된 환경은 N개의 Master 노드가 있고, Slave가 없는 독립적인 구조라고 가정합니다.

Lock 획득 조건

1. Lock의 유효시간은?

우리는 앞서 생명주기 A를 보장하기 위해서 Lock에 유효시간(A)이 있다는 것을 확인했습니다. 따라서 사용자는 Lock요청을 보내기 전에 현재 시간(B)와 Redis에서 응답을 받은 시간(C)를 저장하고,  A - B - C를 빼줌으로써 실제 유효시간을 계산해줍니다. 만약 이 유효시간이 음수라면 Redis는 요청을 보낸 인스턴스로 부터 Lock을 획득하지 못한 것으로 간주합니다.

왜 유효 시간을 계산할 때 초기 유효 시간에서 소요된 시간을 빼는가?

 

분산 환경에서 여러 Redis 인스턴스에 잠금을 설정하려면 시간이 걸립니다. 예를 들어, 5개의 인스턴스에서 잠금을 설정하는 데 각각 10ms가 걸린다면, 총 50ms가 소요됩니다. 이 경우 실제로 클라이언트가 작업을 수행할 수 있는 시간은 30초(초기 유효 시간)에서 50ms(잠금을 설정하는 데 소요된 시간)를 뺀 시간입니다.

 

이렇게 하는 이유는 클라이언트가 잠금을 설정하는 데 걸린 시간을 고려하여 실제 작업을 수행할 수 있는 시간을 정확히 파악하기 위함입니다. 만약 이 시간을 고려하지 않으면 클라이언트는 잠금이 예상보다 빨리 해제될 수 있으며, 이로 인해 작업 도중에 다른 클라이언트가 자원을 잠글 수 있는 상황이 발생할 수 있습니다.

 

따라서 초기 유효 시간에서 잠금을 설정하는 데 소요된 시간을 뺀 유효 시간을 사용하여 클라이언트가 안전하게 작업을 수행할 수 있는 시간을 정확하게 계산하는 것입니다.

2. 과반수로부터 응답이 왔는가?

그림과 같이 노드들에게 Lock 획득 요청을 보냈을 때 과반수 이상의 노드들에게서 Lock을 획득했다면 해당 자원에 Lock을 성공한 것입니다.

이 알고리즘에는 문제점이 없을까?

분할 브레인 문제

클라이언트1과 클라이언트2가 동시에 락을 요청하게 되면, 두 클라이언트 모두 락을 얻지 못하고 계속 대기 상태에 있을 수 있습니다. 이를 위해서 다음과 같은 대비책이 있습니다.

1. 랜덤 지연(Random Delay): 클라이언트가 락을 요청할 때 일정한 지연을 두고 재시도하게 합니다. 이 지연 시간은 랜덤하게 설정되어 충돌 가능성을 줄입니다.
2. 락 해제 후 재시도: 락 획득에 실패한 경우, 최대한 빨리 락을 해제하고 다시 요청합니다. 이렇게 하면 다른 클라이언트에게 락을 획득할 기회를 제공하게 되어 시스템의 교착 상태를 방지할 수 있습니다.
3. 홀수 노드 사용: 홀수 개의 노드가 있을 때는 네트워크가 두 부분으로 나뉘더라도 항상 한 쪽이 더 많은 노드를 가지게 되어 합의를 도출하기 쉬워집니다.

시분할 드레프트

시분할 드리프트는 분산 시스템 내에서 각 노드의 시계가 서로 다른 속도로 이동하면서 발생하는 시간 차이를 말합니다. 우리는 앞서 봤듯이 유효 시간이 각 인스턴스 기반으로 세팅되게 됩니다. 이렇게 되면 만료된 시점이 서로 다르게 해석됨으로 상호 배제 속성을 위반할 수 있게 됩니다.

 

이 시분할 문제가 발생하게 되면 만료된 시점이 서로 다르게 해석됨으로 상호 배제 속성을 위반할 수 있게 되고, 두 개 이상의 클라이언트가 동일한 리소스에 접근하는 상황을 초래할 수있습니다.

 

 

 

해결 방법:

펜싱 토큰 알고리즘

펜싱 토큰은 분산 시스템에서 일관성을 유지하기 위해 사용하는 방법입니다. 클라이언트가 잠금을 획득할 때마다 증가하는 고유한 번호입니다. 이를 통해 잠금의 유효성을 확인하고, 잠금이 만료된 후에도 지속적으로 데이터를 수정하려는 시도를 방지할 수 있습니다.

펜싱 토큰 알고리즘

1. 펜싱 토큰 할당: 클라이언트가 잠금을 요청할 때마다 잠금 서비스는 클라이언트에게 고유한 펜싱 토큰을 할당합니다. 이 토큰은 단조 증가하는 숫자로 관리됩니다.
2. 펜싱 토큰 검증: 클라이언트는 리소스에 접근할 때마다 이 펜싱 토큰을 함께 제출합니다. 스토리지 서비스는 클라이언트가 제출한 토큰이 현재 유효한 토큰보다 높은지 확인합니다.
3. 토큰 유효성 검증 실패: 만약 클라이언트의 토큰이 유효하지 않다면, 스토리지 서비스는 접근을 거부합니다.

 

 

 

 

[참고자료]

https://redis.io/docs/latest/develop/use/patterns/distributed-locks/