一休.com Developers Blog

一休のエンジニア、デザイナー、ディレクターが情報を発信していきます

データベースの在庫の持ち方をビットで管理してる話

こんにちは、一休.comスパ(以下、「スパ」)の開発を担当しているshibataiと申します🙏 今回はスパのデータベースの在庫の持ち方で試行錯誤した話をさせていただきます。

背景

2024-03-29追記: 一休.comスパにおける在庫の特徴について

一休.comスパが扱う「在庫」は、「ある日付の特定の時間に対する空き枠」です。以降の説明では、スパ施設ごと、日付ごと、また時間ごとに増えていく「在庫」をいかに効率よく扱うかについて説明しています。

詳細については次のスレッドも参照してください！

現在の実装

スパは予約を受け付けるために在庫の管理をしてます🎁 データベースで在庫テーブルを持っていますが、ベタな管理をしています。 特定の施設・日・在庫の数を00:00をt0000とみなして15分おきにt0000・t0015..t2345まで格納してます🤔 在庫テーブルのイメージは以下です。

shop_id inventory_id inventory_date t0000 t0015 (省略) t1300 t1315 (省略) t2345
1 1 2024-01-01 0 0 ... 1 0 ... 0
1 2 2024-01-01 0 0 ... 0 1 ... 0

この設計は在庫の調査時に在庫数を確認しやすいのですが、レコード挿入時にtxxxの形にしたり、描画時にtxxxをtimeに変換する必要があったりと、実際に在庫を含めた描画を行う処理に難ありでした😞 チーム内で相談した結果、検索で描画する際は時間の配列(例: ['10:00', '11:15', '12:45'])を圧縮したビットを使うようにしました。

shop_id inventory_id inventory_date timeBits1 timeBits2
1 1 2024-01-01 1 0
1 2 2024-01-01 64 2

具体的な実装は後述しますが、カラムをビットで管理する場合のメリット・デメリットは以下です。

【メリット】

  • あるスパンごとのカラムを大量に持たずにビットの表現で圧縮できるのでデータ容量を抑えることができる
  • 動的にカラムを決めるために一般的にオーバーヘッドの大きいと言われるリフレクションを使わなくていいため、ビット値を用いると比較的高速に検索可能
  • 施設単位やプラン単位などで在庫有無をサマライズしたい時、ANDやOR検索で柔軟な条件指定が可能

【デメリット】

  • テーブルをSELECTで検索するだけでは状態がわからない(値を変換しなければならない)ため、デバッグやクエリ構築の難易度が上がる
  • ビット値と時間の配列の間を相互変換するライブラリの用意が必要
  • ビット値はBIGINT型でも桁溢れする場合があるので、Bit1とBit2といったようにある部分で分割する検討が必要

以下からはビット演算の仕組みと、実際にどういうイメージで検索するかを説明します👀

ビット演算とは？

データをビット列(0 or 1で構成される)とみなして演算します。 メリットは、値に対してANDやOR検索ができることです。 例えば1/2/3をビット列で表した場合、00000001/00000010/00000011です。 1と2でビットOR演算を行うと、

   00000001
OR 00000010
-------------
   00000011

各ビットを縦に見て、少なくとも一方に1がある場合、結果のそのビット位置は1になるので、演算結果は10進数の3です。 実際にSQLServerで検索する際にAND演算を使う例を出すと、

CREATE TABLE Example (
  Bits INT
);

INSERT INTO Example(Bits) VALUES (3);
SELECT * FROM Example　WHERE Bits & 1 = 1; // Bits列の値と1のビットANDが1に等しい行を選択するのでヒットする
SELECT * FROM Example　WHERE Bits & 2 = 2; // Bits列の値と2のビットANDが2に等しい行を選択するのでヒットする
SELECT * FROM Example　WHERE Bits & 4 = 4; // 3（00000011）と4（00000100）はそれぞれに1が立っている位置が違うのでヒットしない

Pythonの代表的なORMであるSQLAlchemyを使う場合は以下のように書けます。

query.filter(Example.Bits.op("&")(bits1) == bits1)

実装例

ビット演算で在庫管理するには、たとえば次のように実装します。

  1. INSERT INTO Example(Bits) VALUES (n);の nに相当する値を在庫がある時間帯からビットへ変換して格納
  2. 検索時に時間をquery.filter(Example.Bits.op("&")(bits1) == bits1)として検索し、取得できたBitsカラムを時間帯に変換

なので、デメリットでもお伝えしましたとおり、ビット値と時間の配列の間を相互変換するライブラリの用意が必要です。 今回は先人達が実装してくれていたライブラリが社内にあったため、ありがたく使わせていただきました。

変換の考え方

例えば00:00-23:45で15分スパンとしたとき、1日は96区切りです。 10:00 ~ 19:00に在庫が存在するを表現すると以下のようになり、96bitsで時間が有効であれば1が立つと考えることができます👼 要件によっては00:00で終わりではなく、24時以降の表現をしたい場合もあるので、1日の区切り数やスパンをどうするかはプロジェクトの定義によって決めて下さい。

    |0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  |
    ||   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
    <000000000000000000000000000000000000000011111111111111111111111111111111111100000000000000000000>

1に関して、96bits(12bytes)のままではバイトオーダーの都合上扱いづらいので16bytesに変換すると、b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xf0\x00\x00'で、先頭~8bytesまでと9~16bytesまでの値を取得できます。これをbits1とbits2カラムとして格納します。 変換の一部をPythonでの実装してみると以下です。 実際の社内では複数のユースケースに対応できるように、より複雑なことをしてますが、社内のソースコードをそのまま載せられないのでサンプルコードのみです🙏

bits = '000000000000000000000000000000000000000011111111111111111111111111111111111100000000000000000000'
bytes_array = int(bits, 2).to_bytes(16, byteorder='big')
bits_int1 = int.from_bytes(bytes_array[0:8], byteorder="big", signed=True)
bits_int2 = int.from_bytes(bytes_array[8:16], byteorder="big", signed=True)

print(bits_int1) # 0
print(bits_int2) # 72057594036879360

2.に関しても逆の処理を行えば良く、検索したい時間をビットに変換し、データベースから時間帯をAND演算で取得。取得できたbits1/bitsをbytesに変換しつなげて、96bitsを復元します。 あとは0と1の状態によって、00:00から15分おきに繰り返しで判定することで時間帯を復元できます🍿 変換の一部をPythonでの実装してみると以下です。

bits_pair = (0, 72057594036879360)
bytes_int1 = bits_pair[0].to_bytes(8, byteorder="big", signed=True)
bytes_int2 = bits_pair[1].to_bytes(8, byteorder="big", signed=True)
reconstructed_bits = format(int.from_bytes(bytes_int1 + bytes_int2,  byteorder="big"), '096b')
print(reconstructed_bits) # 000000000000000000000000000000000000000011111111111111111111111111111111111100000000000000000000が復元される

以上が相互変換するイメージでございます。

最後に

時間をビットで持つ実装の他にもチューニングしたため、単体での評価はできていませんが、今回の取り組みを通してスパの検索画面の描画は従来から1/3~1/5程度時間短縮することができました。 よって、ビットでの管理は今回スパの課題の解決手段としてはとても有効だったと考えます。 前述の通りデメリットもありますが、課題の解決手段の一つとして参考になれば幸いです！

一休では、ともに試行錯誤しながらよいサービスを作ってくれる仲間を募集しています！

hrmos.co

カジュアル面談も実施していますので、ぜひお気軽にご連絡ください！ www.ikyu.co.jp

Copyright© 株式会社一休®, All Rights Reserved.