역사: Go 1.14 이전에는 런타임이 중앙 잠금으로 보호된 단일 전역 타이머 힙을 유지했습니다. 타이머를 생성하거나 수정하는 모든 고루틴이 이 잠금을 위해 경쟁했으며, 이는 타임아웃이 있는 수천 개의 동시 연결을 관리하는 고속 네트워크 서버에서 심각한 확장성 병목 현상을 발생시켰습니다.
문제: 코어 수가 증가함에 따라 전역 타이머 잠금은 직렬화 지점이 되었습니다. 고루틴이 time.AfterFunc을 호출하거나 기존 타이머를 수정할 때 전역 잠금을 획득하고, 4-히프 구조를 업데이트하고, 전용 타이머 스레드를 깨울 수도 있었습니다. 이 직렬화된 접근은 CPU 코어와 함께 타이머 작업이 수평적으로 확장되는 것을 방해하여 부하하의 지연 시간을 악화시켰습니다.
해결책: Go 1.14는 타이머 시스템을 P(프로세서)별 타이머 힙을 사용하도록 재설계했습니다. 각 논리 프로세서는 자신의 64-히프(4-히프 변형)의 타이머를 유지합니다. 타이머가 생성되거나 재설정될 때 런타임은 타이머의 상태 단어에 대한 원자적 비교 및 교환 작업을 사용하여 비잠금 알고리즘을 실행합니다(타이머는 runtime.timer 구조체로 표현됨). 타이머가 소유자의 다른 P에 의해 수정되면 런타임은 원본 고루틴을 차단하지 않고 힙 간 이동을 위해 원자적 업데이트를 사용합니다. 타이머 프로세서는 이제 스케줄러의 findRunnable 루프에 통합되어 각 P가 전역 동기화 없이 로컬 힙을 스캔할 수 있습니다.
// 타이머 수정의 개념적 표현 func resetTimer(t *timer, when int64) { // 원자성을 이용한 비잠금 상태 전이 for { old := atomic.Load(&t.status) if old == timerWaiting || old == timerRunning { // 원자적으로 훔치거나 업데이트 시도 if atomic.CompareAndSwap(&t.status, old, timerModifying) { t.when = when // 로컬 P의 힙 내에서 리밸런싱 atomic.Store(&t.status, timerWaiting) break } } } }
문제 설명: Go로 작성된 고주파 거래 게이트웨이는 시장 개장 중 지연 시간이 10ms를 초과하는 스파이크를 경험했음에도 불구하고 CPU 사용률은 낮았습니다. 프로파일링 결과 모든 뮤텍스 경합의 40%가 runtime.timer 작업에서 발생했으며, 특히 SetReadDeadline을 통해 연결 읽기 마감 시간을 연장하는 데서 나타났습니다. 운영팀은 처음에 네트워크 지연을 의심했지만 Go의 실행 추적기는 전역 타이머 잠금이 범인으로 지목했습니다.
고려된 다양한 해결책:
한 가지 접근 방법은 표준 라이브러리 외부에서 사용자 공간 타이밍 휠을 구현하는 것이었습니다. 이는 만료 시간에 따라 타이머를 버킷으로 샤딩하고 고정 크기 원형 버퍼를 사용하는 것이었습니다. 이것은 런타임 잠금 경합을 제거했지만 상당한 복잡성을 도입했습니다: 거래 팀은 휠 발전을 위한 별도의 고루틴을 유지하고 긴 타임아웃에 대한 오버플로우 버킷을 처리하며 런타임의 보장 없이 메모리 안전성을 보장해야 했습니다. 게다가 휠의 세분성은 서브 밀리초 거래 요구에 대해 충분하지 않았고, 구현은 유지 관리 부담의 위험이 있었습니다.
또 다른 고려된 해결책은 time.Timer 객체를 적극적으로 풀링하고 재사용하여 할당을 최소화하는 것이었습니다. 이는 GC 압력을 줄였지만 Reset() 또는 Stop()을 호출할 때 전역 타이머 잠금에 대한 근본적인 경합 문제를 해결하지 않았습니다. 팀은 배치된 마감 점검을 위해 time.Ticker를 사용해보기도 했지만, 이는 타임아웃 시 즉각적인 연결 종료 요구를 위반하여 규제 사양에 비준수하게 만들었습니다.
선택된 해결책 및 결과: 팀은 Go 1.15(여기에는 P별 타이머 개선이 포함됨)로 마이그레이션하고 직접 SetReadDeadline 호출을 time.AfterFunc 콜백을 통해 마감 시간 확장을 관리하는 사용자 정의 연결 래퍼로 교체했습니다. 이 변경은 타이머 항목을 모든 사용 가능한 P에 분산시켜 뮤텍스 경합을 경미한 수준으로 감소시켰습니다. 결과적으로 피99 지연 시간이 95% 감소함(12ms에서 0.6ms로)하여 게이트웨이가 스케줄러 저하 없이 100,000개의 동시 연결을 처리할 수 있게 되었습니다.
런타임은 고루틴이 Ps 간 이동할 때 타이머 마이그레이션을 어떻게 처리하며, 타이머가 단순히 고루틴을 따라갈 수 없는 이유는 무엇입니까?
타이머는 생성되거나 마지막으로 재설정된 P에 바인딩되며, 고루틴에 바인딩되지 않습니다. 고루틴이 작업 훔치기 도중 Ps 간 이동하면 타이머는 원래 P의 힙에 남아 있어야 하며, 이는 모든 컨텍스트 전환에서 원자적 오버헤드를 피하기 위해서입니다. 타이머가 작동하면 런타임은 관련 고루틴이 이제 다른 P에서 실행되고 있음을 확인하고 해당 P의 실행 대기열에 콜백을 대기시킵니다. 이 분리는 필수적입니다. 왜냐하면 타이머 힙은 힙 불변성 유지를 요구하기 때문에 타이머가 고루틴과 함께 마이그레이션할 수 있도록 허용하면 모든 도난 시마다 원본 및 목적지 P 타이머 힙을 잠가야 하여 P별 디자인이 제거한 경합을 다시 도입하게 됩니다.
타이머 구현에서 네 가지 상태의 원자 상태 기계(timerIdle, timerWaiting, timerRunning, timerModifying)가 필요한 특정 경쟁 조건은 무엇입니까?
상태 기계는 타이머가 실행을 위해 선택된 후 콜백 실행 전에 더 늦은 시간으로 재설정되는 "잃어버린 깨우기" 경쟁 조건을 방지합니다. 원자적 상태가 없으면 P A는 자신의 힙에서 타이머를 선택하고(실행 중으로 표시), P B는 동시에 이를 재설정할 수 있습니다. 네 가지 상태는 Reset 작업이 timerModifying 또는 timerRunning 상태를 보도록 보장하며, 타이머를 수정하기에 안전해질 때까지 회전합니다. 후보자들은 종종 timerModifying가 상태 변경 동안 일시적인 스핀 잠금 역할을 하여 콜백이 오래된 데이터로 실행되거나 완전히 누락되는 것을 방지한다는 점을 놓칩니다.
런타임이 타이머에 대해 표준 이진 힙 대신 64-히프 구조를 유지하는 이유와 이것이 캐시 선 최적화와 어떤 관련이 있는지 설명하십시오.
64-히프(4-히프)는 트리의 깊이를 로ग₄(n) 수준으로 줄여 log₂(n)와 비교하여, 상향 및 하향 작업 중 포인터 추적 및 캐시 미스를 최소화합니다. 표준 이진 힙에서는 각 비교에 두 자식을 로드해야 하며(잠재적으로 두 캐시 선); 4-히프는 한 번에 네 개의 자식을 로드하여 현대 x86_64 아키텍처의 단일 64바이트 캐시 선에 맞춥니다. 이 구조는 의도적으로 한 타협이지만, 각 레벨에서 비교 수를 증가시키지만 캐시 미스를 상당히 줄이는 장점이 있습니다. 이는 P당 수천 개의 타이머를 관리할 때 타이머 힙 작업의 지연을 지배합니다.