TigerBeetle이 시작 이후에는 메모리를 할당하지 않는 이유와, 정적 메모리 할당이 예측 가능성·과부하 처리·성능에 어떤 이점을 주는지 설명합니다.
TIGER_STYLE.md(TigerBeetle 코딩 가이드)를 읽은 몇몇 분들은 TigerBeetle이 시작 이후에는 메모리를 전혀 할당하지 않는다는 사실에 놀랍니다.
일반적인 메모리 할당을 다시 짚어봅시다. 대부분의 언어에서는 프로그램 시작 시 고정 크기의 객체와 배열을 선택할 수 있습니다. 또는 프로그램이 실행되는 동안 객체와 배열의 크기를 바꿀 수도 있습니다. 예를 들어 객체에 새 키를 추가하거나, 더 많은 원소를 담기 위해 배열을 늘릴 수 있습니다.
예를 들어 JavaScript에서 빈 배열을 만들고 그 안에 항목을 push하면, 배열은 새 항목을 담기 위해 내부적으로 할당과 재할당을 할 수 있습니다. 이것이 동적 메모리 할당입니다.
또는 JavaScript에서 고정 크기로 배열을 초기화하고 그 크기를 절대 바꾸지 않을 수도 있습니다. 배열의 용량 안에 있는 인덱스에만 원소를 배치하는 것입니다. 이것이 정적 메모리 할당입니다.
TigerBeetle은 Zig로 작성되었습니다. 그리고 JavaScript처럼, 동적으로 메모리를 할당하는 자료구조(JavaScript의 배열과 비슷한 방식)를 사용할 수도 있고, 정적으로만 메모리를 할당하도록 선택할 수도 있습니다. TigerBeetle은 후자를 택합니다.
하지만 Zig 표준 라이브러리의 좋은 점 중 하나는 자료구조가 정적 할당에 친화적으로 설계되어 있다는 것입니다. 예를 들어 TigerBeetle은 Zig의 ArrayList와 HashMap을 사용하지만 크기는 고정합니다. ArrayList.addOneAssumeCapacity나 HashMap.putAssumeCapacityNoClobber 같은 메서드는 우리가 실수로 더 많은 메모리를 할당하려는 버그를 잡는 데 도움이 됩니다.
우리가 이렇게 하는 이유가 가비지 컬렉션과 대부분의 use-after-free 버그를 피하기 위해서라고 짐작할 수 있습니다. 그것도 좋은 이유이지만, 그 외에도 몇 가지가 더 있습니다!
정적 메모리 할당을 사용하면 과부하를 처리하기가 쉽습니다. 객체와 배열의 크기가 고정되어 있으므로, 잘못 설정된 클라이언트가 한 번에 너무 많은 연결을 만들거나 너무 많은 메시지를 보내려고 할 때 버퍼가 끝없이 커지지 않습니다.
이 덕분에 운영자 입장에서 TigerBeetle의 동작을 더 예측하기 쉬워집니다. 데이터베이스 안에 cgroups가 있는 것과 비슷합니다.
그리고 더 탐구할 가치가 있지만 충분히 풀어 설명하려면 각각 별도의 블로그 글이 필요한 관점도 몇 가지 있습니다:
기본적으로 TigerBeetle은 모든 것을 고정된 양으로 다룹니다:
필요한 총 메모리는 시작 시 약간의 덧셈과 곱셈만으로 간단히 계산됩니다. (현재는 시작 전, 즉 컴파일 시점에 이미 결정되지만, 메모리를 처음 할당할 수 있는 시점이라는 점에서 중요한 것은 시작 시점입니다.)
예를 들어, 여기에는 TigerBeetle의 합의 프로토콜을 위한 메시지를 저장하는 데 필요한 메모리 양을 계산하는 방식이 나와 있습니다(동시 상호작용과 프로토콜 순열의 모든 조합에 걸쳐서도 마찬가지입니다):
/// The number of full-sized messages allocated at initialization by the replica message pool.
/// There must be enough messages to ensure that the replica can always progress, to avoid deadlock.
pub const messages_max_replica = messages_max: {
var sum: usize = 0;
sum += config.io_depth_read + config.io_depth_write; // Journal I/O
sum += config.clients_max; // Replica.client_table
sum += 1; // Replica.loopback_queue
sum += config.pipeline_max; // Replica.pipeline
sum += 1; // Replica.commit_prepare
// Replica.do_view_change_from_all_replicas quorum:
// Replica.recovery_response_quorum is only used for recovery and does not increase the limit.
// All other quorums are bitsets.
sum += config.replicas_max;
sum += config.connections_max; // Connection.recv_message
sum += config.connections_max * config.connection_send_queue_max_replica; // Connection.send_queue
sum += 1; // Handle bursts (e.g. Connection.parse_message)
// Handle Replica.commit_op's reply:
// (This is separate from the burst +1 because they may occur concurrently).
sum += 1;
sum += 20; // TODO Our network simulator allows up to 20 messages for path_capacity_max.
break :messages_max sum;
};
/// The number of full-sized messages allocated at initialization by the client message pool.
pub const messages_max_client = messages_max: {
var sum: usize = 0;
sum += config.replicas_max; // Connection.recv_message
sum += config.replicas_max * config.connection_send_queue_max_client; // Connection.send_queue
sum += config.client_request_queue_max; // Client.request_queue
// Handle bursts (e.g. Connection.parse_message, or sending a ping when the send queue is full).
sum += 1;
sum += 20; // TODO Our network simulator allows up to 20 messages for path_capacity_max.
break :messages_max sum;
};
그리고 우리가 계산을 틀리면 어떻게 될까요? 정적 할당을 강제하기 때문에, 이런 계산은 단언문으로 검사할 수 있습니다(예를 들어 항상 사용 가능한 free message가 있는지 확인). 따라서 정적 할당 계산이 잘못되었다면, 프로덕션에서 제한 없이 결국 리소스 고갈(그리고 연쇄 장애!)로 드러나는 대신 fuzzing을 통해 더 일찍 발견할 수 있습니다. 단언문과 결합하면 정적 할당은 fuzzing의 효과를 크게 증폭시킵니다!
이것은 TigerBeetle에서 메모리가 할당되는 한 가지 예일 뿐입니다. 하지만 이 예와 마찬가지로 모든 할당은 시작 시에 단 한 번만 일어납니다. 간단한 계산과 함께 말이죠.
이런 방식이 가능했던 이유는 설계 단계에서 네트워크, 디스크, 메모리, CPU를 포함한 모든 리소스 사용량을 대략적인 계산으로 미리 스케치해 두었기 때문입니다.
하지만 “모든 것이 고정된 양”이라는 말이 여전히 모호하게 들릴 수 있습니다. 그래서 몇 가지 지점을 조금 더 자세히 살펴보겠습니다.
TigerBeetle은 동시에 최대 N개의 클라이언트 연결만 허용합니다. 이것이 제한적으로 들릴 수 있지만, MySQL이나 PostgreSQL과 다르지 않습니다. 동시에 N개를 초과하는 연결이 만들어지면 TigerBeetle은 연결을 끊습니다.
또한 TigerBeetle에는 정확히 두 가지 데이터 타입만 있습니다: accounts와 transfers입니다. accounts와 transfers는 고정 크기이며 캐시 라인에 정렬되어 있습니다. 두 타입 모두 128 bytes입니다(M1, 보고 있습니다!).
Cap’n Proto에서 영감을 받아, TigerBeetle에는 직렬화나 역직렬화가 없습니다. 클라이언트는 account 또는 transfer struct의 바이트를 그대로 wire를 통해 씁니다. TigerBeetle은 클라이언트로부터 메시지를 읽을 때 그 바이트를 다시 account 또는 transfer struct로 캐스팅합니다. Zero-copy입니다. 메시지에는 임의의 비트 뒤집힘을 감지하기 위한 체크섬이 포함됩니다. 그리고 추가 검증은 비즈니스 로직에서 수행됩니다.
클라이언트는 한 번에 하나의 메시지만 in flight 상태로 가질 수 있습니다. 각 메시지에는 최대 쿼리 수가 있습니다(기본 최대값은 메시지당 8191개 쿼리이며, 128 byte 헤더를 위한 공간을 남깁니다). 클라이언트는 다음 메시지를 보내기 전에 마지막 메시지에 대한 응답을 기다려야 합니다. 데이터베이스에 대한 이런 쿼리 배치는 정적 메모리 할당과 더불어 높은 처리량과 bounded latency를 의미합니다.
이제 감이 오실 겁니다. 연결 수, 고정 크기 메시지 등이 최대값으로 정해져 있으면 메모리를 정적으로 할당하는 것은 쉽습니다.
여전히 저장소 문제는 남아 있습니다. TigerBeetle에 transfer와 account를 추가할수록 사용 메모리가 증가하는 것 아닌가요?
사실 정적 할당은 메모리에 있는 것에 관한 이야기입니다. TigerBeetle은 데이터베이스이므로 장기 저장소는 메모리가 아닙니다. 데이터베이스의 동적인 부분은 디스크에 저장되는 부분입니다.
TigerBeetle은 저장소를 위해 자체 LSM tree 시스템을 구현합니다(실제로는 흥미로운 최적화를 위해 약 30개의 트리를 LSM forest로 통합합니다). 그리고 모든 LSM tree와 마찬가지로 메모리 안에 있는 부분과 디스크에 있는 부분이 있습니다. 메모리 안의 부분은 예상하셨겠지만 시작 시에 할당됩니다. 그리고 작고 점진적인 flush를 디스크로 수행하여 메모리 내 부분을 완벽하게 제한된 상태로 유지합니다.
세부 사항은 더 복잡해지지만, 정적 메모리 할당에 관한 규칙은 바뀌지 않습니다.
메모리를 한 번만, 그것도 미리 할당하는 시스템을 구축하려면 미리 생각하는 작업이 필요합니다. 많은 개발자(저를 포함해서)에게 이것은 큰 사고방식의 전환입니다. 하지만 우리가 발견한 바는 이렇습니다. 필요한 메모리에 대해 몇 주만 깊이 생각해 두면, 시간이 지날수록 엄청난 보상을 얻게 됩니다.
장난감 데이터베이스를 만드는 것을 좋아한다면, 다음 프로젝트에서는 메모리를 정적으로 할당해 보세요! 그리고 TigerBeetle에서 이것이 실제로 어떻게 동작하는지 보고 싶다면 데이터베이스를 다운로드해 보세요(참고: 아직 프로덕션 전 단계입니다!). 그리고 직접 사용해 보시기 바랍니다!