최근 동료에게 이런 말을 들었다.
RedLock은 노드마다 시계가 어긋나면 락이 깨질 수 있다.
생각해보니 정말 일리있는 말인것 같다. RedLock은 독립적인 Redis 노드를 이용해 과반수 이상의 키를 소유했는지 여부로 판단하는데 여러 노드 간의 시계열이 어긋나면 TTL에 의해서 키가 사라지고 락이 깨질 수 있을것 같다.
실제로 찾아보니 마틴 클레프만의 위험성을 강조한 글도 찾아 볼 수 있었다.
https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
How to do distributed locking — Martin Kleppmann’s blog
How to do distributed locking Published by Martin Kleppmann on 08 Feb 2016. As part of the research for my book, I came across an algorithm called Redlock on the Redis website. The algorithm claims to implement fault-tolerant distributed locks (or rather,
martin.kleppmann.com
마틴 클레프만의 글을 정리해보면 아래와 같이 정리 될 수 있다.
서로 다른 redis 노드에 키와 TTL을 저장한다. 만약 `PX 3000` 을 보내면 redis는 만료될 절대 시간을 계산해서 저장한다. 그리고 그 계산은 노드의 시계를 기준으로 동작한다. 만약 노드가 3개라면 3개의 시계가 존재하며 그 3개의 시계는 서로 맞추지 않는다.(물론 엘라스틱 캐시나 NTP 설정을 통해서 어느정도 맞긴 한다.) 이 경우 TTL을 1초로 했다면 정말로 3개 노드의 시계이 딱 맞을까? 이 시계이 어그러지면 어떻게 될까?
이번 포스팅에서는 이런 문제와 해결 방법을 정리해보려고 한다.
1. 시나리오
초당 1,000 요청, 선착순 쿠폰 3만장, 오픈 후 30초 이내 소진
위 상황에서 고려해야할 항목은 아래와 같다.
- 정확도 : 3만장인데 3만 900장이 발급된다면 사고다.
- 줄을 세워야 한다 : 선착순이기 때문에 모든 요청이 그 뒤에 서게 된다.
- 멈춰도 시간은 흐른다 : 락을 쥔 프로세스가 멈춰도 TTL은 만료된다.
위 시나리오 테스트를 위해서 2번 측정을 진행했다.(로컬 테스트라 요청 수 자체는 조절했다..)
- 정확성 : 수량을 100으로 두고 소진시킨다. -> 초과 발급 발생 여부 확인
- 성능 : 수량을 100만으로 두고 절대 소진되지 않게 한다. -> 모든 요청에 락 경합이 발생한다.
2. 쿨럭 드리프트 - 시계는 어긋난다
컴퓨터의 시계는 똑같이 맞췄더라고 하더라도 시간이 지나면 벌어진다. ( 물리부품이기 때문에 개체마다 주기가 미세하게 다르고 온도와 환경에 따라 변한다.)
그래서 보통은 NTP를 이용해서 맞추는 데, 맞추는 방식이 두 가지다.
- slew : 시계를 살짝 빠르게/느리게 돌려서 서서히 맞춘다.
- step : 현재 시각 = 정확한 시각 으로 확 바꾼다. 시간이 튀거나 뒤로간다.
2.1 락이 깨지는 이유
Redis의 TTL은 절대 시각으로 저장된다. `PX 3000` 을 주면 3초 뒤가 아니라 현재 시각 + 3000ms 라는 타임스탬프를 기록하고, 만료 검사는 그값을 그 노드의 시스템 시간과 비교한다.
클라이언트: "TTL 3초를 잡았고 획득에 200ms 썼으니 2.768초는 안전하다"
노드 C: "내 시계로는 이미 만료 시각이 지났다"
-> 클라이언트와 노드가 서로 소통하지 않는다.
Redis 노드 끼리는 시간을 맞추지 않는다. 각자 따로 NTP를 볼 뿐이며, RedLock 프로토콜에도 시각을 동기화하는 단계가 없다. 맞추는 과정에서 사고가 나는게 아니라, 맞추는 과정이 아예 없어서 각 노드가 제멋대로 만료를 판정한다.
12:00:00 A가 3대 전부 획득. TTL 3초
12:00:01 node-2, node-3의 NTP가 step으로 +5초 점프
→ 기록된 만료 시각을 이미 지났다
→ 두 노드에서 락 키가 사라진다
ㄴ A에게 아무도 알려주지 않는다
12:00:01 B가 node-2, node-3 획득 → 2/3 과반 → "락 획득 성공" A와 B가 동시에 임계 구역에 있다
2.2 락 정상 동작 VS 클럭 드리프트 발생
현재 로컬에서 테스트를 하고 있기 때문에 시계를 돌리는 건 생각보다 어렵다.
컨테이너에서 `date -s` 를 하면 커널의 CLOCK_REALTIME을 공유하기 떄문에 호스트와 다른 컨테이너까지 전부 영향 받는다. 리눅스에 time namespace가 있긴 하짐나 CLOCK_MONOTONIC과 CLOCK_BOOTTIME 만 가상화하고 CLOCK_REALTIME은 의도적으로 제외한다. 하필 Redis의 만료 판정을 보는 시계가 저 값이다.
그래서 시계 대신 TTL을 건드려서 테스트 환경을 만들었다.
내가 만들고 싶은 상황은 아래와 같다.
TTL을 1000ms로 줬는데, 100ms 만에 키가 사라진다. 왜? redis 노드별 시간이 어긋났기때문이다.
| 방법 | 결과 | |
| A | 노드 시계를 900ms 앞으로 돌린다 | 100ms 만에 만료 |
| B | 그 노드에만 TTL을 100ms로 준다 | 100ms 만에 만료 |
밖에서 보기엔 A와 B가 동일하다. 관측되는건 "언제 키가 사라졌나" 이므로 둘다 100ms이다.
그리고 3개의 redis 노드 중 2개에만 준다. 왜냐하면 전부 100ms로 TTL을 설정하면 그건 그냥 TTL을 100ms로 준 것이고 노드 끼리 어긋난 상황이 아니다.
T=0 A 가 3/3 키 획득
--------------------------------------------------
T=100 노드2, 노드3 만 만료 (노드1 은 살아있음)
→ A 는 아직 노드1 을 갖고 있다
--------------------------------------------------
T=100 B 가 락 획득 시도 → 노드1 실패, 노드2 성공, 노드3 성공
→ 2/3 과반 → "획득 성공"
A: 노드1 보유 - 둘 다 자기가 락을 가졌다고 믿는다
B: 노드2+노드3 보유 - 과반이 두 번 만들어졌다
결과적으로 임계 영역이 깨진다.
실험 설계
변수를 하나만 두기 위해 나머지는 전부 고정했다.
| 항목 | 값 |
| 락 | RedLock(독립 노드 3대) |
| 쓰기 방식 | 읽고-계산하고-쓰기 |
| TTL | 1000ms |
| 락 타임아웃 | 2000ms |
| 부하 | 40 VU X 25초 |
| 쿠폰 수량 | 100장 |
| time skew | 900ms |
RedLock 코드
package com.study.redisallpack.infrastructure.lock
import com.study.config.redis.RedLockNodes
import com.study.redisallpack.domain.lock.DistributedLock
import com.study.redisallpack.domain.lock.Fence
import com.study.redisallpack.domain.lock.FenceGenerator
import com.study.redisallpack.domain.lock.LockAcquisitionException
import com.study.redisallpack.domain.lock.LockType
import io.lettuce.core.ScriptOutputType
import org.slf4j.LoggerFactory
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty
import org.springframework.stereotype.Component
import io.lettuce.core.SetArgs
import io.lettuce.core.api.StatefulRedisConnection
import java.time.Duration
import java.util.UUID
import java.util.concurrent.ThreadLocalRandom
@Component
@ConditionalOnProperty(name = ["redis.redlock.enabled"], havingValue = "true", matchIfMissing = true)
class RedLock(
private val nodes: RedLockNodes,
private val fenceGenerator: FenceGenerator,
) : DistributedLock {
private val log = LoggerFactory.getLogger(javaClass)
override val type = LockType.REDLOCK
override fun <T> withLock(key: String, wait: Duration, lease: Duration, block: (Fence) -> T): T {
require(nodes.size > 0) { "RedLock 노드가 없습니다. redis.redlock.nodes 를 설정하세요." }
val token = UUID.randomUUID().toString()
val deadline = System.nanoTime() + wait.toNanos()
while (true) {
val validity = tryAcquireQuorum(key, token, lease)
if (validity != null) {
log.debug("[RedLock] 획득 key={} 유효={}ms", key, validity.toMillis())
return try {
block(Fence(fenceGenerator.next(key), validity))
} finally {
releaseAll(key, token)
}
}
if (System.nanoTime() >= deadline) {
throw LockAcquisitionException(key, type, "과반을 얻지 못했습니다. key=$key 노드=${nodes.size}")
}
Thread.sleep(ThreadLocalRandom.current().nextLong(RETRY_JITTER_MILLIS))
}
}
private fun tryAcquireQuorum(key: String, token: String, lease: Duration): Duration? {
val startedAt = System.nanoTime()
val futures = nodes.connections.mapIndexed { i, conn ->
val px = (lease.toMillis() - nodes.skewOf(i)).coerceAtLeast(1)
conn.async().set(key, token, SetArgs.Builder.nx().px(px))
}
val acquired = futures.count { runCatching { it.get() }.getOrNull() == OK }
val elapsed = Duration.ofNanos(System.nanoTime() - startedAt)
val validity = validity(lease, elapsed)
if (acquired >= nodes.quorum && !validity.isNegative && !validity.isZero) {
return validity
}
log.debug(
"[RedLock] 실패 key={} 획득={}/{} 과반={} 경과={}ms 유효={}ms",
key, acquired, nodes.size, nodes.quorum, elapsed.toMillis(), validity.toMillis(),
)
releaseAll(key, token)
return null
}
private fun releaseAll(key: String, token: String) {
nodes.connections.forEach { conn ->
runCatching {
conn.async().eval<Long>(UNLOCK_SCRIPT, ScriptOutputType.INTEGER, arrayOf(key), token)
}.onFailure { log.debug("[RedLock] 해제 실패 key={} {}", key, it.message) }
}
}
companion object {
private const val OK = "OK"
const val CLOCK_DRIFT_FACTOR = 0.01
const val CLOCK_DRIFT_ALLOWANCE_MILLIS = 2L
fun drift(lease: Duration): Duration =
Duration.ofMillis((lease.toMillis() * CLOCK_DRIFT_FACTOR).toLong() + CLOCK_DRIFT_ALLOWANCE_MILLIS)
fun validity(lease: Duration, elapsed: Duration): Duration = lease - elapsed - drift(lease)
private const val RETRY_JITTER_MILLIS = 20L
private val UNLOCK_SCRIPT = """
if redis.call('GET', KEYS[1]) == ARGV[1] then
return redis.call('DEL', KEYS[1])
else
return 0
end
""".trimIndent()
}
}
정상적인 상황
| 항목 | 값 |
| HTTP 200(발급 성공) | 100 Req |
| DB 실제 발급 | 100 건 |
| 남은 수량 | 0 건 |
| 허수 발급 | 0 건 |
| 소진 이후 응답 | 41 건 |
| 락 타임아웃 | 440 건 |
| 총 요청 | 581 건 |
우선 클럭 드리프트가 발생하지 않은 정상적인 상황의 결과는 쿠폰 100장이 모두 정상적으로 소진되었다.
현재 상태에서 클럭 드리프트가 발생한다면 어떤 상황으로 변할까?
클럭 드리프트가 발생한 상황
| 항목 | 값 |
| HTTP 200(발급 성공) | 103 Req |
| DB 실제 발급 | 100 건 |
| 남은 수량 | 0 건 |
| 허수 발급 | 3 건 |
| 소진 이후 응답 | 199 건 |
| 락 타임아웃 | 344 건 |
| 총 요청 | 646 건 |
RedLock을 이용해서 분산락을 구현한 경우, 정상적인 경우와 클럭 드리프트가 발생한 케이스를 비교해보면 결과가 확실하다.
- 정확성이 박살낫다 - 실제 DB로 인해서 발급 자체는 100건이지만 HTTP 요청이 200으로 3명에게 허위 발급되었다.
- 지표상으로는 좋아 보인다. - 락 타임아웃이 440 -> 344건으로 줄었다. 그럴만 한게 락이 더 빨리 풀렸으니 대기가 짧아져 지표상으로는 좋아보인다.
- DB 숫자는 멀쩡하다 - 락 경합이 깨졌기 때문에 아래와 같은 상황에서 유저는 쿠폰을 정상 발급 받았다고 전달 받을 수 있다.
A: SELECT issued=99 → remaining=1>0 통과 → issued=100 쓰기
B: SELECT issued=99 → remaining=1>0 통과 → issued=100 쓰기
↑ A의 증가를 덮어쓴다
2.3 시계를 맞춰도 깨진다 - GC
사실 redis 노드 간 시계가 깨지는 경우는 많지 않은것 같다. 여기에 NTP를 잘 맞추거나, AWS를 사용하고 있다면 ElasticCache를 쓰면 더욱 그렇다.(RedLock으로 분산락을 구현하는 경우가 많을까? 이건 잘 모르겠다. 클러스터도 아닌 서로 다른 독립적인 Redis 노드가 필요한데?)
각 노드 간 시간을 맞추더라도 프로세스가 멈추면 동일하게 발생할 수 있다.
NTP가 완벽하고 3개의 노드의 시계가 나노초까지 일치한다고 가정해보자.
12:00:00.000 A가 락 획득. TTL 3초
12:00:00.010 A의 JVM이 Full GC 시작
— Stop-The-World 스레드 전부 정지 —
12:00:03.000 TTL 만료. 락 해제 (시계는 정확하다. 예정대로 만료된 것뿐이다)
12:00:03.100 B가 락 획득. 정당한 획득이다
12:00:05.000 A가 깨어난다. 자기가 5초간 멈췄다는 걸 모른다
A: 쿠폰 발급 실행 ← B와 동시에 임계 구역
위 케이스에서는 A와 B 모두 락을 정당하게 획득했다.
이처럼 프로세스가 멈추게 되면 동일하게 락 경합이 깨지게 될 수 있다. 그리고 멈추는 원인은 GC 뿐만이 아니다.
| 원인 | 규모 |
| JVM Full GC / 대용량 힙 STW | 수백 ms ~ 수 초 |
| 컨테이너 CPU throottling | 수백 ms ~ 수 초 |
| 메모리 페이징 스왑 | ~ 수 초 |
| 기타 | 임의 |
위 케이스 모두 자기도 모르게 프로세스가 멈출 수 있다.
그래서 이러한 문제를 해결하기 위해서 아래와 같은 결론이 도달하게 된다.
"락이 안 풀리게 하겠다" -> "풀려도 상관 없게 하겠다."
2.4 펜싱 토큰
펜싱 토큰은 락을 획득 할때마다 발급되는 단조 증가하는 번호로 쓰기 요청에 함께 실어 보내고, 보호 대상 자원이 "내가 본 것보다 작거나 같은 번호는 거부한다"
| 조건 | 뜻 | 왜 필요한가? |
| 락 회득 시점에 발급 | 일을 시작하기 전에 이미 손에 쥔다 | 멈춘 뒤에 받으면 최신 번호를 받아버려 의미가 없다. |
| 단조 증가 | 절대 되돌아가지 않는다. | 되감기면 지난 차례의 쓰기가 다시 통과한다. |
| 자원이 검사 | 락이 아니라 쓰기 대상이 판단한다 | 락은 자기가 만료된 걸 모르므로 판단할 수 없다. |
락 경합 실패했던 상황에 토큰을 넣으면 아래와 같이 방어가 가능하다.
12:00:00 A가 락 획득 → 토큰 5← 뚫리기 전에 이미 받았다
12:00:00 A: 작업 중...
12:00:00.1 노드2, 노드3 조기 만료 (클럭 드리프트)
12:00:00.1 B가 과반 획득 → 토큰 6 → 발급, lastFence = 6
12:00:00.4 A: 작업 끝, issue(5) 호출 5 <= 6 → 거부
A는 여전히 자기가 락을 가진걸로 알고 있지만 토큰이 6보다 작기 때문에 거부된다.
펜싱 토큰은 누가 발급해야할까?
RedLock 에서 락 획득은 과반의 노드가 내 키를 갖고 있는 상태다. 그런데, 각 노드가 알 고 있는 값은 누가 내 키를 SET 했는가? 뿐이다.
node-1: "lock:coupon 키에 UUID-abc 가 들어있다"
node-2: "lock:coupon 키에 UUID-abc 가 들어있다"
node-3: "lock:coupon 키에 UUID-abc 가 들어있다"
따라서, RedLock으로 분산락을 구현하고 펜싱 토큰까지 넣기 위해서는 외부 도움이 필요하다.
| 외부 툴 | 순서를 만드는 방법 | 펜싱 토큰 |
| Zookeeper | 합의 로그(zxid) | 로그에서 자연스럽게 추출됨 |
| etcd | 합의 로그(revision) | 로그에서 자연스럽게 추출됨 |
조금 쉽게 구현하려면 RDB 낙관적 락을 이용해서 토큰을 발급할 수 있다.
UPDATE fence_sequence SET token = token + 1
WHERE fence_key = :key AND token = :expected -- 내가 읽은 값이 그대로일 때만
`token`이 버전 역할을 수행하면 된다. 단조 증가하므로 별도의 `version` 컬럼도 필요없다.
// 현재 토큰을 읽는다.
val current = repository.findByFenceKey(key) ?: create(key)
// 토큰 비교 := 낙관적 락
if (repository.bumpIfUnchanged(key, current.token) > 0) {
return current.token + 1
}
2.5 결과
펜싱토큰을 구현(제공)하기 위한 방법은 여러 가지 있지만 일반적으로는 아래와 같이 3가지 방법이 사용된다.
- Redis를 이용한 펜싱 토큰 : INCR, 원자적, 재시도 없으나 failover시 되 감김
- Rdb를 이용한 펜싱 토큰 : 낙관적 락, 재시도 있으나 되감기지 않음
- Zookeeper를 이용한 펜싱 토큰 : 순차 znode 생성, 되감기지 않으나 과반수 이상의 fsync가 필요
그중 Redis와 Rdb를 이용한 펜싱 토큰으로 분산락의 락을 유지하고 성능을 측정해보았다.
Redis 펜싱 토큰 분산락 결과
결과
- HTTP 200 : 100건
- DB 실제 : 100건
- 허수 발급 : 0건
- 펜싱 토큰에 의한 쓰기 차단 : 45건
- 락타임아웃 : 348건
- P95 토큰 발급 : 0.81ms
Rdb 펜싱 토큰 분산락 결과
결과
- HTTP 200 : 100건
- DB 실제 : 100건
- 허수 발급 : 0건
- 펜싱 토큰에 의한 쓰기 차단 : 54건
- 락타임아웃 : 351건
- P95 토큰 발급 : 7.91ms(Redis와 비교했을때 10배 정도 느려짐)
결과적으로 정확성은 모두 문제가 없었다.
정리
락은 자기가 만료된 걸 모르는 클라이언트를 막을 방법이 원리적으로 없어보인다. 그래서 Zookeeper, RDB, 별도 Redis 등의 외부 도구를 이용해서 락이 깨지더라도 쓰기를 막도록 해야한다.
특히 RedLock을 이용한 경우 외부 도구를 어떤 도구를 쓸지 판단해야하는데
아래와 같이 구분할 수 있겠다.
| 상황 | 선택 |
| 빠르고 가끔 틀려도 되는것(단순 중복 작업 방지) | Redis INCR |
| 틀리면 안되고 자원이 DB 안 | 낙관적 락 |
| 틀리면 안되고 자원이 DB 밖 | Zookeeper |