The binary search of distributed programming

2016-02-14

분산 프로그래밍의 이진 탐색

원문은 Salvatore Sanfilippo님이 2016-02-14에 게재했습니다. 이 블로그 구독하기

어젯밤 Martin Kleppmann이 쓴 Redlock 분석 글(http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html)을 다시 읽고 있었다. 어느 대목에서 Martin은 Redis로 단조 증가하는 ID를 생성할 좋은 방법이 있는지 궁금해한다.

겉보기에는 단순해 보이는 이 문제는 얼핏 보이는 것보다 더 복잡할 수 있다. 모든 상황에서 항상 보장되어야 하는 안전성 속성을 충족해야 하기 때문이다. 생성된 ID는 언제나 과거에 생성된 모든 ID보다 커야 하며, 동일한 ID가 여러 번 생성되어서는 안 된다. 이는 네트워크 파티션이나 다른 장애 상황에서도 반드시 유지되어야 한다. 도달할 수 있는 노드가 과반수 미만이면 시스템은 단순히 가용 불가 상태가 될 수는 있지만, 절대 잘못된 답을 내놓아서는 안 된다(참고: 뒤에서 보겠지만 이 알고리즘은 요청 부하가 높을 때 발생하는 또 다른 라이브니스 문제가 있다).

그래서 분산 시스템 알고리즘을 좀 더 가지고 놀아보고 그 과정에서 조금 더 배워볼 겸, 해결책을 찾아보기로 했다. 사실 이 문제를 해결할 수 있는 알고리즘을 하나 알고 있었다. 효율적이지 않아 초당 수많은 ID를 생성하기에는 적합하지 않은 알고리즘이다. Raft나 Paxos 같은 많은 복잡한 분산 알고리즘들이 자신들이 제공해야 하는 전체 속성을 구축하기 위한 기반으로서 단조 증가 ID를 얻기 위한 단계로 이를 사용한다. 이 알고리즘은 이해하고 구현하기가 극도로 쉽고, 왜 동작하는지 직관적으로 이해할 수 있다는 점에서 매력적이다. 말하자면, 분산 알고리즘의 이진 탐색 같은 것이다. 충분히 쉬우면서도 분산 프로그래밍에 입문하는 사람들이 아하! 하는 순간을 경험하게 할 만큼 영리한 무언가다.

다만 클라이언트 측에서 구현할 수 있도록 알고리즘을 수정해야 했다. 부디 여전히 올바르기를 바란다(피드백 환영한다). 이 알고리즘을 Redlock을 개선하는 데 사용할 생각은 없지만(이전 블로그 포스트 참조), 이런 종류의 문제를 풀어보려는 시도는 좋은 연습이 될 뿐 아니라, 실제 시스템에서 가지고 놀 만한 간단한 문제를 찾는 분산 시스템 입문자들에게 흥미로운 읽을거리가 될 수 있다고 생각한다.

어떻게 동작하는가?

이 알고리즘의 요구사항은 다음 두 가지다:

set_if_less_than() 연산을 지원하는 데이터 스토어.
클라이언트에 응답하기 전에 쓰기 시 데이터를 디스크에 fsync()할 수 있는 데이터 스토어.

위 조건에는 거의 모든 *SQL 서버, Redis 및 여러 다른 스토어가 포함된다.

N개의 노드 집합이 있다고 하자. 알고리즘 설명을 단순화하기 위해 N = 5라고 가정하자. “current”라는 키를 값 0으로 설정하여 시스템을 초기화한다. Redis로 표현하면 다음과 같이 한다:

SET current 0

5개 인스턴스 모두에서 수행한다. 이는 초기화 과정의 일부이며 새로운 “클러스터”가 초기화될 때만 수행되어야 한다. 이 단계는 생략할 수도 있지만 설명을 더 단순하게 만든다.

새로운 ID를 생성하기 위해 다음과 같이 한다:

과반수 인스턴스(N=5인 경우 3개 이상)로부터 “current” 값을 가져온다.
3개 인스턴스에 도달하지 못했다면 1단계로 돌아간다.
우리가 얻은 값들 중 최댓값을 구해 1을 더한다. 이를 $NEXTID라 하자.

도달할 수 있는 모든 노드에 다음 쓰기 연산을 전송한다.

IF current < $NEXTID THEN
    SET current $NEXTID
    return $NEXTID
ELSE
    return NULL
END

3개 이상의 인스턴스가 $NEXTID로 응답하면 알고리즘이 성공한 것이며, 새로운 단조 증가 ID를 성공적으로 생성한 것이다.
그렇지 않고 과반수에 도달하지 못했다면 1단계로 돌아간다.

4단계에서 전송하는 내용은 간단한 Redis Lua 스크립트로 쉽게 변환할 수 있다:

local val = tonumber(redis.call('get',KEYS[1]))
local nextid = tonumber(ARGV[1])

if val < nextid then
    redis.call('set',KEYS[1],nextid)
    return nextid
else
    return nil
end

안전한가?

내가 직관적으로 이 방식이 동작한다고 믿는 이유는, 변형된 형태로 심도 있게 분석된 알고리즘들의 한 단계로 사용된다는 사실 외에도 다음과 같다:

우리가 “투표”의 과반수를 확보할 수 있었다면, 정의상 다른 어떤 클라이언트도 우리가 생성한 ID보다 크거나 같은 ID에 대해 과반수를 확보했을 리가 없다. 그렇지 않다면 이미 3개 이상의 인스턴스에 current 값이 $NEXTID 이상인 상태였을 것이고, 우리가 과반수를 얻는 것은 불가능했을 것이다. 따라서 생성된 ID는 항상 과거의 ID보다 크며, 같은 조건 때문에 두 인스턴스가 동일한 ID를 생성하는 것도 불가능하다.

친절한 독자라면 이 알고리즘의 버그나 다른 분석된 시스템들에서 사용된 이 알고리즘에 대한 분석을 알려줄 수도 있을 것이다. 하지만 위 내용은 클라이언트 측에서 실행되도록 변형된 것이므로 실제로는 더 많은 프로세스가 관여하고, 동등함을 증명하기 위해 재분석이 필요하다.

왜 느린 알고리즘인가?

이 알고리즘의 문제는 동시 접근이다. 많은 클라이언트가 동시에 새로운 ID를 생성하려고 하면 아무도 과반수를 얻지 못할 수 있으며, 더 큰 숫자로 다시 시도해야 한다. 이는 생성된 ID 시퀀스에 “구멍”이 생길 수 있음을 의미하기도 한다. 따라서 클라이언트는 1, 2, 6, 10, 11, 21, … 같은 시퀀스를 생성할 수 있다. 동시 접근으로 인한 스플릿 브레인 상태 때문에 많은 숫자가 “소모”될 수 있기 때문이다.

(위 문장에서 “스플릿 브레인”은 노드 간에 불일치한 상태가 있다는 의미가 아니라, 특정 ID에 대해 합의하기 위해 과반수에 도달할 수 없었다는 의미임을 참고하자. 보통 스플릿 브레인은 예를 들어 여러 노드가 자신이 마스터라고 주장하는 등 설정상의 충돌을 의미한다. 하지만 Raft 논문에서는 스플릿 브레인이라는 용어가 여기서 사용한 것과 같은 의미로 사용된다).

동시 접근으로 인한 빈번한 실패 없이 초당 몇 개의 ID를 생성할 수 있는지는 네트워크 RTT와 동시 클라이언트 수에 달려 있다. 하지만 흥미로운 점은 클러스터와 통신하며 새로운 ID 생성을 차례로 직렬화하여 클라이언트 접근을 중재하는 “ID 서버”를 만들면 알고리즘을 더 확장 가능하게 만들 수 있다는 것이다. 단일 ID 서버가 필요한 것이 아니므로 단일 장애 지점이 생기지 않는다. 이중화를 위해 몇 개를 실행하고 수백 개의 클라이언트가 이에 연결되도록 할 수 있다.

이 스키마를 사용해 초당 5천 개의 ID를 생성하는 것은 충분히 가능해야 하며, 특히 클라이언트가 멀티플렉싱이나 스레드 방식을 사용해 5개 노드에 동시에 요청을 보내도록 영리하게 구현된 경우 더욱 그렇다.

클라이언트가 많고 접근을 중재하는 노드가 없을 때의 또 다른 접근법은, 알고리즘의 한 라운드가 실패했을 경우 무작위적이고 지수적인 지연을 두고 노드에 다시 접속하는 것이다.

왜 fsync가 필요한가?

여기서는 매 쓰기마다 fsync가 필수이다. 노드가 다운되었다가 재시작될 경우 “current” 키의 최신 값을 반드시 가지고 있어야 하기 때문이다. current 값이 과거로 되돌아가면 새로 생성된 ID가 과거에 생성된 어떤 ID보다도 항상 크다는 우리의 안전성 속성을 위반할 수 있다. 하지만 동일한 목표를 달성하기 위해 완전 복제된 FSM을 사용하더라도 어차피 fsync가 필요하다(다만 동시 접근 문제는 없다. 예를 들어 일반적인 조건에서 Raft를 사용하면 요청을 보낼 수 있는 단일 리더가 있다).

따라서 Redis의 경우, 쓰기가 클라이언트에 응답하기 전에 항상 영속화되도록 AOF를 활성화하고 AOF fsync 정책을 always로 설정해야 한다.

그 ID들로 무엇을 하나

그런 ID 집합은 “전체 순서(total ordering)”라 불리는 속성을 가지므로 다양한 맥락에서 매우 유용하다. 보통 분산 연산에서는 무엇이 먼저 일어나고 무엇이 나중에 일어났는지 말하기 어렵다. 그런 ID들을 사용하면 특정 이벤트들의 순서를 항상 알 수 있다.

간단한 예를 들자면, 서로 다른 프로세스들이 이 시스템을 이용해 항목들의 리스트를 계산하고 각 하위 리스트를 로컬 저장소에 보관할 수 있다. 마지막에 여러 리스트를 병합하여 올바른 순서의 최종 리스트를 얻을 수 있는데, 마치 처음부터 각 프로세스가 항목을 추가할 수 있는 단일 공유 리스트가 있었던 것처럼 말이다.

이 알고리즘의 기원

여기서 설명한 내용은 Paxos의 첫 번째 단계와 Raft 리더 선출 모두와 매우 유사하다. 하지만 이는 전체 순서를 만들기 위해 과반수를 사용하는 Lamport 타임스탬프의 특수한 경우로 보인다.

이 블로그 포스트의 초안에 대해 피드백을 준 Max Neunhoeffer와 Martin Kleppmann에게 감사드린다. 오류가 있다면 모두 내 책임이다.