-----------------
업데이트: 이 알고리즘은 현재 Redis 문서에서 설명하고 있습니다 => http://redis.io/topics/distlock. 이 글은 이전 버전 그대로 두었으며, 향후 업데이트는 Redis 문서에 반영될 예정입니다.
-----------------

많은 사람들이 Redis를 이용해 분산 락을 구현한다. 많은 이들은 이를 훌륭한 활용 사례로 보며, Redis가 원래 해결하기 어려운 문제를 훌륭하게 해결해 준다고 생각한다. 반면 다른 이들은 이것이 완전히 잘못됐고 안전하지 않으며 Redis를 잘못 사용하는 사례라고 본다.

사실 둘 다 일리가 있다. 분산 락은 안전성을 보장하면서 동시에 고가용성까지 요구한다면, 즉 Redis 노드가 다운되더라도 클라이언트가 계속 락을 획득하고 해제할 수 있어야 한다면 결코 간단하지 않다. 동시에 빠른 락 매니저는 실제로 해결하기 어려운 수많은 문제를 해결할 수 있으며, 때로는 완벽과는 거리가 먼 해결책이라도 매우 느린 해결책보다는 낫다.

Redis 기반으로 빠르고 신뢰할 수 있는 시스템을 동시에 가질 수 있을까? 이 블로그 포스트는 그 영역에 대한 탐색이다. N개의 Redis 인스턴스를 이용해 분산되고 신뢰할 수 있는 락을 구현하는 간단한 알고리즘에 대한 제안을 설명해 보려 한다. 커뮤니티가 이 알고리즘을 분석하고 의견을 주어 유효한 후보인지 검증하는 데 도움을 주기를 바란다.

# 우리가 정말 원하는 것은 무엇인가?

분산 시스템을 논하면서 우리가 원하는 안전성(safety)과 활성(liveness) 속성을 명시하지 않는 것은 대부분 무의미하다. 이 두 요구사항이 명확해야 설계가 올바른지 검증할 수 있고, 다른 사람들이 설계를 분석해 버그를 찾을 수 있기 때문이다. 여기서는 설계를 단 세 가지 속성으로 모델링하려 한다. 분산 락을 효과적으로 사용하기 위해 최소한으로 필요하다고 생각하는 보장들이다.

1) 안전성 속성: 상호 배제. 어떤 시점이든 하나의 클라이언트만이 락을 보유할 수 있다.

2) 활성 속성 A: 데드락 없음. 리소스를 락한 클라이언트가 크래시되거나 네트워크 분할이 발생하더라도 결국에는 항상 락을 획득할 수 있어야 한다.

3) 활성 속성 B: 내결함성. Redis 노드의 과반수가 살아 있는 한 클라이언트는 락을 획득하고 해제할 수 있어야 한다.

# 분산 락, 가장 단순한 방법

우리가 무엇을 개선하려는지 이해하기 위해 현재 상황을 먼저 분석해 보자.

Redis로 리소스를 락하는 가장 단순한 방법은 인스턴스에 키를 생성하는 것이다. 보통 Redis의 expire 기능을 이용해 제한된 TTL을 가진 키를 생성하므로, 어떤 식으로든 결국 락이 해제된다(위 목록의 속성 2). 클라이언트가 리소스를 해제해야 할 때는 키를 삭제하면 된다.

표면적으로는 잘 동작하는 것처럼 보이지만 문제가 있다. 이는 아키텍처상 단일 장애 지점이 된다. Redis 마스터가 다운되면 어떻게 될까?
그럼 슬레이브를 추가하자! 마스터를 사용할 수 없을 때 슬레이브를 사용하면 되지 않을까. 안타깝게도 이 방법은 viable하지 않다. Redis 리플리케이션이 비동기 방식이기 때문에 이렇게 하면 상호 배제라는 안전성 속성을 구현할 수 없기 때문이다.

이 모델에서는 명백한 레이스 컨디션이 발생한다:

1) 클라이언트 A가 마스터에서 락을 획득한다.

2) 키에 대한 쓰기가 슬레이브로 전송되기 전에 마스터가 크래시된다.

3) 슬레이브가 마스터로 승격된다.

4) 클라이언트 B가 이미 A가 락을 보유한 동일한 리소스에 대해 락을 획득한다. <- 안전성 위반!

때로는 장애와 같은 특수한 상황에서는 여러 클라이언트가 동시에 락을 보유해도 전혀 문제가 되지 않을 수 있다.
만약 그렇다면 여기서 읽기를 멈추고 리플리케이션 기반 솔루션을 그대로 즐기면 된다. 그렇지 않다면 더 안전한 구현 방법을 위해 계속 읽어보자.

# 먼저, 단일 인스턴스에서 올바르게 구현해 보자

위에서 설명한 단일 인스턴스 구성의 한계를 극복하기 전에, 이 단순한 경우에서 올바르게 구현하는 방법을 먼저 확인해 보자. 가끔 발생하는 레이스 컨디션을 허용할 수 있는 애플리케이션에서는 이 자체로도 충분히 쓸 만한 해결책이며, 단일 인스턴스에서의 락이 여기에서 설명할 분산 알고리즘의 기반이 되기 때문이다.

락을 획득하는 올바른 방법은 다음과 같다:

SET resource_name my_random_value NX PX 30000

이 명령은 키가 아직 존재하지 않을 때만(NX 옵션) 30000밀리초의 만료 시간(PX 옵션)을 걸어 키를 설정한다.
키는 “my_random_value”라는 값으로 설정된다. 이 값은 모든 클라이언트와 모든 락 요청에 걸쳐 고유해야 한다.

기본적으로 이 랜덤 값은 락을 안전하게 해제하기 위해 사용된다. Redis에게 “키가 존재하고, 키에 저장된 값이 내가 기대한 값과 정확히 일치할 때만 키를 삭제하라”고 지시하는 스크립트를 통해서다. 이는 다음 Lua 스크립트로 구현한다:

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

이는 다른 클라이언트가 생성한 락을 삭제하는 것을 방지하기 위해 중요하다. 예를 들어 클라이언트가 락을 획득한 뒤, 락 유효 시간(키가 만료되는 시간)보다 오래 어떤 연산에 블로킹되고, 나중에 이미 다른 클라이언트가 획득한 락을 삭제해 버릴 수 있다.
그냥 DEL을 사용하는 것은 안전하지 않다. 다른 클라이언트의 락을 삭제할 수 있기 때문이다. 위 스크립트를 사용하면 모든 락이 랜덤 문자열로 “서명”되므로, 락을 해제하려는 클라이언트가 설정한 락이 그대로 유지되고 있을 때만 락이 삭제된다.

이 랜덤 문자열은 무엇이어야 할까? 나는 /dev/urandom에서 가져온 20바이트를 가정하지만, 여러분의 작업에 충분히 고유성을 보장할 수 있는 더 저렴한 방법을 찾을 수도 있다.
예를 들어 안전한 방법 중 하나는 /dev/urandom으로 RC4를 시드한 뒤 의사 난수 스트림을 생성하는 것이다.
더 단순한 방법은 마이크로초 단위 해상도의 유닉스 타임과 클라이언트 ID를 조합하는 것이다. 가장 안전한 방법은 아니지만 대부분의 환경에서는 충분히 역할을 할 것이다.

키의 TTL로 사용하는 시간을 “락 유효 시간”이라고 부른다. 이는 자동 해제 시간이면서, 동시에 클라이언트가 필요한 연산을 수행해야 하는 시간이기도 하다. 이 시간이 지나면 다른 클라이언트가 락을 다시 획득할 수 있으며, 이는 상호 배제 보장이 락을 획득한 시점부터 주어진 시간 창 내에서만 제한적으로 유지된다는 점에서 기술적으로 위반이 아니다.

이제 락을 획득하고 해제하는 좋은 방법을 갖게 되었다. 단일 인스턴스로 구성되고 항상 가용한 비분산 시스템을 전제로 한다면 이 시스템은 안전하다. 이제 이러한 보장이 없는 분산 시스템으로 개념을 확장해 보자.

# 분산 버전

알고리즘의 분산 버전에서는 N개의 Redis 마스터가 있다고 가정한다. 이 노드들은 완전히 독립적이므로 리플리케이션이나 다른 암묵적인 조정 시스템을 사용하지 않는다. 단일 인스턴스에서 락을 안전하게 획득하고 해제하는 방법은 이미 설명했다. 알고리즘에서는 이 방법을 이용해 단일 인스턴스에서 락을 획득하고 해제한다고 전제한다. 예제에서는 N=5로 설정하는데, 이는 합리적인 값이다. 따라서 서로 독립적으로 장애가 발생하도록 서로 다른 컴퓨터나 가상 머신에서 5개의 Redis 마스터를 실행해야 한다.

락을 획득하기 위해 클라이언트는 다음 과정을 수행한다:

1단계) 현재 시각을 밀리초 단위로 가져온다.

2단계) 동일한 키 이름과 랜덤 값을 사용해 N개의 인스턴스 모두에 순차적으로 락 획득을 시도한다.

2단계에서 각 인스턴스에 락을 설정할 때, 클라이언트는 전체 락 자동 해제 시간에 비해 작은 타임아웃을 사용한다.
예를 들어 자동 해제 시간이 10초라면, 타임아웃은 대략 5~50밀리초 범위가 될 수 있다.
이는 다운된 Redis 노드와 통신을 시도하느라 클라이언트가 오랫동안 블로킹되는 것을 방지하기 위함이다. 인스턴스를 사용할 수 없으면 가능한 한 빨리 다음 인스턴스와 통신을 시도해야 한다.

3단계) 클라이언트는 현재 시각에서 1단계에서 얻은 타임스탬프를 빼서 락을 획득하는 데 걸린 경과 시간을 계산한다.
과반수 인스턴스(최소 3개)에서 락을 획득했고, 락을 획득하는 데 걸린 총 경과 시간이 락 유효 시간보다 짧은 경우에만 락을 획득한 것으로 간주한다.

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

5단계) 어떤 이유로든 락 획득에 실패했다면(N/2+1개 인스턴스를 락하지 못했거나 유효 시간이 음수인 경우), 클라이언트는 모든 인스턴스의 락 해제를 시도한다(락하지 못했다고 생각한 인스턴스까지 포함해서).

# 동기적인가, 아닌가?

기본적으로 이 알고리즘은 부분적으로 동기적이다. 프로세스 간에 동기화된 클록은 없지만, 각 프로세스의 로컬 시간이 거의 동일한 속도로 흐르며, 그 오차는 락의 자동 해제 시간에 비해 작다는 가정에 의존한다. 이 가정은 현실 세계의 컴퓨터와 매우 유사하다. 모든 컴퓨터는 로컬 클록을 가지고 있으며, 서로 다른 컴퓨터 간의 클록 드리프트가 작다는 점을 보통 신뢰할 수 있다.

또한 상호 배제 규칙을 좀 더 정교하게 다듬어야 한다. 락을 보유한 클라이언트가 락 유효 시간(3단계에서 얻은 값)에서 약간의 시간(프로세스 간 클록 드리프트를 보정하기 위한 불과 몇 밀리초)을 뺀 시간 안에 작업을 완료하는 경우에만 보장이 유지된다.

# 재시도

클라이언트가 락을 획득하지 못했을 때는, 동일한 리소스에 대해 동시에 락을 획득하려는 여러 클라이언트 간의 동기화를 깨기 위해 랜덤한 지연 시간 후에 재시도해야 한다(그렇지 않으면 아무도 승리하지 못하는 스플릿 브레인 상태가 발생할 수 있다). 또한 클라이언트가 과반수의 Redis 인스턴스에서 더 빨리 락을 획득하려 할수록 스플릿 브레인 상태가 발생할 수 있는 윈도우가 줄어들고(재시도 필요성도 줄어든다), 따라서 이상적으로는 클라이언트는 멀티플렉싱을 이용해 N개의 인스턴스에 SET 명령을 동시에 전송해야 한다.

과반수의 락을 획득하지 못한 클라이언트가 (부분적으로) 획득한 락을 가능한 한 빨리 해제하는 것이 얼마나 중요한지 강조할 필요가 있다. 그래야 키 만료를 기다리지 않고도 락을 다시 획득할 수 있기 때문이다(다만 네트워크 분할이 발생해 클라이언트가 더 이상 Redis 인스턴스와 통신할 수 없게 되면, 가용성에 대한 페널티를 치르고 만료를 기다려야 한다).

# 락 해제

락 해제는 단순하다. 클라이언트가 특정 인스턴스를 성공적으로 락했다고 생각하는지 여부와 관계없이 모든 인스턴스에서 락을 해제하면 된다.

# 안전성 논증

이 시스템은 안전한가? 다양한 시나리오에서 어떤 일이 일어나는지 이해해 보자.

먼저 클라이언트가 과반수 인스턴스에서 락을 획득할 수 있다고 가정해 보자. 모든 인스턴스는 동일한 TTL을 가진 키를 포함하게 된다. 하지만 키가 설정된 시점이 서로 다르므로 만료 시점도 달라진다. 그러나 첫 번째 키가 최악의 경우 T1 시점에(첫 번째 서버에 접속하기 전에 샘플링한 시각) 설정되었고 마지막 키가 최악의 경우 T2 시점에(마지막 서버로부터 응답을 받은 시각) 설정되었다면, 해당 집합에서 가장 먼저 만료되는 키는 최소 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 동안은 존재한다고 확신할 수 있다. 나머지 키들은 더 늦게 만료되므로, 최소한 이 시간 동안은 키들이 동시에 설정되어 있다고 확신할 수 있다.

과반수의 키가 설정되어 있는 동안에는 다른 클라이언트가 락을 획득할 수 없다. N/2+1개의 키가 이미 존재하는 상태에서 N/2+1개의 SET NX 연산이 성공할 수 없기 때문이다. 따라서 락이 획득되었다면, 동시에(상호 배제 속성을 위반하면서) 다시 획득하는 것은 불가능하다.

하지만 동시에 락을 획득하려는 여러 클라이언트가 동시에 성공할 수 없다는 점도 보장해야 한다.

클라이언트가 락의 최대 유효 시간(기본적으로 SET에 사용하는 TTL)과 가깝거나 그보다 긴 시간을 사용해 과반수 인스턴스를 락했다면, 해당 락을 무효로 간주하고 인스턴스들의 락을 해제할 것이다. 따라서 우리는 클라이언트가 유효 시간보다 짧은 시간 안에 과반수 인스턴스를 락한 경우만 고려하면 된다. 이 경우 위에서 이미 설명한 논증에 따라 MIN_VALIDITY 동안에는 어떤 클라이언트도 락을 재획득할 수 없어야 한다. 따라서 여러 클라이언트가 동시에 N/2+1개 인스턴스를 락할 수 있는 경우(여기서 “시간”은 2단계 종료 시점을 의미)는 과반수를 락하는 데 걸린 시간이 TTL보다 커서 락이 무효가 되는 경우뿐이다.

안전성에 대한 형식적인 증명을 제공하거나 버그를 찾아낼 수 있는가? 그런 도움을 주신다면 매우 감사하겠다.

# 활성 논증

시스템의 활성은 세 가지 주요 특징에 기반한다:

1) 락의 자동 해제(키가 만료되므로): 결국 키는 다시 락을 걸 수 있는 상태가 된다.

2) 클라이언트들이 보통 협조적으로 동작한다는 점: 락을 획득하지 못했을 때나 락을 획득한 뒤 작업을 마쳤을 때 락을 제거하므로, 키 만료를 기다리지 않고도 락을 재획득할 가능성이 높다.

3) 클라이언트가 락을 재시도해야 할 때, 과반수 락을 획득하는 데 필요한 시간보다 상당히 긴 시간을 기다린다는 점: 이를 통해 리소스 경합 시 스플릿 브레인 상태가 발생할 확률을 낮춘다.

하지만 적어도 하나의 시나리오는 매우 특수한 네트워크 분할/재결합 패턴이 무한히 반복될 경우 시스템 가용성을 침해할 수 있다.
예를 들어 N=5인 경우, 두 클라이언트 A와 B가 동시에 같은 리소스를 락하려고 시도할 때, 아무도 과반수 락을 획득하지 못하지만 A와 B의 락을 합치면 과반수 노드를 락한 셈이 될 수 있다(예: 클라이언트 A가 2개 인스턴스를, 클라이언트 B가 1개 인스턴스를 락한 경우).
그러고 나서 클라이언트들이 락한 인스턴스를 해제하기도 전에 네트워크 분할로 격리된다. 이 경우 리소스는 자동 해제 시간과 거의 같은 시간 동안 락할 수 없는 상태로 남는다. 키가 만료되면 두 클라이언트 A와 B는 다시 분할에 합류해 같은 패턴을 반복하고, 이 과정이 무한히 이어질 수 있다.

위 문제를 다른 관점에서 보면, 네트워크 분할이 발생하면 “TTL” 시간만큼의 가용성 페널티를 치르게 되며, 분할이 계속되면 이 페널티를 무한히 치를 수 있다는 것이다.

보장된 활성을 확보할 수 있는 간단한 방법을 찾지 못했다(사실 열심히 시도해 보지도 않았다). 하지만 최악의 경우는 발생시키기 어려워 보인다.
기본적으로 이 알고리즘으로는 속성 2에 대한 근사치만을 제공할 수 있다는 의미다.

# 성능, 장애 복구와 fsync

Redis를 락 서버로 사용하는 많은 사용자는 락 획득 및 해제 지연 시간과 초당 수행 가능한 획득/해제 연산 수 측면에서 높은 성능을 필요로 한다. 이 요구사항을 충족하기 위해 N개의 Redis 서버와 통신할 때 지연 시간을 줄이는 전략은 확실히 멀티플렉싱이다(또는 가난한 사람 버전의 멀티플렉싱, 즉 소켓을 논블로킹 모드로 두고 모든 명령을 전송한 뒤 나중에 한꺼번에 응답을 읽는 방식으로, 클라이언트와 각 인스턴스 간의 RTT가 비슷하다고 가정한다).

하지만 크래시 복구 시스템 모델을 목표로 한다면 퍼시스턴스에 대해 추가로 고려해야 할 사항이 있다.

기본적으로 여기서의 문제를 보자면, Redis를 퍼시스턴스 없이 설정했다고 가정해 보자. 클라이언트가 5개 중 3개 인스턴스에서 락을 획득한다. 락을 획득한 인스턴스 중 하나가 재시작되면, 이때 동일한 리소스에 대해 다시 락을 걸 수 있는 인스턴스가 3개가 되고, 다른 클라이언트가 다시 락을 걸어 락의 배타성이라는 안전성 속성을 위반할 수 있다.

AOF 퍼시스턴스를 활성화하면 상황이 꽤 개선된다. 예를 들어 SHUTDOWN을 전송하고 재시작하는 방식으로 서버를 업그레이드할 수 있다. Redis의 expire는 서버가 꺼져 있는 동안에도 가상으로 시간이 계속 흐르는 것처럼 의미적으로 구현되어 있으므로, 우리의 모든 요구사항이 충족된다.
하지만 이는 정상적인 종료인 경우에만 해당한다. 정전 같은 경우는 어떨까? Redis가 기본값처럼 매초 디스크에 fsync하도록 설정되어 있다면, 재시작 후 키가 사라져 있을 수 있다. 요컨대, 어떤 종류의 인스턴스 재시작 상황에서도 락의 안전성을 보장하려면 퍼시스턴스 설정에서 fsync=always를 활성화해야 한다. 이는 결국 전통적으로 분산 락을 안전하게 구현하는 데 사용되는 CP 시스템과 동일한 수준으로 성능을 완전히 망가뜨린다.

좋은 소식은 우리 알고리즘에서는 과반수 서버에 도달했다고 해서 락 획득을 바로 멈추지 않기 때문에, 실제로 안전성 위반이 발생할 확률은 작다는 것이다. 대부분의 경우 락은 5개 서버 모두에서 유지되므로, 하나가 키 없이 재시작되더라도 실제로 안전성 위반이 발생할 가능성은 현실적으로 매우 낮기 때문이다(불가능한 것은 아니지만). 요컨대 이는 사용자가 선택할 문제이며 큰 트레이드오프다. 레이스 컨디션 발생 확률이 매우 작기 때문에, 크래시 복구 이벤트 이후 극히 낮은 확률로 여러 클라이언트가 동시에 락을 획득하는 것을 허용할 수 있다면, 매 연산마다 fsync를 하는 것은 피할 수 있고, 또 피해야 한다.

# 레퍼런스 구현

redis-rb를 기반으로 한 간단한 레퍼런스 구현을 Ruby로 작성했다: http://github.com/antirez/redlock-rb

# 도움을 주실 분을 찾습니다

분산 시스템에 관심이 있다면 의견이나 분석을 들려주시면 큰 도움이 될 것이다.
또한 다른 언어로 된 레퍼런스 구현도 환영한다.

미리 감사드립니다!

수정: 이 블로그 포스트 댓글과 Hacker News를 통해 받은 피드백 중 본문에 반영할 만한 내용이 있어 추가한다.

1) 아래 댓글에서 Steven Benjamin이 지적했듯이, 인스턴스를 재시작한 뒤 그 인스턴스를 이용해 획득한 모든 락이 만료될 때까지 충분한 시간 동안 해당 인스턴스를 쿼리 불가능한 상태로 유지할 수 있다면 fsync가 필요하지 않다. 사실 퍼시스턴스 자체가 전혀 필요하지 않으므로, 순수 인메모리 설정만으로도 안전성 보장을 제공할 수 있다.

예시: 앞서 5개 중 3개 서버에서 락을 획득하고, 락을 획득한 서버 중 하나가 비어 있는 상태로 재시작되는 레이스 컨디션 예시를 설명했다. 이때 다른 클라이언트가 이 서버와 이전 클라이언트가 락하지 않은 나머지 두 서버를 락함으로써 동일한 락을 획득할 수 있다. 하지만 재시작된 서버가 그 서버로 획득했던 모든 락이 만료될 때까지 충분한 시간 동안 쿼리에 응답하지 않는다면, 이러한 레이스가 더 이상 발생할 수 없음을 보장할 수 있다.

2) Hacker News 사용자 eurleif는 클라이언트가 연산 완료에 너무 오래 걸리고 있음을 인지했을 때 락을 재획득하는 전략이 가능하다는 점을 지적했다. 이는 키에 저장된 값이 기대한 값과 일치할 경우 만료를 연장하는 스크립트를 전송해 기존 락을 연장함으로써 할 수 있다. 새로운 파티션이 없고, 키가 만료되기 전에 충분히 미리 락 연장을 시도한다면 락이 연장된다는 것이 보장된다.

3) Hacker News 사용자 mjb는 서로 다른 클록이 로컬 시간을 증가시키는 속도의 차이를 설명하는 데 “skew”라는 용어가 올바르지 않으며, 실제로 말하고자 하는 것은 “drift”라는 점을 지적했다. 올바른 용어를 사용하기 위해 “skew”를 “drift”로 교체한다.

매우 유용한 피드백에 감사드린다.