kawasin73のブログ

技術記事とかいろんなことをかくブログです

高速な XBRL パーサーを Python で書く

必要なことを必要なだけ。どうも、かわしんです。

前回の記事では、AI を使って作ってきた日本の上場株式銘柄解析システムのアーキテクチャについて解説しました。

kawasin73.hatenablog.com

今回は、銘柄解析の肝となる XBRL パーサーである Arelle が遅かったので、Python で自前の高速なパーサーである xbrlp を作って 20 倍速くした話をします。

9 月上旬当時の Claude Code, Codex にはまともな効率の良いプログラムを書くことができなかったのでこのパーサーのコアの部分は自分で書いています。

ソースコードは単一の Github リポジトリにはなっていないので、gist にあげておきました。この記事の一番下に埋め込んでいます。

XBRL parser · GitHub

こんな感じで使います。

gist.github.com

XBRL とは

XBRL とは、決算報告や財務諸表をプログラムで解析しやすく設計された XML ベースのフォーマットです。日本では、上場企業は金融庁が管理する EDINET に有価証券報告書をアップロードすることが義務付けられており、EDINET の閲覧サイト では無料で過去 10 年分のアップロードされた XBRL ファイルをダウンロードすることができますし、pdf ファイルなどでの閲覧もできます。また、無料の API 登録をすることで API 経由で過去の XBRL ファイルをダウンロードすることもできます。

また、四半期の決算発表で公表される決算短信XBRL ファイルも東証にアップロードされ、TDNet の適時開示情報閲覧サービス で無料でダウンロードできます。TDNet の API は有料ですが、日次の一覧も銘柄ごとの一覧も Web ベースのシステムで無料で閲覧し XBRL ファイルをダウンロードすることができます。邪推ですが、おそらく TDNet の無料の閲覧システムはリアルタイム性や信頼性への保証がないから有料版の API と差別化されているのだと思います。多分。

なぜ XBRL をパースするのか

上場企業の財務諸表を手に入れたいのであれば、yfinance を使うのが無料で使えるメジャーな手法だと思います。しかし、ネットネットバリュー株投資をする上ではいかに詳細な資産の項目を取るかが重要なので、1 次情報である XBRL ファイルを直接パースして柔軟にデータの抽出を行うことにしました。

例えば、7058 共栄セキュリティーサービス は、固定資産として「金地金」を 10 億円分保有していますが、yfinance では一般的な企業を前提にして正規化しているため、金地金のデータは無視されています。

とはいえ、yfinance は十分精度高くデータの抽出と正規化をしているので、一般的な解析をするには yfinance のデータで十分だと思います。

なぜ自前の XBRL パーサーを書くのか

PythonXBRL パーサーとしては、Arelle が有名です。初めは Arelle を使ってデータの抽出を行っていましたがとても遅いです。

このツイートにもありますが、有価証券報告書をひとつパースし終わるまでに 5 秒くらいかかります。4000 銘柄が毎年 4 回四半期と通期の決算を報告するので 1 年分だけで 16000 ファイルありますし、マルチプロセスで並列に動かしても1年分を全てパースするのに一晩かかります。それを 10 年分パースして EDINET と TDNet それぞれでパースすると考えると全てパースするのに1週間くらいかかってしまいます。データ抽出ロジックを都度改良する度にその変更をデータベースに反映するのに 1 週間かかるのは流石にしんどいので最適化を考えました。

Claude Code に Arelle のパース中のプロファイルを取らせてなぜ遅いのか調査させると、メタデータの構築とそのバリデーションに CPU 時間を食われているということでした。しかし、自分のデータ抽出にはバリデーションは不要ですし、利用するメタデータも一部のみです。例えば、データを抽出する時は QName のみを使って要素を判別するので日本語や英語のラベルは必要ありません。また、要素同士の関係性を表すリンクベースには、calculationLinkbaseRefdefinitionLinkbaseRefpresentationLinkbaseRef などがありますが、実際に利用するのは 1 つのみで、他のリンクベースは必要ないです。

Arelle はあらゆるユースケースに対応するために最初の読み込み時に全てのデータを読んでモデル構築をするので、自分のデータ抽出に必要ないデータ読み込みをスキップすることで高速化ができそうですが、Arelle にはそういう最適化が可能な API がないため、自分で 1 から XBRL パーサーを書くことにしました。

最初は Rust で書いて Python バインディングを提供しようとしていましたが、インストールが煩雑になってしまうし、XML パーサーが Rust の標準ライブラリになかったため、Python で書くことにしました。Arelle の遅さが言語由来ではなく無駄な処理が多いためだったというのも理由です。

どうやって速くするのか

大きく 2 つの処理をスキップすることで速くします。すでにパースされたメタデータファイルの読み込みのスキップと不要なリンクベースファイルの読み込みのスキップです。

XBRL は数値データが埋め込まれた HTML である本文の -ixbrl.htm ファイルとメタデータ構造を定義する複数の XML ファイルで構成されます。メタデータファイルにも、要素同士の関係を表すリンクベースファイル (_cal.xml, _def.xml, _pre.xml, _lab.xml) や、どのようなメタデータファイルがあるかをリストして、本文に含まれうる要素を列挙するスキーマファイル (.xsd) ファイルがあります。スキーマファイルは import タグによって複数のスキーマファイルを再帰的に読み込むこともできます。

共通したスキーマファイルのキャッシュ

メタデータファイルには会社ごとの XBRL ファイル群に含まれるローカルのファイルと、EDINET などがリモートサーバーから HTTP 経由で提供するファイルがあります。リモートのスキーマファイルのパース結果は同じになるため会社ごとにパースする必要はありません。リモートのスキーマファイルのパース結果をメモリ上にキャッシュすることで、複数の XBRL ファイルをバッチでパースする時に重複するパース処理をスキップすることができます。

また、リモートのファイルはローカルのファイルシステムにダウンロードしてキャッシュし不要なネットワークアクセスを防ぐようにしました。一度読み込みを行った XBRL ファイルについては再読み込み時にはネットワークアクセスが発生しません。

必要なデータのみの読み込み

Parser クラスは必要なデータのみを読み込むメソッドを明示的に提供し、ユースケースごとに不要になるデータの読み込みをユーザーが防ぐことができるようにします。

  • load_facts(): 本文中の <ix:nonNumeric>, <ix:nonFraction> タグに埋め込まれたデータを読み込んで返します。
  • load_presentation_links(): 表示上の親子関係を表すリンクベースを返します。
  • load_calculation_links(): 計算上の親子関係を表すリンクベースを返します。
  • load_labels(): 全要素のラベルを返します。

データの抽出のみを行うときは load_calculation_links()load_facts() を使い、不要なラベルや _pre.xml の読み込みコストをスキップできるようにします。

ソフトウェアの品質へのこだわり

Zero Dependency

僕は Zero Dependency 過激派なので、自分が作るライブラリでは依存する third party ライブラリを最小限にします。依存するライブラリが増えれば増えるほどソフトウェアの品質を落とします。Python には XML パーサーが標準ライブラリにあるので僕のパーサーは全て標準ライブラリのみで作っています。外部ライブラリをインストールしなくても使えるので、ポータビリティが高くなります。

メモリ効率の最適化

僕はいつも メモリアロケーションに対する罪悪感 を持っているのでメモリの使い方には気を使います。

データやリンクベースの読み込み API では、結果をリストではなくイテレータで返します。要素数やリンク数はかなり大量になるため、リストにまとめてから返すと一時的なメモリ消費量が大きくなってしまいます。イテレータにすることで一時的なメモリ使用量のスパイクを抑えることができます。また、必要なデータが途中までで全て読み込めた場合は読み込みを途中で中断することもできます。

文字列の結合は、毎回メモリアロケーションと文字列のコピーが発生するためなるべく最小限にします。Python の標準ライブラリの XML パーサーではタグ名などをネームスペースを解決した状態で出力します。例えば、ix:nonFraction{http://www.xbrl.org/2008/inlineXBRL}nonFraction と出力されます。ネームスペースのマッピングを管理してタグを比較することが必要なのですが、要素ごとに ix:nonFraction のタグを URI 埋め込みのものに変換するのは文字列結合のコストがかかり無駄なので、タグ名変換の文字列結合はネームスペースが検出された時にまとめて行いキャッシュして使い回すようにします。

本当はファイルからバッファに読み込まれた XML をゼロコピーでパースするのが理想ですが、標準ライブラリの XML パーサーは対応していません。また、要素ごとに前述のネームスペース解決をしているので効率が悪いです。xml.etree.ElementTree 以外にも xml.saxxml.parsers.expat が標準ライブラリにはありますが、いずれもイテレータにすることができないため、諦めて標準ライブラリ由来の非効率性については許容することにしました。

必要なことを必要なだけ

Simple Made Easy でも紹介されている通り、効率の良いライブラリは Simple であることを目指すべきです。Arelle は Easy であるため、初心者でも使いやすいですが遅いです。

効率の良いライブラリはシンプルで小さな責務を果たすために必要な最小限の機能を提供し、ユーザーはそれを組み合わせることで様々なユースケースに対応します。上記の "必要なデータのみの読み込み" で説明したようにそれぞれの読み込みメソッドは対応するファイルを上から順に読み込んで必要な情報をイテレータで返すだけのシンプルな処理のみを行います。リンクベースからのグラフの構築などはライブラリユーザーの責務になります。これにより、不要な処理をしない効率良く使い勝手の良いプログラムを書くことができるようになります。

また、Fact ではそれぞれの要素の値のパースを遅延させます。例えば、千円単位の要素の 1,234 という文字列は 1234000 という数値に変換されるべきですが、xbrlp では各要素の Fact.value が呼ばれるまで変換はしません。これは、大部分の要素がデータ抽出には無関係で qname によるフィルタリングでどうせ弾かれるためです。必要のないデータのパースは行わずできるだけ生データのまま持ち回って、必要なデータを必要なだけ処理するようにして効率化します。

テスト

xbrlp が正しく全てのデータをヌケモレなくパースしているかどうかを確かめるために、ゴールデンテストを用いて検証しています。過去 10 年のそれぞれの年について JP GAAP, US GAAP, IFRS などの会計方法の違う実際の XBRL ファイルを複数ファイル選び Arelle を使ってデータ抽出してゴールデンファイルを作っています。

ix:nonNumeric に含まれる HTML データが標準ライブラリの xml パーサーによってパースされてしまい、元の生 HTML 文字列を復元できないという違いが発見されましたが、標準ライブラリを使う限りは避けられないので、正規化された後の XML 文字列が一致することを確認してヨシとしています。

正直、標準ライブラリの xml パーサーは余計なことを色々しているので効率が悪く、Simple ではなく Easy よりだなという印象です。

まとめ

自作の xbrlp パーサーによって XBRL ファイルのデータ抽出が大体 20 倍くらい速くなりました。それまでは1年分の XBRL ファイルを全て処理するのに一晩かかっていましたが、10 分で終わるようになりました。1週間かかる 10 年分のデータ抽出やりなおしも一晩で終わります。

また、速いプログラムはただ速いというメリットだけでなく、力づくで全部の処理をやり切るという選択肢を可能にすることでワークフローに大きな影響を与えることができます。それまではデータ抽出ロジックを改良した後にデータベースをアップデートするのに時間がかかるのでどのようにデータを壊さずに差分更新するかということに腐心していましたが、一晩で全データを再処理し切れるのであればシンプルにデータを1から作り直すという選択肢が取れるようになりました。

速いは正義です。

以下はおまけです。

gist.github.com

AI に作らせる株式分析システム

1発当てて大儲け。どうも、かわしんです。

X の流行を見るに AI コーディングを流石にやらないといけないと思い、今年の8月から Claude Code Max プランを契約して AI コーディングの題材として日本の上場銘柄解析システムを作らせていました。

https://x.com/kawasin73/status/1951869172377682136

新しい技術を追わない をポリシーにしている自分としては、ここらがいい感じに整備されてきてコスパのいい参入タイミングかなと思い使い始めましたが、結果的にはいいタイミングだったと思います。

さて、上場銘柄の有価証券報告書のデータフォーマットである XBRL のパーサー自体は実は2年前に作っていたのですが、ファイルのダウンロードと解析をするために手元で毎回 Python スクリプトを実行しないといけないため、めんどくさくて数ヶ月に1回くらいしか実行して確認していませんでした。それを AI エージェントを使って 1 から作り直して、さらに自動化して便利にしました。

今回はどういうものを作ったかと、どのような思想で作ったかをソフトウェアエンジニアの目線から説明したいと思います。

AI の使い方については別の記事にしますが、僕はほとんどソースコードを書いておらず、95% 以上は AI が書いてます。

作った解析ページ

ネットネットバリュー株ランキングページ

ランキングページ

ネットネットバリューPBR 推移ページ

この指標は、会社が持っている現金や有価証券など即時現金化が可能な資産から総負債を引いた会社の解散時価値で時価総額を割った PBR に似た指標です。この値が 1 を割れば現金が割引価格で売られている状態になりお得になります。

どの項目を即時現金化可能な資産として選ぶかや、それぞれの割引率などを独自に設定できるようにしています。

また、PBR チャートタブでは、独自に計算した PBR の過去の推移をチャートにして表示しています。これによって最近 PBR の値が小さくなったのかどうかを判別することができます。

オニールの成長株発掘ランキングページ

ランキング一覧ページ

銘柄詳細ページの上の方

銘柄詳細ページの下の方

これは、「オニールの成長株発掘法」という本で紹介されているスクリーニング手法を実装したページです。EPS の成長率やリラティブストレングスという株価の推移の指標を元にスクリーニングします。

各銘柄の詳細ページでは、いつ決算が発表されたかのマーカーと、どの区間でシグナルが点灯したかを背景の色を変えることで可視化しています。

ちなみにランキングページから詳細ページまで1枚の HTML でできた SPA です。

オニールのマーケットの天井検出ページ

市場天井検出ツール

これも、「オニールの成長株発掘法」という本で紹介されているマーケットが上昇トレンドから天井をうって下落に転じる前に現れる「分配日」をカウントしていつマーケットが下落するのかを予測するツールです。

シグナルが出た日をマーカーで表示し、注意期間を背景の色を変えることで可視化しています。

ただ、パラメータのチューニングが難しく、ベイズ最適化でパラメータを計算しようとしましたがうまくいきませんでした。

ソフトウェアエンジニアとしての思想

自動化

毎日のデータのダウンロードや解析スクリプトの実行をやるのはめんどくさいので、とにかく全部自動化するのが目標です。流石に株の売り買いも自動化すると不具合があった時の代償が大きいので自分で判断して売買しますが、勝手に条件を満たす銘柄が見つかったら通知を飛ばしてくれるのが理想です。

メンテコストの最小化

個人プロジェクトなので運用の手間をゼロにしたいです。めんどくさいので。24 時間待機するサーバーを持った時点でセキュリティのリスクがあり、ソフトウェアのアップデートなどがめんどくさいです。なので、全部フルマネージドなサービスを使います。

なるべく利用するサービスの数を減らして、メンテナンスをゼロにします。一度作ったらほったらかしにしても動き続ける堅牢なシステムは要素を減らすことで得られます。

アーキテクチャ

全体のアーキテクチャはこんな感じです。肝は、全てを SQLite ファイルで管理し、Github Actions の日次バッチで SQLite を更新して、S3 に置かれた最新の SQLite ファイルを引き回すことでローカルやブラウザ上での解析の全てに対応していることです。必要なインフラは AWS S3 と Githubリポジトリだけです。

Github Actions で日次処理

Github Actions には cron のサポートがあって、以下のように設定すると毎日 18 時に CI workflow が実行されます。

on:
  schedule:
    # Run daily at 6:00 PM JST (9:00 AM UTC)
    - cron: "0 9 * * *"
  workflow_dispatch: # Allow manual trigger for testing

毎日以下の処理を行います。

  • 最新の SQLite ファイルをS3 からダウンロード
  • その日に更新された株価、XBRL などのファイルをダウンロード
  • ダウンロードしたファイルをパース+正規化して、SQLite ファイルに追記
  • ダウンロードした生データファイルを S3 に aws s3 sync
  • 最新の SQLite ファイルを S3 に上書き保存
  • データを解析して必要な通知を行う
  • SQLite ファイルダウンロードリンクや解析 web page リンクを Summary の Web UI に表示

CI の失敗による欠損データを防ぐために、更新するデータは SQLite ファイル内の最新の日付以降を取得するようにして、SQLite ファイルのアップロードは一番最後に行うようにしています。

日次処理に Github Actions を使えばいいというアイディアは ChatGPT が教えてくれました

https://x.com/kawasin73/status/1959106840828289471

S3 に生データと SQLite データベースファイルを保存

パースロジックを変更したときには全ての XBRL ファイルに対してパースをし直すので、全ての XBRL ファイルが手元に必要です。XBRL ファイルは金融庁が提供する EDINET からダウンロードしますが、過去 10 年分しか提供していません。また、DoS を避けるために 1秒に 1 ファイルをダウンロードするので XBRL ファイルのダウンロードはできれば一度だけにしたいです。そのため、Github Actions でダウンロードした XBRL ファイルなどの生ファイルは全て S3 にアップロードして永久保存しています。定期的に aws s3 sync をして S3 のファイルを手元にダウンロードしてパーサーの改善をしています。

生データファイルは、年毎に tar.gz ファイルにまとめて Amazon S3 Glacier Deep Archive クラスで保存することでダウンロードコストと保管コストを下げています。

SQLite ファイルはバージョニングを有効にして上書きして更新しています。SQLite ファイルは時々詳細な分析をするために、ローカルにダウンロードして使います。最初は Github Artifacts に保存するようにしていたのですが、ダウンロードが 1MB/s と超低速なので諦めて S3 を使うようにしました。また、presigned URL を Github Actions のサマリーに書き込んで、WebUI から簡単にダウンロードすることができるようにしました。SQLite ファイルは数百 MB にもなるので gzip バージョンも置いてブラウザから高速でダウンロードできるようにしました。

https://x.com/kawasin73/status/1963626393285100003

Github Pages で static HTML ファイルで解析ページを提供

最初に紹介した解析ページはそれぞれ Gemini canvas モードに作ってもらいました。デフォルトでレスポンシブ対応なのでスマホでも確認できます。Gemini canvas モードすごい。

CSS / javascript が全て入った HTML 1ファイルなのでビルドも必要なく取り回しが楽です。ライブラリとしては sqlite-wasm でクエリして、解析結果を lightweight-charts で表示しています。他のチャートライブラリも試しましたが、大量のデータやマーカーを描画するとスクロールがカクついて動かなくなるので、ヌルヌル動く lightweight-charts はとてもおすすめです。

毎日 Github Actions が最新の S3 の SQLite ファイルの presigned URL を生成して解析ページのリンク URL のクエリパラメータに含ませています。ページがブラウザで開かれると javascriptSQLite ファイルを自動でダウンロードしてキャッシュしブラウザ上で動的に解析をします。細かいパラメータ調整もブラウザ内でできるようになっています。また、ローカルにあるデータベースファイルを指定することもできるので解析ページの追加開発も簡単にできます。

データベースも含んだ解析ページの全てが一つ URL にまとまっているので、そのリンクを誰にでも共有することができます。S3 の presigned リンクは 7 日間の有効期限があるので流出しても被害は限定できます。特に認証はしていないので簡単に友人に共有できるのが便利です。

Github issue を作って通知

毎日解析ページをチェックするのは手間なので、日次バッチで解析を行って新しい銘柄が発見されたら自分に通知して欲しいです。僕は Slack などは使ってないのでメールでの通知方法を検討しました。

ただし、メール配信サービスを使ったり gmail の認証情報の設定をするのは大がかりになって面倒くさいです。そこで Github issues を使うことにしました。

新しい銘柄が発見されたら Github Actions は新しい Github issue を作成します。それによってリポジトリオーナーの自分にメールが届く仕組みです。メールには issue の文章が表示されるので簡単に確認できます。もし、その銘柄が気に入らなければその理由とともに issue を close すれば、後で確認できるログにもなります。

まとめ

こんなシステムを設計して実装しましたが、かなり便利になりました。作業は休日や仕事終わりだけで、3ヶ月でここまで来れたので AI ってすごいなと思いました。アイディアはあるけど形にするのが面倒くさいという時に強力な相棒になります。

ただ、効率の良いプログラムやアーキテクチャは、まだ僕でないと作れないなと思ったので、もう少しはソフトウェアエンジニアとしての旨みのある仕事は残っていきそうです。

AI の使い方や、XBRL ファイルのパースの手法などについてはまた別の記事で解説したいと思います。

オチとしては、今年の運用成績は日経平均に負けてます。個別株なんかせずにインデックス投資をした方がいいのかもしれない。

Recall.ai のリングバッファのパフォーマンスを検証する

推測より計測。どうも、かわしんです。

昨日、Recall.ai のリングバッファがどのように設計されたのかを考察しました。

kawasin73.hatenablog.com

その後、Hacker News のコメントを見ているとリングバッファはオーバーエンジニアリングでもっと簡単な方法として以下の手法などが提案されていました。

  • TCP のウィンドウサイズを変える
  • /dev/shm を使う
  • 共有メモリでの送信は Mojo がサポートしている

WebSockets cost us $1M on our AWS bill | Hacker News

TCP のウィンドウサイズを変えたとしても、ユーザー空間とカーネル空間の無駄なメモリコピーの量は変わらないので今回のメモリコピーのボトルネックには効かない思われます。

/dev/shm については、Memory backed file にデータを書き込んでそのファイルのファイルディスクリプタUnix ドメインソケットで送り、コンシューマ側で mmap すればメモリコピーの回数は共有メモリのリングバッファの手法と同じなので、一考の価値はあります。

しかし、フレームごとに tmpfs にファイルを作成して Unix ドメインソケット経由で送信して mmap しなおすオーバーヘッドがある上に、書き込み時にはメモリページの割り当てが発生し、読み込み時には mmap された領域のページテーブルを埋めるまでページフォルトが大量に発生するなど、オーバーヘッドが大きそうで本当にパフォーマンスが良いのかどうかは怪しいです。

/dev/shm を直接使う場合はプロデューサが死んだ時に大きめのメモリがリークするので回収するための死活監視が必要になりますが、memfd_create(2) を使えば自動的に回収されます。

Mojo については、Rust のバインディングはまだ完成していないので使えないと思いますが、mojo::BigBuffer は実質的には上の /dev/shm の手法と同じです。

ということで、リングバッファと Memory backed file を Unix ドメインソケットで送って mmap する手法のどちらがどのくらい速いのかが気になったので検証してみました。

実際の検証コードは文末に埋め込んでありますが、特徴としては

  • 3MB の固定長のランダムなデータを送信する
  • プロデューサは 3 スレッドから並列にそれぞれ 100 フレームずつ書き込み、コンシューマはシングルスレッドで読み込む
  • リングバッファの最大数と Unix ドメインソケットで同時に送れるのは最大 30 フレーム分まで
  • 同一プロセス内の別のスレッドからそれぞれ送るが、パフォーマンス特性としては別プロセスの場合と変わらないはず
  • Unix ドメインソケットを使ったスロットリングは複数コネクションが必要になるのでとりあえずセマフォで代替
  • memfd は Linux にしかなくて、macOS で開発できなかったので、LinuxmacOS の両方で使える tempfile クレートで代替。実態は Memory backed file なのでパフォーマンス特性は同じはず

結果

  • Linux
    • リングバッファ: 1.95 s くらい
    • Memory backed file: 5.2 s くらい
  • macOS
    • リングバッファ: 750 ms くらい
    • Memory backed file: 10 s くらい

リングバッファの方が結構速いです。macOS では Memory backed file の方が遅すぎるので何か別の問題がありそうな気もします。

Linux (AWS EC2)

リングバッファ

$ for i in {1..5}; do ./cmp_ringbuffer/target/release/cmp_ringbuffer; done
producer 2
producer 1
producer 0
start
producer 0 finished
producer 1 finished
producer 2 finished
finished: 1.973099031s
producer 2
producer 1
producer 0
start
producer 2 finished
producer 1 finished
producer 0 finished
finished: 1.964035006s
producer 2
producer 1
producer 0
start
producer 2 finished
producer 0 finished
producer 1 finished
finished: 1.956276696s
producer 2
producer 1
producer 0
start
producer 2 finished
producer 0 finished
producer 1 finished
finished: 1.968726078s
producer 2
producer 1
producer 0
start
producer 2 finished
producer 1 finished
producer 0 finished
finished: 1.959291665s

Memory backed file

$ for i in {1..5}; do ./cmp_memfd/target/release/cmp_memfd; done
producer 2
producer 1
producer 0
start
producer 1 finished
producer 2 finished
producer 0 finished
finished: 5.206459836s
producer 2
producer 1
producer 0
start
producer 1 finished
producer 2 finished
producer 0 finished
finished: 5.225634239s
producer 2
producer 1
producer 0
start
producer 1 finished
producer 2 finished
producer 0 finished
finished: 5.207194755s
producer 2
producer 1
producer 0
start
producer 0 finished
producer 1 finished
producer 2 finished
finished: 5.216124744s
producer 2
producer 1
producer 0
start
producer 2 finished
producer 1 finished
producer 0 finished
finished: 5.194187799s

macOS (手元の Macbook Pro 2018)

リングバッファ

$ for i in {1..5}; do ./cmp_ringbuffer/target/release/cmp_ringbuffer; done
producer 0
producer 1
producer 2
start
producer 2 finished
producer 1 finished
producer 0 finished
finished: 717.866646ms
producer 0
producer 2
producer 1
start
producer 0 finished
producer 2 finished
producer 1 finished
finished: 733.328122ms
producer 1
producer 0
producer 2
start
producer 0 finished
producer 1 finished
producer 2 finished
finished: 736.151382ms
producer 1
producer 2
producer 0
start
producer 0 finished
producer 2 finished
producer 1 finished
finished: 740.951105ms
producer 0
producer 2
producer 1
start
producer 2 finished
producer 1 finished
producer 0 finished
finished: 751.015461ms

Memory backed file

$ for i in {1..5}; do ./cmp_memfd/target/release/cmp_memfd; done
producer 0
producer 1
producer 2
start
producer 1 finished
producer 0 finished
producer 2 finished
finished: 10.866407023s
producer 0
producer 2
producer 1
start
producer 0 finished
producer 1 finished
producer 2 finished
finished: 11.167087375s
producer 2
producer 1
producer 0
start
producer 1 finished
producer 2 finished
producer 0 finished
finished: 10.824447892s
producer 0
producer 2
producer 1
start
producer 1 finished
producer 0 finished
producer 2 finished
finished: 10.833614174s
producer 0
producer 2
producer 1
start
producer 1 finished
producer 0 finished
producer 2 finished
finished: 11.07388444s

おまけ

リングバッファの実装

gist.github.com

Memory backed file の実装

gist.github.com

Recall.ai のリングバッファの設計を考察する

あなたとわたしとロバストとパフォーマンス。どうも、かわしんです。

先日 Recall.ai というビデオ会議に関連するサービスのブログ記事を読みました。

www.recall.ai

インフラ費用を減らすために動画処理サーバーのプロファイルをとったところ、CPU 時間を一番使っていたのがビデオフレームを送信する際の Web Socket の通信のメモリコピーだったということがわかったので、共有メモリ上に実装したリングバッファを使うことで CPU 使用量を半分にしてサーバー代を半分にしたという豪快なお話です。

同じサーバー内のプロセス間通信に Web Socket を使うと、以下のオーバーヘッドがあります。

  • Chromium プロセスからカーネル内のバッファへのメモリコピー
  • カーネル内のバッファから動画処理プロセスへのメモリコピー
  • Web Socket の改竄防止のために自動で行う全データのマスキング

これらのコストは、ロックフリーでゼロコピーの共有メモリのリングバッファを使うことで削減できます。

まさに技術で課題を解決している感じがしていい話なのですが、以下の要件を満たす共有メモリ上のリングバッファライブラリがなかったため自作したらしいです。

  • ロックフリー
  • マルチプロデューサ / シングルコンシューマ
  • 可変長のフレームに対応
  • ゼロコピー
  • サンドボックス内から送信
  • 低遅延のシグナリング

しかし、この記事にはざっくりとしたリングバッファの概要しか記述がなく、またそのリングバッファライブラリは OSS にはなっておらず、どのように実装したかは不明です。Recall.ai の Github にはそれっぽいリポジトリは見つかりませんでした。

(https://www.recall.ai/post/how-websockets-cost-us-1m-on-our-aws-bill より)

リングバッファを具体的にどのように作ったのかが気になったので、自分だったらどのように設計するかを考察してみました。

上で列挙した以外には以下の要素がブログ記事中でわかっています。これらがパズルのように後で設計を絞るのに役立ちます。

デザインドキュメントを書く時、検討したがうまくいかない案は普通は後ろの方に "Alternative Considered" の章にまとめますが、この記事ではどのように考察したのかも読んでほしいためうまくいかない案を考察してからうまくいく案を導き出す方式で書いています。

データフォーマットとデータ構造

さて、ロックフリー + マルチプロデューサ + 可変長フレーム のリングバッファであるためリングバッファに書き込む際の操作はざっくり以下のステップになるはずです。

  1. write pointer をデータ長分 atomic に増やしてリングバッファ内の領域を確保する
  2. 確保した領域にデータを書き込む
  3. データが読み込み可であることを通知する

リングバッファにヘッダとデータを詰める

可変長のリングバッファのデータフォーマットとして簡単に思いつくのは、固定長のヘッダと可変長のデータ分の領域を (1) のステップで確保するものですが、実はうまくいきません。

             read ptr                        write ptr
              ∨                               ∨
 | free space | header | data | header | data | free space |

なぜかというと、ヘッダ内の書き込み可フラグが (1) のステップの時点で初期化されていないためからです。ロックフリーで並列にアクセスするためには、リングバッファ内の空き領域の先頭の次のヘッダに該当する部分が (1) を行う前に初期化されている必要がありますが、事前に初期化しようにも (1) が終わるまで空き領域の先頭の位置はわからないため、ヘッダの初期化はできません。コンシューマ側で読み込み完了時に空き領域に戻される領域を全てゼロクリアするなどして初期化はできますが、毎回全てをゼロクリアするのはメモリアクセスの観点からも非効率的です。

メタデータ専用のリングバッファ

それを解決するために、2つのリングバッファを用意してみます。

  • 固定長のメタデータのためのリングバッファ
  • 可変長のデータのためのリングバッファ
           read index            write index
            ∨                     ∨
| free slot | metadata | metadata | free slot | free slot |
                    
| free space | data | data | free space |
             ^             ^
           read ptr   write ptr

固定長のメタデータのリングバッファを読み込み側が解放する時に初期化することでメタデータの初期化の問題が解決されます。しかし、メタデータリングバッファの write index とデータリングバッファの write ptr をロックなしに操作するため、2つのリングバッファの順序が入れ替わってしまう可能性があるなどロジックが複雑になってしまいます。さらに、データリングバッファの空き領域が無くなった時のシグナリングセマフォを使うと、1 バイト単位でセマフォに登録しなければならないため、セマフォ操作が大量に発生し非効率です。

リングバッファを固定長のブロック で管理する。

元記事によると 1080p の動画の 1 フレームの大きさは、3110.4 KB だそうです。結構でかいです。最初の案では、空き領域の先頭がどこになるかわからないため領域の解放時に戻される領域を全てゼロクリアしないといけないことが問題でした。リングバッファを 1 MB 単位で確保したり解放したりするようにすると、空き領域の先頭になる可能性のある部分は 1 MB 毎の先頭に限定され、空き領域に戻すときにヘッダの初期化のためにゼロクリアする部分が大幅に少なくなります(1 MB あたり数バイト)。

また、リングバッファの空き領域が無くなった後に空き領域が増えたことを通知するセマフォも、<リングバッファのサイズ> / 1 MB 個だけ登録すればいいのでセマフォ操作も少なくなります。

| free block | header | data   | unused area | free block |
             | multiple of block size        |

データのサイズによっては確保したブロックの後ろの部分は使われない無駄な領域になりますが、ブロックの大きさを調整することで無駄になる領域の割合を下げることができます。全体的な CPU 時間のオーバーヘッドとのトレードオフで決めることになります。

プロデューサの処理

  1. データサイズとヘッダサイズから必要なブロック数を計算する
  2. ブロック確保用のセマフォを必要なブロック数 sem_wait して必要なブロック数を予約する
  3. write ptr を確保したブロックサイズ分 atomic に増やして領域を確保する
  4. ヘッダにデータの大きさなどのメタデータを書き込む
  5. データをリングバッファの確保した領域にコピーする
  6. ヘッダ内の読み込み可のフラグを有効にする
  7. データ完了通知用のセマフォを 1 回 sem_post する

read/write ptr はリングバッファの先頭からのオフセットで表されます。

セマフォの獲得は 1 ブロック単位で行うので、全体のリングバッファのブロック数が少ないと複数のプロデューサが不完全な個数のブロックをセマフォから予約してデッドロックする可能性があります。そのためリングバッファのサイズは、最大のプロデューサの数と最大フレームのサイズの積以上に設定する必要があります。

コンシューマの処理

まず、peek ptr がある意味を考えます。もし 1 フレームごとに処理をするのであれば read ptr から先頭のフレームを peek して、処理が終わってから read ptr を移動させればいいはずなので peek ptr は必要ありません。つまり、peek ptr があるということは、複数フレームを並行に処理する可能性があるということがわかります。

これを元に、コンシューマ側での読み込み処理を考えてみます。

Peek 処理

  1. peek ptr が指す先頭のヘッダの読み込み可フラグが有効になっているかを確認する
  2. もし、読み込み可でない場合はデータ完了通知用のセマフォsem_wait してステップ 1 に戻る。ただし、sem_wait が unblock された場合でも先頭ではなくその先のフレームの読み込みが可能になっただけの場合があることに注意。いずれにせよその場合は sem_wait しなおすことになる。
  3. 先頭のフレームが読み込み可であった場合は、peek ptr をフレームを含む領域のサイズ分増やしてからデータのポインタを呼び出し元に返す。

この読み込み処理はシングルコンシューマなのでシングルスレッドで行われますが、返されたそれぞれのデータの読み込み自体は別スレッドから並列に行えます。

Pop 処理

フレームの処理が終わった後の解放処理は以下のようになります。read ptr の先頭ではなく途中のフレームが先に処理済になった場合に対応するために、ヘッダに処理済フラグを用意します。

  1. 処理済フレームデータのポインタからヘッダの位置を逆算する
  2. ヘッダの処理済フラグを立てる
  3. もし、処理済フレームが read ptr の先頭でなかった場合は (read ptr != ヘッダの先頭) ここで解放処理は終了。
  4. もし、処理済フレームが read ptr の先頭であった場合は、フレームデータに含まれる全てのブロックの先頭のヘッダの読み込み可フラグに相当する位置をゼロクリアする
  5. read ptr をフレームを含む領域のサイズ分増やして、ブロック確保用のセマフォを解放されるブロック数 sem_post する
  6. step 3/4 に戻って次のフレームがすでに処理済であった場合は引き続き解放処理をする

死活監視

もしプロデューサが処理の途中でクラッシュするなどして止まった場合、リングバッファの処理途中のフレーム以降全てが読み込みできずにシステムが止まってしまいます。

もしかしたら Recall.ai ではここまでやってないかもしれないですが、システムの壊滅的な停止を防ぐためにも死活監視の仕組みをリングバッファに入れる必要があります。

プロデューサの死の判定

プロデューサプロセスの死は Unix ドメインソケットのコネクションを事前に貼っておくことで検知することができます。もしプロデューサが死ぬと自動的にコネクションが切断状態になり、ソケットを epoll などで読み込み待ちしているコンシューマに通知されます。プロデューサが終了メッセージをソケットに書き込むことなくコネクションが切断された場合はコンシューマは異常状態からの復帰モードに入ることができます。コンシューマは、異常死を検知した時点での write ptr の値を atomic に取得して、peek ptr がその値に到達するまで読み切るまで異常状態を続けます。

コピー途中の死からの復帰

プロデューサがデータをコピーしている途中で死んだ場合、ヘッダにフレームの大きさが書いてあるのでそのフレームをコンシューマは捨てることができます。ただし、そのフレームを書いているプロデューサが突然死したプロデューサかどうかを判定するために、ヘッダにプロデューサの ID を書き込むことにします。

また、プロデューサの ID は前述のコネクションを接続するときにコンシューマから割り振ってプロデューサに伝えることで一意性が保たれます。

ヘッダ更新前の死からの復帰

プロデューサが write ptr を更新した直後のヘッダを更新する前に死んでしまった場合、そのフレームの大きさをコンシューマは知ることができません。それ以降のフレームは正常なフレームも含めて残念ながら捨てることになります。コンシューマはヘッダのサイズが長時間更新されないフレームを検出した時、それ以降のフレームを諦めて peek ptr を異常状態に入った時の write ptr の値に書き換えて処理を再開します。フレームを捨てるのは peek 済のフレームが全て処理済になった状態 (read ptr == peek ptr) で行い、peek ptr を動かすブロック数分、ブロック確保用のセマフォsem_post します。

もし、死んだプロデューサ以外のプロデューサからのフレームを捨てることが受け入れられない場合はブロックごとの状態を管理することになりますが、データがブロックの境界で連続しなくなってしまうので設計を 1 から見直すことになると思います。

コンシューマの死

コンシューマが死んで復帰した場合も、プロデューサ側はコンシューマの死を Unix ドメインソケットによって検出できるのでコンシューマとのコネクションが貼り直されるまでリングバッファの書き込みを中断することで対応できます。

コンシューマが復帰した後はプロデューサの ID が全て新しくなるため、コンシューマはデータの書き込みを再開させる前にリングバッファ内にあるデータを全て処理します。その後、新しいプロデューサの ID をソケット経由で送信してプロデューサにデータの書き込みを再開させます。

不明な点

ブログの元記事からはどうするのかが不明な点はこんな感じだと思います。

  • どうやって共有メモリを Chromium の JS 環境に繋ぎ込んでいるのか
    • 元記事では "our Chromium" と言っているので、ChromiumC++ のコードに手を入れて JS から渡されたビデオフレームをリングバッファに書き込んでいるのだと思われます。
  • 共有メモリのデータがライブラリ外から壊されないのか
    • 共有メモリ自体を JS 環境に見えないようにすれば Third-party コードを実行する JS から共有メモリを正しく使うことを保証できます。
  • ひとつのプロデューサが遅すぎる場合全体を律速してしまう
    • 全てのプロデューサが同じデバイス上での同質な Chromium プロセスなので速度の違いは想定しなくてもいい気もします。

まとめ

こう考えてみると、考察するのに必要な情報はあのブログ記事にまとまっていたので Overview Design としてはかなりよく書かれた記事だったのだなと思いました。

ライブラリを作る時はすべての場合に対応しないといけないので設計って大変です。今回は死活監視によってロバストなリングバッファに仕上がりました。

皆さんも、ロバストとパフォーマンスを両立したプロダクトを作っていきましょう。

Rust で SQLite を再実装した 2023

気合いで実装、どうもかわしんです。

この記事は Rust Advent Calendar 2023 の6日目情報検索・検索技術 Advent Calendar 2023 の 6 日目です。

Rust で SQLiteフルスクラッチで実装しています。

github.com

なぜ SQLite を Rust で再実装しようと思ったのかについては以前の記事で紹介しています。一言で言えば、誰も Rust で SQLite を書いている人がいなかったからやってみたのですが、そもそも SQLite が強すぎるということが再実装しているうちにわかってきて絶望しています。

kawasin73.hatenablog.com

4 ヶ月前にこの記事を書いたときは簡単な SELECT 文しか実行できなかったのですが、現時点では SELECT, INSERT, DELETE 文をサポートし、expression についても比較などの一部をサポートしています。こんな感じで CLI から利用することもできますし、ライブラリとして組み込むこともできます。

$ git clone https://github.com/kawasin73/prsqlite.git

$ cd ./prsqlite

$ sqlite3 tmp/sqlite.db
sqlite> CREATE TABLE example(col1, col2 integer);
sqlite> CREATE INDEX i_example ON example(col2);
sqlite> INSERT INTO example(col1, col2) values(null, 1);
sqlite> INSERT INTO example(col1, col2) values(10, 2);
sqlite> INSERT INTO example(col1, col2) values(1.1, 3);
sqlite> INSERT INTO example(col1, col2) values('Hello prsqlite!', 4);
sqlite> INSERT INTO example(col1, col2) values(X'707273716c697465', 5);
sqlite> .quit

$ cargo build && ./target/debug/prsqlite tmp/sqlite.db
prsqlite> SELECT * FROM sqlite_schema;
table|example|example|2|CREATE TABLE example(col1, col2 integer)
index|i_example|example|3|CREATE INDEX i_example ON example(col2)
prsqlite> SELECT * FROM example;
|1
10|2
1.1|3
Hello prsqlite!|4
prsqlite|5
prsqlite> SELECT col1 FROM example WHERE col2 == 4;
Hello prsqlite!
prsqlite> INSERT INTO example(col1, col2) VALUES (123, 6);
prsqlite> INSERT INTO example(rowid, col2) VALUES (20, 20);
prsqlite> INSERT INTO example(rowid, col2) VALUES (6, 6);
the rowid already exists
prsqlite> INSERT INTO example(rowid, col2) VALUES (7, 7);
prsqlite> INSERT INTO example(col1, col2) VALUES ('hello', 21);
prsqlite> SELECT rowid, * FROM example WHERE col2 >= 6;
6|123|6
7||7
20||20
21|hello|21
prsqlite> DELETE FROM example WHERE col2 < 20;
prsqlite> SELECT * FROM example;
|20
hello|21
prsqlite> DELETE FROM example;
prsqlite> SELECT * FROM example;
prsqlite> .quit

今回は SQLite を再実装している上で頑張ったところを紹介していきたいと思います。

相互互換性

prsqlite は SQLite で生成したデータベースファイルで動くのはもちろん、prsqlite で生成したデータベースファイルでも SQLite が正しく動くようにすることを目指しています。そのため、SQLite のファイルフォーマット などのドキュメントや、SQLiteソースコードを読んでどのような挙動にするべきかを確認しながら実装しています。

Zero dependency

依存ライブラリを増やせば増やすほど自分のプロダクトは不安定になります。そのため、prsqlite では Rust の標準ライブラリ以外は使わないことにしています。逆にRust の標準ライブラリはそれなりに充実していて、OS ごとのファイルシステムの抽象化がされているので便利です。現在は開発のしやすさから例外的に anyhow というエラーの便利ライブラリを使っていますが、そのうち anyhow も独自のエラー型で置き換える予定です。

本家の SQLite ではもっと過激で、依存しているのは memcmp() などの 10 個の関数のみです。それを 自慢するドキュメント があります。printf() すら自作しています。残念ながら SQLite 独自のフォーマット記号があるので再実装の難易度が跳ね上がります。浮動小数点数の文字列変換 を試みましたが一旦諦める羽目になりました。

外部ライブラリを使わないので、全て手書きしています。SQL のパーサー (token.rs, parser.rs) やファイルフォーマットのシリアライザ・デシリアライザ (btree.rs, cursor.rs, record.rs) 、ページ管理 (pager.rs) 、簡単なクエリプランニング (query.rs) なども全部自作のものです。

No unsafe

Rust の大きな特徴の一つにメモリ安全があり、それゆえに Rust で書かれたコードはセキュリティ的な評価が高くなります。(The Rule Of 2)

Rust には unsafe という機能があり、そのブロックの中ではメモリ安全の検証をスキップすることで Rust の borrow checker には違反するが実際にはメモリを破壊しないコードを書くことができます。それによって複雑すぎるコードや無駄なチェックのない効率的なコードを書くことができます。(例えば copy_nonoverlapping () vs <[u8]>::copy_from_slice()) しかし、unsafe を使うことでプログラムの一部にコンパイラによってメモリ安全性が保証されていない部分ができてしまうので、unsafe のないライブラリには一定のセキュリティ的な価値があります。

prsqlite は今の所 unsafe を使わずに全てのコードが書かれています。全てのコードは Rust の borrow checker のルールに従って書かれているということです。これがなかなかしんどくて、本当は正しいコードも現行の Rust の borrow checker では弾かれてしまうこと (特にループが絡むと捕捉しきれないみたいです) があり、それを回避するために工夫する必要がありました。例えば query::Query::next()) はループの中から直接値を返すことができるはずなのですが、borrow checker はなぜかそれをエラー判定するので、一旦ループから抜けて値を返すようにしています。実際に次世代の Polonius という borrow checker で試してみるとループ内から値を返してもエラー判定はされません。

Pager はハッシュマップに保存されていますが、読み込みと書き込みの両方に対応するために RefCell<HashMap<PageId, Rc<RefCell>>> というちょっと複雑なデータ構造になっています。また、参照の作成のたびに内部のカウンターのチェックを行うので少しオーバーヘッドがあります。このオーバーヘッドはメモリ安全を完璧に保証するためには仕方ないのですが、なるべく参照の作成の回数を少なくするようにして対処しています。

テスト

あとで手戻りをするのが嫌なので、テストはたくさん書いてます。コンポーネントごとのユニットテストもですし、全体の統合テストも書いています。体感 3 分の 2 はテストな気がします。

将来的には本家の SQLite のテストケース も流用できたらいいなと思っていますが、まだサポートしている SQL 文の種類が少ないのでできていません。

なるべく速い実装

パフォーマンス改善は後回しにしても、パフォーマンス改善するときはなかなか来ないですし、実際に改善しようとしてもどこをすればいいかを探すのは大変です。そのため、実装の複雑さが増さない限り最初から最適なコードを書くことが大切です。

僕は速い実装にするために この記事 でも紹介したように以下の 2 つのことを気をつけています。

まずは、無駄なことをしないことが大切です。メモリコピーの量やメモリアロケーションの回数もなるべく少なくするべきです。

次に、条件分岐を避けることです。条件分岐は分岐予測が外れたときのペナルティが大きいのでなるべく条件分岐をせずにコードが書けると良いです。僕はなるべく if 文を使わずに書くことができないかを意識しています。SQLite では、ページのヘッダサイズの計算を以下のように行なっていますが、

first = hdr + ((flags&PTF_LEAF)==0 ? 12 : 8);

prsqlite では以下のようにして条件分岐をなくしています。

    /// The btree page header size.
    ///
    /// * Returns 8 if this is a leaf page.
    /// * Returns 12 if this is an interior page.
    ///
    /// This does not invoke conditional branch.
    pub fn header_size(&self) -> u8 {
        // 0(leaf) or 8(interior)
        let is_interior = (!*self.pagetype()) & LEAF_FLAG;
        // 0(leaf) or 4(interior)
        let additional_size = is_interior >> 1;
        8 + additional_size
    }

Btree の実装

SQLite の実装の中で一番めんどくさかったのは、btree の実装です。特に、データの挿入と削除です。ページの分割や削除が異様にめんどくさいです。

SQLite のおもしろ仕様 (2) : ファイルフォーマット でも紹介したように、SQLite ではインデックスは B 木 を、テーブルは B+ 木を使っています。そのため、微妙に実装が違う部分と共通する部分があります。

また全てのデータは可変長です。そのため、ページ内に幾つのセルが保存されるかは動的ですし、セルのサイズも動的です。ページを分割した時に中間のキーが何番目のセルになるのかは詰め直さないとわからないですし、中間のキーが親のページに収まるかも詰めてみないとわからないです。

最悪なのは、データの挿入でページを分割するときに 3 つのページに分かれてしまうことすらあります。

最後に

だんだん実装が大変になってきて飽きてきましたが、時々頑張ります。本家の SQLite のテストケースを流せるようになるのは大きなマイルストーンだと思うのでそこまで頑張りたいです。

SQLite のおもしろ仕様 (2) : ファイルフォーマット

後方互換性って辛いね、どうもかわしんです。

最近 Rust で SQLiteフルスクラッチで再実装しています。

github.com

再実装するために SQLite の公式ドキュメントやソースコードを読み込んでいるわけですが、その過程で気付いたおもしろポイントを共有しようかと思います。

今回はその第二弾、ファイルフォーマット編です。第一弾はこちら:SQLite のおもしろ仕様 (1) : データ型 - kawasin73のブログ

前提知識 : ページ

まず、この記事を面白いと思ってもらうための前提知識です。

大抵のデータベースはデータを保存するファイルをページという単位で管理します。SQLite ではデフォルトでは 1 ページ 4096 バイトです。これは、ファイルを保存するデバイス(HDD や SSD など)としてブロックデバイスを想定しているからです。ブロックデバイスとはデータの読み書きをブロック単位で行う、1 バイト単位のアクセスができないデバイスです。ブロックのサイズは 512 バイトだったりもっと大きかったりしますが、2 の冪乗のサイズです(例外があるかは知りません)。1 ページには 1 つ以上のブロックがピッタリ収まります。

多くのデータベースシステムでは I/O レイテンシーが支配的になるため、ディスクへのアクセスを最適化するためにページの境界を超えたデータの保存はしません。全てのデータアクセスの単位はページ内に収まるように設計されています。

可変長のデータの保存の仕方

第一弾 で紹介したように SQLite ではそれぞれのカラムにどの型のデータが来るかは実際に INSERT されるまでわかりませんし、同じカラムでも別の行では異なるデータ型になることもあります。つまり、ページ内に保存されるセルは全て可変長です。そのため、1 ページに何個のセルを保存できるかは動的に決まります。

SQLite のフォーマットではセルをページの後から先頭に向かって保存していき、それぞれのセルの先頭のオフセットをセルポインタとしてページの先頭から後ろに向かって保存していきます。

セルポインタは 2 バイトなので、X 番目のセルポインタの位置は一撃でわかり、ビッグエンディアンエンコードされた値を読み取ればセルのオフセットも一撃で取得することができます。

もしセルサイズ + 2 バイトの余裕がそのページにない場合はそのページは満杯になったとして処理をします。

このシリアライズ方法は、可変長のデータをファイルに保存したいときとかに応用できそうです。

Overflow への対応

SQLite は、4096 バイトを超える文字列など 1 ページに収まらないような大きなデータの保存にももちろん対応しています。ある閾値を超えるサイズのデータは Cell Payload Overflow Pages に分割され、先頭のデータのみがセルとしてテーブルのページに保存されます。後続のはみ出たデータは Cell Payload Overflow Pages として連結リストの要領で複数ページに分割して保存されます。

さて、その閾値とセルとして保存されるバイト数は以下のように計算されます。

  • X is U-35 for table btree leaf pages or ((U-12)*64/255)-23 for index pages.
  • M is always ((U-12)*32/255)-23.
  • Let K be M+((P-M)%(U-4)).
  • If P<=X then all P bytes of payload are stored directly on the btree page without overflow.
  • If P>X and K<=X then the first K bytes of P are stored on the btree page and the remaining P-K bytes are stored on overflow pages.
  • If P>X and K>X then the first M bytes of P are stored on the btree page and the remaining P-M bytes are stored on overflow pages.

なんかぱっと見、複雑です。複雑なのは作者も認識しているようで、ドキュメントのすぐ下では後悔と負け惜しみが述べられていました。

In hindsight, the designer of the SQLite b-tree logic realized that these thresholds could have been made much simpler. However, the computations cannot be changed without resulting in an incompatible file format. And the current computations work well, even if they are a little complex.

(日本語訳): 振り返ってみると、SQLiteのBツリーロジックの設計者は、これらの閾値をもっとシンプルに設定できたと気づきました。しかし、計算方法を変更すると、ファイルフォーマットの互換性が失われるため、変更はできません。そして、現在の計算方法は、少々複雑であっても、うまく機能しています。

後方互換性って辛いね。

B 木 vs B+ 木

B 木とは 1 つのノードに 3 つ以上の値を保存する木構造です。ノードをページの単位に揃えることができるのでデータをブロックデバイスに保存するデータベースと相性がよく、データベースではデータ構造として B 木やその派生がよく使われます。

B+ 木は B 木の派生の一種です。B 木はそれぞれの値が重複せずに 1 つのノードだけに保存されている一方で、B+ 木は全ての値とキーの組を葉ノードのみに保存して検索のためのキーが中間ノードに重複して保存されているという特徴があります。B+ 木は中間ノードに値を保存しないため、より多くのキーと子ノードへのポインタを一つのノードに保存でき、木の階層を減らすことができます。また、葉ノード同士を繋ぐポインタを持つことで範囲検索時にアクセスするページ数を減らすことができるという利点もあるらしいのですが、SQLite では葉ノード同士を繋ぐということはしていませんでした。詳しくは自分で調べてみてください。

SQLite ではテーブルに B+ 木を、インデックスに B 木をと使い分けています。僕の推測ですがインデックスは巨大なサイズのキーを葉ノードと中間ノードに重複して保存するときの無駄が大きすぎるため B 木を使っているのだと思います。一方、テーブルのキーは 64 ビットの符号付整数を Varint エンコードしたものなので 1 ~ 9 バイトとサイズの上限が十分小さく、中間ノードに重複して保存したときの無駄は小さく済みます。

木の構造が微妙に違うので、SQLite の実装ではテーブルとインデックスで sqlite3BtreeTableMoveto()sqlite3BtreeIndexMoveto() のように別々の関数が定義されています。一方でそれ以外の操作 (sqlite3BtreeInsert(), sqlite3BtreeNext() など) は共通の関数が提供されています。実装してみるとわかりますが、意外と共通の操作が多いです。

過去のバグの代償

Freelist はデータの削除などで使わなくなったページを再利用のためにリストするための構造です。

A bug in SQLite versions prior to 3.6.0 (2008-07-16) caused the database to be reported as corrupt if any of the last 6 entries in the freelist trunk page array contained non-zero values. Newer versions of SQLite do not have this problem. However, newer versions of SQLite still avoid using the last six entries in the freelist trunk page array in order that database files created by newer versions of SQLite can be read by older versions of SQLite.

(日本語訳): SQLiteの3.6.0 (2008-07-16)より前のバージョンでは、フリーリストのトランクページ配列の最後の6エントリのいずれかに非ゼロ値が含まれている場合、データベースが破損していると報告されるバグがありました。新しいバージョンのSQLiteにはこの問題はありません。しかし、新しいバージョンのSQLiteは、新しいバージョンのSQLiteで作成されたデータベースファイルが古いバージョンのSQLiteでも読み取れるように、フリーリストのトランクページ配列の最後の6エントリを使用しないようにしています。

3.6.0 より前のバグのために Freelist trunk page の最後の方の 24 バイトは未来永劫使われない領域になってしまいました。

後方互換性って辛いね。

ドキュメントされていない仕様

prsqlite は本家の SQLite と互換性を持つことを目標としているので、ドキュメントはもちろんですが本家のソースコードも読みながら実装しています。

そこで、どうやら 4 バイトより小さいセルは 4 バイトとして領域が確保されているらしいことがわかりました。これはドキュメントには書かれておらず衝撃でした。

static int balance_nonroot(
// ...
        while( b.szCell[b.nCell]<4 ){
          /* Do not allow any cells smaller than 4 bytes. If a smaller cell
          ** does exist, pad it with 0x00 bytes. */


static int freeSpace(MemPage *pPage, u16 iStart, u16 iSize){
// ...
  assert( iSize>=4 );   /* Minimum cell size is 4 */


static int fillInCell(
// ...
    if( n<4 ) n = 4;

僕の推測ですが、解放されたセルのサイズが 4 バイト未満だとページ内の freeblock list に追加できず "fragmented free bytes" として無視されてしまうため、なるべく解放されたセルを再利用させるための最適化なのだと思います。しかし、3 バイト未満のセルがあるファイルを SQLite が処理するとセルの解放時に別のセル領域を破壊してしまうため、これはドキュメントするべき仕様な気がします。

一方で、テーブルは最低 1 カラム以上、インデックスは最低 1 カラム + rowid の 1 integer 以上の要素が Record Format によってペイロードシリアライズされるため、全てのセルは 4 バイト以上になるのですが、btree cursor 自体は Record Format とは独立であること、SQLite 自身が 3 バイトのセルのテスト をしている以上仕様っぽいです。

最後に

ファイルフォーマットは一度ファイルがユーザーの手元で作られてしまうと後方互換性を常に意識しながら拡張していかないといけないので、メモリレイアウトと比べてやり直しが効かず特に大変です。

こういう後方互換性を避けるためには、MessagePack とか Protocol Buffers とかのシリアライズフォーマットを使うとか SQLite などの組み込みデータベースを使うと安心です。しかし、部分更新をしたい場合とか、やりたいことに対して組み込みデータベースは複雑すぎる場合などは、自分でファイルフォーマットを考える必要があり(あった)、大変でありつつも楽しいですね。ハハハ。

天下一 Game Battle Contest 2023 に参加した

予習は大切、どうもかわしんです。

「天下一 Game Battle Contest 2023」に参加しました。4位でした。

tenka1.klab.jp

去年このコンテストの存在をちょうど終了した時に知ってやりたいなと思い、Twitter アカウントをフォローして1年待ってました。今回の大会は去年の大会がベースになっているということで事前に予習してから挑みました。

ルールは以下を参照してください。

tenka1-2023/problem.md at master · KLab/tenka1-2023 · GitHub

言語の選択

個人的には Rust か Python がなれているのですが、Go で参加することにしました。

  • Rust
    • 所有権とか、mutable/immutable の制限を気にしながら書くのがめんどくさい。素早く書けない。
    • 複数スレッドでの処理もめんどくさい
  • Python
    • 素早く書けるけど、シングルスレッドになる
  • Go
    • 4年前は一番得意だった言語
    • マルチスレッドが goroutine を使うことで簡単に書ける
    • コンパイルするので凡ミス(typo とか)は防げる

4 方向への予測をマルチスレッドで並列に処理できたら有利だなと思ったので Go でやりました。が、結局僕のロジックはシングルスレッドで全部計算しても 10 ms もかからず、500ms の制約を十分クリアできたのでマルチスレッドの必要はなかったです。

Go は愚直に書かないといけないのでシンプルにめんどくさかったです。ぶっちゃけ Rust で書いた方が実装速度が速かったような気もします。

細かい小技

スタートダッシュ

2023 のコンテストは 2022 のコンテストと同様に複数リーグの構成になっていて、それぞれのリーグの上位数名と下位数名が上下のリーグに移動しながら4時間かけて順位が決まっていくルールになっています。

決勝に進める 1 ~ 8 位もそもそも最上位のクラス 1 のリーグにいないとなれません。リーグ自体は参加した時点で一番下のリーグに組み込まれるので、素早く試合に参加することでスタート地点を有利にすることができます。

予習してたので、ルールが公開されて大体のルールが同じことを確認してから、すぐにサンプルコードで試合を開始して無事クラス 1 のリーグからスタートすることができました。

バージョン管理

運営から提供される gorunner はそれぞれの試合ごとに登録されたコマンド (go run main.go) を実行して試合に参加させます。

Go のサンプルコードは tenka1-2023/go/main.go にありますが、これを開発しながら並行して試合に参加するとコマンド実行のタイミングによっては main.goコンパイルに失敗したり中途半端なロジックの状態で参加することになってしまいます。そのため、main.go で開発して実装の区切りがついたら以下のコマンドを実行してバージョン管理をしてました。

cp main.go v0001.go
go build v0001.go

実装したロジック

大枠としては、2つのエージェントそれぞれについて4方向に進んだ時にどういう感じに有利かを判定して比べながら一番いいものを選択するという方式でやりました。4方向はそれぞれ Prediction 型で表すことにしました。

github.com

戦術的優先度

ShortTermPrediction で表しているのが、1 手先のどのマスが有利なのかです。1 手先のマスの状態によって ShortTermPredictionValue で優先度をつけます。空白が一番優先度が高いです。

const (
    EmptySteal ShortTermPredictionValue = iota
    EmptyMayStolen
    Empty
    EmptyMayConflict
    SelfHalfMayConflict
    EnemyHalf
    EnemyHalfMayConflict
    SelfHalfRecover
    EnemyFullCanSteal
    EnemyFull
    SelfHalf
    EnemyFullMayConflict
    EnemyHalfMayStolen // TODO
    EnemyHalfMayConflictEnemy
    SelfFullMayConflict
    EnemyFullMayRecovered
    SelfFull
    Others
    Dont
)

また、進む先のマスの 1 マス先、2 マス先をそれぞれ見て、敵のエージェントがいないかどうかを確かめます。もしいる場合は、相手が被る方向に移動してきた時に有利になるかどうかで優先順位が変わります。例えば敵の半壊のマスはEnemyHalf* の派生で優先順位が決まります。

       if state[1] == 1 {
            priority = EnemyHalf
            if len(enemies0) > 0 {
                priority = Dont
            } else if slices.Contains(enemies1, state[0]) {
                priority = EnemyHalfMayConflictEnemy
                damageTarget = slices.Contains(enemies1, target)
            } else if len(enemies1) > 0 {
                priority = EnemyHalfMayConflict
                damageTarget = slices.Contains(enemies1, target)
            } else if len(enemies2) > 0 {
                priority = EnemyHalfMayStolen
                damageTarget = slices.Contains(enemies2, target)
            }

一番ムカつくのが自分が全壊にしたマスを敵に取られることなので、それが起きないように Dont を指定しています。

ターゲット指定

以下の記事で紹介されていた通り、順位が最終的なポイントに直結するので、1 位の時は 2 位の敵を、1 位でない時は一つ上の順位の敵を優先して攻撃するようにしました。EstimateRanking() で順位を予測しています。

天下一 Game Battle Contest 2022 参加記 - matsu7874のブログ

戦略的優先度

例えば周りが全部自分のマスに囲まれた時1手先の優先度だけでは効率的に動けません。

そのため、4 方向へのそれぞれの最短で到達できるエリアに存在するマスの状態によって potential を計算し (CalcPotential())、もし potential が低い方向(つまり自分のマスが多く意味の薄い方向)に移動しようとした場合は、第 2 優先の方向へ移動するようにしました。

     if idx_0 == 0 {
            minPotential := predictions0[0].potential
            minPotentialIdx := 0
            maxPotential := 0
            for i, p := range predictions0 {
                if p.potential <= minPotential {
                    minPotential = p.potential
                    minPotentialIdx = i
                }
                if p.potential >= maxPotential {
                    maxPotential = p.potential
                }
            }
            if predictions0[0].shortTermPrediction.priority > SelfHalfMayConflict && minPotentialIdx == 0 && maxPotential-minPotential > 700 {
                log.Println("potential 0")
                idx_0 = 1
            }
        }

不利なマスの乗り越え

1 マス先だけを見ているとあるマスを隔てて空白マスが広がっていた時にそちら側に移動することができません。壁になってるマスを乗り越えて空白マスを取りに行くと有利になります。

2 マス先の考慮を Length2Prediction で行うことにしました。ただし、わざわざ不利なマスを乗り越えていった直後に敵にそのマスを取られるのは悔しいので空白マスの周囲に敵がいるかどうかを検証して、マスの乗り越えをするかを判断します。

周期的な動きの抑制

一番優先順位の高いマスを選びランダムな要素はないので、似たようなユーザーと鉢合わせた時に同じ2マスを交互に移動し続けたり、周期的な挙動をする可能性があります。その場合自分の得点が変わらないまま周期的な動きをしていないユーザーだけが動き続けて不利になってしまいます。そのため、2ターン周期と4ターン周期で同じマスに同じ状態で移動していないかを確認して、無限に周期的な動きをしてターンを浪費することを防ぎます。

     // pendulum 2
        if len(agentLog) > 2 {
            previousPos := agentLog[len(agentLog)-1][0]
            pos := predictions0[0].pos
            if IsSamePos(pos, previousPos) && IsSameState(move.Field[pos[0]][pos[1]][pos[2]], fieldLog[len(fieldLog)-2][pos[0]][pos[1]][pos[2]]) {
                log.Println("pendulum 0 for 2")
                idx_0 = 1
            }
        }

        // pendulum 4
        if len(agentLog) > 4 && idx_0 == 0 {
            previousPos := agentLog[len(agentLog)-3][0]
            pos := predictions0[0].pos
            if IsSamePos(pos, previousPos) && IsSameState(move.Field[pos[0]][pos[1]][pos[2]], fieldLog[len(fieldLog)-4][pos[0]][pos[1]][pos[2]]) {
                log.Println("pendulum 0 for 4")
                idx_0 = 1
            }
        }

特殊移動

今回の大会では特殊移動が新しい要素として加わりました。4 方向のどれかに 5 マス移動して強制上書きするか、任意の場所にジャンプして周囲の 5 マスを強制上書きすることができる機能でエージェントにつき 1 回まで実行できます。

ぶっちゃけ上の部分で時間を使ってしまったので特殊移動は十分に考えることができなかったです。

任意ジャンプした場合は周囲 4 マスが塗りつぶされ、その次の移動は必ず自分のマスになるため、1 ターン無駄になります。そのため、縦に強制上書きするものだけ選択するようにしました。(NewSpecialPredictionStraight())

前半で特殊移動しても点数に加算されないので後半になったタイミングで実行するようにしました。また2つのエージェントが同時に特殊移動してマスが被ったら無駄なので違うタイミングで特殊移動するようにしました。(被るかどうかは予測可能なので余裕があれば改善できた)

感想

最初の方はスタートダッシュがうまくいって 1 位をキープできていたのですが、途中から抜かされてしまいました。考慮できる点はもっとあったし、もっと無駄な移動を省けていたはずなのでその差だと思います。4時間はあっという間でした。

楽しかったです。