TIL

Distributed Locks with Redis

• 분산 락은 서로 다른 프로세스가 베타적인 방식으로 공유 자원을 사용하여 작동해야 하는 상황에서 매우 유용한 요소이다.

Safety and Liveness Guarantees

• 분산 락을 효과적으로 사용하는 데 필요한 최소한의 세 가지 속성이 존재
  • 안정성 (safety): 상호 배제. 특정 순간에 한 클라이언트만 락을 획득 가능
  • 활력성 (liveness) A: 데드락 없음. 클라이언트가 충돌하거나 분할되더라도 결국에는 항상 잠금 획득 가능
  • 활력성 (liveness) B: 내결함성. 대부분의 Redis 노드가 가동되는 한, 클라이언트는 잠금을 획득하고 해제 가능

Failover-based 구현만으로 충분하지 않은 이유

• Redis에서 리소스를 잠그는 가장 간단한 방법은 인스턴스에서 키를 생성하는 것
  • 일반적으로 Redis 만료 기능을 사용해 제한된 기간으로 생성되며 결국에 해제됨
  • 클라이언트는 리소스를 해제해야할 때 키를 삭제
• 문제점
  • 레디스가 단일 실패 지점이 된다.
  • 만약 복제본을 추가한다면 레디스 복제가 비동기식이기 때문에 상호 배제라는 안정성을 구현할 수 없다.
• 상호 배제가 지켜지지 않는 시나리오
  1. 클라이언트 A가 잠금 획득
  2. 키에 대한 쓰기가 복제본으로 전송되기 전 마스터가 장애
  3. 복제본이 마스터로 승격
  4. 클라이언트 B는 A가 이미 잠금을 획득했음에도 동일한 리소스에 잠금을 획득

단일 인스턴스 구현

• 단일 인스턴스 설정의 한계를 극복하기 전에 간단한 사례에서 이를 올바르게 수행하는 방법을 살펴보려고 한다.
• 경쟁 조건(race condition)이 허용되는 애플리케이션에서 실제로 실행 가능한 솔루션이다.

• 잠금을 얻기 위한 명령

    SET resource_name my_random_value NX PX 30000
  

  • 키가 아직 존재하지 않는 경우에만 키를 설정 (NX 옵션)
  • 만료 시간은 30000ms (PX 옵션)
  • 키의 값으로 “my_random_value”를 설정하는데 이 값은 모든 클라이언트와 잠금 요청에서 유니크해야 한다.
  • 각 클라이언트가 유니크 값으로 잠금을 설정하는 이유는 안전하게 잠금을 해제하기 위해서이다.
    • 값이 일치할 때만 키를 제거하도록하여 다른 클라이언트가 잠금을 해제할 수 없도록
• 이 방법으로 단일 인스턴스의 비분산 시스템에서 안전한 잠금 획득과 해제를 가능하게 한다.

Redlock Algorithm

• 분산 버전 알고리즘에서 레디스 마스터가 N개 있다고 가정한다.
  1. 현재 시간을 밀리초 단위로 가져온다.
  2. 모든 N개 인스턴스에서 동일한 키와 임의의 값으로 순차적으로 잠금 획들을 시도
  1. 잠금 획득 시 전체 잠금 자동 해제 시간에 비해 짧은 타임아웃을 설정
  2. ex) 전체 자동 해제 시간이 10초인 경우 타임아웃은 5~50ms
  3. 클라이언트가 다운된 레디스 노드에 오래 블로킹되는 것을 방지하고 최대한 빨리 다음 인스턴스와 통신을 시도해야 한다.
     1. 클라이언트는 현재 시간에서 1단계에서 얻은 시간을 빼서 잠금 획득 경과 시간을 계산
  4. 대부분의 인스턴스에서 잠금을 획득할 수 있었고 경과 시간이 잠금 유효 시간보다 적은 경우에만 잠금을 획득한 것으로 간주
     1. 잠금을 성공적으로 획득한 경우 잠금 유효 시간은 초기 유효 시간에서 경과 시간을 뺀 시간으로 간주
     2. 클라이언트가 잠금을 획득하지 못한 경우 (N/2 + 1개의 인스턴스 잠금을 못 얻었거나 계산 시간이 음수인 경우) 모든 인스턴스 잠금 해제를 시도

알고리즘이 비동기적인가

• 이 알고리즘은 프로세스간 동기화된 시계는 없지만 다음 가정에 의존
  • 모든 프로세스의 로컬 시간이 잠금 자동 해제 시간에 비해 오차 범위가 적음
  • 거의 같은 속도로 업데이트됨
• 때문에 상호 배제 규칙을 더 구체적으로 명시해야 한다.
  • 잠금 획득 클라이언트가 잠금 유효 시간에서 일정 시간(프로세스 간 클럭 드리프트를 보정하기 위한 몇 밀리초)을 뺀 시간 내에 작업을 종료하는 동안만 보장

실패 재시도

• 클라이언트가 잠금을 획득할 수 없는 경우 동일 리소스에 동시에 잠금을 획득하려는 여러 클라이언트의 동기화를 해제하기 위해 무작위 지연 후 다시 시도해야 한다.
  • 이로 인해 split brain이 발생할 수 있다.
• 이상적으로는 클라이언트가 멀티플렉싱을 사용하여 N개 인스턴스에 동시에 SET 명령을 보내야 한다.
  • 잠금 획득 시도 속도가 빠를 수록 split brain 상태가 발생할 가능성이 적어진다.
• 대부분의 잠금 획득을 하지 못한 클라이언트가 부분적으로 획득한 잠금을 최대한 빨리 해제하여 잠금을 다시 획득하기 위해 키 만료를 기다릴 필요가 없도록 하는 것이 매우 중요하다.
  • 단 네트워크 파티션이 발생하여 레디스와 통신할 수 없는 경우, 키 만료를 기다리는 동안 지불하는 가용성 패널티가 있다.

잠금 해제

• 잠금 해제는 단순
• 클라이언트가 특정 인스턴스의 잠금을 획득 했든 안했든 수행할 수 있다.

Safety Arguments

• 클라이언트가 대부분 인스턴스에서 잠금을 획득했다 가정
  • 모든 인스턴스에는 동일한 유효 기간을 가진 키가 포함되지만 다른 시간에 설정되었으므로 다른 시간에 만료된다.
  • 첫 번째 키가 최악의 시간 T1(첫 번째 서버에 연결하기 전 샘플링하는 시간)에 설정
  • 두 번째 키가 최악의 시간 T2(마지막 서버로 응답을 받은 시간)에 설정
  • 이 경우 집합에서 만료되는 첫 번째 키는 최소한 MIN_VALIDITY = TTL - (T2 - T1) - CLOCK_DRIFT 동안 존재할 것
  • 다른 모든 키는 나중에 만료될 것
• 대부분 키가 설정되어 있는 동안에는 다른 클라이언트가 잠금을 획득할 수 없다.
  • N/2 + 1개 키가 이미 존재하기 때문
• 클라이언트가 최대 유효 시간에 가깝거나 더 큰 시간을 써서 대부분 인스턴스를 잠근 경우 잠금은 유효하지 않은 것으로 간주한다.
  • 유효 시간 보다 짧은 시간 내에 대부분의 인스턴스를 잠그는 경우만 고려해야 한다.
• MIN_VALIDITY의 경우 어떤 클라이언트도 잠금을 다시 획득할 수 없어야 한다.
  • 즉 여러 클라이언트가 동시에 N/2 + 1개 인스턴스를 잠글 수 있으며 잠금 획득 경과 시간이 TTL 보다 커서 잠금이 무효가 되는 경우에만 가능하다.

Liveness Arguments

• 시스템 활력성은 세 가지 주요 기능을 기반으로 한다.
  • 잠금 자동 해제 (만료 이후): 결국 키를 다시 사용할 수 있어 잠금 획득 가능
  • 클라이언트는 잠금 획득 실패하거나 작업 종료 시 잠금을 해제하는 데 협조적이기 때문에 잠금을 다시 획득하기 위해 만료될 때까지 기다리지 않아도 된다.
  • 클라이언트가 잠금 획득을 재시도할 때 필요한 시간보다 상대적으로 더 긴 시간을 기다리므로 리소스 경합 중 split brain 상황을 확률적으로 방지할 수 있다.
• 그러나 네트워크 파티션에 대해선 TTL 시간에 해당하는 가용성 패널티를 지불할 수 있다.
  • 파티션이 무한히 연속되면 시스템을 무한정 사용할 수 없게 될 수도 있다.

성능, 장애 복구 및 fsync

• 레디스를 잠금 서버로 사용하는 사용자들은 잠금 획득, 해제하는 데 걸리는 지연 시간과 초당 수행 가능한 획득/해제 작업 수 모두에서 높은 성능을 필요로 한다.
• N개 레디스 서버와 통신하여 지연을 줄이는 전략은 멀티 플렉싱을 사용하는 것
  • 클라이언트와 각 인스턴스 간의 RTT가 비슷하다는 가정 하에 소켓을 non-blocking으로 설정하고 모든 명령을 전송 후 나중에 모두 읽는 방식
  • 왕복 시간 (Round Trip Time, RTT) 은 데이터 패킷이 대상으로 전송되는 데 걸리는 시간과 해당 패킷에 대한 승인이 원본에서 다시 수신되는 데 걸리는 시간을 더한 것
• 하지만 장애 복구 시스템 모델에는 지속성에 대해서도 고려해야 한다.
  1. 5개 인스턴스 중 클라이언트 A가 3개에서 잠금을 획득한다.
  2. 잠금 획득한 인스턴스 중 하나가 재시작
  3. 클라이언트 B가 인스턴스 3개로 다시 잠금을 획득할 수 있다.
  4. 상호 배제 위반
• AOF 지속성을 활성화와 fsync=always 활성화를 통해 지속성 문제를 해결할 수 있다.
  • AOF를 통해 서버가 재시작되어도 키 설정을 유지할 수 있다.
  • 완전 종료가 아닌 서버 정전 시에도 fsync=always를 통해 매번 디스크에 write하기를 동기식으로 기다리면서 키 유실을 방지할 수 있다.
  • 그러나 이렇게 하면 동기화 오버헤드가 추가되어 성능에 영향을 미친다.
• 지연된 재시작을 통해 레디스 지속성 없이도 안정성을 확보할 수 있다.
  • 인스턴스가 장애 후 재시작될 때 더 이상 현재 활성화된 잠금에 참여하지 않도록 하는 방법
  • 즉 현재 활성화된 잠금 집합은 시스템에 다시 참여하는 인스턴스를 제외한 다른 인스턴스를 잠그며 얻은 것
  • 장애 후 인스턴스를 최소 TTL 보다 조금 더 오래 사용할 수 없게 만들면 이를 보장할 수 있다.
  • 다만 이는 대부분 인스턴스에 장애가 발생하는 경우 가용성 저하로 이어질 수 있다.

일관성에 대한 면책 조항

• 펜싱 토큰을 구현해야 한다.
  • 이는 상당한 시간이 소요되는 프로세스에 특히 중요하며 모든 분산 잠금 시스템에 적용된다.
  • 잠금 수명을 연장하는 것도 옵션이지만 잠금 획득 프로세스가 살아 있는 한 잠금이 유지된다고 가정해서는 안 된다.
• 레디스는 TTL 메커니즘에 monotonic clock을 사용하지 않는다.
  • 즉 clock이 바뀌면 프로세스에서 잠금을 획득할 수 있다.
  • 관리자가 서버의 시간을 수동으로 설정 못하도록 하고 NTP를 올바르게 설정하면 문제를 완화할 수는 있다.
  • 하지만 여전히 일관성 손상 가능성이 존재한다.

---

https://redis.io/docs/manual/patterns/distributed-locks/