병렬 프로그래밍

project1/src/main.cc는 순수 싱글스레드다. include/pool.h에 스레드풀이 존재하지만 main.cc 어디서도 사용되지 않는다. 병렬 프로그래밍 과목의 첫 과제에서 기본 브랜치가 순차 코드인 것은 변명의 여지가 없다. origin/multi 브랜치에 병렬 버전이 있으나, 채점자가 master를 본다면 그것은 없는 것과 같다.

README는 - [x] make Failure Link and Output Link로 체크되어 있지만, include/ahocorasick.h 어디에도 failure link를 구성하는 코드가 없다. match()는 모든 시작 위치마다 루트에서 트라이를 다시 타는 완전 탐색이다. 복잡도는 Aho-Corasick의 O(|q| + matches)가 아니라 O(|q| × L_max)로, 실체는 “트라이로 최적화한 브루트포스”다. 이름과 문서가 구현을 잘못 광고하고 있다.

sync()(ahocorasick.h:102)는 A/D 이후 첫 질의에서 자동자 전체를 다시 만든다. 저자 본인의 주석에 It's not necessary, and slow라고 적혀 있고, README의 - [ ] efficent delete algorithm도 미완 표시다. 즉 이 과제에서 난이도가 몰려 있는 부분이 미해결 상태다.

include/unique.h:211의 unique::list::_insert(const T&)에 return true가 없다. 반환값을 사용하면 정의되지 않은 동작이다. 정작 이 클래스는 어디에서도 사용되지 않는다(dead code). 결함 자체보다 쓰지도 않을 제네릭 컨테이너를 직접 만들었다는 사실이 이 레포 전체의 우선순위 문제를 대변한다.

질의 하나를 DEFAULT_THREAD_SIZE(17)개로 쪼개 fork-join 한다. 질의 길이가 수십~수백 바이트면 packaged_task 할당 + 뮤텍스 큐 + future::get 비용이 매칭 본체보다 크다. 정석은 질의 간 파이프라인(입력 / 매칭 / 출력 순서 재배열)이다. 게다가 failure link가 없는 알고리즘을 그대로 병렬화했으므로, 잘못된 것을 빠르게 하는 구조다.

330행의 return true 때문에 그 아래 wait-for 그래프 구성과 BFS 사이클 탐지 전체가 도달 불가능한 코드다. 실제 동작은 “데드락 탐지”가 아니라 “충돌하면 무조건 abort”다. 과제의 핵심 요구사항이 구현되어 있지 않다.

락 보유자는 항상 waiting[rid]에 엔트리를 남긴다. 따라서 try_acquire 실패는 곧 waiting[rid]가 비어 있지 않음을 뜻하고, 위 결함에 의해 모든 충돌이 예외 없이 abort된다. 그 결과 블로킹 acquire()로 가는 try_failed 분기도 도달 불가능해진다.

즉 README가 가장 길게 설명한 산출물 — 획득 순서를 보장하는 thread::safe::Mutex의 lock() / lock_shared() 대기 로직 — 이 프로그램 수명 동안 단 한 번도 실행되지 않는다. 실제로 쓰이는 것은 try_lock / try_lock_shared뿐이다. 노력의 대부분이 죽은 코드에 들어갔다.

try_lock()(mutex.hpp:50)은 FIFO 순서를 무시하고 waiter 큐 뒤에 자신을 넣으면서 writing = true로 만든다. 반면 unlock()은 “첫 번째 writer 엔트리”를 지운다. 따라서 대기 중인 다른 writer의 엔트리를 지울 수 있고, 그 writer는 영원히 만족될 수 없는 조건을 기다린다.

또한 do { wait(lock, pred); } while (writing); 구조는, wait(lock, pred)가 술어가 참이면 즉시 반환한다는 점에서 위험하다. 이 상태에 빠지면 내부 mutex를 쥔 채 tight spin이 되고, unlock()이 그 뮤텍스를 얻지 못해 영구 정지한다.

container.hpp:167–169에서 첫 연산이 abort될 때 new로 만든 Operation 3개를 해제하지 않는다. 위에서 보았듯 모든 충돌이 abort이므로 상시 누수다.

더 나쁜 것은 overflow abort 경로다. waiting[]에 등록된 포인터를 제거하지 않은 채 undo()가 그 객체를 delete한다. waiting에 해제된 포인터가 영구히 남고, 그 레코드를 건드리는 이후 모든 트랜잭션은 영원히 abort한다.

container.hpp:313의 T count;는 생성자 초기화 리스트에 없고 기본 멤버 초기자도 없다. 커밋 ID와 종료 조건(order() > e)이 미정의 값에서 출발한다. 게다가 order()는 global 뮤텍스 없이 count를 읽어 데이터 레이스다.

transaction()의 모든 락 획득·해제·커밋이 단 하나의 std::mutex global 안에서 일어난다. per-record RW 락을 만든 의미가 사라지고 사실상 전역 직렬화다. Project 4에서 저자가 비판한 lock_sys->mutex 병목을 Project 2에서 스스로 재현한 셈이다.

정답 검증 스크립트 test.py는 동료(Sangchul Lee)의 것이고 — 출처를 명시한 것은 옳다 — 실행 결과가 하나도 커밋되어 있지 않다. 이 프로젝트가 옳게 동작했다는 증거가 레포에 존재하지 않는다. 또한 표준 라이브러리 분기를 #if defined(__GNUC__) && (__GNUC__ < 7)로 했는데, clang은 __GNUC__ = 4를 정의한다. 실제로 현재 빌드하면 fatal error: 'experimental/string_view' file not found로 죽는다. __has_include를 봤어야 한다.

이 알고리즘의 정확성 증명은 “레지스터의 읽기/쓰기가 원자적이고 순서가 보인다”를 전제한다. 코드에는 그 전제가 없다. x86에서 정렬된 포인터 저장이 찢어지지는 않지만, 메모리 배리어도 volatile도 없어 -O3에서 컴파일러가 객체 초기화와 저장을 재배열하거나 table[i] 로드를 루프 밖으로 끌어낼 수 있다. C++ 표준상으로는 그냥 data race, 즉 정의되지 않은 동작이다. 네임스페이스가 atomic인데 원자 연산이 0개다.

원 알고리즘에서 moved[]는 각 scan 호출의 지역 상태다. 여기서는 Snapshot의 멤버라 모든 스레드가 공유한다. 두 가지가 동시에 깨진다.

• 다른 스레드가 scan을 시작하며 fill로 내 진행 상태를 리셋한다 → 최대 n회 재시도라는 wait-free 보장이 무너진다.
• 다른 스레드가 세워둔 moved[i]를 보고 “i가 두 번 움직였다”고 오판한다 → 내 scan 시작보다 이전의 스냅샷을 정답으로 반환한다. 선형화 지점이 존재하지 않는 값을 돌려주는 것이므로 정확성 결함이다.

출력되는 숫자는 메인 스레드가 큐에 넣은 태스크 수이지 완료된 update 수가 아니다. 게다가 모든 future를 60초 내내 보관한다.

직접 빌드해 돌린 결과(g++ -O2, 4스레드, 2초): update : 2161742, maximum resident set size 368,967,680 바이트. 60초로 환산하면 10GB급이다. 따라서 results/out_SCS의 56M, out_server2의 98M도 전부 push 카운트이고, result.png는 사실상 “단일 생산자 + 뮤텍스 하나짜리 태스크 큐”의 처리량 그래프다.

README는 “I do not understand why SCSLab Server's return low performance than others”로 끝난다. 원인은 다섯 가지가 겹친 것이며, 전부 코드에서 확인된다.

올바른 측정은 스레드마다 자기 루프에서 update를 돌리고 스레드-로컬 카운터를 합산하는 것이다. 코드 20줄이면 바뀌고, 그랬다면 물음표로 끝나지 않았을 것이다.

trash[tid]에 1000개가 쌓이면 delete한다(snapshot.hpp:75). 그 순간 다른 스레드의 scan()이 old_value[i]로 그 포인터를 들고 있을 수 있다 → use-after-free. hazard pointer나 epoch reclamation이 필요한 자리를 상수 지연으로 대체했고, 주석에도 근거 없이 I think do not need라고만 적혀 있다. 초당 100만 회 갱신에서 1000회는 1밀리초도 되지 않는 유예다.

lock_rec_lock_fast가 항상 새 락을 만들고 성공을 반환하므로, 충돌 검사(lock_rec_other_has_conflicting)·대기 큐 등록·데드락 탐지를 담당하는 lock_rec_lock_slow가 절대 호출되지 않는다. 저자 본인의 주석에도 그렇게 적혀 있다. lock_set_lock_and_trx_wait도 #ifndef ITE4065로 제거되어 어떤 트랜잭션도 락을 기다리지 않는다.

lock_alloc이 ut_malloc_nokey(sizeof(lock_t))만 할당하고, n_bits 설정과 lock_rec_set_nth_bit(lock, rec_id.m_heap_no)를 건너뛴다. InnoDB는 레코드 비트맵으로 락 대상을 식별하는데 그 비트맵이 없다. 충돌 검사를 하고 싶어도 정보가 없어 불가능하다.

따라서 이것은 “확장 가능한 락 매니저”가 아니라 “락을 걸지 않는 락 매니저”다. read-only 워크로드는 S락끼리 어차피 충돌하지 않으므로 Milestone 1의 결과는 우연히 맞지만, Milestone 2(read/write)는 격리 수준이 사실상 사라진다. README의 “I ran the sysbench test to write to it, but it was not a problem”은 증거가 되지 못한다 — sysbench oltp_read_write는 쿼리 성공 여부만 보고 직렬성을 검증하지 않는다. 바로 다음 줄의 “I am expecting that someday it'll get an error”가 정확한 진단이다.

sizeof(hash_cell_t*)는 8바이트인데 hash_cell_t는 {node, tail, head}로 24바이트다. 16바이트를 힙 밖에 쓴다.

물리 삭제는 실행 중 트랜잭션의 최소 타임스탬프를 구해 cur_lock->timestamp < min_timestamp인 락만 해제한다. 그런데 ACTIVE 트랜잭션의 timestamp는 항상 0이다. 타임스탬프가 커밋 시점에만 부여되기 때문이다. 활성 트랜잭션이 하나라도 있으면 min_timestamp = 0이 되어 조건이 절대 참이 되지 않고, 락이 영원히 회수되지 않는다.

README의 “종료 전에 시간을 충분히 줘야 한다”, “mysqld가 메모리가 안 비워졌다며 에러를 낸다”는 증상이 정확히 이것이다. 저자는 이를 설계의 한계(“victim 하나가 전부 처리해서 느리다”)로 서술했지만, 실제 원인은 두 줄짜리 시점 버그다. 시작 시점에 타임스탬프를 부여하면 대부분 해소된다.

원자 로드도 volatile도 배리어도 없다. -O2에서 로드가 루프 밖으로 hoist되면 무한 루프다. __sync_* 빌트인은 그 자체로 배리어지만, 그 사이의 평범한 읽기(state, hash, head)는 전혀 보호되지 않는다. 또 trx_sys->mysql_trx_list 순회를 trx_sys->mutex 없이 수행한다(1740행, 7937행).

results/의 원본 sysbench 로그를 직접 집계했다(th* = enhanced, oth* = base, result.png로 교차 확인).

README는 이 트레이드오프를 한 줄도 언급하지 않고 128스레드 결과만 강조한다. 게다가 개선판은 충돌 검사를 하지 않아 더 적은 일을 하는데도 중간 구간에서 진다. per-lock ut_malloc_nokey와 GC 스핀 오버헤드가 그만큼 크다는 뜻이다. “전역 뮤텍스 경합을 할당 비용과 맞바꿨고, 그 거래는 64스레드를 넘어야 이익” — 이것이 이 데이터의 정직한 결론이며, 그렇게 썼다면 훨씬 강한 보고서가 되었을 것이다.

• cell3333 같은 디버깅기 변수명이 최종 제출본에 남아 있다.
• ITE4065_READ_ONLY / ITE4065_READ_WRITE가 univ.i에 정의만 되고 어디서도 사용되지 않는다. 게다가 #define X FALSE + #ifdef X 패턴은 항상 참이 되는 함정이다.
• storage/innobase/include/ite4065.h는 라이선스 헤더만 있는 빈 파일이다.
• lock0lock.h에서 gclist / gclist_state를 Depreciated라고 주석 달아놓고 실제로는 핵심 경로에서 사용 중이다.
• sysbench 커맨드라인, my.cnf, 테이블 수·크기, 격리 수준이 README에 없다. th*/oth* 파일명 규칙도 설명이 없어 그래프 없이는 어느 쪽이 개선판인지 알 수 없다.