2023-01-09

『データ指向アプリケーションデザイン』を読んだー第II部分散データ 5~6章

エンジアリング book

こちらの続きです hiramekun.hatenablog.com

本はこちら

データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理

Amazon

5章レプリケーション
- リーダーとフォロワー
- レプリケーションラグにまつわる問題
6章パーティショニング
続き

5章レプリケーション

レプリケーションとは、ネットワークで接続された複数のマシンに同じデータのコピーを保存しておくことを指す。レプリケーションを行う理由は以下の通り。

レイテンシを下げる：データを物理的にユーザーの近くで保持するため
可用性を高める：一部に障害があってもシステムが動作し続けるようにするため
スループットを高める：読み取りのクエリを処理するマシン数をエスケースアウトせせるため

この章では、パーティショニングは考えずにレプリケーションについてまとめる

リーダーとフォロワー

データベースのコピーを保存する各ノードはレプリカと呼ばれる。全ての書き込みが、全てのレプリカに行き渡るようにするには、リーダーベースレプリケーションがよく使われる（別名アクティブ/パッシブ、マスター・スレーブレプリケーション。MySQL ではマスター・スレーブと呼ばれることが多い。MySQL :: MySQL 5.6 リファレンスマニュアル :: 17 レプリケーション）。動作原理は以下の通り。

レプリカのうち、一つはリーダーに指定される。データベースに書き込む場合、クライアントはリクエストをリーダーに送信する。
他のレプリカはフォロワーと呼ばれる。リーダーはデータを自身のストレージに書き込んだ後、その変更をレプリケーションログもしくは変更ストリームの一部として全フォロワーに送信する
各フォロワーはこのログをリーダーから受け取った後、その内容に従ってリーダー上で処理されたのと同じ順序で全ての書き込みを自身のストレージに行う。
クライアントがデータベースから読み取りを行う場合には、リーダー・フォロワー関係なく全てのレプリカにリクエストを送ることができる。

同期的か非同期的か

レプリケーションを行うシステムで重要なのは、レプリケーションが同期的に行われるのか、非同期的に行われるのかどうか。もし非同期である場合、書き込みが即時反映されないレプリカが存在する事になる。その一方で、同期型レプリケーションにも利点と欠点が存在する。

利点：フォロワーが持っているデータが最新であり、リーダーとの一貫性が保証される。
欠点：同期型のフォロワーが反応を返さなかった場合、リーダーは全ての書き込みをブロックするため書き込み処理ができなくなってしまう。

よって可用性を考えるのであれば、全てのフォロワーを同期型にするのは現実的ではない。実際に同期型レプリケーションを有効にするのであれば、複数のフォロワーのうち一つを同期型にして、残りは非同期型にするのが良い。もし同期型のフォロワーが利用できなくなった場合は、非同期型のフォロワーを一つ同期型に変更すれば良い。

また、全てのフォロワーを非同期にすることも頻繁にある。

利点：全てのフォロワーに遅延が生じていても、リーダーが書き込み処理を継続できる。
- 特にフォロワーが多い場合や、フォロワーが地理的に分散している場合は大きな利点となる。
欠点：リーダーに障害が発生した場合、フォロワーにレプリケーションされていない書き込みは全て失われる。

障害への対処

フォロワーの障害：キャッチアップリカバリ
- フォロワーは障害発生前に最後に処理したトランザクションをログから判断できるので、フォロワーはリーダーに接続し、接続が切れた後に生じた全てのデータ変更を要求できる
リーダーの障害：フェイルオーバー
- フェイルオーバー時の手順は複雑で、簡潔に以下の手順を踏む
  - フォロワーのいずれかをリーダーに昇格させる
  - クライアントは新しい書き込み先を新しいリーダーに設定し直す
  - 他のフォロワーはデータ変更を新しいリーダーから受信する
- フェイルオーバーが発生した場合、問題となることは多く存在する
  - 非同期のレプリケーションを使用する場合、新しいリーダーは以前のリーダーから全ての書き込みを受信していない可能性がある。その場合、新しいリーダーは受信してない書き込みを破棄することが多い
  - 受信していない書き込みを破棄する場合、障害の発生要因となるので注意が必要。
    
    同期が遅れていたMySQLのフォロワーがリーダーに昇格。その結果 auto increment によりリーダーで割り当て済みのprimary keyを発行。Redisにもprimary key は保存されていたので、MySQLとRedisでデータ不整合が発生 GitHub availability this week | The GitHub Blog
- 2つのノードが共に自身をリーダーだと信じてしまうスプリットブレインが起こりうる

リレプリケーションログの実装

ステートメントベースのレプリケーション
- リーダーは実行する全ての書き込みリクエスト（ステートメント）をログに記録し、そのステートメントログをフォロワーに送信する。つまり、全ての INSERT, UPDATE, DELETE といったSQL文がフォロワーに転送されることになる。
- NOW() や RAND() といった非決定的な関数を含む場合は、それぞれのレプリカで異なる結果になってしまう（回避策は存在する）。
ストレージエンジンが書き込む際のログを使用するwrite-aheadログの転送
レプリケーション用の独立したログフォーマットを用いる論理ログレプリケーション
トリガベースレプリケーション

レプリケーションラグにまつわる問題

書き込むが少なく、読み取りのクエリが多いアプリケーションでは、多くのフォロワーを作り、リクエストを分散させる選択肢がよく取られる。その際、レプリケーションは非同期的に行う必要がある。同期的にレプリケーションする場合、フォロワーの一つがダウンするとシステム全体が書き込み不能になってしまうため。

非同期的にレプリケーションをする場合、リーダーで書き込まれた内容がフォロワーに反映されるまでラグがある。最終的にリーダーとフォロワーが同じ状態になることを、結果整合性 と呼ぶ。また、リーダーとフォロワーの間に異なる状態が存在する時間差を レプリケーションラグ と呼ぶ。

レプリーケーションラグによって、いくつか問題が生じる

クライアントが自分で書き込んだ内容をフォロワーから読み取る際に、内容が反映されていない可能性がある。
- 書き込んだ内容を読み込んだ際にその内容が反映されている一貫性のことを、read-after-write一貫性 と呼ぶ
- 解決策としては、(1) ユーザーが変更した可能性のあるものを読み取る場合はリーダーから読み取りを行う (2) 最後の更新からある一定の時間内に行う読取は、リーダーから行うなどがある
同じクライアントが異なるフォロワーにアクセスし、古い状態のデータが見えることがある。
- モノトニックな読み取り では、これが生じないことを保証する
- 連続で同じクライアントがデータを読み取る場合に、古い状態のデータが見えないことを保証する
- 各クライアントが常に読み取りを同じレプリカから行うようにすれば、モノトニックな読み取りを実現できる
一貫性のあるプレフィックス読み取り を行い、書き込みの順序通りに読み取りが行われるようにする

6章パーティショニング

レプリケーションでは同じデータを複数のノードで保持することだった。パーティションはそれとは異なり、データを分割して配置することを表す。これはシャーディングとも呼ばれる。

パーティショニングする主な理由は、スケーラビリティ。大規模なデータセットを数多くのディスクに分散して配置できるため、クエリの負荷を分散させることができる。

パーティショニングしたデータをレプリケーションして複数のノードに保存することが多い。

キー・バリューデータのパーティショニング

パーティショニングの目的は、データとクエリの負荷をノードで均等に分散させること。パーティショニングが均等になっておらず、一部のパーティションが他と比べて多くのデータやクエリを担当している状態を スキュー と呼ぶ。また、この状態で高負荷が集中しているパーティションを ホットスポット と呼ぶ。

キー・バリューデータに対して、データとクエリの負荷をノードで均等に分散させるための手法はいくつか存在している。

キーの範囲に基づくパーティショニング
- 連続的なキーの範囲を分割し、各パーティションに割り当てる
- 範囲のみのパーティショニングでは、場合によってホットスポットが生じうるのが欠点
キーのハッシュに基づくパーティショニング
- 多くの分散データストアではこちらを採用
- ハッシュ関数が決まれば、それぞれのパーティションにハッシュ値の範囲を割り当てて分割することで、パーティション間で均等にキーを分散することができる
- ハッシュ値を使ってパーティショニングすることで、キーのソート順序は失われてしまうため、検索時の効率性は下がるのが欠点

パーティショニングとセカンダリインデックス

レコードを特定するためではなく効率的な検索処理に用いられるセカンダリインデックスを持つ場合は、パーティショニングではユニークなキーによって分割されるため、追加でセカンダリインデックスを利用するための仕組みが必要になる。

ドキュメントによるセカンダリインデックスでのパーティショニング
- それぞれのパーティションが、パーティション内に保存されているセカンダリインデックスをドキュメントに追加して保存する。他のパーティションに保存されているデータは知らない。
- 別名ローカルインデックスとも呼ばれる。
- 検索をする際は、全てのパーティションに対して検索する必要があることに注意。この影響で、セカンダリインデックスへの検索が高負荷になる可能性がある。
語によるセカンダリインデックスでのパーティショニング
- 全てのパーティションをカバーするグローバルインデックスを構築する方法。
- セカンダリインデックスの値に応じてパーティショニングすることで実現する。
- 検索時にはドキュメントによるセカンダリインデックスよりも効率的。その一方で、書き込み時には多くのパーティションに書き込むこともり、パフォーマンス低下の可能性がある。

パーティションのリバランシング

負荷をクラスタ内のあるノードから別のノードへと移行するプロセスを リバランシング と呼ぶ。

キーをノードで割った剰余でパーティションを行なっている場合、ノード数が変化するとほとんどのキーはノード間を移動する必要があり、必要以上にデータを移動させる必要がある。そのため、単に剰余を用いるのはパーティショニング時に得策ではない。

ノード数よりも多くのパーティションを用意し、一つのノードに複数のパーティションを割り当てる方式であれば、負荷に応じてパーティション内のデータは変えずにパーティションをノード間で移動することでリバランシングが可能になる。この方式では、パーティション数は最初から大きめの値を固定で設定する。

一方で、動的にパーティショニングを行う方式もある。データ量に応じて動的にパーティションする場合は、データの量が増えるとパーティションを分割し、データの量が減った場合はパーディションを結合する。パーティション数をノード数に比例させる方法もある。これは、ノードあたりのパーティションを固定するというものになる。

自動のリバランスと手動のリバランス

リバランシングはリクエストを再ルーティンし、大量のデータをノード間で移動させる負荷の大きい処理。障害検知も自動で行なっている場合、自動でリバランシングさせると、データを移動する際に一時的にノードが過負荷に陥り、クラスタの再配置が実行される可能性がある。これが行われると、さらにパフォーマンスが悪化する。なので、リバランシングにはどこかで人を介在させると良い。

リクエストのルーティング

データをパーティショニングできたとして、クライアントはどのようにして自身のデータが属するノードと通信するかが問題となる。これには大きく分けて3つのアプローチがある

クライアントが任意のノードに接続する。その後、ノードが適切なノードにリクエストを転送する
クライアントからのリクエストは全てルーティング層に送られ、ルーティングそうが適切なノードにリクエストを転送する
クライアントがパーティショニングと、ノードの割り当てを認識し、直接適切なノードにリクエストを送信する

続き

hiramekun.hatenablog.com

2022-12-11

MySQL における primary key についてメモ

エンジアリング DB 独り言

MySQL における primary key について

MySQL における primary key （プライマリキー、主キーとも呼ばれる）は、テーブルの中のカラムに対して指定できるもので、以下のような特徴を持ちます

テーブルで一つのみ指定できる
NULLは許容しない
一意の（ユニークな） ID を付与する
インデックスが自動で構築される

インデックス構造の基礎知識についてはこちらの記事が非常にわかりやかったのでぜひ参考にしてみてください

MySQL with InnoDB のインデックスの基礎知識とありがちな間違い - クックパッド開発者ブログ

primary key として何を利用するか？

ここで議論となるのは、primary key として何を利用するかという点です。

AUTO_INCREMENT

よくあるのは、DB側の機能として AUTO_INCREMENT を利用し、DB側で採番するという方法です。

メリットとしては以下のようなものが挙げられます。

アプリケーション側の実装が不要
連番なので必ずキーが被ることはない
連番なのでインデックス構築の効率が良い

上記の利点からよく採用される AUTO_INCREMENT ですが、以下のようなデメリットもあります。

DBに書き込まれるまで primary key が定まらず、アプリケーション側では一度書き込んだ後の値を使用する必要がある
複数DBで採番すると ID が重複するため、DBの台数を増やすことができない

採番テーブル

次によくあるのは、採番テーブルを用意し、そこで連番を管理する方法だと思います。こちらではDBにデータを書き込む前に primary key を取得するため、 AUTO_INCREMENT におけるデメリットの1を解決できます。

一方で、DBの台数を増やすことができないデメリットは残しますし、primary key を取得する際に毎回採番テーブルへのIOが発生する点は新しいデメリットです。

UUID

今までのように DB側で primary key を使うのではなく、アプリケーション側で一意な primary key を生成する方法もあります。

その場合はこれまでのように primary key を生成する処理をDBに依存する必要がないのが利点です。

一意な ID と聞くと、UUID が候補として挙げられます。ここではその中でも UUID version1 を取り上げます。UUID を使う場合はパフォーマンス面での懸念があります。次の記事で非常に丁寧に解説されているので読んでみてください。

MySQLでプライマリキーをUUIDにする前に知っておいて欲しいこと | Raccoon Tech Blog

自分の言葉でまとめると、こんな感じになります。

インサート時、読み込み時ともに、UUID のうちランダムな部分が原因となり、インデックス構築時にクラスタインデックス（B-treeの発展版なようなものという理解）の全リーフのインデックスを読み込む可能性がある。
- 前提として、UUID を生成する際にタイムスタンプが参照されるが、タイムスタンプを表すビットの中で、上位ビットと下位ビットを入れ替えたりするため、時系列でシーケンシャルな値になっていない。
- もしシーケンシャルであれば、近い値のインデックスは場所的にも近いので、一部分だけ読み込めば良い。キャッシュにもヒットする可能性が高い。

UUID を使う場合でも、MySQL の uuid_to_bin という関数を使えば、パフォーマンス問題が解決するようです。

MySQL :: MySQL 8.0 リファレンスマニュアル :: 12.24 その他の関数

まず、UUID を16進数表現からバイナリに変換することで 32byte から 16byte に変換することができます。これにより、インデックスの保持に必要な容量が減りパフォーマンス若干向上します。

文字列 UUID をバイナリ UUID に変換し、結果を返します。 (IS_UUID() 関数の説明には、許可されている文字列 UUID 形式がリストされます。) 戻りバイナリ UUID は VARBINARY(16) 値です。 UUID 引数が NULL の場合、戻り値は NULL です。無効な引数がある場合は、エラーが発生します。

また、インデックスとして使用している場合は次の引数が重要です。 swap_flag を 1 にすることで、UUID 生成の際にスワップされてしまったタイムスタンプ部分の上位ビットと下位ビットを再度交換し、ほぼシーケンシャルな ID として利用することができるようになります。

swap_flag が 1 の場合、戻り値の形式は異なります: time-low 部分と time-high 部分 (それぞれ 16 進数の最初と 3 番目のグループ) がスワップされます。これにより、より迅速に変化する部分が右側に移動し、結果がインデックス付けされたカラムに格納されている場合はインデックス付けの効率を向上させることができます。

ULID

ULID は UUID の問題点であったタイムスタンプがそのまま保持されていない点を解消し、タイムスタンプを上位ビットにそのまま保持し、下位ビットにランダム列が入ります。

ulid/spec: The canonical spec for ulid

そのためデフォルトでほぼシーケンシャルとなり、インデックス周りのパフォーマンス低下を抑えることができます。

他にも、

128bit (=16byte)
UUID は文字列で36文字必要なところ、26文字で抑えられる
1msあたり、1.21e+24 のユニークな ULID が生成される

あたりの特徴があります。くわしくはリンク先の仕様を見てください。

UUIDv1, UUIDv4, v7, ULID の比較はこんなところでしょう。

フォーマット	ソート可能性	単調増加性	ランダムさ程度
UUIDv1	基本なし（binary変換すればあり）	なし	（調べたが不明。MACアドレスをもとに生成されるため推測される）
UUIDv4	なし	なし	122 bits
UUIDv7	あり	あり	62 bits
ULID	あり	あり	80 bits

ULIDs and Primary Keys | Dave Allie の表に UUIDv1 を追加して記載しました。

別に考える必要のあること

そもそも UUID version1 はなぜ生成時にタイムスタンプの上位ビットと下位ビットをスワップするような作りなのか
UUID version6, 7, 8 はソート可能なように提案されているようだが、現在どの程度使用されているのか。他のアルゴリズムと比べてパフォーマンスはどうなのか。
- 時間順にソート可能なUUIDv6, UUIDv7, UUIDv8の提案仕様 - ASnoKaze blog
- Differences and Similarities with uuidv6? · Issue #10 · ulid/spec
ULID の場合は、バイナリ形式で保持するとパフォーマンス上昇はどの程度あるのか
分散システムで厳密にシーケンシャルな ID が必要な場合は別に色々と考える必要がある
- Facebook, Twitter, Instagram等がどうやってIDを生成しているのかまとめ - Qiita

その他参考文献

2022-08-08

『データ指向アプリケーションデザイン』を読んだー第I部データシステムの基礎

エンジアリング book

『データ指向アプリケーションデザイン』を読んで特に印象に残ったところをメモとして残します。分厚いので数回に分けます。
書籍が素晴らしいので、詳細はそちらを読んでみてください。

データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理

Amazon

はじめに
1章信頼性、スケーラビリティ、メンテナンス性に優れたアプリケーション
2章データモデルとクエリ言語
- リレーショナルモデルとドキュメントモデル
3章ストレージと抽出
- データベースを駆動するデータ構造
- 列指向ストレージ
4章エンコーディングと進化
続き

はじめに

データ指向とは、データの量や複雑さ、変化の速度が主な課題となるアプリケーションのことを指す。目的を達成するためにどのような種類の技術を用いるのが適切か的確に判断し、優れたアプリケーションのアーキテクチャ基盤を構築するためのツール群の組み合わせ方を理解できるようになることを目指す。

1章信頼性、スケーラビリティ、メンテナンス性に優れたアプリケーション

ソフトウェアシステムにおける重要な3つの課題

信頼性。システムは障害があったとしても正しく動作し続けるべき。
スケーラビリティ。データ量の増加、トラフィック量の増加などといった成長に対して、無理のない方法で対応可能であるべき。
メンテナンス性。時間が経つにつれて多くの人が関わるが、それらの人がシステムに生産的に関われるべき。

2章データモデルとクエリ言語

リレーショナルモデルとドキュメントモデル

ドキュメントデータモデルの良さは以下のような点

スキーマの柔軟性
ローカリティから来る優れたパフォーマンス
データ構造がアプリケーションのものに近い場合がある

特にアプリケーションの構造が一体多の関係からなるツリー構造を持ち、そのツリー全体が通常は一度にロードされる場合、ドキュメントデータモデルを利用するのは良い考えとなる。その一方で、アプリケーションが多対多の関係を必要とするなら、ドキュメントモデルの魅力は薄れる。

多くのドキュメントデータベースにおけるJsonサポートでは、ドキュメント内におけるスキーマを強制しない。スキーマがないということは、任意のキーとバリューをドキュメントに追加できるということ。スキーマレスという言葉がよく使われるが、厳密には スキーマオンリード （データ構造は暗黙的であり、データの読み取り時に解釈される）であり、逆にリレーショナルデータベースなどでは スキーマオンライト と呼ばれている。スキーマオンリードはドキュメントの構造が統一されていない場合にはメリットとなる。

3章ストレージと抽出

データベースを駆動するデータ構造

データベースから特定のキーの値を効率的に見つけるためにはインデックスが必要となる。インデックスがない場合は O(n) の計算コストがかかり、スケーラブルではない。インデックスは、データから作られる追加のデータ構造として存在している。

インデックスはデータの書き込みのたびに更新する必要があるため、書き込み速度を低下させる。読み出しクエリは高速にしてくれるので、重要なトレードオフとなる。

インデックスの管理方法にはいくつか種類がある。

ハッシュインデックス。インメモリのハッシュマップの中には、全てのデータに対してデータファイル中のバイトオフセットをマッピングする。こうすることで、ディスクに保存されているファイルのどの場所に目的のデータがあるか検索することができる。ファイルが一定の大きさを超えると、新しくセグメントファイルを作成して新しい書き込みは新しいファイルへと行う。とはいえ、このインメモリハッシュマップがメモリに収まり切る必要がある。
SSTable（Sorted String Table）。SSTableはファイルの中身がキーでソートされている。この場合は全てのデータをインメモリに持つ必要はない。なぜなら、それぞれのファイルの先頭の単語だけわかれば、どのセグメントファイルにアクセスすれば良いかわかるため。このログ指向ファイルシステムから構築されたインデックス構造はLSMツリー（Log-Structured Merge-Tree）と呼ばれる。
Bツリー。SSTableと同様に、キーとバリューのペアをキーでソートされた状態で保持する。n個のキーを持つBツリーの深さは常に O(logn) となる。ログ型のインデックス構造とは異なり、データを上書きする。

一般的に、SSTableから構築されたインデックスのLSMツリーは書き込みを高速に処理でき、Bツリーは読み取りが高速に行えるものとみなされている。ただし、LSMツリーではファイルのコンパクション処理が実行中の読み書きに影響を与える場合や、書き込みを受け付けるペースに対してコンパクションが追いつかなくなる可能性に注意が必要となる。

列指向ストレージ

多くのオンライン分析処理データベース（OLAPデータベース）では、ストレージは行指向でレイアウトされている。CSVを想像するとイメージがしやすい。その一方で、データウェアハウスでは列指向ストレージを用いている。一つの行に含まれる値をまとめて保持するのではなく、それぞれの列に含まれる全ての値を保存する。

列指向ストレージの特徴の一つとして、圧縮が容易という点がある。しばしば一つの列の中のuniqueな値は行数に比べて小さくなるので、それに対応するビットマップエンコーディングを行うことで圧縮することができる。

4章エンコーディングと進化

後方互換性と前方互換性

システムの構築は、変化に容易に適合できるようにするべきである。これを進化性と呼ぶ。システムが進化性を保ち動作し続けるためには、互換性に気をつける必要がある。

後方互換性：古いコードによって書かれたデータを新しいコードが読めること
前方互換性：新しいコードによって書かれたデータを古いコードが読めること

後方互換性は、新しいコードを書く人が古いデータを知っていれば対応可能。一方で前方互換性は新しいデータで追加された分を古いコードが無視する対応が必要なので比較的難しい。

これらの互換性は、例えばローリングアップデート中を考えるとサポートする必要性をイメージしやすい。

言語固有のフォーマット

Javaの java.io.Serializable Rubyの Marshal Pythonの pickle など、プログラミング言語自体がインメモリオブジェクトをバイト列にエンコードする機能を持つことも多い。これは特定のプログラミング言語と密に結合しており、他の言語でデータを読むのが難しくなってしまう。一時的な目的を除いて、特定の言語の組み込みエンコーディングを使うのは良くない考え。

Json, XML のバイナリエンコーディング

Json と XML はバイナリ文字列をサポートしていない。そのため、Base64を使ってバイナリデータをエンコードする方法が使われる。これは正しく動くが、データサイズが33%増加してしまう。

Json や XML はバイナリフォーマットと比べると多くの容量を使用するため、バイナリエンコーディングも開発されている（例：Jsonにおける MessagePack）。しかし、削減できる容量はわずかであり、それだけのために人間が読めないフォーマットにする価値があるかは怪しい。

Protocol Buffers

Protocol Buffers (protobuf) は Google で開発されたライブラリで、バイナリエンコーディングのライブラリ。エンコードするデータに対するスキーマを必要とする。エンコーディング後のデータはフィールド名をバイト列に含まないという点で、MessagePack のような Json のバイナリエンコーディングと大きく異なる。その代わりに1, 2, 3...という数値がフィールドタグとして割り当てられる。この数値はスキーマ定義に書かれている数値であり、スキーマ定義があることによるフィールド名そのものを書くことなくフィールド名を特定することができる。

Protocol Buffers におけるスキーマの進化

Protocol Buffers はどのようにして後方・前方互換性を保ちつつスキーマの変化を扱うのだろうか。

エンコードされたレコードは単にバイナリエンコードされたフィールドを繋げたものにすぎない。それぞれのフィールドはフィールドタグで識別され、データ型が付与される。つまりフィールドタグが非常に重要。タグを変更するとエンコード済みの既存の全データが不正なものとなってしまうため、フィールド名を変更することはできるがフィールドタグは変更できない。

前方互換性

新しいタグ番号を使用することによって、スキーマには新しいフィールド加えることができる。古いコードでは認識できないタグ番号を持つ新しいフィールドを無視する。参考：https://developers.google.com/protocol-buffers/docs/proto3#updating

後方互換性

古いフィールドは新しいコードでも読み取ることができる。注意が必要なのは、古いフィールドを新しいコードでも読み取るために、新しく追加するフィールドは必須にできないという点。

続き

hiramekun.hatenablog.com

2022-04-24

【Scala】Monocleを使ってみたメモ

Scala book

何の記事か

こちらの『Scala Design Patterns』の11章前半です。

Scala Design Patterns: Design modular, clean, and scalable applications by applying proven design patterns in Scala, 2nd Edition (English Edition)

作者:Nikolov, Ivan
Packt Publishing

Amazon

Lensパターンの実装方法の一つとして scalaz.Lens が紹介されていましたが、他に紹介されていた Monocle を使って書き換えてみようというメモです。

Lensパターンとは

Lensパターンは、ネストが深くなっているオブジェクトの一部だけプロパティを書き換えたい、その一方でイミュータブルなオブジェクトを使用したいときなどに使われます。例えば以下のようなオブジェクトで、User から user.company.address.city.country.code を書き換えようとすると大量のコードを書く必要が出てきます。

classDiagram
  class User {
    +name: String
    +company: Company
    +address: Address
  }
  class Company {
    +name: String
    +address: Address
  }
  class Address {
    +number: Int
    +street: String
    +city: City
  }
  class City {
    +name: String
    +country: Country
  }
  class Country {
    +name: String
    +code: String
  }
  
  User *-- Company
  User *-- Address
  Company *-- Address
  Address *-- City
  City *-- Country

例えばこんな感じにプロパティを一つ書き換えただけなのに、 Country を含むオブジェクトを全てcopyして作り直す必要があります。

val userFixed = user.copy(
  company = user.company.copy(
    address  = user.company.address.copy(
      city = user.company.address.city.copy(
        country = user.company.address.city.country.copy(
          code = user.company.address.city.country.code.toUpperCase
        )
      )
    )
  )
)

そこで役に立つのがLensパターンのようです。変更したいプロパティにレンズを通してフォーカスするイメージらしいのですが、具体的なLensパターンの実装自体は未調査です。

scalaz.Lens

本の中でLensパターンを実現しているライブラリとしてまず紹介されているのは、scalaz.Lens です。Lens[A, B] は LensFamily[A, A, B, B] のエイリアスとなっていました。 LensFamily[A1, A2, B1, B2] は更新前後で型が変わる場合に対応しているのですが、変わらない場合は基本的に Lens[A, B] を使うのが良さそうです。

/**
 * A Lens Family, offering a purely functional means to access and retrieve
 * a field transitioning from type `B1` to type `B2` in a record simultaneously
 * transitioning from type `A1` to type `A2`.  [[scalaz.Lens]] is a convenient
 * alias for when `A1 === A2`, and `B1 === B2`.
 *
 * The term ''field'' should not be interpreted restrictively to mean a member of a class. For example, a lens
 * family can address membership of a `Set`.
 *
 * @see [[scalaz.PLens]]
 *
 * @tparam A1 The initial type of the record
 * @tparam A2 The final type of the record
 * @tparam B1 The initial type of the field
 * @tparam B2 The final type of the field
 */
sealed abstract class LensFamily[A1, A2, B1, B2]

type Lens[A, B] = LensFamily[A, A, B, B]

Lensのgetterとsetterを Lens.lensu(setter, getter) で定義してあげます。lensu の関数定義は以下の通りです。

def lensu[A, B](set: (A, B) => A, get: A => B): Lens[A, B]

使用する側ではUser -> Company のように、クラス -> クラスのプロパティ という感じで順にアクセスする方法を定義します。

object User {
  val userCompany: Lens[User, Company] = Lens.lensu[User, Company](
    (u, company) => u.copy(company = company),
    _.company
  )

  val userAddress: Lens[User, Address] = Lens.lensu[User, Address](
    (u, address) => u.copy(address = address),
    _.address
  )

  val companyAddress: Lens[Company, Address] = Lens.lensu[Company, Address](
    (c, address) => c.copy(address = address),
    _.address
  )

  val addressCity: Lens[Address, City] = Lens.lensu[Address, City](
    (a, city) => a.copy(city = city),
    _.city
  )

  val cityCountry: Lens[City, Country] = Lens.lensu[City, Country](
    (c, country) => c.copy(country = country),
    _.country
  )

  val countryCode: Lens[Country, String] = Lens.lensu[Country, String](
    (c, code) => c.copy(code = code),
    _.code
  )
}

そして、andThen のエイリアスである >=> を使って繋げてます。こうすることで、User から Country.code までたどることができます。

  val userCompanyCountryCode: Lens[User, String] = userCompany >=> companyAddress >=> addressCity >=> cityCountry >=> countryCode

// こっちは compose を使ったもの。表記が逆になるだけでやってることは同じ。
  val userCompanyCountryCodeCompose: Lens[User, String] = countryCode <=< cityCountry <=< addressCity <=< companyAddress <=< userCompany

Monocle

本の中で具体的に紹介されていたのは scalaz.Lens でしたが、より便利なライブラリとしてお勧めされていた Monocle · Access and transform immutable data を使って書き換えてみようと思います。

まず、Monocleはサイトを見ると Scala 2.13 以降に対応しているようなので、サンプルプロジェクトのScalaのバージョンを2.12から上げます。ScalaTestやMockitoなどのプロジェクトに含まれている他のライブラリのバージョンも、Scalaのバージョンに追従して上げる必要がありました。

scalaVersion := "2.13.8"

libraryDependencies ++=  {
  Seq(
    ...
    "dev.optics" %% "monocle-core"  % "3.1.0",
    "dev.optics" %% "monocle-macro" % "3.1.0",
    ...
  )
}

基本的にはサイトに書いてある通りで、以下のような流れになります。

foo.focus で foo オブジェクトの持っているプロパティ内部に注目
focus の中で指定したプロパティを、 modify によって変更
変更後のオブジェクトを取得

簡単ですね。

  val ivanFixed = ivan.focus(_.company.address.city.country.code).modify(_.toUpperCase)

暗黙的に AppliedFocusOps に変換しているらしいのですが、中身はマクロで書かれていて理解はまだできませんでした。

出力結果を見ると確かに UK と大文字になっていることが確認できます。

User(Ivan,Company(Castle Builders,Address(1,Buckingham Palace Road,City(London,Country(United Kingdom,uk)))),Address(1,Geneva Lake,City(geneva,Country(Switzerland,CH))))
Capitalize UK code...
User(Ivan,Company(Castle Builders,Address(1,Buckingham Palace Road,City(London,Country(United Kingdom,UK)))),Address(1,Geneva Lake,City(geneva,Country(Switzerland,CH))))

2022-04-22

【Scala】Optionモナドをcats.Monadを使って書いてみる

Scala book

何の記事か

Scala Design Patterns で例として挙げられていた Optionモナドを、 cats.Monad を用いて書き換えてみます。以前 Scala Design Patterns のモナドに関する章を噛み砕いで追いました。

hiramekun.hatenablog.com

では cats の Monad を使うとどのように書けるのだろうか？と思い、色々調べながら実験した内容をメモしました。

cats.Monad

cats.Monad の定義は以下の通りです。

trait Monad[F[_]] extends FlatMap[F] with Applicative[F]

FlatMap[F] は文字通り flatMap を持つもの
Applicative[F] は ap と pure を持ち、Functor[F] を継承している。pure は以前のブログでまとめたところの unit に相当する部分だと理解
Functor[F] は map を提供していることを以前のブログでもまとめている

これを使って Scala Design Patterns にあるように Option モナドを書き換えてみようと思います。

まずはcats公式のサンプルを見てみます。すると、すでに Applicative[Option] が存在する場合の例が載っていました。

If Applicative is already present and flatten is well-behaved, extending the Applicative to a Monad is trivial.

import cats._

implicit def optionMonad(implicit app: Applicative[Option]) =
  new Monad[Option] {
    // Define flatMap using Option's flatten method
    override def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] =
      app.map(fa)(f).flatten
    // Reuse this definition from Applicative.
    override def pure[A](a: A): Option[A] = app.pure(a)

    @annotation.tailrec
    def tailRecM[A, B](init: A)(fn: A => Option[Either[A, B]]): Option[B] =
      fn(init) match {
        case None => None
        case Some(Right(b)) => Some(b)
        case Some(Left(a)) => tailRecM(a)(fn)
      }
  }

tailRecM は初めて見る関数ですが、これは cats の主張として「Monadを再帰的に処理する場面は多々あり、末尾再帰にしないとスタックオーバーフローが発生するので、Monadを定義する際に強制的に末尾再帰を定義させる」とのことです。

In addition to requiring flatMap and pure, Cats has chosen to require tailRecM which encodes stack safe monadic recursion, as described in Stack Safety for Free by Phil Freeman. Because monadic recursion is so common in functional programming but is not stack safe on the JVM, Cats has chosen to require this method of all monad implementations as opposed to just a subset.

例を見ると、catsのMonadは継承するものではなく引数としてimplicitに与えるイメージのようですね。（なぜ継承ではなく移譲になっているのかは、もう少し理解を深める必要がありそうです。）

書き換えてみる

さて、Applicative の実装は今回のやりたいことから外れるので、Applicative を利用しているところを書き換えていこうと思います。

flatMap は値が Some だったらその中身に対して受け取った関数を実行すれば良い。
pure は引数を受け取るコンストラクタなので、Some を返せば良い

以上を踏まえると、今回作る MyOption は次のように定義することができます。

implicit def optionMonad: Monad[MyOption] =
  new Monad[MyOption] {
    override def pure[A](x: A): MyOption[A] = MySome(x)
                                                                                                 
    override def flatMap[A, B](fa: MyOption[A])(f: A => MyOption[B]): MyOption[B] = fa match {
      case MySome(value) => f(value)
      case MyNone() => MyNone()
    }
                                                                                                 
    @tailrec
    override def tailRecM[A, B](a: A)(f: A => MyOption[Either[A, B]]): MyOption[B] = f(a) match {
      case MySome(Right(value)) => MySome(value)
      case MySome(Left(value)) => tailRecM(value)(f)
      case MyNone() => MyNone()
    }
  }

次にこれを実際にどのようにして MyOption から使うのかですが、自分は

MyOption のコンパニオンオブジェクトに先ほどの optionMonad を implicit に定義し、
MyOption のコンストラクタに implicit で渡す

ようにしてみました。

object MyOption {
  implicit def optionMonad: Monad[MyOption] = ...
}
sealed class MyOption[A](implicit val optionMonad: Monad[MyOption]) {
  def flatMap[B](f: A => MyOption[B]): MyOption[B] = optionMonad.flatMap(this)(f)

  def map[B](f: A => B): MyOption[B] = optionMonad.map(this)(f)
}

case class MySome[A](value: A) extends MyOption[A]

case class MyNone[A]() extends MyOption[A]

extends MyOption[A] で MyOption[A] のコンストラクタ引数が足りないので、Scalaのコンパイラは implicit に定義されたものを探しに行きます。この時に、コンパニオンオブジェクトの中に含まれている implicit 定義もコンパイラの探索対象となります。

変換のソース型か期待されるターゲット型のコンパニオンオブジェクトの中に含まれているimplicit定義も、コンパイラーの探索対象に入る

Scalaスケーラブルプログラミング第4版, p.415 より引用

IntelliJの View: Show Implicit Hints を on にすると、暗黙的に渡されているパラメータを表示することができるのですが、それを使うと、きちんと引数に渡されていることが確認できます。

まとめ

使ってあげるとこんな感じになり、map/flatMap が実装されているので for 式でも書くことができます。

object Main {
  def main(args: Array[String]): Unit = {
    val result = for {
      x <- MySome(1)
      y <- MySome(2)
    } yield {
      x + y
    }
    println(result) // MyOption(3)
  }
}

今回作成したMyOptionのコードをまとめると以下のようになります。

（Scala with cats や fpinscala も進めていきたいなあ...）

参考

2022-04-11

【因果推論】媒介された影響の排除

因果推論統計グラフィカルモデル

こちらの第3章後半です

入門統計的因果推論

作者:Judea Pearl,Madelyn Glymour,Nicholas P. Jewell
朝倉書店

Amazon

媒介

ある変数が別の変数に影響を与える場合、直接影響を与える場合と間接的に影響を与える場合とが存在し、この二つを分離することは一般的には難しい。間接的な影響のことを、媒介された影響と呼ぶ。

例として、採用に性別による差別が存在するかどうか調査したいとする。今回は以下の4つの変数が関わっているとし、 $X$ から $Y$ への直接的な効果を計測したい。

$X$ : 性別
$Y$ : 採用
$Z$ : 資格
$I$ : 収入

f:id:thescript1210:20220410235828p:plain:w500

まず資格について条件付けをする場合を考えてみる。条件付けするというのはつまり、 $P(採用決定|男性, 資格あり)$ と $P(採用決定|女性, 資格あり)$ を比べるということだ。この二つに差があれば、性別が採用決定に影響を及ぼしていると判断することができる。

しかし、今回のように収入 $I$ という交絡因子を含む場合は条件付けによって比べることはできない。なぜなら、資格 $Z$ で条件づけることによって、 $Z$ と $Y$ が $I$ と通じて従属になってしまうためだ。（資格 $Z$ を条件付けするために収入 $I$ に影響を及ぼし、収入 $I$ が採用 $Y$ へと影響を及ぼすため。）

であれば、資格 $Z$ について条件付けをする代わりに、資格を固定すれば良い。変数を固定するのは、他の変数がどんな値を取ろうとも、その値に固定されるという意味であり、その変数に向かう矢印を全て削除することと同義である。

介入と固定に関しては過去記事を参照

hiramekun.hatenablog.com

したがって、今回の場合の直接効果、CDE (controlled direct effect) は以下で定義される。

${ CDE = P(Y=採用決定|do(X=男性), do(Z=資格あり)) - P(Y=採用決定|do(X=女性), do(Z=資格あり)) }$

より一般的に、 $Z$ が $X$ と $Y$ の間の媒介変数である時、 $X$ の値を $x$ から $x\prime$ に変化させたときの $Y$ のCDEは

${ CDE = P(Y=y|do(X=x), do(Z=z)) - P(Y=y|do(X=x\prime), do(Z=z)) }$

となる。

これは、 $I$ について調整することで次のように式変形ができる。

${ \begin{eqnarray} CDE &=& P(Y=y|X=x, do(Z=z)) - P(Y=y|X=x\prime, do(Z=z)) \\ &=& \sum_{i}\left[P(Y=y|X=x, Z=z, I=i) - P(Y=y|X=x\prime, Z=z, I=i)\right]P(I=i) \end{eqnarray} }$

2022-04-09

【因果推論】逆確率重み付け法

統計グラフィカルモデル因果推論

こちらの第3章後半です

入門統計的因果推論

作者:Judea Pearl,Madelyn Glymour,Nicholas P. Jewell
朝倉書店

Amazon

以前効果検証入門でも学習していましたが、表記方法や捉え方が異なっていたため、まとめてみました。

hiramekun.hatenablog.com

前提

逆確率重み付け法とは、バックドア基準やフロントドア基準を満たしている共変量 $Z$ に対して、傾向スコアを持ちいることで効率的に $P(y \mid do(x))$ を求める方法である。（下図はバックドア基準を $z$ が満たしている例）

バックドア基準やフロントドア基準を使えば、実際に介入することなく効果量を計算することができる。このためには、基準を満たす共変量 $Z$ を見つけて、調整化公式を適用すれば良い。

ここで調整化公式を思い出すと、いずれも $Z$ に関して総和を取っている。

バックドア基準： $P(y \mid d o(x))=\sum_{z} P(y \mid x, z) P(z)$
フロントドア基準： $P(y \mid d o(x))=\sum_{z} P(z \mid x) \sum_{x^{\prime}} P\left(y \mid x^{\prime}, z\right) P\left(x^{\prime}\right)$

これは、 $Z$ の取りうる値が大きくなればなるほど計算量は大きくなるということを表している。

傾向スコアと逆確率重み付け法

これを解決するのが、傾向スコア と 逆確率重み付け法 である。

傾向スコアは $g(x, z) = P(X=x|Z=z)$ で表される関数で、効果検証入門によると以下のような意味を持ち、ロジスティック回帰などで求めることができるという。

傾向スコアとは、各サンプルにおいて介入が行われる確率のこと。傾向スコアを用いた分析は、介入が行われた仕組みに注目し、介入グループと非介入グループのデータの性質を近くするする操作を行う。
『効果検証入門』用語まとめ - ひらめの日常

ベイズの法則より、

${ P(Y=y, Z=z|Z=z) = \frac{P(Y=y, Z=z, X=x)}{P(X=x)} }$

これ合わせて、調整化公式の $P(y \mid d o(x))=\sum_{z} P(y \mid x, z) P(z)$ の分母分子に傾向スコアをかけて式変形をすると、以下が導出される。

${ \begin{eqnarray} P(y|do(x)) &=& \sum_z \frac{P(Y=y|X=x, Z=z)P(X=x|Z=z)P(Z=z)}{P(X=x|Z=z)} \\ &=& \sum_z \frac{P(X=x, Y=y, Z=z)}{P(X=x|Z=z)} \end{eqnarray} }$

つまり、母集団のそれぞれのケースの確率を、傾向スコアで割れば良い。

※ 『効果検証入門』では確率ではなく期待値を求めていた点などで式の表現が異なっている。

何が嬉しいか

これにより、計算量は調整化公式を用いる時と比べて削減できている。例えば、 $Z$ の取りうる値が数百万あったとする。それに対して、得られたデータが数百件だったとする。この時、

調整化公式を用いると、例えば $Z$ がバックドア基準を満たしていた場合、全ての $Z$ に対して $P(y \mid x, z) P(z)$ を計算する必要がある。
逆確率重み付け法を用いると、観測されていない $P(X=x, Y=y, z=z)$ は考慮に入れなくて良いため、観測された分のみ計算すれば良くなる。

この辺も後で読みたい

逆確率重み付け（IPW）のイメージ。

まず、簡単な例から答えを準備。飽和モデルでは、ノンパラg-formulaとIPWは一致することを利用します。

共変量Lで条件つけることで交換可能性が成立するとします。
つまりこの時、AとYとの「関連」は、AのYへの「効果」と考えられます。 https://t.co/ugeVA6S7w4 pic.twitter.com/ijthimurXE
— Sato Shuntaro｜佐藤俊太朗 (@Shuntarooo3) March 26, 2022

5章 レプリケーション

リーダーとフォロワー

同期的か非同期的か

障害への対処

リレプリケーションログの実装

レプリケーションラグにまつわる問題

6章 パーティショニング

キー・バリューデータのパーティショニング

パーティショニングとセカンダリインデックス

パーティションのリバランシング

自動のリバランスと手動のリバランス

リクエストのルーティング

続き

MySQL における primary key について

primary key として何を利用するか？

AUTO_INCREMENT

採番テーブル

UUID

ULID

別に考える必要のあること

その他参考文献

はじめに

1章 信頼性、スケーラビリティ、メンテナンス性に優れたアプリケーション

2章 データモデルとクエリ言語

リレーショナルモデルとドキュメントモデル

3章ストレージと抽出

データベースを駆動するデータ構造

列指向ストレージ

4章 エンコーディングと進化

後方互換性と前方互換性

言語固有のフォーマット

Json, XML のバイナリエンコーディング

Protocol Buffers

Protocol Buffers におけるスキーマの進化

前方互換性

後方互換性

続き

何の記事か

Lensパターンとは

scalaz.Lens

Monocle

何の記事か

cats.Monad

書き換えてみる

まとめ

参考

媒介

前提

傾向スコアと逆確率重み付け法

何が嬉しいか

5章レプリケーション

6章パーティショニング

1章信頼性、スケーラビリティ、メンテナンス性に優れたアプリケーション

2章データモデルとクエリ言語

4章エンコーディングと進化