O(1) 결정론적 전처리란 무엇인가

O(1) 결정론적 전처리의 의미

O(1) 결정론적 전처리는 입력 데이터의 크기와 관계없이 항상 일정한 시간 내에 처리를 완료하는 것을 의미합니다. 이는 일반적인 소프트웨어 처리 방식과 근본적으로 다른 접근입니다.

일반적으로 데이터 처리 시간은 입력 크기에 비례하여 증가합니다 — O(n), O(n log n) 등. 하지만 O(1) 전처리에서는 데이터가 1KB든 1GB든, 전처리 단계의 소요 시간이 동일합니다. 이것이 가능한 이유는 전처리 대상이 개별 데이터 단위(패킷, 센서 값, 입찰 요청)이며, 각 단위에 대한 필터링·정규화·라우팅 연산이 상수 시간에 완료되도록 설계되어 있기 때문입니다.

결정론적(deterministic) 이라는 수식어는 더욱 중요합니다. 단순히 “빠른” 것이 아니라, 항상 같은 시간에 완료된다는 보장을 의미합니다. 10번을 실행하면 10번 모두 동일한 지연 시간을 보입니다. 이것이 확률적 평균(average case)이 아닌 최악 경우(worst case) 보장이라는 점에서 기존 접근과 결정적으로 다릅니다.

기존 방식의 한계

전통적인 데이터 전처리는 운영체제 커널을 거치며 비결정적(non-deterministic) 지연이 발생합니다:

• 커널 오버헤드: 시스템 콜과 인터럽트 처리에 수 마이크로초가 소요됩니다. 네트워크 패킷 하나를 수신하기 위해 커널은 인터럽트 핸들링, 소켓 버퍼 할당, 프로토콜 스택 처리 등 수십 단계를 거칩니다.
• 컨텍스트 스위칭: 프로세스 간 전환 시 CPU 레지스터, TLB, 캐시 상태가 교체되며, 이 비용은 시스템 부하에 따라 크게 변동합니다. 바쁜 시스템에서는 컨텍스트 스위칭 한 번에 10μs 이상이 소요될 수 있습니다.
• 메모리 복사: 커널 공간에서 사용자 공간으로의 데이터 복사(copy_to_user)는 CPU 사이클과 메모리 대역폭을 소비합니다. 대용량 데이터일수록 이 병목이 심화됩니다.

이러한 오버헤드가 문제인 이유는 단순히 “느려서”가 아닙니다. 예측 불가능하기 때문입니다. 동일한 작업을 반복해도 매번 다른 지연이 발생하며, 시스템 부하가 높을수록 편차가 커집니다. 이를 지터(jitter) 라고 하며, 실시간 시스템에서 지터는 평균 지연보다 더 치명적인 문제입니다.

왜 “평균적으로 빠른 것”으로는 부족한가

HFT(고빈도 매매)에서 99.9번째 백분위 지연(tail latency)이 평균의 10배라면, 1,000번의 거래 중 1번은 경쟁사에게 기회를 뺏깁니다. 전자전에서 대응 신호 생성이 때때로 느려진다면, 그 “때때로”가 실전에서 치명적 결과를 초래합니다. PID 제어에서 제어 주기가 불규칙하면, 피드백 루프가 불안정해져 제품 불량으로 이어집니다.

O(1) 결정론적 전처리는 이 문제를 근본적으로 해결합니다. 최악 경우에도 동일한 성능을 보장하므로, 시스템 설계자가 안심하고 의존할 수 있는 기반을 제공합니다.

Akritai의 접근

Akritai는 세 가지 핵심 기술을 결합하여 O(1) 결정론적 전처리를 구현합니다:

1. Kernel Bypass: OS 커널을 완전히 우회하여 NIC에서 유저스페이스로 직접 데이터를 전달합니다. DPDK, AF_XDP 등의 기술을 활용하여 커널 오버헤드를 원천 제거합니다.

2. Zero-Copy Pipeline: 데이터가 처리 파이프라인을 통과하는 동안 단 한 번의 메모리 복사도 발생하지 않습니다. 메모리 매핑과 공유 버퍼 링을 통해 CPU 캐시 효율을 극대화합니다.

3. Lock-Free Architecture: 뮤텍스나 세마포어 없이 비차단 알고리즘(CAS, 링 버퍼)으로 동시성을 처리합니다. 락 경합으로 인한 비결정적 대기를 원천 차단합니다.

이 세 기술이 결합되면, 전처리 경로에 비결정적 요소가 존재하지 않게 됩니다. 결과적으로 입력이 들어온 순간부터 전처리 완료까지의 시간이 하드웨어 수준의 결정론적 상수로 수렴합니다.

이 글은 기술 블로그 시리즈의 첫 번째 글입니다. 후속 글에서 Kernel Bypass 네트워킹과 FPGA vs GPU 비교를 다룹니다.