ハクソク

世界を動かす技術を、日本語で。

Zigによる静的メモリ割り当て

108日前原文(nickmonad.blog)

概要

  • ZigでのRedis互換キーバリューサーバ「kv」開発記録
  • 静的メモリ割り当てによる安定性・保守性向上の実践
  • 接続管理・コマンド解析・ストレージ各段階の設計詳細
  • 設定によるリソース上限の明確化とトレードオフ
  • Zigのメモリアロケータ設計活用例

Zigによる静的メモリ割り当て型キーバリューサーバ設計

  • ZigでRedis互換の小型キーバリューサーバ「kv」開発
  • 目標は本番運用可能な最小限コマンド実装
  • TigerBeetleや「TigerStyle」ガイドラインに影響を受けた設計思想
  • 初期化時に全メモリ確保、実行中の動的割り当て・解放禁止
  • パフォーマンスの予測可能性・安定性、設計の単純化・保守性向上

静的メモリ割り当ての課題と利点

  • システム設計時に「どれだけメモリを確保するか」を明確化
    • 最大接続数・各接続のバッファサイズ・想定データ量などを事前設定
  • 設計時に全リソース要求量を洗い出すことで、プログラム理解が深まる
  • Zigは明示的なメモリアロケーションと多様なAllocatorインターフェースで設計容易

接続管理

  • Connection構造体で、各クライアントとの通信情報を保持
  • io_uring対応のため、リクエストライフサイクル中に必要な情報を管理
  • 初期化時に以下の3つのプールを確保
    • Connection構造体用
    • 受信バッファ用（recv_buffer）
    • 送信バッファ用（send_buffer）
  • 各プールはstd.heap.MemoryPoolやカスタムByteArrayPoolで実装
  • ランタイムではプールから切り出し・解放するだけで動的確保不要
  • 最大接続数・各接続のバッファサイズはConfig構造体で設定
  • プール枯渇時はリクエスト拒否、サーバの安定性・予測性向上
  • 設定例：1000接続程度が現実的、用途に応じて調整可能

コマンド解析

  • Redis互換のため、RESPフォーマットのコマンド解析を実装
  • 受信バッファをイテレータで走査し、CRLF区切りで分割
  • parse関数でバッファを解析し、コマンド内容を抽出
  • 解析時の一時的なメモリ管理にFixedBufferAllocatorを活用
    • 初期化時にバッファ確保、リクエスト毎にresetで再利用
    • シングルスレッド処理なら一つのAllocatorを使い回し可能
  • 最大コマンド長・最大レスポンス長を考慮してバッファサイズを設定
  • 解析時は「ゼロコピー」方式で効率化、必要最小限のコピーのみ
  • コマンド実行後、レスポンスデータはsend_bufferへコピー

キーバリューストレージ

  • 基本構造はハッシュマップ（std.StringHashMapUnmanaged）
  • Zigの「unmanaged」バージョンを利用し、初期化時に容量確保
  • 実行時はputAssumeCapacityで追加、追加時の動的確保不要
  • 初期化時に容量不足時はエラーで即停止、実行時の予期せぬOutOfMemoryを回避
  • 最大キー数・最大バリューサイズ等もConfigで事前設定

設計・運用上のトレードオフ

  • 静的割り当ては柔軟性に欠けるが、堅牢性・保守性向上
  • 設計段階でリソース上限を明確化することで、システム全体の安定運用
  • ZigのAllocator設計や型安全性が、このような設計に非常に適している
  • 本実装は学習目的であり、さらなる最適化や設計改善の余地あり

これらの設計思想・実装例は、Zigやシステムプログラミングの学習や堅牢なサーバ設計に役立つ知見と言える。

Hackerたちの意見

> すべてのメモリは起動時に静的に割り当てられなければなりません。初期化後に動的にメモリを割り当てたり（解放して再割り当てすることも含めて）、することはできません。これにより、パフォーマンスに大きく影響を与える予測不可能な動作を避けられ、使用後解放（use-after-free）も防げます。さらに言えば、これにより、すべての可能なメモリ使用パターンを設計の一部として事前に考慮した設計と比べて、より効率的でシンプルな設計が実現でき、パフォーマンスも向上し、メンテナンスや理解がしやすくなるという経験があります。 > タイガースタイル 30年以上業界で知られている技術が「タイガースタイル」とか、こういうグル的なものに再パッケージされるのは本当に不思議だよね。
└
そうだね。埋め込みコードを書く仕事をしている私たちは、これを「コードを書く」と呼んでるよ。
└
知られてはいるけど、埋め込みプログラミング以外ではあまり使われていないね。データベースを書くときに必要ないのにこれを使っているのを見ると、みんな注目しちゃうよね。じゃあ、なんで彼らはこの意識的な選択をしたんだろう？人を小さく見せたくなる気持ちもわかるけど、ここでは必要ないと思う。TigerBeetleは素晴らしいものを作り上げたと思うし、彼らのプログラミングへのアプローチがそれを生み出したんだと思う。
└
これは、タイガービートルのスタイルに関するドキュメントの一部みたいだね。いわゆる「Googleスタイルガイド」のコード版と似たような感じ。これらは新しいことが書かれていることは少ないけど、特定のプロジェクトや組織がコードスタイルに関してどうしているかを文書化しているんだ。
└
静的アロケーションは昔からあるけど、意味がある場面でも考慮されることは少ないよね。純粋な静的アロケーションを使ったデータベースエンジンをいくつか設計したことがあるけど、開発者はこのモデルに対して不満を持つことが多い。アロケーションを委譲する方が簡単に見えるからだけど、実際には複雑さを隠してるだけなんだよね。アロケーションを除けば、多くの最適化はソフトウェアが瞬時のリソース制限にどれだけ近いかを正確に把握することが必要だから、パフォーマンスエンジニアリングの一般的な良いプラクティスだよ。ほとんどの人はやってないけど（ほとんどのオープンソース実装を見てみて）、これを推進することは悪くないと思う。
└
こういう皮肉で見下したようなコメントは誰の役にも立たないし、極端な場合には全体のグループを悪いイメージでステレオタイプ化することもあるよね。もっと建設的な現実は、ゲームや組み込みシステムのような特定の業界で一般的な技術が、なぜもっと広く採用されるのが難しいのかを議論することだと思う。そして、多くの文脈で良いアイデアが今広がっていることを祝うこと！また、他の業界が見逃しているかもしれないアイデアを共有すること（そして、なぜそれが存在しないのかを批判的に問いかけること）も大事だよね。アイデアは広がるためにマーケティングが必要だから、ポジティブな意味でのマーケティングってそういうことだし（ネガティブな場合は色々とドロドロしてるけど！）。もし企業が使っているコーディングスタンダードがこのアイデアが生き延びて成長するためのマーケティングなら、全然アリだよね、「タイガースタイル」で行こう！人間ってそんなもんだよ。
└
> 「業界で30年以上知られている技術の一つが、次世代との知識共有だ。まず、どこでそれを見つけるかなんてわからない。どの本？どの先生？本がたくさんありすぎて、全部読む必要があるの？もし同僚がそれを知らなかったら、どうやって共有するの？それに、昔からの言い伝えがあるけど、得意なことは決して無料でやるなって。これは正確にはトレードシークレットではないけど、どれだけの人が自分の知っている高度な技術やトリックについてブログを書いている？私はLuaのクロージャから本物のC関数ポインタを作る方法についてブログを書いたけど、それは自分の製品を宣伝するためのもので、実際にはトレードシークレットとして隠しておくべきだったかもしれない（そのブログ記事からは0件の売上しかなかったし）。誰が個人的な利益もなく「虎スタイル」の知識を新しい世代と共有したがるの？秘密裏に使ったり、本に書いたり、広告のためにブログに書いたりするインセンティブがあるんじゃないの？」
└
もっと文脈を加えると、TigerStyleは単なる静的割り当て以上のもので、実際に以前の作業に明示的に言及しているんだ。> 「NASAのPower of Ten — Safety Critical Codeを開発するためのルールは、あなたのコーディングの仕方を永遠に変えるだろう。」詳しく言うと：* https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI... * https://spinroot.com/gerard/pdf/P10.pdf
└
> すべてのメモリは起動時に静的に割り当てられなければならない。初期化後に動的にメモリを割り当てたり、解放したり再割り当てしたりすることはできない... 業界で30年以上知られている技術が再パッケージされているのは驚きだね。これがGPUシェーダープログラミングの仕組みでもある。ヒープ割り当てや一般的なポインタに相当するものはなく、できるだけローカルメモリや事前に割り当てられた共有バッファを使って作業することが求められる。だから、この技術は今でもかなり関連性があると思うよ。かなり長い歴史があるけどね。
└
今のシステムがほとんどすべて動的に割り当てている中で、特に関連性が高いと思う。中には各オブジェクトがそれぞれ独自のランタイム割り当てになっているものもあって、Javaなんかがその代表だね。一見すると素晴らしいけど、無限のスケールと完璧に一般的な感じがする。システムは何でも扱える。でも、すべてを扱う必要があるのかな？そして、すべての可能なシナリオを扱うことの複雑さのコストはどうなるの？
Tigerbeetleの開発者による関連の最近の投稿: https://matklad.github.io/2025/12/23/static-allocation-compi...
今、Redisの代わりにNATSでまさにこのパターンをやってるよ。似たような戦略を取っている人がいるのを見るのは面白いね。Zigのエコシステムが標準ライブラリのパターンに従ってアロケータインターフェースを渡すことで、イディオマティックなコードを書くのがめっちゃ簡単になるし、呼び出し元でアロケーション戦略を決められるのがいいよね。もちろん、他の言語でも何十年も前からやられてきたけど、このパターンに従いながらlibcのような既存のエコシステムを活用するのは簡単じゃないし、呼び出される側は通常、使われているアロケーション戦略について何かを知っておく必要がある（その戦略に従わない標準関数を避けるためだけでも）。
└
この（概念実証）コードベースには、Zigであってもアロケーション戦略についての知識が必要なケースがいくつかあるけど、それは自分の設計の問題だね。投稿で触れたかったのは、システムのコンポーネントがどんなアロケーション戦略でも動くようにしようとする試みについて。最近のZigプロジェクトでは、`gpa: std.mem.Allocator`や`arena: std.mem.Allocator`みたいなのが意図を示すために使われてるのをよく見るけど、アロケータのインターフェースは一般的なんだよね。
個人的には、静的割り当てが理論計算機科学にとってかなり大きな影響を持つと思ってる。実際に論理的に考えられる唯一のプログラムの種類だからね。それに、古典的な意味でのチューリング完全ではないし。私の小さな有限主義者の心が温かくてふわふわするよ。
└
あなたが言いたいのは「まさにチューリング完全ではない」ってことじゃない？
└
自分は学者じゃないけど、あのByteArrayのリンクリストを見ると、これは「静的アロケーション」ってよりも「サイト特化型アロケータを再実装した」って感じがする。あと、LwIPを思い出させるんだよね。事前にアロケートされたバッファ構造が枯渇すると、デバッグがめちゃくちゃ大変だったから。
└
> 「実際に論理的に考えられる唯一の種類のプログラムだよ。理論的には無限のメモリがあっても、チューリング完全なプログラムについて考えるのにはあまり関係ない。実際には、どんなプログラムが停止するかを保証できないという問題は、興味深いおもちゃとしての役割を超えるメモリを持つシステムにも当てはまる。つまり、これは自明だと思うけど、私たちのコンピュータはすでに有限のメモリを持っている。プログラムに少しだけ少ないメモリを与えたところで、何も変わらない。結局、1980年代のコンピュータが持っていたメモリよりも、静的に割り当てられたプログラムにもっと多くのメモリを与えている可能性が高いし、1980年代のコンピュータの制限が私たちをプログラムについて考えるのが上手くさせたわけでもない。」
└
> 「実際に論理的に考えられる唯一の種類のプログラムだよ。どういう意味？動的割り当てを使った形式的な推論ツールはたくさんあるよ、例えばLeanとか。」
└
> 実際に理論的に考えられる唯一のプログラムの種類だ。いや、それは停止問題から理論的に逃れることを可能にする制約の一つだけど、唯一ではないよ。例えば、完全な関数型プログラミング言語は再帰を弱い形に制限することでそれを実現している。また、一般的に言えば、完全にチューリング完全な言語やスタイルで書かれた多くのプログラムについても考えることができる。人々は停止問題を誤解していて、どんなプログラムでも終了分析を成功させることができないと言っているけど、実際には動的割り当てを行うプログラムを含め、多くの実用的なプログラムでそれが可能なんだ。逆に、静的に制約されたメモリしか使わないプログラムもあって、その分析は完全に手の届かないところにある。例えば、最初の2^1000の整数に対してコラッツ予想をチェックするプログラムは、約1ページのメモリしか必要としない。
仕事でサービスを使って、これのもっとラフなバージョンをやってるよ。大きなバッファやキャッシュは静的（ランタイムで設定）サイズだけど、内部のデータ構造は大体最小限のものと仮定して、標準のアロケータを使ってアイテムを追加できるから、心配しなくていいんだ。
何か見落としてるかもしれないけど、2つの考えがある：1. オーバーコミット機能って、これのメリットを減らさない？最初のアロケーションはうまくいくけど、実行時にメモリが足りなくなる可能性があるよね。2. KVストアの場合、静的にアロケートしたメモリがどれが使われているかを把握しないと、アプリケーションレベルの使い回しバグのリスクがあるよね？
└
ここで作者です！オーバーコミットは確かに注意が必要だね。TigerBeetleのドキュメントでも触れられてると思う。Linuxでは明示的に無効にしないといけないと思うよ。2つ目の質問については、はい、何が使われているかを把握する必要があるね。キーと値は、利用可能なものを管理するためにフリリストを使ったメモリプールからアロケートされるんだ。キー/値ペアを追加するリクエストが来たら、まずキーのプールと値のプールの両方にスペース（つまり、利用可能なバッファ）があるかをチェックする。これらが「予約済み」とマークされると、フリリストはそのことを忘れちゃうんだ、バッファがプールに戻されるまで。これが役に立てばいいな！
└
オーバーコミットを回避するには、アロケーション時にすべてのアロケートされたページに1バイト書き込むことで、実際にアロケートされるようにすることができるよ。
このプロジェクトに偶然にも関連するのが、私のゼロアロケーションRedisクライアントなんだ。もしkvがRESPv3をサポートしていれば、問題なく動くはずだよ :^) https://github.com/kristoff-it/zig-okredis
└
いいね！絶対に見てみるよ :)
TigerBeetleについて理解しておくべき重要なことは、ファイルシステムをバックにしたデータベースだってこと。静的割り当ては、一度にメモリ内のリソースの数（接続数や単一のクエリから返されるレコード数など）を制限することを意味してる。これらのことは実際には制限されている（MySQLやPostgresは同時接続数に制限があるし、アプリケーションはページネーションを実装すべきだ）。これらの制限を事前に考えて指定するのは、操作がタイムアウトしたりOOMになるよりも良い。一方で、TigerBeetleはデータベースに保存できるデータの量に制限を課していない。=> https://tigerbeetle.com/blog/2022-10-12-a-database-without-d... O(N)メモリを使うのは、必要ないなら常に悪いことだ。ファイルシステムをバックにしたデータベースなら、そんなことはない。（静的割り当てを使っているかどうかに関わらず。私はRubyのウェブアプリに取り組んでいて、N件のレコードを一度にメモリに読み込むのは避けて、固定サイズのバッチを使っている。）事前に割り当てを行うのは、これらの制限について考えたことを確認するためのとても良い方法で、ミスを避け、割り当てのランタイムコストを回避することができる。これは、OPの状況とはまったく異なり、彼らはインメモリデータベースを実装している。つまり、1) 保存するkvペアの数に制限を課さなければならず、2) スタートアップ時にすべてのkvペアのコストを支払っている。これは、保存するkvペアの数に固定の上限があるとわかっている場合にのみ許容される。
└
なるほど。例えば、あなたのRedisインスタンスは固定RAMを持っているから、起動時にあらかじめ割り当ててフラグメンテーションを避けるのがいいかも。Memcachedも似たような感じ（固定サイズのスラブ）だけど、あらかじめ割り当てはされていない。もし複数のサービス（ウェブ、データベース、キャッシュなど）とハードウェアを共有しているなら、これが狙っているパフォーマンスは優先事項ではないかもね。
└
そうだね、いいポイントだ！ちょっとした指摘だけど、TigerBeetleは「ファイルシステム」バックのデータベースじゃなくて、意図的に単一の「ファイル」に制限していて、ファイルシステムを介さずに生のブロックデバイスやパーティションで動作できるんだ。
これ、ゲームにもよく合うよ。私はFixedBufferAllocatorを使って、アセット以外のすべてを事前に割り当ててる（システムやエンティティなど）。Tigerstyleは効率的でデバッグ可能なソフトウェアの良い出発点だね。記事ありがとう！