분산 시스템 연구자인 Martin Kleppmann이 어제 Redlock(http://redis.io/topics/distlock)에 대한 분석을 공개했습니다. 해당 분석은 여기에서 확인할 수 있습니다: http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

Redlock은 제가 Redis와 함께 사용하도록 설계한 클라이언트 측 분산 락 알고리즘입니다. 하지만 이 알고리즘은 특정 기능을 갖춘 데이터 저장소를 구현한 여러 노드를 클라이언트 측에서 조율하여, 다중 마스터 기반의 장애 내성을 갖추고 가급적 안전한, 자동 해제 기능이 있는 분산 락을 만들도록 합니다. 예를 들어 MySQL을 이용해 Redlock을 구현할 수도 있습니다.

이 알고리즘의 목표는 단일 Redis 인스턴스나 장애 조치(failover) 기능이 있는 마스터-슬레이브 구성으로 분산 락을 구현하던 사람들을, 복잡도는 매우 낮고 성능은 뛰어나면서도 훨씬 더 신뢰할 수 있고 안전한 방식으로 옮겨오도록 하는 것이었습니다.

Redlock을 공개한 이후 많은 사람들이 여러 언어로 이를 구현해 다양한 용도로 사용해 왔습니다.

Martin의 분석은 Redlock이 안전하지 않다는 결론을 내립니다. Martin이 분석을 공개한 것은 매우 반가운 일입니다. 원래 Redlock 명세(http://redis.io/topics/distlock)에서 제가 직접 분석을 요청했기 때문입니다. 그래서 Martin에게 감사드립니다. 다만 저는 그 분석에 동의하지 않습니다. 좋은 점은 분산 시스템이 다른 프로그래밍 분야와 달리 꽤 수학적으로 정확하다는 것입니다. 그렇지 않다면 그렇지 않은 것이고, 그래서 주어진 속성 집합은 알고리즘에 의해 보장되거나, 특정 가정 하에서는 보장되지 않을 수도 있습니다. 이 글에서는 Martin의 분석을 하나하나 살펴보아, 해당 분야의 다른 전문가들이 두 문서(분석과 반박 분석)를 검토하고, 궁극적으로 Redlock을 안전하다고 볼 수 있는지 판단할 수 있도록 하고자 합니다.

Martin이 Redlock이 안전하지 않다고 생각하는 이유

분석에서 제시된 논거는 크게 두 가지입니다:

1. 자동 해제 기능이 있는 분산 락(락을 획득한 뒤 고정된 시간 동안만 상호 배제가 보장되는 락)은 클라이언트가 만료 시간 이후에도 락을 사용해 공유 자원에 접근하면서 상호 배제를 위반하는 문제를 피할 방법이 필요합니다. Martin은 Redlock에는 그런 메커니즘이 없다고 말합니다.
2. Martin은 문제 “1”과 별개로, 알고리즘이 실제 시스템에서는 보장될 수 없는 시스템 모델에 대한 가정을 하기 때문에 본질적으로 안전하지 않다고 말합니다.

두 가지 우려를 명확하게 구분하기 위해 하나씩 차례대로 다루겠습니다. 먼저 첫 번째 “1”부터 시작하겠습니다.

분산 락, 자동 해제 그리고 토큰

자동 해제 메커니즘이 없는 분산 락, 즉 락 소유자가 무기한으로 락을 보유하는 방식은 사실상 쓸모가 없습니다. 락을 쥔 클라이언트가 장애로 종료되고 짧은 시간 안에 전체 상태를 복구하지 못하면, 분산 락이 보호하려던 공유 자원에 영원히 접근할 수 없는 교착 상태가 발생합니다. 이는 대부분의 상황에서 용납할 수 없는 가용성(liveness) 문제를 만들기 때문에, 제대로 된 분산 락은 반드시 스스로 자동 해제될 수 있어야 합니다.

그래서 실제 사용되는 락은 클라이언트에게 최대 생존 시간과 함께 제공됩니다. 만료 시간이 지나면 상호 배제 보장, 즉 락의 *핵심* 속성은 사라집니다. 다른 클라이언트가 이미 락을 획득했을 수도 있습니다. 두 클라이언트가 서로 다른 시점에 락을 획득했는데, 첫 번째 클라이언트가 GC 일시 중지나 다른 스케줄링 문제로 너무 느리게 동작하여 두 번째 클라이언트가 락을 획득한 시점과 동시에 공유 자원 맥락에서 작업을 시도하면 어떻게 될까요?

Martin은 이 문제가 분산 락 서버가 락마다 토큰을 함께 제공하면 피할 수 있다고 말합니다. 그의 예시에서 토큰은 항상 증가하는 것이 보장되는 단순한 숫자일 뿐입니다. Martin이 토큰을 사용하는 논리는, 두 클라이언트가 동시에 락으로 보호되는 자원에 접근할 때 데이터베이스 쓰기 트랜잭션(클라이언트의 작업 결과를 구체화한다고 가정되는)에 토큰을 포함시킬 수 있기 때문입니다. 가장 큰 락 번호를 가진 클라이언트만 데이터베이스에 쓸 수 있게 되는 것입니다.

Martin의 말을 인용하면:

“이 문제에 대한 수정은 사실 꽤 간단합니다. 저장소 서비스에 대한 모든 쓰기 요청에 펜싱 토큰(fencing token)을 포함시켜야 합니다. 이 맥락에서 펜싱 토큰은 단순히 클라이언트가 락을 획득할 때마다 증가하는(예: 락 서비스에 의해 증가되는) 숫자입니다”

… 생략 …

“이는 저장소 서버가 토큰을 검사하고 토큰이 뒤로 간 쓰기를 거부하는 적극적인 역할을 해야 함을 의미합니다”.

저는 이 주장에 여러 가지 문제가 있다고 생각합니다:

1. 대부분의 경우 상호 배제를 보장해야 할 때 분산 락 시스템이 필요한데, 이 속성이 위반되는 순간 이미 실패한 것입니다. 분산 락이 매우 유용한 이유는 공유 자원에 대해 다른 제어 수단이 없을 때 정확히 그 때문입니다. 그런데 Martin의 분석에서는 락의 상호 배제가 위반되었을 때 경합을 피할 다른 방법이 항상 있다고 가정합니다. 강한 보장을 제공하는 락을 굳이 왜 쓰는지 의문이 들게 하는, 매우 이상한 추론 방식이라고 생각합니다. 만약 다른 방식으로 경합을 해결할 수 있다면 말입니다. 그럼에도 아래에서 다른 논점들을 계속 이어가겠습니다. 설령 이러한 매우 인위적인 맥락에서도 Redlock이 잘 동작할 수 있음을 보이기 위해서입니다.
2. 데이터 저장소가 과거의 모든 토큰보다 토큰이 클 때만 항상 쓰기를 허용할 수 있다면, 그 저장소는 선형성을 보장하는(linearizable) 저장소입니다. 선형성을 보장하는 저장소가 있다면, 획득한 Redlock마다 증가하는 ID를 그냥 생성하면 되므로, 이는 매번 새로운 락마다 증가하는 토큰 ID를 제공하는 다른 분산 락 시스템과 Redlock을 동등하게 만들 것입니다. 하지만 다음 항목에서 보듯이 굳이 그럴 필요는 없습니다.
3. 그러나 “2”는 어차피 합리적인 선택이 아닙니다. 대부분의 경우 공유 자원에 대한 작업 결과는 선형성을 보장하는 저장소에 쓰는 것이 아니기 때문입니다. 그렇다면 어떻게 해야 할까요? 각 Redlock은 큰 무작위 토큰과 연결됩니다(충돌을 무시할 수 있는 방식으로 생성되며, Redlock 명세에서는 문자로 “/dev/urandom에서 20바이트”라고 가정합니다). 고유한 토큰으로 무엇을 할 수 있을까요? 예를 들어 Check and Set을 구현할 수 있습니다. 공유 자원 작업을 시작할 때 그 상태를 “”으로 설정한 뒤, 쓰기 시점에 토큰이 그대로 유지될 때만 읽기-수정-쓰기를 수행하는 것입니다.
4. 특정 사용 사례에서는 어쨌든 순서가 있는 토큰이 유용하다고 말할 수도 있습니다. 그런 사용 사례를 떠올리기는 어렵지만, Martin이 언급한 GC 일시 중지로 인해 토큰을 획득한 순서가 클라이언트가 공유 자원에 대해 작업을 시도하는 순서와 반드시 일치하지는 않는다는 점에 유의해야 합니다. 따라서 락의 순서가 공유 자원에 대한 작업 결과와 인과적으로 연결되지 않을 수도 있습니다.
5. 대부분의 경우 락은 트랜잭션 방식이 아닌 형태로 업데이트되는 자원에 접근하기 위해 사용됩니다. 때로는 분산 락을 이용해 물리적인 객체를 움직이기도 합니다. 또는 다른 외부 API와 상호작용하기 위해 사용하기도 합니다. 등등.

다시 한 번 언급하고 싶은 것은, 이 모든 논의에서 이상한 점은 상호 배제가 위반되었을 때 경합 상황에서 문제를 처리할 방법이 항상 있어야 한다고 가정한다는 것입니다. 사실 경합 상황에서 문제를 피할 수 있는 그런 시스템이 있다면 애초에 분산 락 자체가 필요 없을 가능성이 높고, 적어도 강한 보장을 제공하는 락은 필요 없으며, 대부분 동시 접근을 피하기 위한 성능상의 이유로 약한 락만 있으면 될 것입니다.

하지만 위 내용이 매우 유용하다는 Martin의 의견에 동의한다고 하더라도, 요점은 각 락마다 고유 식별자를 동일한 목적에 사용할 수 있으며, 저장소에 강한 보장을 요구하지 않는다는 점에서 훨씬 더 실용적이라는 것입니다.

시스템 모델에 대해 이야기해 봅시다

위의 비판은 기본적으로 매 락마다 단조 증가하는 카운터를 제공하지 않는, 자동 해제 기능이 있는 모든 분산 락에 공통적으로 해당합니다. 하지만 Martin의 또 다른 비판은 Redlock에만 해당합니다. 여기서 Martin은 알고리즘 자체를 분석하여 그것이 결함이 있다고 결론 내립니다.

Redlock은 서로 다른 프로세스가 대략 비슷한 “속도”로 시간을 셀 수 있는 준동기(semi-synchronous) 시스템 모델을 가정합니다. 서로 다른 프로세스들은 절대 시간에 대한 오차 한계를 가질 필요가 전혀 없습니다. 그들이 해야 할 일은 단지, 예를 들어 5초를 최대 10% 오차로 셀 수 있으면 되는 것입니다. 그러면 하나는 실제로 4.5초를 세고, 다른 하나는 5.5초를 세더라도 문제가 없습니다.

Martin은 또한 Redlock이 메시지 최대 지연에 대한 상한을 요구한다고 말하는데, 제가 보기에는 그렇지 않습니다(그의 추론이 왜 문제가 되는지 뒤에서 설명하겠습니다).

그럼 서로 다른 프로세스가 같은 속도로 시간을 셀 수 없다는 문제부터 시작해 보겠습니다.

Martin은 시스템에서 클록이 무작위로 점프할 수 있는 이유로 두 가지 문제를 듭니다:

1. 시스템 관리자가 수동으로 클록을 변경하는 경우.
2. ntpd 데몬이 업데이트를 받아 클록을 크게 변경하는 경우.

위 두 문제는 “1” 그런 짓을 하지 않음으로써(그렇지 않으면 “echo foo > /my/raft/log.bin”으로 Raft 로그를 망가뜨리는 것도 문제가 됩니다), 그리고 “2” 클록을 직접 점프시키지 않고 더 긴 시간에 걸쳐 변화를 분산시키는 ntpd를 사용함으로써 피할 수 있습니다.

하지만 저는 Redis와 Redlock 구현이 운영체제가 제공하는 단조 증가 시간(monotonic time) API로 전환하여 위와 같은 문제를 덜 겪도록 해야 한다는 점에서는 Martin의 말이 맞다고 생각합니다. 이는 과거에도 여러 번 제안된 바 있으며, Redis 내부에 약간의 복잡성을 더하지만 좋은 아이디어입니다. 앞으로 몇 주 안에 구현할 예정입니다. 하지만 단조 증가 시간 API로 전환하는 동안에도, 클록을 변경하는 소프트웨어(타임 서버)나 사람(시스템 관리자) 요소 없이 운영체제에서 동작하는 프로세스는 gettimeofday()만으로도 제한된 오차 내에서 상대 시간을 셀 *수* 있습니다.

과거에는 GPS 장치를 사용하는 등 절대 시간 오차에 상한이 있다고 가정하고 분산 시스템을 구현하려는 시도도 있었습니다. Redlock은 그런 것을 전혀 요구하지 않습니다. 단지 서로 다른 프로세스가 10초를 9.5초나 11.2초(예시에서 최대 ±2초)로 셀 수 있으면 되는 것뿐입니다.

그렇다면 Redlock은 안전한 것일까요, 아닐까요? 그것은 위 가정에 달려 있습니다. 구현 세부 사항(시간을 가지고 장난치는 것을 좋아하는 시스템 관리자와 타임 서버)을 배제하기 위해, 단순화를 위해 단조 증가 시간 API를 사용한다고 가정해 봅시다. 프로세스가 고정된 비율의 최대 오차로 상대 시간을 셀 수 있을까요? 저는 이에 대해 분명히 그렇다고 답할 수 있으며, “프로세스가 로그를 손상 없이 쓸 수 있는가?”라는 질문에 답하는 것보다 훨씬 더 쉽게 그렇다고 답할 수 있다고 생각합니다.

네트워크 지연 등

Martin은 Redlock이 프로세스가 대략 같은 속도로 시간을 셀 수 있다는 사실에만 의존하지 않는다고 말합니다. 그는 이렇게 말합니다:

“하지만 Redlock은 그렇지 않습니다. 그 안전성은 많은 타이밍 가정에 달려 있습니다. 모든 Redis 노드가 키를 만료 전에 대략 정확한 시간 동안 보유하고, 네트워크 지연이 만료 시간에 비해 작으며, 프로세스 일시 중지가 만료 시간보다 훨씬 짧다고 가정합니다.”

그러니 위 주장을 여러 부분으로 나누어 보겠습니다:

1. Redis 노드가 키를 대략 정확한 시간 동안 보유한다.
2. 네트워크 지연이 만료 시간에 비해 작다.
3. 프로세스 일시 중지가 만료 시간보다 훨씬 짧다.

Martin이 “시스템 클록이 점프한다”고 말할 때마다, 우리는 알고리즘에 문제가 되는 방식으로 시스템 시간을 건드리지 않음으로써, 혹은 단순화를 위해 단조 증가 시간 API를 사용함으로써 이를 이미 다루었다고 가정하겠습니다. 그래서:

주장 1에 대해: 이는 문제가 되지 않습니다. 우리는 이미 시간을 대략 같은 속도로 셀 수 있다고 가정했습니다. 이에 대한 실제 반론이 없는 한 말입니다.

주장 2에 대해: 상황은 조금 더 복잡합니다. Martin은 이렇게 말합니다:

“좋습니다, 어쩌면 당신은 클록 점프가 비현실적이라고 생각할 수도 있습니다. NTP를 클록을 천천히(slew) 보정하도록만 올바르게 설정했다는 데 매우 자신이 있기 때문입니다.” (네, 이 부분에서는 저희도 동의합니다 ;-) 그는 말을 이어갑니다…)

“그렇다면 프로세스 일시 중지가 어떻게 알고리즘을 실패하게 만들 수 있는지에 대한 예를 살펴봅시다. 클라이언트 1이 노드 A, B, C, D, E에 락을 요청합니다. 클라이언트 1에 대한 응답이 전송 중인 동안, 클라이언트 1은 stop-the-world GC에 들어갑니다. 모든 Redis 노드에서 락이 만료됩니다. 클라이언트 2가 노드 A, B, C, D, E에서 락을 획득합니다. 클라이언트 1은 GC를 마치고, 락을 성공적으로 획득했다는 Redis 노드들의 응답을 받습니다(그 응답들은 프로세스가 일시 중지된 동안 클라이언트 1의 커널 네트워크 버퍼에 보관되어 있었습니다). 이제 클라이언트 1과 2는 모두 자신이 락을 보유하고 있다고 믿습니다.”

몇 달 동안 손대지 않았던 Redlock 명세를 읽어보면, 락을 획득하는 단계는 다음과 같습니다:

1. 현재 시간을 구한다.
2. … 락을 획득하는 데 필요한 모든 단계 …
3. 다시 현재 시간을 구한다.
4. 이미 시간이 초과되었는지, 혹은 락을 충분히 빠르게 획득했는지 확인한다.
5. 락을 이용해 작업을 수행한다.

단계 1과 3에 주목하십시오. 관련된 네트워크나 프로세스에서 어떤 지연이 발생하더라도, 과반수를 확보한 뒤 다시 시간이 초과되지 않았는지 *확인*합니다. 지연은 단계 3 이후에만 발생할 수 있으며, 그 결과 락이 실제로는 만료되었는데도 유효한 것으로 간주되는 상황이 생깁니다. 즉, 다시 Martin이 지적한 첫 번째 문제, 즉 클라이언트가 락 유효 기간이 끝나기 전에 공유 자원에 대한 작업을 멈추지 못하는 문제로 돌아가게 됩니다. 이 문제가 *모든 분산 락 구현*에 공통으로 존재하는 문제이며, 토큰을 이용한 해결책이 얼마나 비현실적인지, 그리고 Redlock에서도 동일하게 토큰을 사용할 수 있는지는 위에서 이미 설명한 바 있습니다.

1과 3 사이에서 무슨 일이 일어나든, 프로세스 사이에 원하는 만큼 네트워크 지연을 추가해도, 너무 많은 시간이 경과했다면 락은 항상 유효하지 않은 것으로 간주되므로, Redlock은 프로세스 간 메시지의 지연에 상한이 없는 경우에도 완전히 영향을 받지 않는 것처럼 보입니다. 이 목표를 염두에 두고 설계되었으며, 위와 같은 경합 조건이 어떻게 발생할 수 있는지 저는 도저히 알 수 없습니다.

그런데도 Martin의 블로그 글은 여러 분산 시스템 전문가들의 검토를 거쳤기 때문에, 제가 무언가를 놓치고 있는 것인지, 아니면 많은 사람들이 동시에 Redlock의 동작 방식을 간과한 것인지 확신할 수 없습니다. 이에 대해 설명을 들을 수 있다면 기쁘겠습니다.

위 내용은 “프로세스 일시 중지”에 대한 우려 3번도 해소합니다. 락을 획득하는 과정 중의 일시 중지는 알고리즘의 정확성에 영향을 주지 않습니다. 다만 다른 자동 해제 기능이 있는 분산 락과 마찬가지로, 일시 중지는 클라이언트가 지정된 락 생존 시간 내에 작업을 수행하는 능력에는 영향을 줄 수 있으며, 이는 위에서 이미 다룬 내용입니다.

네트워크 지연에 대한 잠깐의 곁다리

간단히 덧붙이자면, 자동 해제 기능이 있는 분산 락의 서버 측 구현에서는 클라이언트가 락 획득을 요청하고 서버가 이를 허용하더라도, 프로세스가 GC 일시 중지에 들어가거나 네트워크가 느려지는 등의 이유로 클라이언트가 “좋습니다, 락은 당신의 것입니다”라는 응답을 너무 늦게, 이미 락이 만료된 뒤에 받을 수도 있습니다. 하지만 프로세스가 오랫동안 잠드는 것을 피하기 위해 할 수 있는 일은 많고, 네트워크 지연을 피하기 위해 할 수 있는 일은 많지 않으므로, 락을 획득한 전후로 시간을 확인하여 남은 시간이 얼마나 되는지 보는 단계는 다른 만료 기능이 있는 락 시스템을 사용할 때도 실제로 일반적인 관행이 되어야 합니다.

Fsync를 할 것인가, 말 것인가?

Martin은 어느 대목에서 Redlock이 노드의 지연된 재시작을 사용한다는 점을 언급합니다. 이는 다시 앞서 다룬 대로, 어느 정도 지정된 시간만큼 대기할 수 있는 능력을 요구합니다. 같은 이야기를 반복할 필요는 없겠습니다.

하지만 여기서 중요한 점은, 이 단계가 선택 사항이라는 것입니다. 각 Redis 노드가 모든 연산마다 fsync를 수행하도록 설정할 수도 있으며, 그러면 클라이언트는 응답을 받았을 때 락이 이미 디스크에 영속화되었다는 것을 알게 됩니다. 이는 강한 보장을 제공하는 대부분의 다른 시스템이 동작하는 방식입니다. Redlock에 대해 매우 흥미로운 점은 디스크 관여 자체를 지연된 재시작을 구현함으로써 완전히 배제할 수 있다는 것입니다. 이는 단 몇 대의 Redis 인스턴스로도 초당 수십만 개의 락을 처리할 수 있게 해 주며, 다른 시스템으로는 불가능한 일입니다.

GPS 장치 대 로컬 컴퓨터 클록

시스템 모델로 돌아가서, Redlock의 시스템 모델을 실용적으로 만드는 한 가지는 프로세스가 시스템 클록과 절대 파티션되지 않는다고 가정할 수 있다는 점입니다. GPS 장치가 사용되는 다른 준동기 모델과 비교하면 분명한 차이가 있는데, 이 경우 발생할 수 있는 두 가지 자명하지 않은 파티션이 있기 때문입니다:

1. GPS가 GPS 네트워크로부터 파티션되어 fix를 획득할 수 없는 경우.
2. 프로세스와 GPS가 메시지를 교환할 수 없거나 교환되는 메시지에 지연이 발생하는 경우.

위 문제들은 시스템이 어떻게 구성되느냐에 따라 가용성 또는 안전성 위반으로 이어질 수 있습니다(안전성 문제는 설계 오류가 있을 때만 발생합니다. 예를 들어 GPS가 시스템 시간을 비동기적으로 업데이트하여, GPS가 동작하지 않을 때 절대 시간 오차가 최대 한계를 초과하는 경우입니다).

Redlock의 시스템 모델은 이러한 복잡성이 없고 추가 하드웨어도 필요하지 않으며, 단지 컴퓨터 클록, 심지어 크리스털 온도와 정밀도에 영향을 미치는 다른 요인들로 인한 명백한 편향을 가진 매우 저렴한 클록만 있으면 됩니다.

결론

저는 단조 증가 시간 API에 대해서는 Martin의 지적이 일리가 있다고 생각합니다. Redis와 Redlock 구현은 시스템 클록 변경으로 인한 문제를 피하기 위해 이를 사용해야 합니다. 하지만 그 외에는 위에서 설명한 바와 같이 Redlock의 안전성에 영향을 미치는 다른 분석 지점을 찾지 못했으며, 상호 배제 보장이 필요할 때 Redlock을 사용해서는 안 된다는 그의 최종 결론이 정당하다고 생각하지 않습니다.

전문가들로부터 더 많은 피드백을 받고, 더 많은 데이터를 쌓기 위해 Jepsen과 같은 도구로 알고리즘을 테스트해 보는 것도 매우 좋을 것 같습니다.

이 글을 검토하는 데 도움을 준 친구들에게 큰 감사를 전합니다.