Bashを使ってゼロから作ったMinecraftサーバー（2022）
(sdomi.pl)- Witchcraftは、BashだけでMinecraftサーバーをゼロから実装した実験的プロジェクトで、バイナリプロトコルやJoin Game、チャンク送信まで扱い、実際のクライアント接続を目指している
- Bashがヌルバイトを文字列内に保持できない制約は、バイナリを変数に入れず、
ddとxxdのパイプ内で処理する方法で回避している - 実装上の難点は、VarInt/VarLong、IEEE 754浮動小数点、Position、NBTといったMinecraft固有のデータ形式に集中しており、特にDouble変換は外部コマンド呼び出しのコストのため遅かった
- サーバーはServer List Ping、handshake、Join Game、Chunk Data And Update Lightパケットの順に拡張され、Dimension codecにはvanillaサーバーから取得したNBTバイナリblobを使用している
- フックベースのプラグインでワールド生成やエフェクトを変更できるが、マルチプレイ未完成、
/dev/shm/witchcraftベースのスレッド通信、遅いデータ交換、BusyBox 1.35.0依存といった課題が残っている
BashでバイナリMinecraftプロトコルを扱う
- 初期の試みは2009年のClassic protocolを対象にしていたが、Bashでバイナリデータを正しくパースするのが難しいという制約が先に明らかになった
- Bashの文字列は**ヌルバイト（0x00）**を無視し、ヌルバイトが発生したかどうかを検出する方法もないため、厳密なバイナリプロトコルではデータが破損する可能性がある
- 回避策は、バイナリデータをBash変数やコマンド置換に入れず、パイプ内に保持すること
dd count=$len bs=1 status=none | xxd -pで必要なバイト数を読み取り、hex文字列に変換する- hex文字列上でパターンマッチ、置換、データ抽出を行う
- 応答送信時は
xxdのreverseオプションで再びバイナリに戻す
- MinecraftのデフォルトTCPポートで接続を受けるために**
ncat**を使い、接続が来るとメインのシェルスクリプトmc.shを実行する
プロトコルデータ型の実装
- 最初に実装しやすい対象はServer List Pingパケット
- 必須パケットではないため、サーバーが正しく応答しなくてもゲーム接続自体は可能
- ただしdata typesのような中核的なプロトコル概念を学びやすい
-
VarIntとVarLong
- MinecraftのVarInt/VarLongは、MQTT経験者にはなじみがあるかもしれないLEB128の変種
- LEB128は、バイトを1つのシグナルビットと7つのデータビットに分けて整数長を格納する圧縮方式
- 最初のビットが0ならそのバイトが最後で、1なら次のバイトが続く
- Bashでreference implementationをそのまま移植するのは難しく、moduloとdivisionを使った独自エンコーダーを書いた
- デコーダーはAND演算と乗算を使い、reference方式に近い形で実装した
- LEB128そのものよりも、通常のint、long、signed shortと混在してプロトコルの各所に登場する点のほうが面倒だった
-
IEEE 754浮動小数点
- IEEE 754 Double変換は、実装で最も厄介な部分の一つだった
- 基本実装には負のべき乗を適用するループが必要だが、Bashは負のべき乗を標準ではサポートしない
- Perlは避け、
bcは使用環境やBusyBoxのバージョンではべき乗をサポートしていないように見えた awkは2**-1のような負のべき乗を処理できるため、変換実装に使った- 初期実装は、Player Moveパケットでクライアントが送る約50〜100個のパケットと、各パケットのX・Y・ZのDouble 3個を処理するのに数分かかるほど遅かった
- Bashの
forループ内で繰り返しawkを呼び出していた構造を、awk内部のループに移して外部コマンド呼び出し回数を減らした - その後、変換はXeon E5-2680v2で約10ms程度まで短縮された
- 以前のバージョンの約350msという数値は、確実な測定値ではない
-
Positionデータ型
- PositionはMojangが作った64-bit Longベースのデータ型
- Xは上位26ビット、Zは中間26ビット、Yは下位12ビットに格納される
- Bashには必要なbitshift演算子があるため、実装は簡単だった
- ただしこの型はあまり使われず、多くのパケットはX・Y・Z座標を別々のDouble値として格納する
- その結果、位置データはパケットあたり64ビットから192ビットに増える
- デフォルトのworld borderである30,000,000までの数値だけが必要だと仮定すると、9桁の浮動小数点精度が得られる
- 通常のサーバー通信はzlibを使い、ブロック内の位置表現には現実的に小数点以下2〜3桁以上は必要ないと考えられる
-
NBT
- NBTはMojangの内部形式で、バイナリデータ向けのJSONに似た形式
- JSONと同様、仕様外の任意データ保存にも使われる
- Mojangは例えば可変長bitstreamをLong配列として保存する
- 配列がLongまたはbyte境界に揃っていない場合、最後のLongは0でpaddingされる
- NBTパーサーはほぼ完成させたことがあったが、最後まで仕上げる価値はないと判断した
- そのコードは、プロジェクトディレクトリとして
tmpfsを多用していた最中にシステムクラッシュで失われた
接続可能なサーバーを作る
- Server Pingの次の段階は、実際のゲーム接続に必要なhandshakeと追加パケット処理だった
- クライアントがサーバーに入るには、handshakeを完了し、chunk、player position、inventory、join game関連パケットを受け取る必要がある
- 最大の障害は、Join GameパケットとChunkパケット内部のデータ構造だった
-
Join Game
- Join Gameパケットは初期メタデータを送信する
- 含まれる項目は、プレイヤーentity ID、gamemode、ワールド関連情報、Minecraft 1.16前後から入ったDimension codec
- Dimension codecはNBT Compoundなので実装負担が大きかった
- WitchcraftはこのNBTフィールドをvanillaサーバーから取得して使用している
- この部分は実装で唯一のバイナリblobであり、再実装は可能だが、カスタマイズする必要はないと判断した
-
Chunk Data And Update Light
- Chunk Data And Update Lightパケットは、最初は大きく複雑に見えるが、複数のBitSetフィールドを
0x00にし、Block Entityフィールドを送らなければ単純になる - 残るフィールドはX、Y、heightmaps、Dataフィールド
- heightmapsは
b000000010の繰り返しをより複雑にエンコードした形であり、実質的にはどんな値でもよいと見ている
- Chunk Data And Update Lightパケットは、最初は大きく複雑に見えるが、複数のBitSetフィールドを
Chunk Sectionとpalette処理
- DataフィールドはChunk Section配列
- Chunk Sectionは16×16×16ブロックで、複数のsectionを積み重ねて1つのChunkを作れる
- 実装を単純にするため、この配列は単一要素だけを使う
- Chunk Sectionはblock count、block states container、biome containerで構成される
- block statesとbiome containerはpalette構造を使う
- 実際のブロックデータの前に、サーバーがlocal block IDとglobal block IDのマッピングを定義する必要がある
- できるだけ多くのデータを小さな空間に収めるための構造
- ブロック定義は最小4ビットまで小さくできる
- Witchcraftは管理のしやすさのため、最小4ビットではなく8 bits per blockを使う
- 利用可能なpalette entryは256個になる
- 実際のchunkデータは、palette entryを指すhex数字を送ればよい
- 4ビットpaletteでも、hex文字列では1バイトが2ブロックを表せるため扱いやすいが、chunkあたり16ブロックに制限される
- 標準では4 bits per blockから9 bits per blockまでを許容し、それ以外は15 bits per blockのdirect palette mappingと見なす
- biome paletteは別方式で処理される
- 空のpaletteを送り、biome ID
0x01、つまりminecraft:plainsをchunk内のすべてのregionに直接マッピングする - vanillaの挙動をリバースエンジニアリングした結果に基づく
- 当該パケット部分の既存ドキュメントは不正確な可能性があると疑っている
- 空のpaletteを送り、biome ID
フックベースのプラグイン構造とデモ
- 基本実装だけでは平凡なchunkしか表示されないため、サーバーがchunk表示以上の動作をできることを示すデモが必要だった
- デモごとに別のソースツリーを作らないため、override可能な関数群をhooksと呼び、サーバーがユーザーコードをロードできるようにした
- この構造により、ワールド形状の変更から、
pkt_effectを接続してマウスを動かしたときにプレイヤーがticking noiseを出す動作まで実装できる - サンプルプラグインは、基本paletteからランダムなブロックを選んでchunkを生成する
hook_chunks()でchunk_headerを呼び出す- 4096個のブロックについて
RANDOM%30の値をhexで追加する - 生成したchunkを
$TEMP/world/0000000000000000に保存する - 周辺座標で
pkt_chunkを複数回呼び出し、chunkを送信する
- もう一つのデモであるdigmeoutは、スコアベースのシンプルなゲーム
- プレイヤーを、ランダムに配置された石と鉱石があるchunkに放り込む
- 制限時間が終わるまで、最も価値の高い鉱石を掘るという内容
Witchcraftの制約
- Bashは十進小数の処理が非常に苦手
- Integerはある程度処理できる
- 十進小数は、入力時に掛け算し、出力時に適切な位置に小数点を入れる方法で扱う必要がある
- このためWitchcraftが扱う数値の大半、またはすべてはint
- マルチプレイは正しく動作しない
- ある程度は動くが、完成させたり磨き込んだりする時間はかけていない
- Witchcraftは技術的にはmulti-threaded server
- その結果、スレッド間通信のために良くないhackが必要になる
- ほとんどのglobal dataは
/dev/shm/witchcraft配下に保存され、内部的には$TEMPとして参照される
- 性能は大きな制約として残っている
- 特に複数のthread間のデータ交換が遅い
- 大量のデータを送るのは難しく、solid chunk 16個を生成して送るのに最大1秒かかることがある
- 現在は最新のBusyBox 1.35.0がインストールされている場合のみ実行できる
- GNU coreutilsではテストしておらず、動作しないと予想している
1件のコメント
Hacker Newsのコメント
JavaとBedrock向けのスクリプト可能なMinecraftサーバーをたくさん触ってきた立場からすると、これはかなり印象的
文中で“duckduckgoing”を使っているのも加点ポイント
当時の議論: https://news.ycombinator.com/item?id=30347501 — コメント92件
負の指数は 2^(-n) = 1/(2^n) にすぎない
投稿者が自分の例として 2^-1 = 0.5 まで挙げておきながら、これに気づかず結局 awk に渡したのは意外だった
私のばかげた(?)ライブラリ ctypes.sh を使うべきだった: https://github.com/taviso/ctypes.sh
そうすれば Bash から libm や poll()、select() なんかにもアクセスできる :)
Frankensteinを蘇らせている感じ
Bash に別途インストールしたコンパイル済みの C コードまで必要なら、もう C や Python を要求してもいいわけで、「Bashで書いた」と呼ぶ理由は弱くなる。もちろん敬意を込めて言っているし、こういう「無駄な」プロジェクト自体は好き
ただ、このMinecraftプロジェクトも xxd のような外部ツールに依存しているので、この場合は ctypes.sh を使っても別に悪くないし、むしろ筋が通っている
ちなみに dd や xxd なしでも 純粋な Bash だけでバイナリを読み込み、保存し、操作し、計算し、出力できる。問題になるバイトはヌルだけだが、直接保存はできなくても、読んだ事実を検知して記録し、後で出力時に復元したり、数値として配列インデックスやバイトオフセットなどに使ったりできる
バイナリファイルをコピーする最小の例は
while LANG=C IFS= read -d '' -r -n 1 x ;do printf '%c' \"$x\" ;done bin2。ただ、これは cat なしで cat をしているようなものなので、有用性はあまり伝わらないもっと一般的で実用的な例は https://gist.github.com/bkw777/c1413d0e3de6c54524ddae890fe8d705 にある
LANG=C,IFS=,-d''を組み合わせると 0x00 を除くすべてのバイトにアクセスでき、read()の戻り値で「0x00 を読んだのか」「何も読めなかったのか」「入力が終わったのか」を区別できるwhile()全体のコマンドに<や>を使う必要もない。exec 3<>file_or_fifo_or_ttyで開いて、ループ内でread -u3やprintf >&3などを使えばいいシリアルポートから読む例は https://gist.github.com/bkw777/ddde771cc85fdd888c7ec74953193d66 にあり、実際に使ったコードは https://github.com/bkw777/pdd.sh にある。
tpdd_read,tpdd_write,file_to_fhex,str_to_shexを見れば、シリアルポートとローカルファイルを読み書きしながら、データをいろいろな方法で処理しているのが分かるこれらのループは外部プロセスどころかサブシェルですらない。ループ内で変数を操作しても元のコンテキストのまま。子プロセスがいないので、親シェルと呼ぶのも微妙なくらい
例では
read -n 1で1バイトずつ読んでいるが、必ずそうする必要はない。-n1なしで読むと、ループ1回ごとにヌル区切りの可能な限り多くのデータをまとめて扱えるので、メモリと反復回数を節約できる私の用途では、数値オフセット基準で個々のバイトやバイト範囲を切り出して操作する必要があり、データも今どきの基準では小さいので、16進数ペアの配列がとても便利。
a[n] == byte nとなり、表示可能文字・非表示文字・ヌルをすべて同じように扱えるし、printfで保存・再生成するだけでなく、0x$nや0x${a[n]}のように数値としてもそのまま使えるたとえば
h[]の2番目のバイトを後続ペイロード長として読み取り、${h[@]:2:0x${h[1]}}でそのペイロードを切り出せるこれぞ本物のハッカーサイト。すばらしい
Bash プログラミングはあまり得意じゃないけど、実際には思っているより強力で、そこまでひどくないのが驚き
Bash は vim や Lua と同じくらい好きなツールのひとつ
2MB にも満たない単一バイナリで、どこにでもあり、多くの人が思っているよりずっと多くのことができる
shellcheck と良い習慣を使えば、Bash も読みやすく安全にできる
さらに必要なら、複雑な FFI なしで C/C++ でユーティリティを足せばよく、pip/npm のようなもので正体不明の依存関係を大量に引っ張ってくる必要もない
CI や Dockerfile にインラインの Bash スクリプトが入っていることが多いので、それを全部別のスクリプトファイルに移すのも好き。これで CI に shellcheck がある以上、そのコードも検査される
開発者は「可読性が落ちる」と嫌がるけど、可読性が落ちるどころか、ずっと安全になる
次の問題は、同じ Bash スクリプトが複数のリポジトリの同じファイルにコピーされること。分散ビルド構成なんだけど、改善のアイデアがあれば歓迎
学生のころにもっと時間をかけておけばよかったと後悔している。キャリアを通じてずっとついて回った数少ないツールのひとつだから
商用ゲーム向けのカスタムサーバーを作ることって、今でもあるのかな
特に Java 版はかなり独特な立ち位置にあって、大規模な無料コンテンツアップデートを継続的に受けながら、過去のすべてのバージョンの実行を公式にサポートしていて、MOD コミュニティも非常に活発
Minecraft(Java) はゲームであると同時に、他の人たちがその上に積み上げる ゲームエンジン に近い
バグを直したり、言語を学んだり、内部がどう動いているのか見たくてやることになる
Minecraft は Quake 以降で最高のゲームのひとつ
こんなことが本当に起きたなんて、なんてこった
実装方法についての文章はたくさん読んできたけど、これは圧倒的。これまで読んだ奇妙なプロジェクト記事の中でも間違いなく最高レベルで、本当にすばらしい文章