-----------------
업데이트: 이제 알고리즘은 Redis 문서의 여기 => http://redis.io/topics/distlock에 설명되어 있습니다. 이 글은 예전 버전으로 남겨 두며, 업데이트된 내용은 대신 Redis 문서에 반영할 예정입니다.
-----------------

많은 사람이 분산 락을 구현하는 데 Redis를 사용합니다. 이는 Redis의 훌륭한 사용 사례이며, 그렇지 않으면 해결하기 어려운 문제를 Redis가 아주 잘 해결한다고 생각하는 사람도 많습니다. 반면 Redis의 분산 락은 완전히 문제가 있고, 안전하지 않으며, 잘못된 사용 사례라고 생각하는 사람도 있습니다.

기본적으로 둘 다 맞습니다. 분산 락을 안전하게 만들면서 동시에 높은 가용성을 요구하려면, Redis 노드가 다운되더라도 클라이언트가 락을 획득하고 해제할 수 있어야 하므로 분산 락은 결코 간단하지 않습니다. 동시에 빠른 락 관리자는 실제로 해결하기 어려운 수많은 문제를 해결할 수 있고, 때로는 완벽하지 않은 해결책이라도 매우 느린 해결책보다는 낫습니다.

Redis를 기반으로 빠르면서도 신뢰할 수 있는 시스템을 동시에 만들 수 있을까요? 이 글은 이 영역을 탐구하는 글입니다. 저는 분산되고 신뢰할 수 있는 락을 위해 N개의 Redis 인스턴스를 사용하는 간단한 알고리즘을 제안하려고 합니다. 이 알고리즘이 유효한 후보인지 커뮤니티에서 분석하고 의견을 제시해 주기를 바랍니다.

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

원하는 안전성(safety)과 활성(liveness) 속성을 명시하지 않고 분산 시스템을 이야기하는 것은 대부분 쓸모가 없습니다. 이 두 가지 요구사항을 정의해야만 설계가 올바른지 검증하고, 사람들이 설계를 분석해 버그를 찾을 수 있기 때문입니다. 여기서는 효과적으로 분산 락을 사용하는 데 필요하다고 생각하는 최소한의 보장을 세 가지 속성으로 모델링하겠습니다.

1) 안전성 속성: 상호 배제. 어느 순간이든 락을 보유할 수 있는 클라이언트는 하나뿐입니다.

2) 활성 속성 A: 데드락 없음. 리소스를 잠근 클라이언트가 크래시하거나 네트워크 파티션으로 격리되더라도, 결국에는 항상 락을 획득할 수 있어야 합니다.

3) 활성 속성 B: 장애 허용. Redis 노드의 과반수가 살아 있는 한, 클라이언트는 락을 획득하고 해제할 수 있어야 합니다.

# 분산 락, 순진한 방식

무엇을 개선하려는지 이해하기 위해 현재 상황을 분석해 보겠습니다.

Redis로 리소스를 잠그는 간단한 방법은 한 인스턴스에 키를 생성하는 것입니다. 보통 Redis의 만료 기능을 사용해 제한된 TTL로 키를 생성하므로, 결국 어떤 방식으로든 키가 해제됩니다(목록의 속성 2). 클라이언트가 리소스를 해제해야 할 때는 키를 삭제합니다.

겉보기에는 잘 작동하지만, 이 구조에는 문제가 있습니다. 아키텍처에 단일 장애점이 생긴다는 것입니다. Redis 마스터가 다운되면 어떻게 될까요?
그럼 슬레이브를 추가하고, 마스터를 사용할 수 없을 때 슬레이브를 사용하면 되겠죠! 안타깝게도 이는 실현할 수 없습니다. 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를 초기화하고, 그로부터 의사 난수 스트림을 생성하는 방법은 안전한 선택입니다.
더 간단한 방법은 마이크로초 단위의 Unix 시간과 클라이언트 ID를 결합하는 것입니다. 이 방법은 그만큼 안전하지는 않지만 대부분의 환경에서는 충분할 가능성이 큽니다.

키의 TTL로 사용하는 시간을 “락 유효 시간”이라고 합니다. 이는 자동 해제 시간인 동시에, 다른 클라이언트가 상호 배제 보장을 기술적으로 위반하지 않고 락을 다시 획득할 수 있기 전에 클라이언트가 필요한 작업을 수행해야 하는 시간입니다. 상호 배제는 락을 획득한 순간부터 일정 시간 동안만 보장됩니다.

이제 락을 획득하고 해제하는 좋은 방법이 생겼습니다. 항상 사용 가능한 단일 인스턴스로 구성된 비분산 시스템을 전제로 하면 이 시스템은 안전합니다. 이제 이런 보장이 없는 분산 시스템으로 개념을 확장해 보겠습니다.

# 분산 버전

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

락을 획득하기 위해 클라이언트는 다음 작업을 수행합니다.

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가 인스턴스 2개를 잠그고, 클라이언트 B가 인스턴스 1개만 잠그는 경우). 그런 다음 두 클라이언트가 잠긴 인스턴스의 락을 해제하기 전에 네트워크 파티션으로 격리됩니다. 그러면 자동 해제 시간과 대략 같은 시간 동안 해당 리소스를 잠글 수 없게 됩니다. 키가 만료된 뒤 두 클라이언트 A와 B가 다시 파티션에 합류해 같은 패턴을 반복하면, 이런 상황이 계속됩니다.

위 문제를 다른 관점에서 보면 네트워크 파티션이 발생할 때 “TTL” 시간만큼 가용성 측면의 대가를 치르는 셈입니다. 따라서 파티션이 계속 발생하면 이 대가를 무한히 치를 수 있습니다.

보장된 활성을 제공할 간단한 방법은 찾지 못했습니다(솔직히 말해 아주 열심히 시도하지도 않았습니다). 하지만 최악의 경우가 발생하기는 어려워 보입니다.
기본적으로 이는 이 알고리즘으로는 속성 2를 근사적으로만 제공할 수 있다는 뜻입니다.

# 성능, 크래시 복구, fsync

Redis를 락 서버로 사용하는 많은 사용자는 락을 획득하고 해제하는 지연 시간과 초당 수행할 수 있는 획득 및 해제 작업 수 모두에서 높은 성능을 필요로 합니다. 이 요구사항을 충족하려면 N개의 Redis 서버와 통신할 때 지연 시간을 줄이는 전략은 단연 멀티플렉싱입니다. 또는 간이 멀티플렉싱을 사용할 수도 있습니다. 소켓을 논블로킹 모드로 설정하고 모든 명령을 전송한 다음, 각 인스턴스와 클라이언트 사이의 RTT가 비슷하다고 가정하고 나중에 모든 응답을 읽는 방식입니다.

하지만 크래시 복구 시스템 모델을 목표로 한다면 지속성에 대해서도 고려해야 할 사항이 있습니다.

문제를 이해하기 위해 Redis를 전혀 지속성 없이 구성했다고 가정해 보겠습니다. 클라이언트가 5개 인스턴스 중 3개에서 락을 획득합니다. 클라이언트가 락을 획득한 인스턴스 중 하나가 재시작되면, 이제 같은 리소스에 대해 다시 잠글 수 있는 인스턴스가 3개가 됩니다. 그러면 다른 클라이언트가 해당 리소스를 다시 잠글 수 있어 락의 상호 배제라는 안전성 속성을 위반하게 됩니다.

AOF 지속성을 활성화하면 상황이 상당히 나아집니다. 예를 들어 SHUTDOWN을 전송한 뒤 서버를 재시작해 서버를 업그레이드할 수 있습니다. Redis의 만료는 의미론적으로 구현되어 있어 서버가 꺼져 있는 동안에도 시간이 사실상 계속 흐르므로, 모든 요구사항이 충족됩니다.
하지만 이는 정상적인 종료일 때만 문제가 없습니다. 전원 장애가 발생하면 어떻게 될까요? 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”로 바꿉니다.

매우 유용한 피드백을 주셔서 감사합니다.