Google カレンダーのためのデータベース設計チュートリアル

 (kb.databasedesignbook.com)
13 ポイント 投稿者 GN⁺ 2024-07-25 | 1件のコメント | WhatsAppで共有
  • Google Calendar クローンの予定機能を例に、テーブルから作り始めるのではなく、論理モデルを完成させてから SQL スキーマへ移す設計フローを示す
  • 中核となる方法は、User、DayEvent、TimeEvent、Timezone のような アンカー(anchor) を先に見つけ、属性と 1:N・M:N リンクで要件とカーディナリティを検証すること
  • 予定は終日イベントと時間ベースイベントに分かれ、時間ベースイベントでは開始・終了の ローカル時刻とそれぞれの Timezone を保存し、タイムゾーン変更の可能性まで扱う
  • 繰り返し予定は周期、間隔、月次の繰り返し方式、終了条件、曜日リンクで表現し、画面レンダリングと個別インスタンスの変更のために DaySlot と TimeSlot を別アンカーとして置く
  • 最終的な物理設計は「アンカーごとに 1 つのテーブル」を基本としつつ、DayOfTheWeek はテーブル化しないため、6 個のアンカーテーブルと 2 個の M:N リンクテーブルなど、合計 8 個の SQL テーブルに整理される

設計アプローチ: 先に論理モデルを作る

  • 目的は、Google Calendar クローンのカレンダー機能を対象に、実際のプロジェクトに近い データベーステーブル設計の過程を示すこと
  • 全体の流れは、保存すべきカレンダーデータを説明する 完全な論理モデルを先に作り、そのモデルを物理テーブル構造へ移す順序
  • 前半では、特定のデータベースに縛られない論理モデルを扱う
    • MySQL、Postgres、従来型のリレーショナルサーバー、NoSQL、クラウドデータベースから独立してビジネス要件をモデル化する
  • 後半では、論理モデルを物理テーブルへ変換する 1 つのアプローチを示す
    • 要件が非常に厳しくないシステムでは、有効な設計方式と見なせる

問題範囲: Google Calendar の中核的な予定機能

  • 対象システムは マルチユーザーシステムであり、ユーザー関連データは最小限だけモデル化する
  • イベントにはタイトル、説明、場所のような属性があり得るが、最も複雑な部分は 時刻と日付である
  • モデル化対象のイベントには、次の違いが含まれる
    • 終日イベントと時間ベースイベント
    • 繰り返しイベントと非繰り返しイベント
    • 複数日にまたがる終日イベント
    • タイムゾーンが紐づき、開始・終了時刻が互いに異なる日付または異なるタイムゾーンにあり得る時間ベースイベント
  • 繰り返しイベントには次の形式が含まれる
    • 毎日、または N 日ごとの繰り返し
    • 毎週特定の曜日に繰り返し、2 週間以上の間隔も可能
    • 毎月特定の日、または特定週の曜日に繰り返し
    • 毎年繰り返し
    • 永久に、特定の日付まで、または特定回数だけ繰り返し
  • 繰り返しイベントの特定インスタンスは、別の日付・時刻へ移動したり削除したりできる
  • すでに一部のイベントが過ぎた後でも、繰り返し予定そのものを変更できる必要がある

アンカー、属性、リンクで要件を表現する

  • モデリングは、まず アンカー(anchor) を見つけるところから始める
    • アンカーとは User や Event のように数えられ、データベースに追加できる対象のこと
    • “There are 200 Users in our database”、“When this button is clicked, a new DayEvent is created” のように自然に言えるなら、アンカーと見なせる
  • 属性は、アンカーに関する実際の情報を保存する
    • User にはメール属性を置く
    • DayEvent には名前、開始日、終了日を置く
    • 単一日のイベントも開始日と終了日を同じ値として保存し、複数日イベントと同じ構造で扱う
  • 2 つのアンカーが関係を持つ場合は、属性ではなく リンクを使う
    • 「どの User が DayEvent を作成したか」は、DayEvent の属性に User ID を直接入れる論理属性ではなく、User と DayEvent の間のリンクである
    • リンクは 1:N、M:N、1:1 のカーディナリティを使い、2 つの文で双方向の意味を検証する
  • User と DayEvent の間には 1:N リンクがある
    • User は複数の DayEvent を作成できる
    • DayEvent は 1 人の User によって作成される

時間ベースイベントと Timezone の処理

  • 時間ベースイベントのために Timezone と TimeEvent アンカーを追加する
  • Timezone モデルはチュートリアル目的で最小化されており、人が読める名前だけを属性として持つ
    • 例の値は Europe/Kyiv
    • 実際のタイムゾーン定義には UTC オフセット、夏時間の有無、DST の開始・終了、DST 適用時の UTC オフセット、過去の定義、有効・廃止の有無などが必要だが、別課題として残す
  • TimeEvent には名前、開始ローカル日付・時刻、終了ローカル日付・時刻を置く
    • 例の値は 2024-01-14 12:30、2024-01-14 13:15
  • 時刻は UTC だけを保存するのではなく、ユーザーが入力したローカル時刻として保存する
    • 例として、2058 年 9 月 6 日 09:30〜11:00 の Cologne 時間のビリヤードゲームは、その時点の UTC オフセットを現在は知ることができないため、ユーザーが入力したそのままを保存する必要がある
    • その後、現地の法律が変わった場合は、それに合わせて調整できる必要がある
  • TimeEvent は開始タイムゾーンと終了タイムゾーンについて、それぞれ Timezone と 1:N リンクを持つ
    • 飛行機のチケットの例のように、Amsterdam から London へ向かうフライトは、出発時刻と到着時刻が互いに異なるタイムゾーンにある場合がある
    • ほとんどの時間ベースイベントは開始・終了タイムゾーンが同じだが、一般的なケースに対応するため、両方を常に指定する

繰り返し終日イベントのモデリング

  • 繰り返し終日イベントは、DayEvent に繰り返し関連の属性とリンクを追加して表現する
  • 繰り返し頻度は either/or/or 型の属性として置く
    • 可能な値は daily、weekly、monthly、annually
    • 値が設定されていなければ、非繰り返しイベントと見なす
  • 繰り返し間隔は「繰り返しイベントである場合」にのみ意味を持つ整数属性である
    • 例の値は 2
    • 2 日ごと、2 週間ごと、2 か月ごとのような意味で使われる
  • 月次の繰り返しには別の選択属性がある
    • 同じ日に繰り返す same_day
    • 元の日付と同じ週の曜日に繰り返す same_weekday
  • 週次の繰り返しにおける特定の曜日は、文字列配列属性として扱わず、DayOfTheWeek アンカーと M:N リンクでモデル化する
    • DayOfTheWeek ID の例は Mon、Tue、Wed、Thu、Fri、Sat、Sun
    • DayEvent は複数の DayOfTheWeek に発生し得て、DayOfTheWeek は複数の DayEvent を含み得る
  • 繰り返し終了条件も属性として置く
    • forever
    • until_date
    • N_repetitions
    • until_date の場合は終了日属性を追加する
    • N_repetitions の場合は繰り返し回数属性を追加する

レンダリングと個別インスタンス変更のための Slot

  • 繰り返しイベントを元イベント 1 つだけで保存すると、特定の週画面に表示するイベントを探すクエリが複雑になり得る
  • 画面レンダリングと繰り返しイベントの個別変更のために Slot の概念を導入する
    • DaySlot は特定の日付の終日イベントインスタンスを表す
    • TimeSlot は特定の日付と時刻の時間ベースイベントインスタンスを表す
  • DaySlot には日付とスキップ有無を置く
    • 特定スロットの日付は変更できる
    • 特定週の会議をキャンセルする場合、その DaySlot を skipped としてマークできる
  • DayEvent と DaySlot は 1:N リンクを持つ
    • 1 つの DayEvent は複数の DaySlot を生成できる
    • DaySlot は 1 つの DayEvent に対応する
    • 非繰り返し DayEvent にも常に DaySlot を作成し、レンダリングコードを単純化する
  • 無限繰り返しイベントには、スロット生成範囲の問題がある
    • 誕生日のように毎年永久に繰り返すイベントは、100 年のような任意の上限までスロットを作成できる
    • あるいは、ユーザーが遠い未来のカレンダーページを要求したときにオンデマンドで作成することもできる
  • 日付計算には注意が必要である
    • 2 月 29 日の誕生日
    • 毎月 31 日に発生する月次イベント
    • このような場合、使用を禁止するのか、1 日前または後ろへ移すのかといった決定が必要になる

TimeSlot とタイムゾーン

  • 繰り返し時間ベースイベントにも、終日イベントと同じアプローチを適用して TimeSlot アンカーを置く
  • TimeSlot は特定イベントの特定日付・時刻インスタンスに該当し、繰り返し TimeEvent は複数の TimeSlot に対応する
  • TimeSlot の属性は、開始ローカル日付・時刻、終了ローカル日付・時刻、スキップ有無である
  • 特定の TimeSlot は別の日にも移動できるため、開始・終了時刻情報を別に保持する
  • TimeSlot も開始タイムゾーンと終了タイムゾーンそれぞれについて Timezone と 1:N リンクを持つ
  • TimeEvent と TimeSlot の間には 1:N リンクがあり、非繰り返し TimeEvent にも TimeSlot を生成する

完成した論理モデル

  • ここまで定義したアンカーは合計 7 個である
    • User
    • Timezone
    • DayEvent
    • TimeEvent
    • DayOfTheWeek
    • DaySlot
    • TimeSlot
  • 属性は、User のメール、Timezone の名前、DayEvent の名前・開始日・終了日・繰り返し情報、TimeEvent の名前・開始・終了ローカル時刻、DaySlot と TimeSlot の発生時点と skipped 有無で構成される
  • リンクは合計 10 個に整理される
    • User と DayEvent、User と TimeEvent
    • Timezone と TimeEvent の開始・終了タイムゾーン
    • DayEvent と DayOfTheWeek、TimeEvent と DayOfTheWeek
    • DayEvent と DaySlot、TimeEvent と TimeSlot
    • Timezone と TimeSlot の開始・終了タイムゾーン

SQL テーブルへ移す

  • 物理設計では、教育目的で アンカーごとに 1 つのテーブル戦略を使う
  • 論理モデルには 7 個のアンカー、21 個の属性、10 個のリンクがある
  • 一般的にはアンカー数と M:N リンク数を足して 9 個のテーブルになるが、最終設計では DayOfTheWeek を特殊に扱い、物理テーブルを作らない
  • 最終的な SQL テーブルは合計 8 個である
    • users
    • timezones
    • day_events
    • time_events
    • day_slots
    • time_slots
    • day_event_dows
    • time_event_dows
  • 1:N リンクは N 側のテーブルに外部キー的なカラムとして入る
    • day_events.user_id
    • time_events.user_id
    • time_events.start_timezone_id
    • time_events.end_timezone_id
    • day_slots.day_event_id
    • time_slots.time_event_id
    • time_slots.start_timezone_id
    • time_slots.end_timezone_id
  • M:N リンクは別テーブルとして作る
    • day_event_dows は DayEvent と曜日をつなぐ
    • time_event_dows は TimeEvent と曜日をつなぐ
  • 物理型は論理型に対応させて選ぶ
    • 文字列は VARCHAR
    • 日付は DATE
    • ローカル日付・時刻は DATETIME
    • yes/no は TINYINT UNSIGNED
    • 条件付きでのみ意味を持つ絡み合った属性は NULL 許容型を使う
  • NULL と sentinel 値は、論理モデルではなく 物理スキーマの概念として扱われる

インデックスと省略された属性

  • 例示の SQL スキーマには、熟練したデータベース開発者から見て必要なインデックスが抜けている
    • たとえば day_events.user_id にはインデックスが必要になる場合がある
  • どのカラムまたはカラム組み合わせにインデックスを置くかは、アプリケーションがテーブルをどのように検索するかによって異なる
  • インデックスの話題については Use The Index, Luke を参照できる
  • 論理スキーマを説明する間、一部の属性は似たパターンのため省略されている
    • ユーザー名
    • ユーザーパスワードハッシュ
    • イベントの場所
    • 招待者リスト
  • 省略されたデータ要素は、同じ方法で論理モデル表に追加したうえで SQL スキーマに反映できる

全体の手順

  • ビジネス問題を説明する自由形式テキストから始める
  • アンカー一覧を作成する
  • 属性一覧を作成し、属性の意味を質問形式で明確に書く
  • リンク一覧を作成し、カーディナリティが合っているかを文で確認する
  • 必要であれば、論理モデルをもとにグラフィックスキーマを作る
  • テーブル名、カラム名、物理データ型を埋めて物理モデルを作成する
  • 前段階の情報を使って CREATE TABLE 文で SQL スキーマを作成する
  • データベースサーバーにスキーマを投入し、タイプミスを直してから再投入する
  • 論理モデルをチームと共有する

関連記事

1件のコメント

 
GN⁺ 2024-07-25
Hacker Newsのコメント

  • 自分のカレンダーの任意のイベント1件をiCalendarにシリアライズすると約740バイトで、午前9時〜午後5時まで15分ごとにイベントが入っている極端に忙しいカレンダーでも、1年分全体で11,680項目、約8MBにすぎない。
    なので、スキーマを設計するよりも、カレンダーは単に順次スキャンで実装したほうがはるかに良い問題に見える。iCalendarパーサを最適化して、ダンプされたイベント範囲をGB/s級のスループットでなめられるようにすれば、上の最悪ケースでも1桁ミリ秒以内でスキャン可能。
    悪いデータモデルが多くのユーザーに広まったあとで変更・拡張するより、パーサ最適化は一度解けば済むはるかに単純な問題だし、どうせ新しいデータモデルの最初の作業もiCalendarのインポート/エクスポートになる可能性が高いので、かなり良い折衷案に思える

    • するとSQLのBETWEEN ... AND ...のような範囲検索をまた作り直すことにならないか？ ユーザー1、2、3のイベントを探すのも同じ。
      実際のアプリケーションなら、すでにリレーショナルデータベースにユーザーアカウントのようなものがあるはずで、いきなりディレクトリ内のイベントをスキャンして、その結果をデータベースレコードと結び付けなければならなくなる。
      特定のアプリケーションでは合っているかもしれないが、データベースが本当に得意な特定の作業があり、だからこそ良い選択になる。適切なインデックスがあれば、同等かそれ以上のスループットも可能だろう。イベント用の賢いディレクトリ構造を作らない限りは。だがそれは実質的に1次元のインデックスと同じで、データベースでは複数次元や次元の組み合わせに対してインデックスを作れる。
      結局その通りで、トレードオフの問題だ
    • iCalendarは、カレンダーデータへの高速アクセスのための保存形式ではなく、交換形式として設計されている。
      形式に古さが出ていて、XML/JSONが“流行る”前に設計されたことがわかる。
      参考: https://en.wikipedia.org/wiki/ICalendar
    • DBMSなしでもできるにしても、データには依然として良いスキーマが必要で、それがiCalendarレコードの束であってはいけない。たとえば、安定したユーザーIDの代わりに変更可能で重複しうるメールアドレスしかない
    • そういうアプローチは、記事で述べられている無限のタイムスロット問題にも、よりすっきりした解法を与えられそうだ

  • アプリケーションで繰り返し予定を扱う記事だが、個人的には目が覚める思いだった。ぜひ読むことを勧める: https://github.com/bmoeskau/Extensible/blob/master/recurrenc...

    • 元記事の助言とこの記事の助言が互いに逆なのが興味深い。
      元記事は各日付に常にタイムゾーンを保存しろと言い、リンク先の記事はすべてUTCに変換しろと言っている。この点では元記事に同意する。
      元記事は各イベントごとにデータベース行を生成しろと言い、リンク先の記事はそうするなと言っている。この点ではリンク先の記事に同意する

  • 面接でいちばん大きく失敗したのは、シンプルな予約システムを作りつつ繰り返し予約まで扱わなければならなかったときだった。
    大学に入ったばかりの頃以降、コードで何かを成し遂げようとして、あれほど道に迷って混乱したことはなかった。今でも日付/時刻関連の作業をしなければならないと身構えてしまうし、理由はわからないが頭の中でうまく噛み合わない

    • 「予約システムを設計せよ。ただし繰り返し予約も含む」という設計問題は、「文字列リストをソートする関数を書け。ただし任意のUTF-8文字列と、あらゆるロケールでのアルファベット順の慣習を守らなければならない」に近い。
      見た目は単純だが、現実世界で一般に動くようにしようとすると不可能なくらい複雑になる問題だ
    • あまり自分を責めなくていい。CMSのカレンダーを改善して、はるかに多くの機能をサポートしろという仕事を任され、ほとんど食い尽くされそうになったことがある。その時点ですでに経験は8年ほどあった。
      これは一見してわかりにくいほど難しい問題で、優れたデータモデリング能力が必要だ

  • システムをモデリングする能力は過小評価されている。新しいドメインでは、システムの静的構造、つまりクラスモデルと、動的な振る舞い、つまりユースケースの両方を捉えるために、まず問題全体の分析から始めるべきだ。
    いきなり静的なデータベースモデルに飛び込むと、動的な振る舞いを見落としやすい。こうした単純なCRUDアプリでは問題ないかもしれないが、より複雑なシステムでは大きなミスになりうる

    • データサイエンティストとして、見た目には単純な「スキーマをどう作るか」という面接質問に、その場でかなり苦労したことが何度かある。
      最後に覚えている質問は、クーポン付きの商品テーブルをどう作るかというものだった。最初はテーブル2つで済むだろうと思ったが、履歴も保持しなくてはいけないのでは？ となる。すると商品とクーポンごとに日付/時刻を入れて更新しなければならない。今度はテーブルのインデックスも考えなければならないし、割引価格を得るためのJOINが良い方法なのかも悩み始める。ほとんどのクーポンは1人1回しか使えないが、これをいったいどう実装するのか？
      たぶん単純な商品 + クーポンテーブルだけを求めていたのだろうが、一人で延々と狂ったように掘り下げてしまう
    • こうした分析の成果物はどんな形になるのか？ 参考になるリンク、たとえば文書例や書籍の章のようなものがあれば知りたい

  • モデリングを示すにはうまく選ばれたドメインで、良い入門記事だと思う。
    「anchor」という用語は少し変に感じるが、説明は実際の錨のようにとても具体的で地に足がついており、十分に通じているように思える。
    質問によって属性を定義するという概念は堅実だ。自分たちがどんな問いに答えようとしているのかを定義しないまま、最小限の列名/属性名にすぐ飛びつくことがあまりに多く、その結果、顧客の頭の中にある曖昧さを取り除けない。質問ベースの属性定義は、素早く明確さを得る良い方法だ

    • 「anchor」という用語は、Anchor Modeling(https://en.wikipedia.org/wiki/Anchor_modeling)から受け継いだものだ。「Entity」は広く使われているが、不要な含意や前提を持ち込みうるので使いたくなかった。
      そのうえ、この用語はひどく過積載されている。コンピュータサイエンスでは、実質的にあらゆるものがオブジェクトかエンティティだからだ。
      質問によって属性を定義するという概念が堅実だという反応は、このアプローチの妥当性にとって重要な裏付けになる

  • タイムゾーンは、特に切り替えの前後で頭を悩ませる
    タイムゾーンが夏時間で1時間進み、標準時に戻るときに1時間戻ると仮定しよう
    時刻が1時間先に飛ぶと、1時間のイベントが画面上では2時間にまたがっているように見えることがあり、その2時間目は到達不能、あるいは存在しない
    時刻が1時間戻ると、1時間のイベントが2時間に見えたり、0時間に見えたりすることがある
    タイムゾーンは人間が作った仕組みなのだから、値をハードコードしてはいけない。いつか変わる

    • 移動まで考慮して時間を追跡すると、さらに面白くなる。私が最初に経験したのは、何日も海上にいる船で時間追跡をしていたときだった
      タイムゾーンを双方向に何度もまたぐこともできるし、日付変更線を越えることもあるため、現地の開始日時が現地の終了日時より後になることさえある
    • カレンダーをタイムゾーンなしで全部UTCにしよう、という意味だろうか？ タイムゾーンが人間の作ったものだという点には同意するが、それはより良い地域ごとの整理のために作られたものだ。私は世界中の顧客と仕事をしていて、みんなタイムゾーンを使っている。個人的にはかなり無茶な要求に見える
      むしろ、いまだに夏時間の概念を使っている一部の地域で、それをなくすことに注力したほうがいい。特に次の切り替え後の予定を立てるとき、タイムゾーン間の混乱を最も引き起こすからだ

  • イベントに日付を2つ保存したいとは思わない。イベントの開始時刻と継続時間を保存するほうが簡単だ
    こうするとイベント更新ロジックが単純になる。終了時刻はいつでも開始時刻と継続時間をもとに計算できる

    • 正直に言えば、開始・終了・継続時間の3つを全部保存して、目的に応じて必要なものを使えばいい。代替表現を同期させる単一の入力/更新ポイントだけ用意すればよい
    • そのやり方はデータベース性能の問題になるかもしれない。クエリのたびに継続時間をその場で計算しなければならない
    • 逆も同じではないか？ 開始と終了があれば、継続時間はそのまま計算できる

  • 以前、繰り返し予定のあるカレンダーアプリケーションを手がけたことがある。かなり調査した末に、これを表現するためにRRulesを使うことに決め、とても満足していた。その初期の作業はエージェンシーにいた頃のことだ
    後になってその会社に正社員として加わったところ、別会社の契約者がRRulesを取り除き、イベントインスタンスをその場で作ったり消したりする方式に変えていたのを見て驚いた。障害耐性がほとんどなく、別の作業もしている、ときどき失敗するスクリプトが新規イベントの作成に失敗することがあった。すると毎月の繰り返しイベントで欠ける月が発生する
    多くの検討と調査を経て作ったものを、誰かがそれほどの労力もかけずに取り除いたことがあまりにも歯がゆかった。その会社に数週間いるだけで、CEOがエンジニアリングチームに自分の思いどおりの、誰も使わない機能を作り続けることを期待しているのが分かったが、採用市場の不確実さのため、悲しいことに2年いた
    ついでに言えば、後で検索してみると、GlassdoorにはCEOが書いたのが明らかな偽レビューが、どれも同じ文体で悪いことを一言も書かずに並んでいて、本当にやりきれなかった。私も、そこで働いていた何人もの知人も彼を嫌っていたが、それでもその会社で自分の最高のエッセイを何本か書けたことだけは慰めだ。CTOも救いようがなかった

  • 以前、ローコードプラットフォーム向けのカレンダーおよびリソース管理バックエンドを実装したことがある
    そのコントロールは非常に高度にカスタマイズ可能で、日次・月次・年次など複数のビューに加えて、リソースビューまで選べた。カスタムグループでリソースを予約でき、プラグインごと、リソースIDごとなどにまとめられた。データソースに「plugins」を定義し、開始/終了カラム、タイトルカラム、リソースカラムも指定していた。リソースは外部キーや1:1関係から来ることもあれば、「子」データソースの1:N関係や、同じデータソース/テーブルから来ることもあった
    また、月次・週次・特定曜日・日次など、さまざまな予定シリーズも実装し、どのカラム値をコピーするかも選べるようにしていた。予定の衝突も処理していて、同じリソースを予約したときだけ衝突と見なすこともできた。予定の前後には、別の予定を入れられないバッファも設定可能だった
    ヨーロッパのタイムゾーンや夏時間/冬時間のようなもののせいで、ときどき難しい部分もあったが、かなり楽しい仕事だった

  • Google Calendarに欲しいのは、カレンダー自体の変更ログだけだ。お願いだからデータベースにこれを追加してほしい