SPMC 아키텍처를 전제로 한 락-프리 시퀀스 락의 아이디어와 SBCL 구현, 그리고 간단한 성능 실험을 다룬다.
특수한 락킹 기법과 락-프리 데이터 구조는 요즘 내 작업의 큰 부분을 차지한다. 이 상황이 그나마 감당 가능한 주된 이유는, 아주 이른 시점에 똑똑한 사람들이 SPMC 아키텍처—단일 작성자(생산자), 다중 읽기(소비자)—에 집중하기로 결정했기 때문이라고 생각한다.
프로그래머로서 우리는 일반성을 최대화하려는 경향이 있다. 여러 작성자를 지원할 수 있다면, 왜 하찮은 SPMC 시스템에 만족하겠는가? 문제는 SPMC가 SPSC보다 어렵고, MPMC는 더 복잡하다는 점이다. 보통 동시성이 많아질수록 프로그램은 올바르게 만들기 어려워지고, 확장하기도 어려워지며, 유지보수도 어려워진다. 더 나쁜 점은 이론적인 진행 보장을 제공하기도 더 어려워진다는 것이다.
단순한 경우를 중심으로 아키텍처를 짜는 것 말고도, 이런 현실을 다루는 방법이 몇 가지 있다. 예를 들어 obstruction-freedom 같은 더 약한 프로그램 부류를 정의할 수 있다. 시스템이 obstruction-free라는 것은 다른 모든 스레드가 중단되어 있을 때 어떤 한 스레드가 진행을 보장받는다는 뜻이다. 또는 데이터 구조의 보장 자체를 약화할 수도 있다. 예컨대 단일 FIFO를 노출하는 대신, 여러 큐로 부하와 경합을 분산할 수 있다. 엄격한 FIFO 순서는 잃지만 시스템 병목도 제거된다. 또 다른 선택지는 실제 컴퓨터가 우리의 추상 모델보다 더 강력하다는 점을 찾아내는 것이다. 어떤 이들은 현실적으로 많은 락-프리 기법이 wait-free라고 주장하고, 또 다른 이들은 x86-TSO 머신의 스토어 버퍼가 유한하다는 사실을 이용한다.
지난주 나는 x86 전용 교차-수정 코드(cross-modifying code)를 가지고 낙서하다가 길을 잃었지만, 그 과정에서 단순한 락-프리 프로토콜의 귀여운 예를 하나 발견했다. 바로 락-프리 시퀀스 락이다. 말이 모순처럼 들리지만, 실제로는 말이 된다.
용어부터 더 잘 정의하는 게 도움이 된다. Lock-freedom은 일부(전부는 아님) 스레드가 중단되더라도 전체 시스템은 항상 진행한다는 뜻이다. 고전적인 시퀀스 락은 쓰기 편향(reader/writer) 락의 낙관적 형태다. 동시 쓰기는 금지되며(예: 스핀락으로), 읽기 트랜잭션은 쓰기가 진행 중임을 관측하면 언제든 중단(abort)하고, 세대 카운터(generation counter)가 ABA 문제—읽기 트랜잭션이 빠른 쓰기 전후로 “쓰기가 진행 중이 아님”을 보게 되는 경우—를 피한다.
Transactional Mutex Locks (PDF)에서 시퀀스 락은 작은 시스템에서 부러운 성능을 보였고, 읽기 위주의 워크로드에서는 꽤 괜찮게 확장됐다. 또한 쓰기용 시퀀스 락을 획득할 때 세대가 기대값과 같은지 원자적으로 확인함으로써, reader에서 writer로의 지연 업그레이드(lazy upgrade)도 가능했다. 하지만 진행 보장은 거의 다 잃는다. 중단된 작성자 하나가 전체 시스템을 얼려버릴 수 있다.
락-프리의 핵심 요령은 협력(cooperation)이다. 어떤 스레드가 임계 구역 중간에서 중단되더라도, 그 때문에 막히게 될 다른 스레드가 남은 작업을 대신 완료할 수만 있다면 상관없다. 일반적으로는 꽤 어렵지만, 멱등(idempotent)인 제한된 사용 사례를 생각해낼 수 있다. 락-프리 시퀀스 락에서 임계 구역은 미리 계산된 쓰기 집합이다. 즉 원자적으로 실행된 것처럼 보여야 하는 일련의 대입들이다. 다른 쓰기 집합으로 넘어가기 전에만 멈추면, 쓰기가 여러 번 일어나도 괜찮다.
compare-and-swap에 기반한 원시 연산 하나로 이런 조건부 쓰기를 쉽게 달성할 수 있다. 바로 restricted double compare and single swap(RDCSS)인데, A Practical Multi-Word Compare-and-Swap (PDF)에서 소개됐다. RDCSS는 제어 워드(예: 세대 카운터)와 데이터 워드(가변 셀)가 모두 기대값을 갖는지 원자적으로 확인하고, 그렇다면 데이터 워드에 새 값을 기록한다. 일반적인 쓰기에 대한 의사코드는 다음과 같다.
if (CAS(self.data, self.old, self) == fail) {
return fail;
}
if (*self.control != self.expected) {
CAS(self.data, self, self.old);
return fail;
}
CAS(self.data, self, self.new);
return success;
요령은 첫 번째 CAS가 성공하면 언제나 되돌리는 방법을 안다는 것이다(data의 이전 값은 반드시 self.old여야 한다). 그리고 그 정보가 self에 저장되므로, 첫 번째 CAS를 관측한 어떤 스레드든 RDCSS를 완료하거나 롤백하는 데 필요한 정보를 충분히 갖게 된다. 유일하게 성가신 부분은 2단계 커밋이 필요하다는 점이다. data를 예약하고, control이 expected인지 확인한 뒤에야 data에 쓴다.
쓰기당 compare-and-swap 두 번(거기에 시퀀스 락을 획득하기 위한 한 번)을 치르는 비용을 지불하면, 작성자가 다른 작성자를 배제(lock out)하지 않는다(대신 작성자들이 서로의 진행을 돕는다). 스레드(특히 읽기)는 여전히 기아(starvation)를 겪을 수 있지만, 최소한 쓰기 집합은 미리 공개될 수 있으므로, 읽기는 쓰기가 끝나길 기다리거나/돕는 대신 그 집합에서 조회할 수도 있다. 세대 카운터는 여전히 병목이지만, 쓰기가 짧고 드물게 일어난다면, 다중 워드 compare-and-swap의 3n CAS를 피하기 위한 타협으로는 받아들일 만해 보인다.
SBCL에서 이 기법이 어떻게 보이는지 보자.
먼저 raw 포인터가 없으니(나는 CL에서 sb-locative 해킹을 되살리는 시도를 할 수도 있었지만) 가변 박스(mutable box)가 필요하다.
1 2 3``` (defstruct (box (:constructor make-box (%value))) %value)
다음은 쓰기 레코드 타입이다. 다음 세대(쓰기 완료 시점)의 값과, box에서 (old . new) 쌍으로 가는 해시 테이블을 가진다. RDCSS를 이용해 multiple compare-and-swap을 구현할 때와의 중요한 차이점은, old 값 불일치를 검사하지 않고 단지 그것이 맞다고 가정한다는 점이다.
1
2
3
4
5
6
7```
(defstruct (record
(:constructor %make-record (generation ops)))
(generation (error "Missing arg") :type fixnum :read-only t)
;; map of box -> (cons old new). I use a hash table for
;; convenience but I doubt it's the right choice.
(ops (error "Missing arg") :type hash-table :read-only t))
(declaim (freeze-type record))
중심 병목은 시퀀스 락으로, 각 (읽기) 트랜잭션은 일관된 값을 읽으려 시도하기 전에 이를 스냅샷해야 한다.
1 2 3 4 5 6 7 8 9 10``` (declaim (type (or (and unsigned-byte fixnum) record) current-record)) (defglobal current-record 0)
(defvar initial-record)
(defun snapshot-generation () (let ((initial initial-record)) (if (record-p initial) (record-generation initial) initial)))
스냅샷에 연관된 세대는, 스냅샷이 양의 fixnum이면 스냅샷 그 자체이고, 그렇지 않으면 쓰기 레코드의 세대다.
어떤 읽기를 사용하기 전에, 세대 카운터가 바뀌지 않았는지 확인한다.
1
2
3
4
5
6
7
8```
(defun check ()
#-(or x86 x86-64) (sb-thread:barrier (:read)) ; x86 don't reorder reads
(let ((initial *initial-record*)
(current **current-record**))
(unless (or (eql initial current)
(and (record-p initial)
(eql (record-generation initial) current)))
(throw 'fail t))))
쓰기가 진행 중일 때 읽기 트랜잭션을 시작하는 방법으로는 두 가지가 떠오른다. 쓰기가 완료되도록 돕거나, 소프트웨어로 현재 힙 위에 쓰기를 오버레이하는 것이다. 나는 후자를 택했다. 읽기는 이미 작성자에 의해 시작될 수도 있다. 트랜잭션을 시작할 때 쓰기가 진행 중이면, 쓰기 집합을 *current-map*에 숨겨두고 먼저 거기서 조회한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16``` (defvar current-map nil)
(defun box-value (box) (prog1 (let* ((map current-map) (value (if map (cdr (gethash box map (box-%value box))) (box-%value box)))) (if (record-p value) ;; if we observe a record, either a new write is in ;; progress and (check) is about to fail, or this is ;; for an old (already completed) write that succeeded ;; partially by accident. In the second case, we want ;; the old value. (car (gethash box (record-ops value))) value)) (check)))
이제 읽기 트랜잭션을 시작할 준비가 됐다. 세대 카운터를 스냅샷하고, `*current-map*`을 업데이트한 다음, `box-value`를 사용하는 함수를 실행하려 한다. 다시 말하지만 x86 계열(그리고 SPARC도 그렇지만 SBCL은 그 플랫폼에서 스레드를 지원하지 않는다)에서는 read-read 배리어가 필요 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14```
(defun call-with-transaction (function &rest arguments)
(catch 'fail
(let* ((*initial-record* **current-record**)
(*current-map* (and (record-p *initial-record*)
(record-ops *initial-record*))))
#-(or x86 x86-64) (sb-thread:barrier (:read))
(return-from call-with-transaction
(values (apply function arguments) t))))
(values nil nil))
(defmacro with-transaction ((&rest bindings) &body body)
`(call-with-transaction (lambda ,(mapcar #'first bindings)
,@body)
,@(mapcar #'second bindings)))
다음 함수가 핵심이다. 쓰기 레코드가 정확히 한 번만 진행되도록 돕는다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30``` (defun help (record) (flet ((write-one (box old new) ;; if record isn't the current generation anymore, ;; it has already been completed (unless (eq current-record record) (return-from help nil)) (let ((actual (sb-ext:cas (box-%value box) old record))) (when (eql actual new) ;; already done? next! (return-from write-one))
;; definite failure -> no write went though; leave.
(unless (or (eql actual old)
(eql actual record))
(return-from help nil))
;; check for activity before the final write
(unless (eq **current-record** record)
(sb-ext:cas (box-%value box) record old)
(return-from help nil))
;; Really perform write (this can only fail if
;; another thread already succeeded).
(sb-ext:cas (box-%value box) record new))))
(maphash (lambda (box op)
(write-one box (car op) (cdr op)))
(record-ops record)))
;; Success! move the generation counter forward. (eql record (sb-ext:cas (symbol-value 'current-record) record (record-generation record))))
이제 `help`를 감싼 작은 래퍼로 커밋할 수 있다. Transactional mutex lock에는 쓰기 트랜잭션으로 직접 생성되는 트랜잭션이라는 아이디어가 있다. 우리는 항상 쓰기를 되돌리는 방법을 안다고 가정하므로, 트랜잭션은 reader에서 writer로만 업그레이드될 수 있다. 따라서 쓰기를 커밋할 때는, 새 쓰기 집합을 공개하고 이를 앞으로 진행시키기 전에, 세대 카운터가 (읽기) 트랜잭션과 여전히 일관적인지 확인한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15```
(defun commit (record)
(check-type record record)
(let ((initial
(loop
(let ((value **current-record**))
(check)
(if (record-p value)
(help value)
(return value))))))
(unless (and (eql (sb-ext:cas (symbol-value '**current-record**)
initial record)
initial)
(help record))
(throw 'fail t))
t))
그리고 이제 쓰기를 스케줄링하기 위한 문법적 설탕(syntactic sugar)이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17``` (defvar write-record)
(defun call-with-write-record (function) (let ((write-record (%make-record (mod (1+ (snapshot-generation)) (1+ most-positive-fixnum)) (make-hash-table)))) (multiple-value-prog1 (funcall function) (commit write-record))))
(defun (setf box-value) (value box) (setf (gethash box (record-ops write-record)) (cons (box-value box) value)) value)
(defmacro with-write (() &body body) `(call-with-write-record (lambda () ,@body)))
내 듀얼 코어 노트북에서 스모크 테스트를 하기엔 이 정도면 충분하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23```
(defvar *a* (make-box 0))
(defvar *b* (make-box 0))
(defvar *semaphore* (sb-thread:make-semaphore))
(defun test-reads (n)
(let ((a *a*)
(b *b*))
(sb-thread:wait-on-semaphore *semaphore*)
(loop repeat n
count (with-transaction ()
(assert (eql (box-value a) (box-value b)))
t))))
(defun test-writes (n)
(let ((a *a*)
(b *b*))
(sb-thread:wait-on-semaphore *semaphore*)
(loop repeat n
count (with-transaction ()
(with-write ()
(incf (box-value a))
(incf (box-value b)))
t))))
test-reads 함수는 성공한 읽기 트랜잭션 수를 세고, (box-value a)와 (box-value b)가 항상 같음을 확인한다. 그 일관성은 test-writes가 보장하는데, 이는 (box-value a)와 (box-value b)를 둘 다 증가시키는 데 성공한 횟수를 센다.
기준선(baseline)은 아마도 직렬 실행일 것이고, transactional mutex lock의 이상적인 경우는 작성자가 최대 하나일 때다. 락-프리 시퀀스 락 역시 작성자가 여러 명일 때도 잘 되길 바란다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36``` (defun test-serial (n) (setf a (make-box 0) b (make-box 0) semaphore (sb-thread:make-semaphore :count 4)) (list (test-reads (* 10 n)) (test-reads (* 10 n)) (test-writes n) (test-writes n)))
(defun test-single-writer (n) (setf a (make-box 0) b (make-box 0) semaphore (sb-thread:make-semaphore)) (let ((threads (list (sb-thread:make-thread #'test-reads :arguments (* 10 n)) (sb-thread:make-thread #'test-reads :arguments (* 10 n)) (sb-thread:make-thread #'test-writes :arguments (ceiling (* 1.45 n)))))) (sb-thread:signal-semaphore semaphore 3) (mapcar (lambda (x) (ignore-errors (sb-thread:join-thread x))) threads)))
(defun test-multiple-writers (n) (setf a (make-box 0) b (make-box 0) semaphore (sb-thread:make-semaphore)) (let ((threads (list (sb-thread:make-thread #'test-reads :arguments (* 10 n)) (sb-thread:make-thread #'test-reads :arguments (* 10 n)) (sb-thread:make-thread #'test-writes :arguments n) (sb-thread:make-thread #'test-writes :arguments n)))) (sb-thread:signal-semaphore semaphore 4) (mapcar (lambda (x) (ignore-errors (sb-thread:join-thread x))) threads)))
## 한번 해 보자!
먼저 직렬 케이스. 예상대로 모든 트랜잭션이 성공했고, 총 6.929초( GC 시간 제외 6.628초)가 걸렸다. 작성자 하나와 읽기 둘인 경우, 모든 쓰기는(예상대로) 성공했고 읽기의 98.5%도 성공했다. 이 모든 것이 GC 제외 4.186초에 이뤄졌고, 65%의 속도 향상이다. 마지막으로 작성자 둘과 읽기 둘에서는, 쓰기의 76%와 읽기의 98.5%가 GC 제외 4.481초에 완료됐다. 단일 작성자 케이스 대비 7%의 감속은 꽤 괜찮다. 내 노트북은 코어가 둘뿐이므로, 예컨대 스핀락 같은 것을 쓰면 읽기에서 더 많은 abort와 훨씬 큰 경합을 예상할 것이기 때문이다.
CL-USER> (gc :full t) (time (test-serial 1000000)) Evaluation took: 6.929 seconds of real time 6.944531 seconds of total run time (6.750770 user, 0.193761 system) [ Run times consist of 0.301 seconds GC time, and 6.644 seconds non-GC time. ] 100.23% CPU 11,063,956,432 processor cycles 3,104,014,784 bytes consed
(10000000 10000000 1000000 1000000) CL-USER> (gc :full t) (time (test-single-writer 1000000)) Evaluation took: 4.429 seconds of real time 6.465016 seconds of total run time (5.873936 user, 0.591080 system) [ Run times consist of 0.243 seconds GC time, and 6.223 seconds non-GC time. ] 145.97% CPU 6,938,703,856 processor cycles 2,426,404,384 bytes consed
(9863611 9867095 1450000) CL-USER> (gc :full t) (time (test-multiple-writers 1000000)) Evaluation took: 4.782 seconds of real time 8.573603 seconds of total run time (7.644405 user, 0.929198 system) [ Run times consist of 0.301 seconds GC time, and 8.273 seconds non-GC time. ] 179.30% CPU 7,349,757,592 processor cycles 3,094,950,400 bytes consed
(9850173 9853102 737722 730614)
그렇다면 단순 뮤텍스는 스레드 4개로 어떻게 될까?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27```
(defun test-mutex (n)
(let ((mutex (sb-thread:make-mutex))
(semaphore (sb-thread:make-semaphore))
(a 0)
(b 0))
(flet ((reader (n)
(sb-thread:wait-on-semaphore semaphore)
(loop repeat n do
(sb-thread:with-mutex (mutex)
(assert (eql a b)))))
(writer (n)
(sb-thread:wait-on-semaphore semaphore)
(loop repeat n do
(sb-thread:with-mutex (mutex)
(incf a)
(incf b)))))
(let ((threads
(list (sb-thread:make-thread #'reader
:arguments (* 10 n))
(sb-thread:make-thread #'reader
:arguments (* 10 n))
(sb-thread:make-thread #'writer
:arguments (ceiling (* .75 n)))
(sb-thread:make-thread #'writer
:arguments (ceiling (* .75 n))))))
(sb-thread:signal-semaphore semaphore 4)
(mapc #'sb-thread:join-thread threads)))))
CL-USER> (gc :full t) (time (test-mutex 1000000))
Evaluation took:
5.814 seconds of real time
11.226734 seconds of total run time (11.169670 user, 0.057064 system)
193.10% CPU
9,248,370,000 processor cycles
1,216 bytes consed
(#<SB-THREAD:THREAD FINISHED values: NIL {1003A6E1F3}>
#<SB-THREAD:THREAD FINISHED values: NIL {1003A6E383}>
#<SB-THREAD:THREAD FINISHED values: NIL {1003A6E513}>
#<SB-THREAD:THREAD FINISHED values: NIL {1003A6E6A3}>)
할당은 거의 없다(쓰기 레코드가 없기 때문이다). 하지만 읽기 병렬성이 없어서, 락은 락-프리 시퀀스 락보다 약 20% 느리다. reader-writer 락을 쓰면 아마 그 격차가 줄어들 것이다. 차이는 락-프리 시퀀스 락이 최악의 경우 더 강한 보장을 가진다는 점이다. 불운한 선점(또는 공유 메모리 IPC에서는 크래시)도 시스템 전체가 버벅이거나 심지어 멈추게 만들 수 없다.
위 결과는 내 일반적인 경험과도 일치한다. 락-프리 알고리즘이 항상(혹은 정기적으로) 잘 설계된 락킹 기법보다 더 효율적인 것은 아니다. 하지만 더 견고하고, 추론하기가 더 쉽다. 처리량이 이미 충분하다면, 락을 제거하는 것은 최선 혹은 평균 사례를 개선하기 위해서가 아니라, 데드락을 포함한 최악 사례의 한 부류를 제거하기 위해서다.
추신: 끔찍한 교차-수정 코드 해킹의 스케치가 여기 있다. (586 이후) x86 계열에서는 명령어 캐시가 완전히 일관됨이 드러났다. 프리패치 큐는 쓰기의 선형(가상) 주소에 근거해 스스로 리셋되기까지 한다. 단 하나의 원자적 바이트 쓰기만으로 xchg (%rax), %rcx를 xchg (%rbx), %rcx로 바꿀 수 있는데, 여기서 %rbx는 임의로 변경해도 안전한 위치를 가리킨다. 이는 다른 곳의 제어 워드 값에 의해 조건화된 원자적 저장이다(이 경우엔 명령어 스트림 자체에 숨겨져 있다). 그런 다음 각 트랜잭션마다 머신 코드 시퀀스 하나를 전담시키고, 어떤 Safe Memory Reclamation mechanism (PDF)을 통해 이를 재사용할 수 있다.
문제 하나가 있다. 선점이 없어도(작성자가 선점되면 재스케줄링 시 수정된 명령을 봐야 한다), 저장(store)은 실행에 꽤 오래 걸릴 수 있다. 최악의 경우 CPU는 물리 주소로 변환해야 하고 버스 락을 기다려야 한다. xchg m, r64가 얼마나 오래 걸릴 수 있는지에 상한이 있다고는 확신하지만, 하드한 수치에 대한 문서를 찾지 못했다. 만약
xchg
m, r64
가 예컨대 10k 사이클보다 오래 지속되지 않는다는 것을 안다면, 프로그램은 새 쓰기를 큐에 넣기 전에 그만큼의 사이클을 기다릴 수 있다. 그 대기는 유계이며, 쓰기가 아주 드물게만 비활성화된다면 평균 처리량에 영향을 주지 않으면서도 최악 사례의 동작을 개선할 것이다.