1 of 23

Grnxx の紹介

矢田 晋

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

2 of 23

Grnxx とは

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

3 of 23

発表の内容

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

4 of 23

開発の経緯

5 of 23

開発の経緯(概要)

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

6 of 23

開発の経緯(背景)

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

7 of 23

開発の経緯(目標)

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

8 of 23

新設計の利点

9 of 23

新設計の利点(一覧)

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

10 of 23

新設計の利点(インメモリ化)

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

11 of 23

新設計の利点(インメモリ度)

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

12 of 23

新設計の利点(メモリ管理)

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

13 of 23

新設計の利点(フラッシュ)

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

14 of 23

新設計の利点(シリアライズ)

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

15 of 23

新設計の利点(データ構造)

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

16 of 23

解決すべき課題

17 of 23

解決すべき課題(一覧)

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

18 of 23

解決すべき課題(ID とオフセット)

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

19 of 23

解決すべき課題(大規模化)

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

20 of 23

解決すべき課題(永続化)

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

21 of 23

解決すべき課題(シリアライズ)

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

22 of 23

まとめ + α

23 of 23

まとめ + α

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