Scalable and Practical Locking with Shuffling

Scalable and Practical Locking with Shuffling

Notion에서 보기 

---

Abstract

shuffling

• 미리 수립된 정책에 따라 lock을 얻으려고 기다리는 스레드의 큐를 재정렬하는 것이 핵심 아이디어이다.
• critical path에서 벗어난다.
• 어떻게 NUMA-awareness / NUMA 구조를 인지하여 효율적인 전략을 세우고 보조적인 자료구조를 사용하는지를 보여준다.

1. Introduction

• lock 알고리즘은 멀티코어 머신에서 어플리케이션의 scalcbility를 결정한다.
• HW 발전에 따른 lock 설계 변천
  • MCS : 동시에 락을 얻으려고 하는 스레드의 개수의 증가를 유발하는 cache-line traffic을 설명하기 위해 제안되었다.
  • Cohort lock : NUMA 아키텍처에 대응한 lock 설께 방식으로 외부메모리로의 접근보다 로컬메모리로의 접근 속도가 훨씬 더 빠르다는 NUMA의 특징을 활용하여 어플리케이션 throughput을 향상시킨다.
    • 높은 core count에서 높은 스루풋을 성취할 수 있다 .
    • 소켓의 개수에 비례하여 메모리 사용량이 높아진다. 또한 multiple atomic instruction을 사용하기 때문에 single thread 에서는 성능 이점이 높지 않다.
    ** NUMA : 여러개의 노드 (소켓)으로 구성되어 있으며 각 노드는 여러개의 코어의 각 local 메모리와 캐시를 가지고 있다.
  • https://core.ac.uk/download/pdf/9342245.pdf
  • 하드웨어의 발전은 lock 알고리즘에 큰 영향을 미치지만 memory footprint, low thread countm core overcommition 등의 요인은 고려하지 않는다.

lock scalability에 영향을 미치는 요인

• 서로 다른 캐시간 cache-line movement
• level of thread contention
• core over-subscription
• memory footprint

새로운 lock 설계 기법 : shuffling

• lock 획득 및 반납 단계를 lock order 정책과 분리한다.
• lock waiter (락을 얻기 위해 대기하는 스레드)에게 lock order 정책을 적용한다.
• 대부분 critical path에서 벗어난 곳에 적용한다.
• 대기 큐에 있는 waiter들은 shuffler 역할을 취하고, 특정 정책을 기반으로 대기 큐에서 재배열된다.
• 빠르게 발전하는 하드웨어와 소프트웨어의 특성과 분리된 정책을 사용할 수 있게 한다.

shuffling 기법을 기반으로 한 new lock family : SHFLLOCKS

• non-blocking, blocking, and blocking readers-writer locks
• NUMA-aware
• small memory footprint
• 다양한 경쟁 수준에서 최고의 성능 유지
• 최신 blocking lock에 비해 13배 적은 메모리 오버헤드를 발생시키며 간단한 락 대비 12.5배의 어플리케이션 throughput 개선을 보인다.

2. Background and Motivation

2.1 Lock design

• 그동안 하드웨어가 락 알고리즘에 큰 영향을 미쳤다.
• ex) test-and-set (TAS), ticket lock에 비해 큐 기반 락은 cache traffic을 감소시킨다.
• NUMA 아키텍쳐에서 hierarchical lock은 물리적으로 락을 global/pre-node lock으로 파티셔닝하여 remote 접근을 줄여 스루풋은 개선시킨다.
  • issue
• CNA lock, Malthusian lock : MCS 처럼 대기 스레드의 큐를 재배열하여 CNA는 NUMA 성능을 개선하고 Malthusian은 여분의 스레드를 block한다.

Innovations of shuffling

• 큐가 lock-holding 스레드가 아닌 대기 중인 스레드에 의해 재정렬된다.
• → critical path를 빠르게 유지하고 재배열 정책의 넓은 범위를 지원한다.
• 오직 대기 스레드만 반드시 큐 노드를 유지하고 있고, lock-holding 스레드는 대기 스레드를 deallocate할 수 있다.
• → lock deployment를 단순화하고 최적화를 지원한다.

2.2 Locks in the kernel space

• Linux kernel는 최적의 단일 스레드 성능을 유지하는 것을 목표로 세분화된 lock을 전화하여 concurrency를 보장하기 위해 노력하고 있다.
• lock design consideration
  • 스케줄러와의 상호작용
  • lock structure의 크기
  • explicit memory allocation 피하기
• spinlock
  • Linux의 초기 lock 구조
  • test-and-set → ticket lock → MCS 변형
  • current lock : TAS for fast path + MCS for slow path
• Mutex
  • fast path에서 TAS와 통합한다.
  • mid-path에서 abortable (중단할 수 있는) 큐 기반 spinning을 한다.
  • slow path에서 parking list per-lock instance를 사용한다.
  • mid-path에서 최적화된 hand-over-hand locking을 최적화하여 long-term fairness를 보장한다.
• readers-writer semaphore (rwsem)
  • mutex extension
  • reader, writer, waiting reader 을 표시할 수 있다.
  • slow path에서 reader와 writer 모두 추가될 수 있는 하나의 parking list를 유지한다.
  • core over-subscribed되거나 under-subscribed인 경우에 심각한 cache-line movement가 발생한다.

3. Dominating Factors in Lock Design

• lock은 어플리케이션 scalability에 직접적으로 영향을 미치는 오버헤드를 가지고 있다.

Factor 1. Avoid data movement

• 메모리 대역폭과 NUMA 노드간 interconnect 대역폭은 제한되어 있다 그래서 어플리케이션이 remote로 접근하려 할때 성능이 저하된다.
• ⇒ 모든 락 알고리즘은 cache-line movement와 remote 메모리 접근을 최소화시켜야 한다.

Factor 2. Adapt to different level of thread contention

• 대부분의 multi-threaded 어플리케이션은 fine-grained locking을 사용하여 scalcbility를 향상시킨다.
• 일반적으로 lock design은 low contention과 high contention 둘다 최적화한다.
• → TAS는 low contention 일때, Cohort lock은 high contention을 때 좋은 성능을 보인다.
• 모든 경우의 스레드 contention 에서 최적의 성능을 보이는 알고리즘이 필요하다.

Factor 3. Adapt to over- or under-subscribed cores

• 어플리케이션은 core보다 많은 여러 개의 쓰레드로 쪼개져 task를 병렬적으로 처리할 수 있다.
• → I/O를 효율적으로 처리하고, HW utilization을 개선한다.
• 이때 blocking locks는 스레드 스케줄링 측면에서 스레드를 spinning 시킬지, sleeping 시킬지 효율적으로 선택해야 한다.→ sleeping : 하드웨어 자원 효율적 사용 ↔ sleeping 스레드를 깨우는데 드는 높은 latency
• → spinning : low latency ↔ waste CPU cycle, 다른 스레드에 starvation을 초래하면서도 낮은 자원활용도, lock holder preemption
• 락 알고리즘은 thread - core mapping을 고려해야 한다.

Factor 4. Decrease memory footprint

• lock의 memory footprint는 갅접적으로 application sacalbility에 영향을 미친다.
• 실제 어플리케이션에서 lock은 critical path 상에 있는 다른 자료 구조 내부에 있기 때문에 lock이 allocation은 memory footprint에 영향을 미친다. memory allocator에 스트레스를 주고 성능 저하로 이어진다.
• 락 알고리즘은 lock adoption과 어플리케이션 성능에 영향을 미치기 때문에 memory footprint를 고려해야 한다.

4. SHFLLOCKS

new lock design tech. : shuffling

• critical path를 벗어나서 발생하는 lock policy으로부터 lock 연산을 분리시킨다.
• lock policy는 NUMA-awareness와 효율적인 parking/wakeup 전략을 포함할 수 있다.

implementation of shuffling : SHFLLOCKS

• top-level lock으로 TAS + MCS와 같은 대기 큐의 조합을 사용한다.
• cache-line movement를 최소화하는 NUMA_awareness를 사용할 수 있는 shuffling 매커니즘을 사용한다.
• NUMA-awareness로 인해 high contention 일때도 좋은 성능을 유지하고 TAS lock으로 인해 low contention 일때도 좋은 성능을 유지한다.
• 효율적인 blocking lock 을 설계하기 위해 parking/wakeup policy를 추가한다.
• 지속적이고 최소화된 자료 구조를 필요로 하고, critical section 내부에 추가적인 할당을 요구하지 않기 때문에 memory foorprint를 줄일 수 있다.

4.1 The shuffling Mechanism

• lock을 기다리는 스레드가 lock 개발자가 지정한 policy에 의해 대기 큐를 재정렬한다.
• 스레드가 lock을 얻기 위해 대기 하는 동안 정책 수행을 처리하기 때문에 suffling은 ciritical path에서 벗어나서 수행된다.
• policy 수행과 락 획득/반납 오퍼레이션을 분리한다.
• 본 논문에서는 NUMA 아키텍처를 최적화하기 위한 policy를 설계한다.

4.2 SHFLLOCKS Design

Lock state decoupling

• 대기 큐로부터 lock 획득 상태를 분리시킨다.
• two level of lock을 도입한다.— 소켓 레벨에서 moderate conented를 위한 queue-based lock
• — non-contended를 위한 TAS lock
• queue node는 오직 락 획득 단계에서만 유지되기 때문에 대기 큐를 트랙킹하는 작업과 node allocation의 복잡성을 제거한다.
• → lock-holder가 nested acquisition을 위해 node를 재사용하는 것을 금지한다.
• shuffling 작업을 critical path에서 대기하는 스레드 waiter로 옮긴다.
• single atomic compare-and-swap instruction으로 빠른 trylock 방법을 제공한다.
• 두 개의 매커니즘을 도입하여 lock-waiter preemption 문제를 완화한다.— 내부의 TAS lock을 사용하여 lock stealing을 허용한다.
• — shuffler는 락을 얻기 위해 수동적으로 다음 스레드를 깨운다.

Scheduling-aware parking strategy

• kenel space에 blocking lock을 구현하기 위해 spin-then-park 전략을 사용한다.
• waiter는 커널 스레드 스케줄러가 허용한 시간 동안만 spin한다. 스케줄러는 스레드에게 현재 lock이 사용 가능한지 알려준다.
• waiter는 시스템이 오버로드되었을때만 parking 한다.
• waiter는 현재 CPU 스캐줄링에 active task의 개수가 peek를 찍으면 스케줄러에게 양보한다.

4.2.1 Non-Blocking Version: SHFLLOCK ^NB

• TAS + MCS + queue node on the stack
• thread의 qnode를 socket ID, shuffler status, batch count로 확장시켜 shuffling process의 bookkeeping을 한다.
• shuffling phase
  1. lock holder successor가 있다면 queue에서 그 위치를 건들지 않는다.
  2. waiter만 active shuffler가 될 수 있다.
  3. queue의 head 만 shuffling process를 시작시킬 수 있다.
  4. shuffler는 successor에게 shuffling 역할을 넘긴다.
• 1. 스레드는 처음 TAS lock을 얻으려고 시도한다.→ TAS lock을 얻지 못하면 대기 큐에 들어간다.
  2. → TAS lock을 얻으면 critical section 에 진입한다.
  3. 바로 다음 lock waiter t1이 shuffler가 되고, 같은 소켓에 속한 waiter들을 그룹화한다.
  4. shuffler가 전체 대기 큐를 iterate하면 다음 shuffler가 프로세스를 시작할때 마지막 moved waiter를 선택한다.
  5. shuffler는 같은 소켓에서 waiter을 찾는 것을 다시 시도한다. 그리고 local 소켓으로부터 successor를 찾거나 lock holder가 되어 shuffling 단계를 떠난다.
  6. 소켓 내부에서 shuffler status의 전달은 batching quata가 초과되기 전까지 지속된다.running example of SHFLLOCKS
• lock structure
  • 12 bytes
  • lock state (glock / 4 bytes) + MCS tail (8 bytes)
• how algorithm works
  • 스레드 t가 처음 TAS lock을 steal하려고 시도한다.
  • 실해파면 t는 stack에 queue-node (qnode) 를 지가시켜 MCS 프로토콜을 시작한다. 그리고 qnode 주소의 tail로 자동적으로 swap되어 대기 큐에 들어간다.
  • 큐에 들어간 t는 큐의 head로 갈때까지 기다린다. head에 간 것을 확인하기 위해 t는 predecessor를 확인한다.
  • t가 큐의 head에 도달하면 두번째 byte를 1로 바꾸어 TAS lock contention과 waiter starvation을 피하게 하여 lock stealing을 못하게 한다.
  • 이때 waiter가 있으면 t는 locally spin을 시작하고, waiting queue에 head에 도달할때까지 spin을 한다.
  • (qnode statue = S_WAITING → S_READY)
  • 여기서 t는 또한 is_shuffler 상태를 확인하고 1이면 t가 shuffler가 되고 shuffling phase에 진입한다.
  • 큐의 head에 도달하면 t는 shuffler가 되어 소켓 ID를 기반으로 successcor를 그룹화할 수 있는지 확인한다. 이때, CAS 연산을 통해 TAS lock을 얻으려고 한다.
  • qnode의 batch가 0 일때 오직 queue의 head만 shuffling process를 시작할 수 있다.
  • t는 is_shuffler 상태가 1일때 오직 waiter만 shuffle 할 수 있다. is_shuffler 상태는 이전 shuffler에 의해 set될 수 있다.
  • t가 lock holder가 되면 (t는 TAS lock을 얻으면) MCS unlock 프로토콜을 따르고 t는 다음 successor를 확인한다.
  • successor가 있으면 t는 successor의 qnode 상태를 S_READY로 업데이트하고 없으면 queue tail을 reset하고 lock stealing을 허용한다. lock stealing은 큑가 비어있을 때 새로운 스레드가 TAS을 통해 lock을 얻을 수 있게 한다.
  • unlock phase는 TAS unlock을 사용한다. 첫번째 바이트를 0으로 reset한다.

shuffling

• waiter의 qnode를 임의의 위치에서 대기 큐의 shuffled node의 끝으로 이동시킨다.
• 특정 policy를 기반으로 socket-ID를 기반으로 그룹핑을 하고 shuffler는 batch count를 업데이트하거나 대기하는 qnode의 next pointer를 조정한다.
• first shuffled node인 S는 처음 is_shuffler를 0으로 reset하고 maximum allowed shuffling 값을 확인하여 remote 소켓의 waiter에 starvation이 발생하지 않도록 한다.
• S는 마지막 shuffled qnode를 tracking 하는 동안 queue에서 qnode를 iterate한다. S는 순회하면서 batch count를 증가시키면서 S가 속한 소켓의 노드를 표시한다.
• S의 소켓에 속한 node와 last shuffled node 사이에 있는 waiter가 있을때 pointer를 조정한다.
• TAS lock이 unlock되거나 S가 queue의 head가 되면 항상 S는 shuffle phase를 나간다.
• shuffle phase를 나가기 전에 S는 next shuffler를 배정한다.
• S는 queue를 순회하는 것을 두가지 이유로 멈출 수 있다.— tail의 끝에 합류하는 waiter가 있을 수 있기 때문에 S가 큐의 tail에 도달하면 멈출 수 있다.
• — S는 곧 lock을 얻을 수 있기 때문에 locking 지연을 피하기 위해 successor가 비어있을 때 멈출 수 있다.