50년 후, Two-Phase Locking이 최선인가?

 (concurrencyfreaks.blogspot.com)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 1976년에 공개된 Two-Phase Locking(2PL) 은 직렬 가능성보다 강한 Opacity를 제공하지만, 약 50년이 지난 지금도 읽기 확장성과 진행 보장 한계가 남아 있음
  • 단순한 잠금 획득·해제 규칙으로 여러 레코드 트랜잭션을 처리하면서 강한 격리 수준을 제공해, 상용 트랜잭션 DB와 동시성 자료구조에서 여전히 널리 쓰임
  • 전통적 2PL은 상호 배제 잠금 때문에 읽기끼리도 충돌할 수 있고, reader-writer lock을 써도 이진 검색 트리의 루트처럼 읽기가 몰리는 지점에서 read-indicator 경합이 생김
  • 2PLSF는 reader별 표시를 캐시 라인에 분산해 읽기 잠금 획득 경합을 줄이고, 충돌한 트랜잭션에만 중앙 원자 카운터의 fetch_and_add() 를 적용함
  • No-Wait, Deadlock-detection, Wait-Or-Die 같은 2PL 변형은 live-lock이나 확장성 문제를 남기며, 2PLSF는 읽기 확장성과 starvation-free 트랜잭션을 함께 겨냥한 개선형임

2PL이 여전히 중요한 이유

  • Two-Phase Locking(2PL) 은 직렬 가능성(Serializability)을 제공한 최초의 범용 동시성 제어 중 하나이며, 실제로는 더 강한 격리 수준인 Opacity를 제공함
  • 2PL은 Jim Gray와 동료들의 논문으로 1976년에 공개됐고, 아이디어 자체는 그 이전부터 있었을 가능성이 있어 거의 50년 된 기법으로 다뤄짐
  • 범용 동시성 제어는 여러 객체, 레코드, 튜플 같은 데이터 항목에 대해 all-or-nothing 의미를 갖는 트랜잭션을 가능하게 하는 알고리듬을 뜻함
  • 2PL의 장점은 단순함과 강한 격리에 있음
    • 레코드를 읽거나 쓰기 전에 해당 레코드를 보호하는 잠금을 먼저 획득함
    • 트랜잭션이 끝날 때까지 획득한 잠금을 유지해 일관된 관점을 만들 수 있음

단순한 규칙이 만드는 격리

  • 2PL에서는 트랜잭션 중 각 접근마다 잠금을 획득하고, 더 이상 접근이 없다는 것을 아는 트랜잭션 종료 시점에 모든 잠금을 해제함
  • 종료 시점에는 접근한 데이터의 잠금이 모두 잡혀 있으므로, 해당 트랜잭션에 대한 선형화 지점(linearization point) 이 생김
  • 50년 전에는 레코드 접근을 마친 뒤 잠금을 바로 해제해도 된다고 본 데이터베이스 연구자들이 많았지만, 그런 동시성 제어는 직렬 가능하지 않음
  • 알려진 트랜잭션 상용 데이터베이스는 2PL 또는 T/O, MVCC와의 조합을 사용함
  • 동시성 자료구조 분야에서는 linearizability가 표준에 가깝고, 여러 노드에 일관되게 쓰려면 보통 쓰기 접근에 대해 2PL 같은 방식이 필요함
    • 예외는 lock-free 자료구조지만, 올바른 lock-free 구현은 어렵다는 점이 강조됨

2PL의 병목: 읽기 확장성과 live-lock

  • 2PL의 큰 약점은 읽기 확장성 부족과 live-lock 진행 보장임
  • 고전적 2PL은 상호 배제 잠금을 기준으로 설계되어, 두 스레드가 같은 레코드를 읽기만 해도 충돌하고 하나 또는 둘 다 abort 후 재시작할 수 있음
  • reader-writer lock으로 바꾸면 읽기끼리의 충돌은 줄어들지만, 잠금 비용과 메모리 사용량이 늘어남
    • 상호 배제 잠금은 잠김/풀림 상태를 나타내는 1비트로 구현 가능함
    • reader-writer lock은 이 비트 외에 현재 읽기 모드로 잠금을 가진 reader 수를 세는 카운터가 필요함
    • 예를 들어 7비트 카운터는 최대 128개 스레드를 표현할 수 있고, 각 잠금이 1바이트를 차지할 수 있음
    • 데이터베이스에 수십억 개 레코드가 있으면 잠금만으로도 수십억 바이트가 필요함
  • 더 큰 문제는 카운터 경합임
    • read-non-disjoint 워크로드에서는 많은 읽기가 같은 데이터에 집중됨
    • 이진 검색 트리의 루트 노드는 모든 연산이 하위 노드로 내려가기 전에 읽어야 하는 대표 사례임
    • 2PL에서는 루트 접근마다 잠금 획득이 필요하고, reader-writer lock을 쓰더라도 루트 노드 잠금에 심한 경합이 생김

기존 접근과 확장 가능한 read-indicator

  • TLRW는 Dave Dice와 Nir Shavit이 SPAA 2010에서 제시한 접근으로, reader-writer lock을 사용해 상호 배제 잠금보다 성능을 높였지만 낙관적 동시성 제어만큼 빠르지는 않음
  • TLRW와 유사하게 각 읽기 접근이 reader-writer lock의 단일 변수에 경합하는 구현을 Rank-based Relaxed AVL 이진 검색 트리에 적용하면, 대부분 쓰기 트랜잭션이든 읽기 트랜잭션이든 확장성이 평평해짐
  • read-indicator 경합은 확장 가능한 read-indicator로 완화할 수 있음
    • 선호하는 방식은 각 reader가 도착과 이탈을 별도 캐시 라인에 표시하는 reader-writer lock임
    • 읽기 잠금 획득에는 경합이 없어짐
    • 쓰기 잠금을 얻는 스레드는 허용 여부를 확인하려고 모든 캐시 라인을 스캔해야 하므로 쓰기 잠금 획득 비용이 커짐
  • NUMA Aware reader-writer locks는 이 기법을 사용한 reader-writer lock 알고리듬을 다룸
    • 세 가지 reader-writer lock 알고리듬 중 두 개는 높은 확장성을 가지지만 starvation-free는 아님

2PLSF의 reader-writer lock 설계

  • Two-Phase Locking Starvation-Free(2PLSF) 는 읽기 잠금 획득에서 잘 확장되고 추가 성질을 갖는 reader-writer lock으로 구현한 동시성 제어임
  • 2PLSF의 reader-writer lock은 read-lock을 위해 스레드당 1비트를 예약함
    • 이 비트들은 자체 캐시 라인에 배치됨
    • 인접한 잠금의 read-indicator 비트와 함께 배치됨
  • NUMA-aware reader-writer lock 논문과 마찬가지로 비용은 쓰기 잠금 획득으로 이동함
    • 쓰기 잠금은 여러 캐시 라인을 스캔해야 함
    • 마법 같은 해결책이 아니라 트레이드오프임
  • 이 트레이드오프가 유용한 이유는 대부분의 워크로드가 read-heavy 쪽이고, write-intensive 워크로드도 레코드 조회 단계 등에서 상당한 시간을 읽기 접근에 쓰기 때문임
  • 개선된 reader-writer lock을 사용하면 read-non-disjoint 워크로드에서도 2PL을 확장할 수 있지만, live-lock 문제는 별도로 해결해야 함

2PL 변형들이 남기는 진행 보장 문제

  • 고전적 2PL에는 경합 처리 방식에 따라 No-Wait, Deadlock-detection, Wait-Or-Die 같은 대표 변형이 있음

  • No-Wait

    • 충돌이 발생하면 자기 트랜잭션 또는 상대 트랜잭션을 abort하고 다시 시도함
    • 재시도는 즉시 하거나 지수 백오프 방식으로 나중에 할 수 있음
    • 레코드 A 뒤 B를 수정하려는 트랜잭션과 B 뒤 A를 수정하려는 트랜잭션이 계속 충돌하면, 둘 다 커밋하지 못한 채 abort-restart를 반복할 수 있어 live-lock progress를 가짐

  • Deadlock-detection

    • 잠금에서 대기 중인 스레드 목록을 유지하고 사이클, 즉 데드락을 탐지함
    • reader-writer lock에서는 각 reader가 자기 목록을 가져야 하며, 각 목록을 보호하는 상호 배제 잠금도 필요함
    • read-lock 모드에서 잠금을 잡을 때 모든 reader 목록을 스캔해야 하므로 비용이 커짐
    • 이론적으로 starvation-free가 가능할 수 있지만, starvation-free lock이 필요하고 공개된 고확장 starvation-free reader-writer lock이 없다는 점에서 목적과 충돌함
    • reader마다 목록을 두면 메모리 사용량도 커질 수 있음

  • Wait-Or-Die

    • 모든 트랜잭션에 순서를 부여하고, 잠금 충돌 시 트랜잭션 타임스탬프와 잠금 소유자 타임스탬프를 비교해 대기 또는 abort를 결정함
    • 상호 배제 잠금에서는 소유자를 잠금 내부에 고유 스레드 식별자로 저장할 수 있어 잘 동작함
    • reader-writer lock에서 같은 방식을 쓰려면 reader마다 thread-id가 필요함
    • 256개 스레드를 지원하려면 8비트 × 256 = 256바이트가 reader-writer lock마다 필요함

중앙 원자 카운터 병목과 2PLSF의 차이

  • Wait-Or-Die의 더 큰 장애물은 모든 트랜잭션이 고유 트랜잭션 ID를 가져야 한다는 점임
    • 예를 들어 중앙 원자 변수에서 fetch_and_add() 로 번호를 가져와 순서를 만들 수 있음
  • 최신 CPU 대부분에서는 경합이 있는 원자 변수에 대해 초당 4천만 회 이상의 fetch_and_add()를 수행하기 어려움
    • Visa의 하루 약 6억 6천만 트랜잭션과 비교하면 커 보일 수 있음
    • in-memory DBMS나 동시성 자료구조에서는 충분히 크지 않을 수 있음
    • 한 테스트 머신에서는 초당 2천만 fetch_and_add()를 넘기기 어려웠음
  • 이 fetch_and_add()는 쓰기 트랜잭션뿐 아니라 읽기 트랜잭션을 포함한 모든 트랜잭션에 필요하다는 점이 확장성을 제한함
  • TL2는 읽기 트랜잭션이 원자 fetch_and_add()를 하지 않고 낙관적 읽기를 수행함
    • 읽기 트랜잭션 기준으로 수억 tps까지 확장될 수 있음
    • 반면 Wait-Or-Die 기반 2PL은 40M tps/sec를 넘을 수 없음
  • 2PLSF는 충돌에 들어간 트랜잭션만 순서를 매김
    • 중앙 원자 변수에서 fetch_and_add()를 수행하는 트랜잭션 수가 줄어듦
    • 충돌이 없는 트랜잭션은 40M tps 고원에 묶이지 않음
    • 예시로, 충돌 없이 200M tps가 실행되고 충돌 중인 40M tps만 fetch_and_add() 한계에 묶일 수 있음
    • 알고리듬은 starvation-freedom을 제공함

자료와 최종 평가

  • 2PLSF 알고리듬 자체는 자세히 다루지 않지만, starvation-free 알고리듬 치고는 단순한 편으로 평가됨
  • 참고 자료로 논문과 소스 코드가 제공됨
  • 2PLSF는 ACM 논문으로도 연결되며, Pedro Ramalhete, Andreia, Pascal Felber가 만든 알고리듬으로 정리됨
  • 2PLSF의 목표는 2PL이 처음부터 가졌어야 할 성질에 가까움
    • 읽기가 겹치는 read-non-disjoint 상황에서도 잘 확장됨
    • blocking progress의 가장 높은 형태인 starvation-free 트랜잭션을 제공함
    • 일부 충돌 상황에서도 확장성을 가질 수 있음
  • 2PLSF는 완벽하지 않지만, 충돌 해결 측면에서는 TL2보다 낫다고 평가되며, 기존 2PL과의 차이는 곡괭이와 착암기의 차이에 비유됨

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들
  • 이 주제는 초보지만 흥미롭고, 배포하기 쉬운 일관성 솔루션이 있었으면 좋겠음
    분산 마이크로서비스 아키텍처에서 여러 데이터 저장소를 동기화하거나 “일관되게” 유지하려면 업계 모범 사례가 무엇인지 궁금함
    며칠 전 “settled timestamp”로 불일치 문제를 풀어보려 했는데, 오류 보고가 없는 채로 시간이 지나면 유효한 저장/커밋으로 보는 다중 버전 방식에 가까움. 2단계 커밋에서 두 번째 단계가 시간인 셈임
    다른 서버의 시계를 감시하다가 갱신되지 않으면 그 서버의 settled timestamp를 신뢰하지 않는 방식이고, 매 업데이트마다 응답을 기다리지 않고 다음 timestamp 구간만 기다리면 되므로 많은 서버로 일관성을 확장하려는 의도였음
    무작위 업데이트를 주고받는 10개 스레드로 비결정성을 테스트하는 다중 스레드·다중 프로세싱 Python 코드를 만들었음: https://replit.com/@Chronological/InconsistencySimulation#ma...
    이 시뮬레이션에서 읽기는 모든 서버가 보고한 timestamp 전체의 최솟값이고, 10초 뒤 각 스레드에 카운터 값을 물어보면 가끔 모두 같은 값을 내지만 꽤 자주 split-brain 상태가 됨
    분산 시스템에서 wall clock timestamp가 순서 결정에 적합하지 않고, 논리 시계나 벡터 시계를 써야 한다는 점은 알고 있음
    어느 시점이든 시뮬레이션이 모두 같은 숫자를 보고하게 만들 수 있다면 좋겠음. Bloomlang은 eventual consistency에서 늦게 도착한 값이 결과에 영향을 주어 선형화 가능하지 않은 문제를 해결하려고 함
    특히 일관성을 유지하면서 확장하는 데 관심이 있지만 꽤 어려운 문제로 보임
    • 분산 마이크로서비스 아키텍처를 쓰지 않는 것이 업계 모범 사례임
    • 분산 시스템의 핵심 아이디어는 각 노드가 재생하는 중앙 쓰기 순서 저널을 두는 것임
      여러 시스템이 중앙 저널에 순차적으로 쓰고, 저널은 키-값 저장소처럼 요청을 받음. 그 저널이 모든 노드에 복제되고, 노드들은 저널을 읽어 요청된 복잡한 로직을 수행함
    • 정말로 (a) 분산 데이터 저장소와 (b) 동기식 일관성이 둘 다 필요한지 다시 평가해보는 게 좋음. 둘 중 하나만 포기해도 훨씬 단순해짐
    • 5년 안에 TigerBeetle DB가 일관성 있고 처리량 높고 장애 허용적인 분산 데이터베이스의 업계 기준이 될 것 같음
    • Raft 프로토콜을 보면 됨. 일반적으로 프로토콜 계층에서 직접 통합하려 하기보다는, 직렬화 가능해야 하는 조정/데이터에는 Raft를 구현한 etcd 같은 일관 저장소를 쓰는 게 표준적임
      Kubernetes가 etcd를 쓰므로, 강한 일관성을 가진 키-값 저장소로는 꽤 잘 확장됨
      “여러 데이터 저장소”라고 했으니 이질적인 데이터가 있고 CockroachDB 같은 선택지는 아니라고 가정함
      초보라면 직접 만드는 건 위험함. https://aphyr.com/는 테스트의 기준 같은 자료이고 교육용으로도 훌륭함. Jepsen으로 분산 시스템을 테스트할 수 있지만, Kyle이 견고하다고 보여준 데이터 저장소를 쓰는 편이 낫다
  • 이 새로운 접근이 직렬화 가능 스냅샷 격리(SSI)와 어떻게 비교되는지 궁금함: https://wiki.postgresql.org/wiki/SSI
    이 기술들에 익숙하진 않지만, 데이터베이스를 공부할 때 SSI가 앞으로의 “더 나은” 2단계 잠금처럼 소개됐음. SSI가 2PLSF와 어떻게 다른지, 왜 여기서 언급되지 않았는지 궁금함
    • 새 플랫폼의 메모리 모델을 만들고 있는데, 거의 전부 copy-on-write, 스냅샷, SSI를 중심으로 설계하고 있음
      하지만 분산 효과에서는 여전히 잠금, 2단계 트랜잭션 등이 필요함. 개인적으로는 대체재라기보다 서로 보완적인 기능에 가깝다고 봄
  • 잠금 알고리즘은 훌륭하지만, 적용하기 전에 정말 많은 스레드가 같은 자원을 두고 싸워야 하는지 한 발 물러서서 생각해보는 게 중요함
    메모리 내 자료구조라면 자연스럽지만, 외부 데이터베이스나 다른 공유 외부 자원을 다룬다면 더 나은 방법이 있을 수 있음
    종종 요청을 배치 처리해서 외부 자원에는 더 낮은 동시성, 더 큰 페이로드로 접근할 수 있음. 그 자원이 배치를 잘 처리한다면 필요한 동시성과 잠금이 훨씬 줄어듦
    예를 들어 Postgres를 쓴다면 연결 수가 줄고, 복잡도를 높이는 PgBouncer를 추가하지 않아도 될 수 있음
    다만 요청 배치는 대부분의 프로그래밍 언어가 잘 맞지 않음. Go의 채널이나 Elixir의 프로세스처럼 높은 동시성에 최적화된 언어는 잘할 수 있지만, 모든 것을 스레드로 처리하는 언어에서는 고통스러울 수 있음
  • 저자가 2PL이 원래 이랬어야 한다고 주장하는 2PLSF 논문: https://zenodo.org/record/7886718
  • HN에 올라오는 모든 링크를 HTTPS 링크로 요구하는 새 정책이 정말 필요함
    • 왜 그래야 함? HTTP로도 잘 동작하는 오래된 유용한 사이트가 많음. HTTPS를 지원하는데 HTTP 링크가 올라오는 경우를 말한다면 동의함
    • 순수 읽기 전용으로만 상호작용하는 사이트에서 HTTPS 대신 HTTP 링크를 방문하면 어떤 결과가 생기는지 궁금함. 보안 문제인지, 아니면 프라이버시 문제인지?
    • Firefox를 HTTPS 전용 모드로 실행하면 됨: https://support.mozilla.org/en-US/kb/https-only-prefs
      HTTPS로 업그레이드할 수 없는 사이트에서는 경고가 뜨고, 둘 다 지원하는 사이트는 곧바로 HTTPS 버전으로 이동함
    • 동시성 알고리즘 글을 읽고 나서 떠올린 게 이 관련 없는 관찰인가?
      그리고 HTTP 링크가 좋은 동시성 알고리즘에 관한 것이라면 그래도 읽을 것임
    • 아직 HTTP 전용 웹사이트가 몇몇 남아 있음
  • Wait-Or-Die에서 트랜잭션 ID를 얻으려고 정말 fetch_and_add가 필요함? 애초에 트랜잭션 ID가 필요한지도 의문임
    목표는 충돌 시 누가 기다리고 누가 죽을지 서로 합의할 수 있도록 활성 트랜잭션 사이에 임의지만 일관된 순서를 두는 것처럼 들림. 그러면 스레드 ID를 쓰면 안 되나?
    무작위 숫자도 가능할 수 있음. 동률을 “죽음”으로 처리하면 최악의 경우 양쪽 트랜잭션이 불필요하게 중단되고 새 무작위 숫자로 재시도할 뿐임
    언급되진 않았지만 오래 실행되는 트랜잭션이 짧은 트랜잭션에 굶주리지 않도록 오래된 트랜잭션을 우선하려는 것 같음. 예를 들어 긴 트랜잭션 하나가 평균적으로 짧은 트랜잭션 세 개와 충돌하고, 각 충돌에서 승자가 사실상 무작위라면 긴 트랜잭션이 세 번 모두 이겨 커밋할 확률은 1/8뿐임
    하지만 기아 방지를 위해 매번 오래된 트랜잭션을 우선할 필요는 없고 대부분의 경우면 충분함. 특히 아주 조금 더 오래된 정도라면 더 그렇다
    그래서 스레드 간 시계 오차나 다른 부정확성이 있어도 timestamp나 cycle counter 비슷한 것이 잘 동작할 수 있음. 동률은 스레드 ID로 깨거나, 역시 양쪽 모두 중단하게 하면 됨
  • 2단계 방식과 Paxos를 비교하는 틀을 제공하는 훌륭한 논문임: https://lamport.azurewebsites.net/video/consensus-on-transac...
    • 이름이 겹치지만 2단계 잠금은 2단계 커밋과 다름
      2단계 커밋은 Paxos와 비교할 만한 대상이고, 둘 다 합의 프로토콜 범주에 들어감
      2단계 잠금은 동시성 제어 메커니즘임
  • 영원히 계속되고, 절대 완벽하지도 않음
    첫 번째 잠금 메시지가 사라졌을 때, 잃어버린 것이 응답 메시지가 아니라는 걸 어떻게 알 수 있느냐가 문제임
    단순한 경우라면 GitHub나 Dropbox처럼 그냥 진행하고 나중에 충돌을 처리하면 됨. 데이터베이스라면 행운을 빌어야 하고, 은행이라면 더더욱 그렇다
  • relaxed AVL tree의 마지막 그림을 잘 이해하지 못하겠음. 100% 조회인 오른쪽 끝에서는 TL2 알고리즘이 스레드 수에 따라 선형으로 확장돼야 할 것 같음
    읽기 전용 트랜잭션에서 TL2는 전역 버전을 샘플링한 뒤, 모든 읽기에 대해 로컬 버전이 샘플링된 버전 이하인지 확인하면 됨
    그렇다면 그래프가 왜 선형 이하인지, TL2가 다른 STM 구현만큼 빠르지 않은 이유가 이해하기 어려움
    • TL2에 대한 그런 그래프는 안 보임. 대신 TLRW 그래프는 보이는데, TLRW는 reader lock을 쓰므로 확장성 한계가 있음
  • 무작위화된 큐를 추가하면 단순히 해결될 수 있음
    예를 들어 보통 작업 1000개와 하드웨어 스레드 10~100개가 있다고 하자
    작업 1000개의 정렬된 목록 하나를 만들고, 각 스레드마다 그 복사본을 만든 뒤 매번 복사본의 순서를 무작위화함
    그러면 각 스레드는 자기 목록을 읽고 작업을 실행한 뒤, 비차단 다중 스레드 큐로 구현된 한 목록을 구독하면 됨
    최악의 경우 몇몇 스레드가 어떤 작업을 반복 수행할 수 있음
    이 방식이면 원자적 연산이 최대 1000배까지 확장될 수 있음
답변달기