Redlock 과 Fencing Token

분산 시스템에서 동시에 하나의 프로세스만 특정 자원에 접근하도록 보장하는 것은 어렵다. Redis의 SET NX로 간단히 락을 구현할 수 있지만, 장애 시나리오를 파고들면 빈틈이 보인다.

왜 분산 락이 필요한가

단일 프로세스 환경에서는 뮤텍스나 세마포어로 동시성을 제어한다. 하지만 서버가 여러 대일 때는 프로세스 간 메모리를 공유하지 않으므로, 외부 저장소에 락 상태를 두어야 한다.

대표적인 사례:

• 송금 시스템: 같은 계좌에 대한 동시 잔고 변경을 방지
• 작업 스케줄러: 같은 작업이 여러 Worker에서 중복 실행되는 것을 방지
• 리더 선출: 여러 인스턴스 중 하나만 리더 역할을 수행

Redis는 단일 스레드로 명령을 처리하므로, 원자적 연산을 기반으로 분산 락을 구현하기에 적합하다.

단일 Redis 노드 락

가장 기본적인 형태다.

획득

SET resource_name my_random_value NX EX 30

• NX: 키가 없을 때만 설정한다. 이미 다른 프로세스가 락을 잡고 있으면 실패한다
• EX 30: 30초 후 자동 만료. 락을 잡은 프로세스가 죽어도 락이 영원히 남지 않는다
• my_random_value: 해제 시 본인이 잡은 락인지 확인하기 위한 고유값

해제

-- Lua 스크립트로 원자적 실행
if redis.call("GET", KEYS[1]) == ARGV[1] then
    return redis.call("DEL", KEYS[1])
else
    return 0
end

GET과 DEL을 별도로 실행하면, GET 후 DEL 전에 TTL이 만료되어 다른 프로세스가 락을 잡을 수 있다. 그 상태에서 DEL을 실행하면 남의 락을 해제하게 된다. Lua 스크립트로 원자적으로 처리해야 한다.

한계

단일 Redis 노드에 의존하므로, 그 노드가 죽으면 락 시스템 전체가 멈춘다.

이를 해결하기 위해 Primary-Replica 구성을 쓸 수 있지만, Redis의 복제는 비동기이다. Primary에서 락을 획득한 직후 Primary가 죽으면, Replica에는 아직 락이 복제되지 않은 상태에서 Replica가 Primary로 승격된다. 결과적으로 두 프로세스가 동시에 같은 락을 보유하게 된다.

sequenceDiagram
    participant C1 as Client 1
    participant P as Primary
    participant R as Replica
    participant C2 as Client 2

    C1->>P: SET lock NX → 성공
    Note over P: 락 획득 완료
    P--xR: 비동기 복제 (아직 전달 안 됨)
    Note over P: Primary 장애 발생
    R->>R: Replica → Primary 승격
    C2->>R: SET lock NX → 성공 (락이 없으므로)
    Note over C1,C2: 두 클라이언트가 동시에 락을 보유

이 문제를 해결하기 위해 Antirez(Redis 창시자)가 제안한 것이 Redlock이다.

Redlock 알고리즘

Redlock은 N개의 독립된 Redis 노드(보통 5대)에 락을 시도하여, 과반수(N/2+1) 이상에서 성공하면 락을 획득한 것으로 간주하는 알고리즘이다. 각 노드는 서로 복제 관계가 아닌 완전히 독립된 인스턴스다.

동작 순서

1. 현재 시각을 기록한다 (t1)
2. 5개 노드에 순차적으로 동일한 키와 랜덤 값으로 SET NX EX를 시도한다. 각 노드에 대한 요청에는 짧은 타임아웃(예: 5~50ms)을 설정하여, 죽은 노드에서 오래 기다리지 않는다
3. 현재 시각을 기록한다 (t2)
4. 다음 두 조건이 모두 만족하면 락 획득 성공:
   • 과반수 이상(3대 이상)에서 성공
   • t2 - t1(락 획득에 걸린 시간)이 TTL보다 충분히 짧음
5. 락의 유효 시간은 TTL - (t2 - t1)이다. 획득하는 데 시간이 걸렸으므로 그만큼 빠져야 한다
6. 실패 시: 모든 노드에 DEL을 보내어 부분적으로 잡힌 락을 해제한다

왜 과반수인가

5대 중 2대가 죽어도 나머지 3대에서 과반수를 충족할 수 있다. 동시에 두 클라이언트가 각각 과반수를 확보하는 것은 불가능하다(3 + 3 = 6 > 5). 따라서 한 시점에 최대 하나의 클라이언트만 락을 보유한다.

Redlock의 빈틈: TTL 만료 문제

Redlock이 과반수로 안전성을 확보했지만, TTL이 만료되면 락이 사라진다는 근본적인 문제가 남아있다.

다음 시나리오를 보자:

sequenceDiagram
    participant C1 as Client 1
    participant R as Redis (Redlock)
    participant DB as Database
    participant C2 as Client 2

    C1->>R: 락 획득 (TTL 30초)
    Note over C1: GC pause 35초 발생
    Note over R: 30초 후 TTL 만료 → 락 해제
    C2->>R: 락 획득 → 성공
    C2->>DB: 잔고 변경
    Note over C1: GC pause 종료
    C1->>DB: 잔고 변경 (락이 없는 상태)
    Note over DB: 두 클라이언트가 동시에 자원 접근

Client 1이 락을 잡고 작업 중에 GC pause, 네트워크 지연, 또는 예상보다 오래 걸리는 처리로 인해 TTL이 만료될 수 있다. Client 1은 자신의 락이 만료된 줄 모르고 작업을 계속한다.

이 문제는 Redlock 고유의 문제가 아니라, TTL 기반 분산 락 전체의 구조적 한계이다. ZooKeeper나 etcd 기반 락도 세션 타임아웃이라는 유사한 문제를 갖고 있다.

Lock Extension

TTL 만료를 막기 위해 락을 주기적으로 갱신한다.

동작

• 락 획득 후 TTL/3 간격으로 갱신 요청을 보낸다 (예: TTL 30초 → 10초마다 갱신)
• 갱신은 SET resource_name my_random_value XX EX 30으로 수행한다. XX는 키가 이미 있을 때만 설정하는 옵션이다
• Redlock에서는 과반수 노드에 갱신을 보내야 한다

한계

• GC pause가 갱신 주기보다 길면 TTL이 만료된다. 10초마다 갱신하는데 GC pause가 15초면 갱신을 놓친다
• 네트워크 파티션으로 Redis에 접근이 불가능하면 갱신이 실패한다
• 갱신은 확률적으로 TTL 만료를 줄여주지만, 완전히 방지하지는 못한다

따라서 락 갱신만으로는 부족하고, 자원 접근 측에서의 추가적인 안전장치가 필요하다.

Fencing Token

Martin Kleppmann이 “How to do distributed locking”에서 제안한 방법이다.

핵심 아이디어

락을 획득할 때마다 단조 증가하는 토큰(fencing token) 을 발급한다. 자원(DB 등)에 접근할 때 이 토큰을 함께 전달하고, 자원 측에서 이전에 받은 토큰보다 작은 값은 거부한다.

동작

sequenceDiagram
    participant C1 as Client 1
    participant Lock as Lock Service
    participant DB as Database
    participant C2 as Client 2

    C1->>Lock: 락 획득 → token=33
    Note over C1: GC pause 발생
    Note over Lock: TTL 만료 → 락 해제
    C2->>Lock: 락 획득 → token=34
    C2->>DB: 쓰기 (token=34) → 성공
    Note over DB: last_token = 34
    Note over C1: GC pause 종료
    C1->>DB: 쓰기 (token=33) → 거부 (33 < 34)

Client 1의 토큰은 33이다. Client 2가 이후에 락을 획득하면 토큰 34를 받는다. Client 2가 먼저 DB에 쓰면서 last_token = 34로 기록한다. 이후 Client 1이 토큰 33으로 쓰려고 하면, 34보다 작으므로 DB가 거부한다.

구현 방법

토큰 발급: 단조 증가하는 값을 생성해야 한다.

• Redis의 INCR 명령으로 카운터를 관리
• 별도의 시퀀스 생성기 사용

자원 측 검증: DB에 last_fencing_token 컬럼을 두고, 쓰기 시 비교한다.

UPDATE accounts
SET balance = balance - 10000,
    last_fencing_token = 34
WHERE user_id = 123
  AND last_fencing_token < 34

last_fencing_token < 34 조건으로, 더 최신 토큰이 이미 반영되었다면 쿼리가 0 rows affected를 리턴한다. 별도의 로직 없이 SQL 한 줄로 방어된다.

한계

Fencing Token이 효과적이려면 자원 측이 토큰을 검증할 수 있어야 한다. DB라면 WHERE 절에 조건을 추가하면 되지만, 외부 API처럼 우리가 제어할 수 없는 시스템이라면 적용이 어렵다.

Kleppmann vs Antirez 논쟁

Redlock의 안전성에 대해 Martin Kleppmann(DDIA 저자)과 Antirez(Redis 창시자) 사이에 유명한 논쟁이 있었다.

Kleppmann의 주장

“How to do distributed locking” (2016)

• Redlock은 시스템 시계에 의존한다. 노드 간 시계가 어긋나면(NTP 점프, 시계 드리프트 등) TTL 계산이 틀어지고, 두 클라이언트가 동시에 락을 획득할 수 있다
• GC pause, 네트워크 지연 등으로 클라이언트가 TTL 만료를 인지하지 못하는 문제를 Redlock 자체로는 해결할 수 없다
• 결론: 안전성이 중요하면 ZooKeeper 같은 합의(consensus) 기반 시스템을 써야 한다. 효율성만 필요하면(중복 실행은 허용하되 줄이고 싶을 때) 단일 Redis 노드로 충분하다. Redlock은 어중간하다

Antirez의 반박

“Is Redlock safe?” (2016)

• 시계 점프는 운영 환경에서 방지할 수 있다. NTP를 step이 아닌 slew 모드로 설정하면 급격한 시간 변화가 없다
• GC pause 문제는 Redlock 고유가 아니라 모든 분산 락에 해당한다. ZooKeeper도 세션 타임아웃이 있다
• Redlock은 실용적인 수준에서 충분히 안전하다

정리

	Kleppmann	Antirez
핵심 우려	시계 의존성, GC pause	운영으로 완화 가능
대안 제시	ZooKeeper + Fencing Token	Redlock + 적절한 운영
관점	이론적 정확성	실용적 충분성

이 논쟁에서 도출된 실무적 합의는 다음과 같다:

• 정확성(correctness)이 절대적인 경우 (금융, 분산 합의): Fencing Token을 반드시 같이 쓰거나, ZooKeeper/etcd 기반 락을 쓴다
• 효율성(efficiency)만 필요한 경우 (중복 작업 방지, 캐시 stampede 방지): 단일 Redis 노드의 SET NX EX로 충분하다
• Redlock은 중간 지점이지만, Fencing Token 없이 단독으로 쓰면 위의 TTL 만료 시나리오에 취약하다

References

• Redis - Distributed Locks
• Martin Kleppmann - How to do distributed locking (2016)
• Antirez - Is Redlock safe? (2016)
• Martin Kleppmann - Designing Data-Intensive Applications, Chapter 8
• Redlock Algorithm Specification