🎏

ビットフラグで軽量化する1対多のデータモデル

に公開

こんにちは!
ourly株式会社 執行役員CTO(@tigers_loveng)の相澤です。

プロダクトを開発していると、「1対多の関係を持つデータの関連付け」 に必ずと言っていいほどぶつかります。大抵は中間テーブルを設けて1対多の関係を作ることが鉄板ですが、レコード数が多くなると N 倍に膨れ上がる中間テーブル がパフォーマンスのボトルネックになることもしばしばあります。

そこで今回は、ourly でも実戦投入している ビットフラグ(Bitwise flags) で 1 カラムにまとめてしまうアプローチ を紹介します。メリット・デメリット、適用できるユースケース、実際のモデル実装までまとめたので、同じ悩みを抱える方の参考になれば幸いです。


背景

一般的に1対多のデータ構造を正規化する場合は (親テーブル) : (中間テーブル) : (子テーブル) の3テーブル構成を取ります。

例えば、親テーブルを本を管理するbooksテーブル、子テーブルを本のカテゴリを管理するcategoriesテーブルだとすると以下のように表せます。

シンプルで分かりやすいのですが、

  • 紐付けるカテゴリがN個になると、中間テーブルのレコード数がN倍に増える
  • JOIN が必須になるため クエリが重くなる可能性がある
  • ループ処理でカテゴリを参照する場合に、N+1問題が起きる可能性がある

といった気をつけなければいけない点もあります。

ビットフラグ方式とは

ビットフラグは整数の "ビット" をフラグとして扱う手法です。たとえば 5 つのカテゴリを持つ本を例にすると、

カテゴリID ビット位置 ビット値
1 2^0 (=1) 00001
2 2^1 (=2) 00010
3 2^2 (=4) 00100
4 2^3 (=8) 01000
5 2^4 (=16) 10000

カテゴリ 1・3・4 を紐づけたい場合、ビット位置の 0・2・3 (2^0 + 2^2 + 2^3 = 13) の位置にフラグを立てた、01101(10進数で13) をbooksテーブルの category_flags カラムに保存すれば OK です。

-- 例: id=42 の本にカテゴリ 1,3,4 を付与
UPDATE books SET category_flags = 13 WHERE id = 42;

他にも特定のカテゴリを含む本を取り出す際はビット演算を利用します。

-- カテゴリ3(ビット4)を含む本を取り出す
SELECT * FROM books WHERE category_flags & 4 > 0;

ビット演算については以下記事で分かりやすく解説されています。

https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/kind_basic_theory/bitwise-operation/

ビットフラグは身近な例では、Unix/Linuxのファイルパーミッション管理の仕組みにも利用されています。

https://www.tohoho-web.com/linux/file-system.html#permissions

メリット

  • データストレージの容量圧迫を遅延させることができる: 中間テーブルを利用する場合でも、N行のデータが1行で済む
  • クエリのパフォーマンス悪化を防げる: 1テーブルで親と子のデータを管理する場合、JOINが不要になるため、シンプルなWHERE句だけで済む
  • 移行コストが低い: 関連付け対象のデータが増えでも「最上位ビットを 0 埋め」するだけでDBスキーマ変更不要
    • 後述するようにデータ型ごとに上限があるため、管理個数を増やすためにデータ型を変更する場合はもちろんマイグレーションが必要になる
  • キャッシュしやすい: 整数1カラムなのでRedisなどキー・バリューにもそのまま載せられる

デメリット(というか注意点)

  • 可読性: 生データだけ見ても意味が分からない
  • 削除運用が難しい: 一度使ったビットは基本的に削除や再利用ができない。不要になっても "0" に戻すだけ...
  • 列挙数に上限: INT(32bit)なら31 個、BIGINT(64bit)なら63 個が上限
  • リレーショナル制約を張れない: 外部キー制約やON DELETE CASCADEが使えない
  • トランザクションの競合が起きやすい: 1カラムで制御するため、複数の処理で更新が行われる場合競合が起きやすい

ourlyでの実例

弊プロダクトでは、ユーザーごとに、ID/Pass, Google OAuth, SAMLなどの認証方法を割り当てることが可能で、その割り当てにこのビットフラグ方式を適用しています。
具体的にはモデルに以下のような定数定義を行い、ユーザーの認証方式をチェックするようなイメージです(実際のプロダクトコードとは多少異なります)。

AUTHENTICATION_TYPE_FLAGS = {
  id_pass:      0b00001,  # ID/Pass
  google_oauth: 0b00010,  # Google OAuth
  saml:         0b00100   # SAML SSO
}.freeze

# 例)ユーザーがGoogle OAuthの認証を許可されているか
(authentication_type & AUTHENTICATION_TYPE_FLAGS[:google_oauth]).positive?

また、特定条件下のユーザーは複数の認証方式を許可されているケースもありますが、生データだけではどの認証方式が許可されているかぱっと分からないため、モデルのインスタンスメソッドとして変換メソッドを用意しています。

# 0b00110 → [:google_oauth, :saml]
def readable_authentication_type
  AUTHENTICATION_TYPE_FLAGS.filter_map { |key, bit| key if (bit & authentication_type).positive? }
end

ビットフラグ方式の採用理由

最初はいつも通り、中間テーブルで1認証方式ごとに1行を追加していく方式を考えていたのですが、当時関わりのあった強いエンジニアにアドバイスをもらい、あらためて考えてみると以下の点でビットフラグの方が良いと判断しました。

  • 1ユーザーにつき最低でも1行以上のデータが必要になり、ユーザー数が増えるとその分データ量が増える
  • ユーザーの認証方式は頻繁に更新するものではなく、更新も管理画面の特定の箇所でのみ行う仕様となっている
  • ログイン処理の際に毎回参照するデータになるので、クエリのパフォーマンスを優先的に考慮した構造にしたい
  • 認証方式の種類は限られており、少ない。また、弊プロダクトの仕様上、LINEや𝕏などのSNSログインはニーズがほぼないため増減もあまりない。

整理すると以下のようなシチュエーションではビットフラグ方式による恩恵を受けやすいと考えています。

シチュエーション 理由
選択肢が 少数で増減が少ない ビット上限&マイグレーション不要の恩恵が大きい
読み取りが多い JOIN 排除/軽減によるレスポンス改善が見込める
レコード数が非常に多い 中間テーブルの膨張を防げる

逆に以下のようなケースでは、避けた方が良いかもしれません。

  • 頻繁に追加・削除されるようなデータ
  • 関連付けの際に他の情報(ソート順やメタデータ)を持たせたいデータ

まとめ

ビットフラグは「中間テーブルを無くしたい、もしくはデータ量を抑えたい & 関連付けの対象データ増減が少ない」ケースで強力な武器になります。
ourlyでもユーザー数 × 認証方法の組み合わせを 1カラムに凝縮し、パフォーマンスと実装コストを両立できました。

一方で 変更頻度が高い or 関係が複雑 なドメインでは、中間テーブルの正規化のほうが結果的に健全なことも多いです。用途とライフサイクルを見極め、最適なデータモデリングを選びましょう!

それでは今回はこのへんで。最後まで読んでいただき、ありがとうございました!

ourly tech blog

Discussion