Redis 분산 락(Distributed Locks)

Redis 분산 락(Distributed Locks)

Redis로 구현하는 분산 락 패턴을 다뤄요. 여러 프로세스가 공유 리소스를 상호 배타적으로 다뤄야 하는 환경에서 유용한 기본 프리미티브이에요. 이 페이지는 Redlock 알고리즘을 제안해요.

출처: https://redis.io/docs/latest/develop/clients/patterns/distributed-locks/

분산 락은 서로 다른 프로세스가 공유 리소스를 상호 배타적으로 운영해야 하는 많은 환경에서 매우 유용한 프리미티브예요.

Redis로 DLM(Distributed Lock Manager)을 구현하는 방법을 설명하는 라이브러리와 블로그 포스트는 많지만, 각 라이브러리는 다른 접근을 사용하고, 많은 것이 약간 더 복잡한 설계로 달성할 수 있는 것보다 낮은 보장을 주는 단순한 접근을 사용해요.

이 페이지는 Redis로 분산 락을 구현하는 더 정식적인 알고리즘을 설명해요. 우리는 Redlock이라는 알고리즘을 제안하는데, 이는 단일 인스턴스 접근보다 더 안전하다고 믿는 DLM을 구현해요. 커뮤니티가 이를 분석하고 피드백을 제공하며, 더 복잡하거나 대안적인 설계 구현의 시작점으로 쓰길 바랍니다.

구현체(Implementations)

알고리즘을 설명하기 전에, 참고할 수 있는 이미 사용 가능한 구현체 링크를 몇 개 나열할게요.

안전성과 생존성 보장(Safety and Liveness Guarantees)

분산 락을 효과적으로 쓰는 데 필요한 최소 보장이라고 우리가 보는 세 가지 속성만으로 설계를 모델링할 거예요.

  1. 안전성 속성: 상호 배타(Mutual exclusion). 어떤 순간에도 단 하나의 클라이언트만 락을 보유할 수 있어요.
  2. 생존성 속성 A: 데드락 없음(Deadlock free). 리소스를 락한 클라이언트가 크래시하거나 파티션되더라도, 결국 항상 락을 획득할 수 있어요.
  3. 생존성 속성 B: 내결함성(Fault tolerance). Redis 노드의 과반이 살아있는 한, 클라이언트는 락을 획득하고 해제할 수 있어요.

왜 페일오버 기반 구현만으론 부족할까요

개선하고 싶은 것이 무엇인지 이해하려면, 대부분의 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에게 "키가 존재하고, 그 키에 저장된 값이 내가 기대하는 것과 정확히 같을 때만 제거해라"고 말하는 스크립트로요. 이는 다음 명령으로 이루어져요.

DELEX key IFEQ my_random_value

DELEX 명령은 Redis 8.4에서 도입됐어요. 이전 Redis 버전에서는 다음 Lua 스크립트로 구현할 수 있었어요.

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

이것은 다른 클라이언트가 만든 락을 제거하는 것을 피하는 데 중요해요. 예를 들어 어떤 클라이언트가 락을 획득한 뒤, 락 유효 시간(키가 만료되는 시간)보다 오래 걸리는 연산에 블로킹되고, 나중에 다른 클라이언트가 이미 획득한 락을 제거할 수 있어요. 단순히 DEL을 쓰는 것은 클라이언트가 다른 클라이언트의 락을 제거할 수 있어 안전하지 않아요. DELEX 명령이나 위 스크립트를 쓰면 모든 락이 랜덤 문자열로 "서명"되어, 제거하려는 클라이언트가 설정한 락이 여전히 맞을 때만 제거돼요.

이 랜덤 문자열은 무엇이어야 할까요? /dev/urandom에서 20바이트라고 가정해요. 하지만 작업에 충분히 유일하게 만드는 더 저렴한 방법도 찾을 수 있어요. 예를 들어 RC4를 /dev/urandom으로 시드하고 여기서 의사 랜덤 스트림을 생성하는 건 안전한 선택이에요. 더 간단한 해법은 마이크로초 정밀도의 UNIX 타임스탬프에 클라이언트 ID를 연결하는 거예요. 그리 안전하진 않지만 대부분의 환경에선 충분할 거예요.

"락 유효 시간(lock validity time)"은 키의 TTL로 쓰는 시간이에요. 자동 해제 시간이자, 다른 클라이언트가 락을 다시 획득할 수 있기 전에 클라이언트가 필요한 연산을 수행할 시간이에요. 상호 배타 보장은 락을 획득한 순간부터 특정 시간 창에만 국한되기 때문이에요.

이제 락을 획득하고 해제하는 좋은 방법이 생겼어요. 단일의 항상 사용 가능한 인스턴스로 구성된 비분산 시스템에 대해 추론하는 것은 안전해요. 이제 이런 보장이 없는 분산 시스템으로 개념을 확장해볼게요.

Redlock 알고리즘

알고리즘의 분산 버전에서는 N개의 Redis 마스터가 있다고 가정해요. 이 노드들은 완전히 독립적이라 복제나 다른 암묵적 조정 시스템을 쓰지 않아요. 단일 인스턴스에서 락을 안전하게 획득·해제하는 방법은 이미 설명했어요. 알고리즘이 단일 인스턴스에서 이 방법을 쓴다고 가정할게요. 예시에서는 N=5로 설정하는데 합리적인 값이라, 독립적인 방식으로 대부분 실패하도록 서로 다른 컴퓨터나 VM에서 5개의 Redis 마스터를 실행해야 해요.

락을 획득하기 위해 클라이언트는 다음 연산을 수행해요.

  1. 현재 시간을 밀리초 단위로 얻는다.
  2. 모든 N 인스턴스에 같은 키 이름과 랜덤 값을 써서 병렬로 락 획득을 시도한다. 2단계에서 각 인스턴스에 락을 설정할 때 클라이언트는 총 락 자동 해제 시간에 비해 작은 타임아웃을 사용해 획득한다. 예를 들어 자동 해제 시간이 10초라면 타임아웃은 약 5~50ms 범위일 수 있다. 이는 사용 불가능한 Redis 노드와 통신할 때 클라이언트가 너무 오래 블로킹되는 것을 막아, 연결 시도 타임아웃이 빨리 되도록 보장한다.
  3. 클라이언트는 현재 시간에서 1단계에서 얻은 타임스탬프를 빼서 락 획득에 경과한 시간을 계산한다. 클라이언트가 인스턴스의 과반(최소 3개)에서 락을 획득할 수 있었고, 락 획득에 걸린 총 시간이 락 유효 시간보다 짧을 때만 락이 획득된 것으로 간주한다.
  4. 락을 획득했다면 그 유효 시간은 (3단계에서 계산한) 경과 시간을 뺀 초기 유효 시간으로 간주한다.
  5. 어떤 이유로든 락 획득에 실패했으면(N/2+1 인스턴스를 락하지 못했거나 유효 시간이 음수), 모든 인스턴스의 락을 해제하려 시도한다(락하지 못했다고 생각한 인스턴스도 포함).

알고리즘은 비동기인가요?

알고리즘은 프로세스 간 동기화된 클럭이 없어도, 각 프로세스의 로컬 시간이 거의 같은 속도로 갱신되고 락의 자동 해제 시간에 비해 오차가 작다는 가정에 의존해요. 이 가정은 실제 컴퓨터와 매우 유사해요. 모든 컴퓨터에는 로컬 클럭이 있고, 서로 다른 컴퓨터가 작은 시계 드리프트(clock drift)를 가질 것이라고 보통 신뢰할 수 있어요.

여기서 상호 배타 규칙을 더 명확히 지정해야 해요. 락을 보유한 클라이언트가 (3단계에서 얻은) 락 유효 시간에서 프로세스 간 시계 드리프트를 보정하기 위한 약간의 시간(몇 ms)을 뺀 시간 안에 작업을 종료하는 동안에만 보장돼요.

이 논문은 경계가 있는 clock drift를 요구하는 유사한 시스템에 대한 더 많은 정보를 포함해요: Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

실패 시 재시도(Retry on Failure)

클라이언트가 락을 획득하지 못하면, 같은 리소스에 대해 동시에 락을 획득하려는 여러 클라이언트를 역동기화하려고 랜덤 지연 후 다시 시도해야 해요(이러면 아무도 이기지 못하는 스플릿 브레인 상태가 될 수 있음). 그리고 클라이언트가 Redis 인스턴스의 과반에서 락을 획득하려 시도하는 속도가 빠를수록 스플릿 브레인 상태(및 재시도 필요)의 창이 작아져요. 그래서 이상적으로 클라이언트는 멀티플렉싱을 써서 N 인스턴스에 SET 명령을 동시에 보내야 해요.

과반의 락을 획득하지 못한 클라이언트가 (부분적으로) 획득한 락을 가능한 한 빨리 해제하는 것이 얼마나 중요한지 강조할 가치가 있어요. 그래야 키 만료를 기다릴 필요 없이 락을 다시 획득할 수 있어요. (단, 네트워크 파티션이 발생해 클라이언트가 더 이상 Redis 인스턴스와 통신할 수 없으면, 키 만료를 기다리는 가용성 페널티를 내야 해요.)

락 해제(Releasing the Lock)

락 해제는 간단해요. 클라이언트가 주어진 인스턴스를 성공적으로 락했는지 여부와 무관하게 수행할 수 있어요.

안전성 논거(Safety Arguments)

알고리즘은 안전한가요? 여러 시나리오에서 어떤 일이 발생하는지 살펴볼게요.

먼저 클라이언트가 인스턴스의 과반에서 락을 획득할 수 있다고 가정해요. 모든 인스턴스에는 같은 TTL의 키가 들어 있어요. 하지만 키는 서로 다른 시점에 설정되므로 서로 다른 시점에 만료돼요. 하지만 첫 번째 키가 최악의 경우 T1 시점(첫 서버에 연락하기 전에 샘플링한 시간)에 설정되고, 마지막 키가 최악의 경우 T2 시점(마지막 서버에서 응답을 얻은 시간)에 설정되었다면, 집합에서 첫 번째로 만료되는 키가 최소한 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 동안 존재함을 보장할 수 있어요. 다른 키들은 나중에 만료되므로, 키들이 최소 이 시간 동안 동시에 설정되어 있음을 보장할 수 있어요.

키의 과반이 설정된 동안에는 또 다른 클라이언트가 락을 획득할 수 없어요. N/2+1개의 키가 이미 존재하면 N/2+1개의 SET NX 연산이 성공할 수 없기 때문이에요. 그래서 락이 획득되면 같은 시간에 다시 획득할 수 없어요(상호 배타 속성 위반).

하지만 동시에 락을 획득하려는 여러 클라이언트가 동시에 성공할 수 없도록 하는 것도 확인하고 싶어요.

클라이언트가 락의 최대 유효 시간(기본적으로 SET에 쓰는 TTL)에 가깝거나 그보다 긴 시간을 써서 인스턴스의 과반을 락했다면, 락을 무효로 간주하고 인스턴스를 해제할 거예요. 그래서 클라이언트가 유효 시간보다 짧은 시간에 인스턴스의 과반을 락할 수 있었던 경우만 고려하면 돼요. 이 경우 위에서 이미 밝힌 논거로, MIN_VALIDITY 동안 어떤 클라이언트도 락을 다시 획득할 수 없어야 해요. 그래서 여러 클라이언트가 (2단계 끝 시점을 "시간"으로 해서) N/2+1 인스턴스를 동시에 락할 수 있는 경우는, 과반을 락하는 데 걸린 시간이 TTL 시간보다 커서 락이 무효가 되는 경우뿐이에요.

생존성 논거(Liveness Arguments)

시스템 생존성은 세 가지 주요 특징에 기반해요.

  1. 락의 자동 해제(키가 만료되므로): 결국 키는 다시 락할 수 있게 돼요.
  2. 클라이언트가 보통 협력하여, 락을 획득하지 못했을 때나 락을 획득하고 작업을 종료했을 때 락을 제거하므로, 락을 다시 획득하기 위해 키가 만료되기를 기다릴 필요가 없을 가능성이 높아요.
  3. 클라이언트가 락을 재시도해야 할 때, 과반의 락을 획득하는 데 필요한 시간보다 비교적 큰 시간을 기다려, 리소스 경쟁 중 스플릿 브레인 상태를 확률적으로 드물게 만들어요.

하지만 네트워크 파티션 시 TTL 시간에 해당하는 가용성 페널티를 내요. 그래서 지속적인 파티션이 있으면 이 페널티를 무기한 낼 수 있어요. 클라이언트가 락을 획득하고 락을 제거하기 전에 파티션으로 분리될 때마다 이런 일이 발생해요.

기본적으로 무한히 지속되는 네트워크 파티션이 있으면 시스템이 무한한 시간 동안 사용 불가능해질 수 있어요.

성능, 크래시 복구, fsync(Performance, Crash Recovery and fsync)

락 서버로 Redis를 쓰는 많은 사용자는 락 획득·해제의 지연과 초당 수행할 수 있는 획득/해제 연산 수 양쪽에서 높은 성능이 필요해요. 이 요구를 충족하려면 N개 Redis 서버와 통신해 지연을 줄이는 전략은 확실히 멀티플렉싱이에요(소켓을 논블로킹 모드로 두고 모든 명령을 보낸 뒤, 클라이언트와 각 인스턴스 사이 RTT가 비슷하다고 가정하고 모든 명령을 나중에 읽는 것).

하지만 크래시 복구 시스템 모델을 목표로 한다면 영속화에 관한 또 다른 고려 사항이 있어요.

문제를 보려면 영속화를 전혀 구성하지 않은 Redis를 가정해볼게요. 클라이언트가 5개 중 3개 인스턴스에서 락을 획득해요. 락을 획득한 인스턴스 중 하나가 재시작되면, 같은 리소스에 대해 다시 락할 수 있는 인스턴스가 3개가 되고, 다른 클라이언트가 다시 락할 수 있어 락의 배타성이라는 안전성 속성을 위반해요.

AOF 영속화를 활성화하면 상황이 꽤 개선돼요. 예를 들어 서버에 SHUTDOWN 명령을 보내고 재시작해 업그레이드할 수 있어요. Redis 만료는 서버가 꺼져 있을 때도 시간이 흐르도록 의미적으로 구현되므로, 모든 요구사항이 충족돼요. 하지만 깨끗한 종료일 때만 괜찮아요. 정전은 어떨까요? Redis가 기본값처럼 매초 디스크에 fsync하도록 구성되어 있다면, 재시작 후 키가 없을 수 있어요. 이론적으로 어떤 종류의 인스턴스 재시작에도 락 안전성을 보장하려면 영속화 설정에서 fsync=always를 활성화해야 해요. 이는 추가 sync 오버헤드로 성능에 영향을 줘요.

하지만 상황은 첫눈에 보이는 것보다 낫습니다. 기본적으로 인스턴스가 크래시 후 재시작될 때, 현재 활성화된 락에 더 이상 참여하지 않는 한 알고리즘 안전성은 유지돼요. 즉 인스턴스가 재시작될 때 현재 활성화된 락의 집합은 모두 시스템에 재합류하는 인스턴스 이외의 인스턴스를 락해서 얻은 것이에요.

이를 보장하려면 인스턴스가 크래시 후, 우리가 쓰는 최대 TTL보다 조금 더 오래 사용 불가능하게 만들어야 해요. 이것은 인스턴스가 크래시했을 때 존재했던 락에 관한 모든 키가 무효가 되어 자동으로 해제되는 데 필요한 시간이에요.

*지연 재시작(delayed restarts)*을 쓰면 어떤 Redis 영속화 없이도 기본적으로 안전성을 달성할 수 있어요. 다만 이것이 가용성 페널티로 이어질 수 있다는 점을 주의하세요. 예를 들어 인스턴스의 과반이 크래시하면 시스템은 TTL 동안 전역적으로 사용 불가능해져요(여기서 전역은 이 시간 동안 어떤 리소스도 락할 수 없다는 뜻).

알고리즘을 더 안정적으로: 락 연장하기(Extending the lock)

클라이언트가 수행하는 작업이 작은 단계로 구성되어 있다면, 기본적으로 더 작은 락 유효 시간을 쓰고 락 연장 메커니즘을 구현해 알고리즘을 확장할 수 있어요. 기본적으로 클라이언트가 연산 중간에 락 유효성이 낮은 값에 가까워지면, Lua 스크립트를 모든 인스턴스에 보내 락을 연장할 수 있어요. 이 스크립트는 키가 존재하고 그 값이 락 획득 시 클라이언트가 할당한 랜덤 값과 여전히 같으면 키의 TTL을 연장해요.

클라이언트는 인스턴스의 과반에서 락을 연장할 수 있었고(기본적으로 락을 획득할 때 쓰는 알고리즘과 매우 유사) 그것이 유효 시간 안에 끝났을 때만 락이 다시 획득된 것으로 간주해야 해요.

하지만 이것은 기술적으로 알고리즘을 바꾸지 않으므로, 락 재획득 시도 횟수의 최대치를 제한해야 해요. 그렇지 않으면 생존성 속성 중 하나가 위반돼요.

일관성에 관한 고지(Disclaimer about consistency)

이 페이지 끝의 Analysis of Redlock 섹션을 철저히 검토하길 권해요. Martin Kleppmann의 글과 이에 대한 antirez의 답변은 매우 관련이 깊어요. 일관성과 정확성에 관심이 있다면 다음 주제에 주의해야 해요.

  1. 펜싱 토큰(fencing tokens)을 구현해야 해요. 몇 가지 유의미한 시간이 걸릴 수 있는 프로세스에는 특히 중요하며, 어떤 분산 락 시스템에도 적용돼요. 락의 수명을 연장하는 것도 옵션이지만, 락은 그것을 획득한 프로세스가 살아있는 한 유지된다고 가정하면 안 돼요.
  2. Redis는 TTL 만료 메커니즘에 단조 클럭(monotonic clock)을 쓰지 않아요. 즉 벽시계(wall-clock) 이동으로 인해 하나 이상의 프로세스가 락을 획득할 수 있어요. 관리자가 서버 시간을 수동으로 설정하는 것을 막고 NTP를 제대로 설정해 문제를 완화할 수 있지만, 실제에서 이 문제가 발생해 일관성을 훼손할 여지가 여전히 있어요.

도움 주고 싶으신가요? (Want to help?)

분산 시스템에 관심이 있다면 당신의 의견/분석이 정말 좋아요. 다른 언어의 참조 구현체도 아주 좋을 거예요.

Analysis of Redlock

  1. Martin Kleppmann이 여기서 Redlock을 분석했어요. 이 분석에 대한 반론은 여기에서 볼 수 있어요.

더 알아보기 (Learn more)