TigerBeetle의 ‘정적 할당(시작 후 무할당)’ 접근을 컴파일러에 적용할 수 있는지, 입력/출력을 스트림으로 보고 중간 처리 메모리를 O(1)로 제한하는 아이디어를 탐색한다.
URL: https://matklad.github.io/2025/12/23/static-allocation-compilers.html
Title: Static Allocation For Compilers
2025년 12월 23일
TigerBeetle은 유명하게도 “정적 할당(static allocation)”을 사용합니다. 또 악명 높게도, 여기서 말하는 용어 사용은 다소 독특합니다. 의미하는 바는 임베디드 개발에서 흔히 보는 static 배열이 아니라, 더 약한 형태의 “시작 이후에는 할당이 없다(no allocation after startup)”는 방식입니다. TigerBeetle 프로세스가 사용하는 메모리 양은 ELF 바이너리에 하드코딩되어 있지 않습니다. 런타임의 커맨드라인 인자에 따라 달라집니다. 하지만 모든 할당은 시작 시점에만 일어나며, 해제는 없습니다. 오래 사는 이벤트 루프는 alloc 없이도 즐겁게 빙글빙글 돕니다.
수년 동안 비슷한 기법을 컴파일러에도 적용할 수 있을지 궁금했습니다. 불가능해 보였는데, 오늘은 이 아이디어에서 뭔가 실행 가능한 것을 뽑아낼 수 있지 않을까 싶습니다?
정적 할당은 근본 문제의 ‘물리학’에 달려 있습니다. 그리고 분산 데이터베이스는(적어도 TigerBeetle의 경우) 놀랍도록 단순한 물리학을 가집니다.
시스템의 유일한 입력과 출력은 메시지입니다. 각 메시지는 크기가 유한합니다(1MiB). 시스템의 실제 데이터는 디스크에 저장되며 임의로 커질 수 있습니다. 하지만 단일 메시지가 적용하는 변경(diff)은 유한합니다. 그리고 입력이 유한하고, 출력이 유한하다면, 추가 메모리 할당이 필요해지기란 사실 꽤 어렵습니다!
이 점은 강조할 가치가 있습니다. 정적 할당을 한다는 것은 힘들고, 끊임없이 경계하며, 리소스를 수작업으로 계산해야 하는 일처럼 보일 수 있습니다. 실제로 제가 배운 바는, 이것이 의외로 조합적(compositional)이라는 점입니다. 시스템의 입력과 출력이 유한하기만 하면, 무할당 처리는 쉽습니다. 그리고 그런 시스템 두 개를 큰 어려움 없이 결합할 수도 있습니다. routing.zig는 이런 식의 고립된 서브시스템의 좋은 예입니다.
여기서 유일한 문제는 동시에 도착할 수 있는 메시지의 개수에 물리적 한계가 없다는 점입니다. 당연히 임의의 개수의 메시지를 동시에 처리할 수는 없습니다. 하지만 신뢰할 수 없는 네트워크 위의 분산 시스템이라는 맥락에서, 필요한 처리 리소스가 없으면 메시지를 바닥에 버리는(drop) 것이 안전한 선택이 됩니다.
직관과는 다르게, 해낼 수만 있다면 할당하지 않는 쪽이 할당하는 것보다 더 단순합니다!
아쉽게도 컴파일러에서는 해내기 불가능해 보입니다. “가장 큰 프로그램도 함수가 최대 백만 개일 거야” 같은 말을 할 수는 있겠지만, 그건 메모리 낭비와 나쁜 사용자 경험으로 이어질 겁니다. 또는 제가 Hard Mode Rust에서 했던 것처럼, 고정 크기의 단일 ‘요로(yolo) 아레나’를 쓸 수도 있습니다. 하지만 그건 “정적 할당”과 전혀 비슷하지 않습니다. 아레나에서는 크기를 명시적으로 고정하지만 OOM이 날 수 있습니다. 정적 할당에서는 그 반대입니다. OOM은 없지만, 시작이 끝날 때까지 얼마나 많은 메모리가 필요할지 알 수 없습니다!
컴파일러의 “문제 크기”는 고정되어 있지 않습니다. 입력(소스 코드)과 출력(실행 파일) 모두 임의로 커질 수 있습니다. 하지만 이것은 TigerBeetle도 _마찬가지_입니다. 데이터베이스의 크기는 고정되지 않습니다. 다만 TigerBeetle은 그걸 RAM이 아니라 디스크에 저장하는 ‘치트’를 쓸 수 있습니다. 그리고 TigerBeetle은 디스크에 대해서는 “정적 할당”을 하지 않습니다. 런타임에 ENOSPACE로 실패할 수 있으며, 더 이상 관련 없는 섹터를 재사용하여 가능한 한 오래 버티기 위해 동적 블록 할당기를 포함하고 있습니다.
그러니 이렇게 말할 수 있습니다. 컴파일러는 임의로 큰 입력을 소비하고, 임의로 큰 출력을 생산하지만, 정적 메모리 할당의 관점에서는 그 둘은 “세지 않는다”고요. 시작할 때, 컴파일러 작업의 완성된 불변 결과를 저장할 “출력 아레나(output arena)”를 따로 마련합니다. 그리고 이 출력은, 엄격히 유한한 크기의 청크(chunk) 시퀀스를 처리한 뒤에 누적된다고 가정합니다. 코드베이스의 총 크기를 제한하는 것은 비합리적이지만, 단일 파일을 예컨대 4MiB로 제한하는 것(런타임에서 덮어쓰기 가능)은 괜찮습니다. 그러면 컴파일은 본질적으로 “스트림 처리(stream processing)” 문제가 됩니다. 입력과 출력은 임의로 크지만, 필터 프로그램 자체는 O(1) 메모리에서 실행되어야 합니다.
이 설정에서는 “출력 데이터”에 대해 포인터 대신 인덱스를 사용하는 것이 자연스럽고, 그러면 변경 사이에 이를 디스크에 쉽게 지속(persist)할 수 있습니다. 또한 “변경 청크”를 공간적으로(컴파일러가 새 파일을 본다)만이 아니라, 시간적으로도(컴파일러가 기존 파일의 새 버전을 본다) 생각하는 것이 자연스럽습니다.
실용적인 이점이 있을까요? 모르겠습니다! 하지만 가지고 놀아볼 가치는 있어 보입니다! O(N)인 컴파일러 출력과 O(1)인 중간 처리 산출물을 엄격히 분리하면 컴파일러 아키텍처를 명확히 하는 데 도움이 될 것 같고, 데이터베이스에서 그렇듯 컴파일러에서도 O(1) 처리가 더 단순한 코드로 이어지더라도 그리 놀라지 않을 것 같습니다.
