The binary search of distributed programming

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에게 깊이 감사드립니다. 물론 오류가 있다면 모두 제 책임입니다.