Grnxx の紹介

矢田 晋

有限会社 未来検索ブラジル

Grnxx とは

• 位置付け
• Groonga の後継�
• 読み方
• ぐるんたす�
• 由来
• Groonga + C++�
• 進捗
• 設計・開発中

発表の内容

• 開発の経緯�
• 新設計の利点�
• 解決すべき課題�
• まとめ + α

開発の経緯

開発の経緯（概要）

• より大きなデータを扱えるように�
• より速くデータを検索・更新できるように�
• より小さくデータを格納できるように

開発の経緯（背景）

• Groonga の制約
• 最大レコード数 256M（2億6800万）
• 最大合計キー長 4GiB
• etc.�
• インメモリ DB の台頭
• いろいろなシステム
• Memcached, Redis, etc.
• VoltDB, HyPer, etc.
• IBM, Oracle, Microsoft, SAP, etc.�
• 『乗るしかない このビッグウェーブに』

開発の経緯（目標）

• Grnxx の制約
• 最大レコード数 1T（1兆1000億）
• 最大合計キー長 256TiB
• etc.�
• インメモリ DB の技術を採用
• 開発のポイント
• インメモリ化
• クエリのシリアライズ
• スナップショット (fork)
• クエリの実行方法

新設計の利点

新設計の利点（一覧）

• 大規模化
• 規模に関する制約が緩和される�
• インメモリ化
• メモリ管理の自由度が上がる
• フラッシュによる速度低下を抑える�
• クエリのシリアライズ
• リソースの競合がなくなる
• データの不整合がなくなる
• データ構造の自由度が上がる

新設計の利点（インメモリ化）

• 補助記憶装置の特性
• 大容量・安価・低速
• ブロック単位 I/O（大）
• シークタイム�
• 主記憶装置の特性
• 小容量・高価・高速
• すごい勢いで大容量・安価になった
• キャッシュライン単位 I/O（小）�
• 『補助記憶装置の特性から解放される』

新設計の利点（インメモリ度）

• オンディスク
• 伝統的 DBMS の伝統的ストレージエンジン�
• Groonga
• どちらかといえばインメモリ（ほぼ mmap）�
• Grnxx
• さらにインメモリ寄り（一部 mmap）�
• インメモリ
• Redis, VoltDB, etc.

新設計の利点（メモリ管理）

• 伝統的手法
• 自前でページ単位の管理をする�
• Groonga
• File-backed shared memory mapping (mmap)
• ページの管理は OS にまかせる
• リソースの再利用は自前で頑張る�
• Grnxx
• malloc/free, new/delete
• 基本的にすべて OS にまかせる
• ところにより自前で頑張る

新設計の利点（フラッシュ）

• Groonga
• File-backed shared memory mapping (mmap)
• Dirty ratio が高くなると自動的にフラッシュ
• フラッシュ中は実行速度が抑制される�
• Grnxx
• fork
• 子プロセスはスナップショットを保存
• シーケンシャルアクセス�
• 親プロセスは実行を継続
• COW（Copy-on-Write）になるので更新しても大丈夫
• フラッシュによる影響を受けにくい

新設計の利点（シリアライズ）

• Groonga
• 参照ロックフリー
• リソースの競合
• 新しい領域を確保して更新後のデータを格納する
• 更新前のデータをすぐに破棄できない
• 参照中の更新，更新中の参照
• 更新前のデータと更新後のデータが混在する�
• Grnxx
• クエリをシリアライズする
• 上述の問題がなくなる
• スループットが向上する
• 中途半端な状態が見えなくなる

新設計の利点（データ構造）

• Groonga
• データ構造に対する制約
• File-backed shared memory mapping
• マルチスレッド・マルチプロセス
• 参照ロックフリー�
• Grnxx
• データ構造の自由度
• 補助記憶装置の特性から解放される
• 自由にポインタを使える
• リソースが競合しない

解決すべき課題

解決すべき課題（一覧）

• ID とオフセットの拡張�
• 大規模化とインメモリ化の競合�
• 永続化�
• クエリのシリアライズによる制約

解決すべき課題（ID とオフセット）

• 課題
• レコード ID の拡張
• 256M から 1T へ
• 32-bit から 64-bit へ�
• オフセットの拡張
• 4GiB から 256TiB へ
• 32-bit から 64-bit へ�
• 解決案
• 必要に応じて割り当てを変更する
• 4G 以上になれば 64-bit にする

解決すべき課題（大規模化）

• 課題
• 大規模になるとメモリ上に展開できない
• スワップアウトや OOM Killer
• 全文検索は大規模になりやすい
• 文書を登録したカラム
• 10KB x 100万文書 = 10GB
• 全文検索用の転置索引
• 検索対象の文書と同程度�
• 解決案
• 文書と転置索引は特別扱いする
• File-backed shared memory mapping
• スナップショットや fork のコストにも影響

解決すべき課題（永続化）

• 課題
• Groonga とは異なる明示的な永続化が必要
• 一時停止・再開
• バックアップ
• 障害からの復旧
• etc.�
• 解決案
• スナップショットとクエリログの組み合わせ
• スナップショットから復元
• 更新クエリを適用

解決すべき課題（シリアライズ）

• 課題
• シリアライズによる制約
• マルチコアを使い切れない
• Groonga はマルチスレッド・マルチプロセス対応
• 参照と更新を同時に実行できない
• Groonga は参照ロックフリー�
• 解決案
• スループットの向上
• メモリ管理や排他制御による無駄をなくす
• fork による並列化
• 重いクエリを実行するときに fork を使う
• 参照クエリは子プロセスにまかせる

まとめ + α

まとめ + α

• 今回 Grnxx について話したこと
• ほとんどインメモリ
• 基本はシングルスレッド・シングルプロセス
• リソース管理の手間を省いて効率化�
• 次の機会に話したいこと
• カラムストアとクエリの実行について�
• 今後の予定
• 試験的な設計・実装とベンチマーク
• 情報発信