라이브락

라이브락은 얽힌 실행 흐름들이 쉬지 않고 움직이는 고장입니다. 그런데도 아무도 자기 일을 끝내지 못합니다. 서로에게 길을 내주려고 저마다 물러섰다가 같은 곳에서 다시 부딪히기를 되풀이합니다. 밖에서 보면 장비가 바쁘게 돌고 있어서 멈춘 것으로 보이지도 않습니다.

상세

라이브락은 얽힌 흐름들이 상태를 계속 바꾸는데도 일은 한 걸음도 안 나아가는 고장입니다. 이 편에서 「흐름」은 스레드나 프로세스처럼 따로 나아가는 실행 단위입니다. 데드락(서로를 기다리며 둘 다 멈춰 선 고장)과 달리 이 흐름들은 멈춰 서 있지 않습니다. 각자의 움직임이 상대를 다시 움직이게 만들 뿐입니다.

복도에서 마주친 두 사람

좁은 복도에서 두 사람이 마주 섭니다. 한 사람이 길을 내주려고 왼쪽으로 비킵니다. 상대도 같은 마음으로 자기 기준 오른쪽으로 비킵니다. 둘은 여전히 마주 보고 있습니다.

둘 다 그것을 보고 이번에는 반대쪽으로 옮깁니다. 또 마주 봅니다.

아무도 게으르지 않습니다. 아무도 멈춰 있지도 않습니다. 그런데 지나간 사람은 없습니다.

두 흐름이 서로를 되밀어낸다

락은 한 번에 하나만 쓰도록 자원에 거는 표시입니다. 잡은 쪽만 그 자원을 건드리고, 다 쓰면 놓습니다.

두 흐름이 각각 락 둘을 다 잡아야 일을 끝낸다고 해 봅시다. 흐름을 갑과 을, 락을 A와 B라고 부르겠습니다. 갑은 A를 먼저 잡고 을은 B를 먼저 잡습니다.

이대로 서로를 기다리면 데드락입니다. 그런데 「상대가 쥐고 있으면 내가 쥔 것도 놓고 처음부터 다시」라는 규칙을 넣으면 기다림이 사라집니다. 대신 되풀이가 생깁니다.

둘은 같은 규칙으로 돕니다. 그래서 물러섰다가 다시 시도하기까지의 간격도 같습니다.

sequenceDiagram
    participant 갑
    participant 락A
    participant 락B
    participant 을
    갑->>락A: 잡으려 한다
    락A-->>갑: 잡혔다
    을->>락B: 잡으려 한다
    락B-->>을: 잡혔다
    갑->>락B: 잡으려 한다
    락B-->>갑: 이미 잡혀 있다
    을->>락A: 잡으려 한다
    락A-->>을: 이미 잡혀 있다
    Note over 갑,을: 둘 다 쥔 것을 놓고 처음으로 돌아간다
    갑->>락A: 같은 간격 뒤 다시 잡으려 한다
    을->>락B: 같은 간격 뒤 다시 잡으려 한다

마지막 두 줄에서 돌아간 지점이 시작과 똑같습니다. 되풀이 한 바퀴를 회차라고 하면, 다음 회차도 같은 순서로 흘러갑니다. 두 흐름이 같은 간격으로 물러났다가 같은 간격으로 돌아오는 한, 회차를 아무리 거듭해도 상태는 첫 회차와 같습니다.

재현되는 조건

넷이 다 서면 라이브락이 됩니다.

1. 둘 이상의 흐름이 같은 자원 묶음을 서로 엇갈린 순서로 잡으려 합니다
2. 못 잡았을 때 기다리지 않고 자기가 쥔 것도 놓고 처음으로 되돌립니다
3. 되돌린 뒤 다시 시도하기까지의 간격이 흐름마다 같습니다
4. 다시 시도하는 횟수에 상한이 없습니다

하나만 빠져도 되풀이는 끊깁니다. 둘째가 빠지면 기다림이 남아 데드락이 되고, 셋째가 빠지면 어느 회차에선가 둘의 시점이 어긋나 한쪽이 먼저 둘 다 잡습니다. 넷째가 빠지면 되풀이가 정해진 횟수에서 끝나고 실패로 보고됩니다.

셋째가 이 고장의 핵심입니다. 물러서는 규칙 자체는 데드락을 막으려고 넣은 것입니다. 그 목적은 이룹니다.

어긋남을 만들어 줄 백오프가 없을 때만 되풀이가 이어집니다. 백오프는 다시 시도하기 전에 잠깐 쉬는 것입니다.

flowchart TD
    A["둘이 부딪혀 쥔 것을 놓는다"] --> B{"다시 시도하기까지 쉬는 간격이 흐름마다 다른가"}
    B -->|같다| C["같은 때 다시 부딪힌다"]
    C --> A
    B -->|다르다| D["한쪽이 먼저 둘 다 잡는다"]

왼쪽 고리가 라이브락입니다. 갈림에 걸린 것은 쉬는 간격 하나뿐입니다. 그 간격에 무작위 값을 조금만 섞어도 오른쪽으로 빠집니다.

코드에서 나타나는 꼴

되돌리는 규칙을 그대로 적으면 이런 모양입니다. try_lock 은 잡히면 참을 돌려주고, 이미 잡혀 있으면 기다리지 않고 거짓을 돌려주는 함수입니다.

while True:
    a_ok = a.try_lock()      # 참
    b_ok = b.try_lock()      # 거짓 · 을이 쥐었다
    if a_ok and b_ok:
        break                # 둘 다 잡았다
    if a_ok: a.unlock()      # 쥔 것만 놓는다
    if b_ok: b.unlock()

오른쪽 주석은 갑이 도는 어느 한 회차의 값입니다. 을에서는 두 값이 서로 바뀌어 나옵니다. 어느 쪽도 break 에 닿지 못하고 while 로 돌아갑니다. 돌아가는 길에는 쉬는 구간이 없습니다.

같은 모양이 락 말고 다른 곳에서도 나옵니다. 낙관적 잠금이나 CAS(Compare-And-Swap, 비교 후 교환) 반복문도 실패할 때마다 쉬지 않고 곧바로 다시 시도하면 같은 되풀이에 걸립니다.

데드락·기아와 어떻게 갈리나

이름이 나란히 불리는 고장 셋은 「무엇이 안 나아가나」에서 갈립니다.

못 끝낸다는 결과는 데드락과 같습니다. 그런데 흐름이 하는 일은 정반대입니다. 그래서 대기 상태를 세는 도구는 라이브락을 못 봅니다.

기아와는 범위가 다릅니다. 기아는 다른 흐름들이 일을 끝내고 있다는 것이 오히려 조건이고, 밀린 하나만 못 끝냅니다. 라이브락은 얽힌 쪽이 다 같이 못 끝냅니다.

무엇을 보고 알아채나

멈춰 선 흐름이 없으니 잠금 대기 목록으로는 안 보입니다. 대신 서로 어긋나는 두 값을 나란히 놓고 봅니다. CPU(Central Processing Unit, 중앙처리장치) 사용률은 높게 유지됩니다. 그런데 끝난 일의 수는 늘지 않습니다.

셋째 줄이 가장 또렷한 신호입니다. 되풀이가 이어지면 로그도 같은 주기로 반복됩니다. 한 흐름의 로그를 시각 순으로 잠깐만 따라가도 고리가 드러납니다.

평균으로 재는 값은 늦게 움직입니다. 요청 하나가 아예 안 끝나는 것이라 꼬리 지연이 먼저 커집니다. 그마저도 타임아웃이 걸려 요청이 끊긴 뒤에야 오류 수로 나타납니다.

고리를 끊는 방법

고치는 길은 대개 흐름들의 간격을 서로 어긋나게 만드는 것입니다. 지터는 쉬는 간격에 무작위 값을 조금 섞어 흐름마다 다르게 만드는 방법입니다.

락 순서 고정과 재시도 상한은 데드락에도 함께 걸리는 수단입니다. 어느 것을 고르든 재는 잣대는 하나입니다. 같은 조건을 다시 만들었을 때 회차가 첫 회차와 달라지는지 봅니다.

관련 항목

라이브락과 이름이 나란히 불리는 동시성 고장

데드락 · 기아 · 경쟁 상태 · 우선순위 역전 · 락 호위 · ABA 문제

라이브락이 일어나는 동시 실행 환경

동시성 · 스레드 · 프로세스 · 코루틴 · 컨텍스트 스위치 · 스케줄러

라이브락을 불러들이는 잠금과 재시도 장치

락 · 뮤텍스 · 스핀락 · 세마포어 · 낙관적 잠금 · 임계 구역 · 상호 배제

라이브락의 고리를 끊는 데 쓰는 수단

백오프 · 지수 백오프 · 지터 · 타임아웃 · 재시도 · 서킷 브레이커

같은 재시도 고리에서 함께 터지는 장애

재시도 폭풍 · 썬더링 허드 · 락 경합 · 캐시 스탬피드

라이브락을 알아채는 데 보는 지표

처리량 · 꼬리 지연 · 지연 · 관측성 · 모니터링

라이브락이 나타나는 분산 환경의 절차

분산 시스템 · 합의 · Raft · 스플릿 브레인 · 혼잡 제어

되풀이가 끝나는 것을 보장하려고 따지는 성질

진행 보장 · 논블로킹 알고리즘 · 락 프리 · 공정성 · CAS