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

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

이 알고리즘의 목표는 분산 락을 구현하기 위해 단일 Redis 인스턴스나 페일오버를 갖춘 마스터-슬레이브 구성을 사용하던 사람들을, 훨씬 더 안정적이고 안전하면서도 복잡도는 매우 낮고 성능은 좋은 방식으로 옮겨오게 하는 것이었다.

내가 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)을 포함해야 한다. 이 맥락에서 펜싱 토큰은 클라이언트가 락을 획득할 때마다 증가하는(예: 락 서비스에 의해 증가되는) 단순한 숫자에 불과하다”

… snip …

“이는 스토리지 서버가 토큰을 검사하고 토큰이 거꾸로 돌아간 쓰기를 거부하는 데 적극적인 역할을 해야 함을 의미한다”.

이 주장에는 여러 문제가 있다고 생각한다:

1. 대부분의 경우 상호 배제를 보장해야 하는 분산 락 시스템이 필요할 때, 이 속성이 위반되는 순간 이미 실패한 것이다. 분산 락은 공유 자원에 대해 다른 제어 수단이 없을 때 정확히 매우 유용하다. Martin은 분석에서 상호 배제가 위반되더라도 경합 상태를 피할 다른 방법이 항상 있다고 가정한다. 강한 보장을 가진 락을 굳이 왜 쓰는지 의문이 들게 하는, 분산 락에 대해 생각하는 매우 이상한 방식이라고 생각한다. 그럼에도 아래에서 다른 지점들을 계속 다루겠다. 이는 Redlock이 이 매우 인위적인 맥락에서도 잘 동작할 수 있음을 보이기 위해서다.
2. 데이터 스토어가 토큰이 과거의 모든 토큰보다 클 때만 항상 쓰기를 허용할 수 있다면, 그것은 선형화 가능한(linearizable) 스토어다. 선형화 가능한 스토어가 있다면, 획득한 각 Redlock마다 증가하는 ID를 그냥 생성하면 되므로, 이는 Redlock을 매번 새로운 락마다 증가하는 토큰 ID를 제공하는 다른 분산 락 시스템과 동등하게 만든다. 하지만 다음 지점에서 보겠지만 이는 필요하지 않다.
3. 하지만 어쨌든 “2”는 현명한 선택이 아니다. 대부분의 경우 공유 자원에 대한 작업 결과는 선형화 가능한 스토어에 쓰는 것이 아니니, 그럼 어떻게 해야 하는가? 각 Redlock은 큰 무작위 토큰과 연결된다(충돌을 무시할 수 있는 방식으로 생성되며, Redlock 명세는 문자 그대로 “/dev/urandom에서 20바이트”라고 가정한다). 고유한 토큰으로 무엇을 할 수 있는가? 예를 들어 Check and Set을 구현할 수 있다. 공유 자원 작업을 시작할 때 그 상태를 “`<token>`”으로 설정한 뒤, 쓸 때 토큰이 여전히 동일할 경우에만 read-modify-write를 수행하는 것이다.
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은 안전한가, 아닌가? 이는 위의 내용에 달려 있다. 구현 세부 사항(POKE를 좋아하는 시스템 관리자와 타임 서버)을 배제하기 위해 단순화를 목적으로 단조 증가 시간 API를 사용한다고 가정해 보자. 프로세스가 고정된 최대 오차 비율로 상대 시간을 셀 수 있는가? 나는 이에 대해 분명히 YES라고 답할 수 있으며, “프로세스가 로그를 손상시키지 않고 쓸 수 있는가?”라는 질문에 답하는 것보다 이 질문에 답하는 것이 더 간단하다고 생각한다.

네트워크 지연 등

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에 대해 매우 흥미로운 점은 지연된 재시작을 구현함으로써 디스크 관여를 완전히 선택 해제(opt-out)할 수 있다는 것이다. 이는 몇 개의 Redis 인스턴스로 초당 수십만 개의 락을 처리할 수 있게 하며, 이는 다른 시스템으로는 얻을 수 없는 것이다.

GPS 장치 대 로컬 컴퓨터 클록

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

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

위의 문제들은 시스템이 어떻게 조직되는지에 따라 라이브니스 또는 안전성 위반으로 이어질 수 있다(안전성 문제는 설계 오류가 있을 때만 발생한다. 예를 들어 GPS가 시스템 시간을 비동기적으로 업데이트해서 GPS가 동작하지 않을 때 절대 시간 오차가 최대 한계를 넘어가는 경우).

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

결론

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

전문가들로부터 더 많은 피드백을 받고, 더 많은 데이터를 쌓기 위해 Jepsen이나 유사한 도구로 알고리즘을 테스트해 보면 좋겠다.

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