新しいリードレプリカをクラスタに追加する
サービスが成長するに従って、既存のクラスタにリードレプリカを追加する必要性は必ず生じる。そのときどうやって新しいリードレプリカにリーダーのデータを複製するか？
単にデータファイルをコピーするだけでは、コピー中に生じる差分を吸収できない。かといってコピー中に書き込みをブロックするのは、可用性を犠牲とすることとなるのでスマートな解決策とはいいがたい。
これについてはこうあるべきという合意された答えがある。それをそのまま紹介する。こういうことになる。
同期レプリケーションか、非同期レプリケーションか
書き込みログをネットワーク越しにリードレプリカに転送するジョブは、基本的には軽量で高速動作する。ただしネットワークの不調やリードレプリカの予期せぬ故障など外部要因によって無制限の遅延が発生する可能性は常に存在する。
同期レプリケーション
リーダーノードとリードレプリカの間のレプリケーションを常に同期的に実行するとする。ノード間のネットワークが遅延していても、リードレプリカに正しく疎通がとれるまでリーダーノードは書き込みリクエストに対して ok を返さない。
このときクラスタ全体が常に最新のデータを持つことを保証できる。またリーダーがダウンしてもリードレプリカが読み取りリクエストを処理しつづけることができる。他方で、リードレプリカが一台でも落ちてしまうと、リーダーノードは疎通が取れるようになるまで書き込みリクエストをブロックせざるを得ない状況に陥ってしまう。
つまり、クラスタ全体にわたって同期レプリケーションを実施するというのは、一台でもノードが落ちるとシステム全体が落ちてしまうということにほかならない。分散データベースが要請される前提条件が崩れることになるので、これは許容できない選択となるだろう。
非同期レプリケーション
他方でレプリケーションを非同期で行うとすると、原理的にデータの損失が発生しうる。とはいえ多少のデータ損失を許容できるのであれば、これは有効な選択肢となろう。データ損失など多少なりとも許容できない！ と息巻く気持ちはわかるが、100%の安全性を要件とするのはそもそも不健全だし保証不可能なので、どの程度の損失を許容できるかを明確化し、運用コストとの落とし所を探るのが賢明だろう。その意味で、データ損失を覚悟のうえ非同期レプリケーションを検討するのは有効であるはずと繰り返し述べておく。
どういうときにデータの損失が起こりうるか？ それはリーダーノードが受け付けた書き込みをリードレプリカに転送する前に不意にダウンしてしまうときである。リードレプリカのうち任意の一台が新しいリーダーノードに昇格することで、全体としての可用性は守られるが、クライアントから見ると成功したはずの書き込みが消失してしまうケースが生じうることは避けられない。
実際、データ損失のリスクというトレードオフを飲んでも非同期レプリケーションを採用する事例は多い。特に書き込みクライアントが世界中に散らばっていて、リーダーノードが一台しか存在しない場合であれば、レスポンスタイムの最短化を最優先に考慮してレプリケーションは非同期で行うという選択肢は少なからず有効だろう。
半同期レプリケーション
それでもデータ損失のリスクは受け入れがたいというのであれば、 Facebook 社にて採用されている半同期（ semi-synchronous ）パターンこそがもっとも中庸の落としどころといえるかもしれない。
これはリードレプリカのうち任意の一台について同期レプリケーションを行い、残りのリードレプリカに対しては非同期でレプリケーションを行う方式である。つまり最新のデータが最低でもリーダーのほかにもう一台に存在することが保証されるので、リーダーノードがダウンしてもデータの損失なしにフェイルオーバーできるといえることとなる。
この方式の出典はマツノブ・ヨシノリ氏の公開記事に記載があるので、詳細についてはこれをよく読むのが良い。
データベースを支えるデータ構造: Designing Data-Intensive Applications 第3章より
Designing Data-Intensive Applicationsより、インデックスにまつわる箇所の読書ノートをまとめた。いくつか重要なデータ構造が登場しているが、個別の語彙やアルゴリズムについて深く検討まではしていない。概念を把握する前に、概念の存在をまずは認識した形である。詳細は詳細として、いつか必要が出たときに再訪する。
インデックスとは
n件のレコードから任意のレコードを検索するとき、基本的には O(n) の計算量が想定される。インデックスとは、その計算量を改善するに導入される補助的なデータ構造である。書き込みのたびにインデックスの更新も行わなければならないためインデックスを持つことは必然的に書き込みオーバーヘッドを伴う。
つまり次のようなシンプルなトレードオフとして整理できる。
- 優れたインデックスは読み取りを高速化する
- あらゆるインデックスは書き込みを低速化する
B-tree と LSM-tree
PostgreSQL や MySQL (InnoDB) においてインデックスというと、基本的には B-tree のことを指す。他方でトランザクションログのように大量に書き込まれるデータの扱いに長けた、 LSM-tree というデータ構造もある。
B-tree と LSM-tree はおおむね対照的な特性を持つ。簡単に列挙すると、次のようになる。
LSM-tree
pro
- 高い書き込みスループットを持つ
- 圧縮効率がよく、ディスクを効率的に利用できる
con
- ログをマージするバックグラウンド処理がパフォーマンスに影響を与える
- 平均的にはある程度均等なレスポンスタイムであるが
- 高いパーセンタイルほどレスポンスタイムが悪くなる
- データベースが大きくなるほどリソース効率が下がるリスクが高まる
-書き込み流入量がバックグラウンド処理の速度を超えるとみるみるうちにディスクが溢れてしまう
- 書き込み量がボトルネックになる場合何らかの方法で外部から書き込みをスロットルする必要がある
B-Tree
pro
- トランザクションのための強力なロック性能を持つ
- 任意のキーはインデックス上で常にひとつしか存在しないことが保証されているため
- 時の審判を経ていくつもの改良も行われているからデータ構造としての信頼性はとても高い
con
- ページへの書き込み、ページ分割時の、変更ログの書き込みなどとかく書き込みコストが高い
- フラグメンテーションの問題がつきまとう
マルチカラムインデックスと R-tree
B-Tree と LSM-tree はいずれも単一のキーを値にマッピングするデータ構造であり、複数カラムを効率的にインデックスすることは苦手である。複数カラムを結合して単一のキーとして扱うことはできるが、結合順序に依存することは避けられない。これはつまり、電話帳の索引が姓→名の順で検索しやすくても、名→姓で引くことはできないようなものである。
経緯度データに代表される多次元データを効率よくインデックスするには R-tree のようなまた異なるデータ構造が利用される。
全文検索とあいまい検索
同意語、ミススペル、コロケーションなどを含めたファジーなインデックスを実現するには、また別のテクニックが要求される。 Elasticsearch のエンジンである Lucene は検索語句を入力として受け取り、 レーベンシュタイン距離 に基づいて検索を行う。 Lucene 自体が 有限オートマトン として動作するよう設計されているのである。
すべてをメモリに記憶する
ここまで扱ったトピックは、いずれもディスクに永続化されたデータを効率的に検索するためのものであった。メモリの生産コストが下がったことで、メモリ上で動作するストレージも登場してきている。
インメモリデータベースは伝統的なデータベースよりも速く動作するとされる。よくある誤謬であるが、これはディスクシークやI/Oが省略できるぶん高速であるというよりもむしろ、メモリとディスクの間でデータのエンコード/デコードが不要であるため高速化できているのである。
例えば redis は優先度付きキューやセットを実装しているように、インメモリデータベースはディスクデータベースでは不可能だったデータ構造も実現できる。またデータの読み書きはメモリ上で行いつつも、データの永続化のためにディスクへの書き出しもサポートするプロダクトも存在している。
今後、不揮発性メモリが一般化すれば大きくパラダイムが変わるから、それも見据えてアンテナを張り、思考することが要請される。
信頼性、保守性、スケーラビリティ: Designing Data-Intensive Applications 第1章より
Designing Data-Intensive Applications の第1章の読書ノートを公開する。主題はシステムの信頼性、保守性、スケーラビリティについてである。
個別の手法や技術というよりは、システム設計や技術選定の際に大事にすべきマインドセットに重点をおいた論文である。おおいに同意、納得しながら読めたし、これからも長く大切にしたい視座だとしみじみ味わっている。いつもよりもよく咀嚼しながら読み進めたのに加えて、ダメ押しで記憶に焼き付けるために、サマリとして記録しておく。
現代のシステム開発のパラダイムは、計算能力よりもデータの量、データの複雑度、データの変化の速さを問題にする。このようなシステムをデータシステムと呼ぶことにする。
データシステムに必要な構成要素はおおかた世の中に出揃っている。データベース、キャッシュ、検索インデックス、メッセージキュー、バッチ処理、などの諸要素である。とはいえ、現実の技術選定のあり方は、プロジェクトの特性によるとしか言いようがない。実際、 Redis はデータベースだがメッセージキューとしても使えるし、Apache Kafka はメッセージキューだがデータベースにもなる。そして往々にして、「どのツールを採用するか？」というよりも「どのツールをどう組み合わせるか？」ということが問題になる。
そうしてデータシステムを設計するとき、主要な関心ごとは例えば次のような項目となる:
- どうやってデータの一貫性を保証する？
- どうやってデータシステムの一部が壊れても主要機能が動き続けられるようにする？
- どうやって負荷に耐えてスケールさせる？
- どんな API を用意すれば使いやすいサービスになる？
もちろん糸口は様々にあるが、多くの場合で有効な、3つの基本的な考え方がある。それが表題に掲げた「信頼性、保守性、スケーラビリティ」であり、これらの要素はいずれも非機能要件に分類されるものである。それぞれについて簡単に要約するとこうなる。
- 信頼性: ハードやソフトの障害、あるいはユーザーエラーへの耐用性
- 保守性: 新しいメンバーが既存の振る舞いを守りながら開発に参入していけるか？
- スケーラビリティ: データ量やトラフィックの増大に耐えられる仕組み
以下に見出しを立ててより詳しく検討してみよう。
信頼性
システムの信頼性とは、なにかおかしなことが起きても機能し続けることである。部分的な欠陥が存在する可能性をあらかじめ織り込むことで、「部分で障害が発生しても全体は機能し、要件を満たし続けることができる」という状態を作り出すメカニズムが要請される。たとえばカオスエンジニアリングは有効なアプローチといえるだろう。
ハードウェア障害
耐用年数など、確実な対応が求められる問題は存在する。しかしクラウドコンピューティングの時代であるから、個々のシステム設計者がこのレイヤの問題に精通している必要は必ずしもない。
ソフトウェアエラー
ハードウェア障害によって全てのマシンが連鎖的に落ちることは稀である。しかしソフトウェアエラーにはそれがありうる。テストや監視といったプラクティスの小さな積み重ねで予防できるから、手を抜かずに基盤を整備しよう。
人的エラー
操作ミスや想定外のユースケースによってシステムが破綻することはありうる。そうしたエラーを起こさせないための制約を、ユーザーが不自由を感じない範囲で考えて設計しよう。たとえば自動テストはとりわけコーナーケースの振る舞いを調べるのに有効であるし、本番環境相当のサンドボックスがあればなおよい。明快な監視メトリクスを定義して、問題を予兆することも可能である。
以上が信頼性の議論である。これらは開発コストとのトレードオフで犠牲にされることも少なくない。絶対悪だとはいわないが、その判断は決して軽い意思決定ではないことはよく認識しておこう。
保守性
保守性を高めるにはどうすればよいか？ 逆を考えてみよう。保守性が低くならざるを得ないシステムとはどんなものだろうか？ それは、運用が難しく、新入社員には扱いづらく、変更のするのが困難なシステムのことだ。
ここでは「保守性が高い」という状態を運用が容易で、シンプルで、進化の余地が用意されたシステムと定義しよう。
運用が容易であること
悪いソフトの欠陥を運用でカバーすることはできる。しかし悪い運用はどれほどよいソフトも安全に扱うことはできない。
できることは、ここでも小さなプラクティスの積み重ねしかない。たとえば、個別のマシンに依存せず、システムを停止せずにメンテナンスできるようにすること。あるいは、規定の振る舞いには制約を与えつつ、管理者権限で柔軟に操作できるようにすること。それから、予想可能な振る舞いを定義し、驚きを最小にすること。人に優しいシステムを設計しよう。
シンプルであること
小さくシンプルなシステムが、やがて大きくなるほどに複雑性を高めていく。これは当然の摂理である。しかし、大きなシステムでも複雑性を下げることは十分に可能である。
複雑性には「本質的な複雑性」と「偶発的な複雑性」がある。後者は「事故的な複雑性」といってもよいかもしれない。これを削減することを考えよう。
要するに、「単純な要件を複雑に実装してしまっている」ような箇所を見つけ出し、そこにアプローチしよう。単にテストとリファクタリングが有効なこともある。あるいは適切な抽象化が要請されることもあるだろう。これらの営みによって、この種の複雑性は排除できるはずである。
小さなプログラムならともかく、分散システムにおいてどう抽象化を実装するかを考えるのは難しい。これはより大きな問題であるから、のちの章に話題を譲ろう。
進化の余地が用意されていること
システムの要件は常に変わりうるものである。まずはこの真理に向き合おう。変わり続ける要件に対応できないシステムは本質的に脆弱である。
アジャイルとは組織論だが、方法論としてこの問題に対して有効である。大規模データシステムにおいてどのようにアジャイルを実践するか？ これもまたより大きなトピックである。組織のシンプルさ、システムの抽象化にも密接に関係する問題提起として、これも詳しい議論はのちの章に議論を譲ろう。
スケーラビリティ
システムをミクロに観察して「これはスケールする/しない」と評価することは本質的にはできないはず。より適切な問いは「システムが成長したときに対応できるか？」や「さらに計算資源を投じるときはどうするか？」といった事柄である。これらの問いに答えるには、まず「負荷」を定義しなければならない。
「負荷」の定義はプロダクトの性質によってさまざまである。まず次のような単純な命題から考え始めてみよう。
「負荷」を定義し、それに影響を与えるパラメータを定義できて、はじめてパフォーマンスを語ることができる。2012年のTwitterにとって、それは「ユーザーあたりのフォロワー数の分散」であった。リソース量を変えずに負荷を増やすとどうなる？ あるいは、負荷が増えてもパフォーマンスが変わらないためにはどれだけリソースが必要になる？
パフォーマンスの代表的な指標であるレスポンスタイムを例にとってみよう。最大値や最小値をターゲットにすることにはあまり意味はない。結果が分散していることを前提に、パーセンタイルで評価が行われることが多い。95%, 99%, 99.9%あたりをメトリクスとすることが多い。具体例として、 Amazon では 99.9% の厳しいパーセンタイルをレスポンスタイムの重要指標としている。レスポンスに多くのデータが含まれるのはしばしば大のお得意様であるから、もっとも読み込み負荷の高い上客をこそ満足させることが重要なのである。そのうえでこれより厳しい99.99%のパーセンタイルに投資することは効果に見合わないとも結論づけられている。
「負荷」の定義を誤ったままパフォーマンス改善に着手してしまうと、大きな機会損失につながってしまう可能性が高い。ゆえにスタートアップなどではしばしば、負荷増大を心配するよりも機能の柔軟性を高めるほうが有効である。
Ruby の基数変換において基数の上限は 36 である
SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) に参加した。D - Base n を解きながら、いままで知らなかった Ruby の振る舞いを知りえたので書いておく。
0-9 からなる文字列を、整数 d で基数変換し、整数 n 以下かどうか調べる。これがやりたいことである。整数オーバーフローに気をつけながら変換アルゴリズムを書くのが面倒に思えて、 Ruby の String#to_i ならサクッと安全に変換できるかな？ と考えた。つまりこんな感じである。
def f(s, d, m) s.to_i(d) <= m end require 'minitest/autorun' class T < Minitest::Test def test_f assert_equal(true, f('22', 3, 10)) # 3進数表記: '22'.to_i(3) == 8 < 10 assert_equal(true, f('22', 4, 10)) # 4進数表記: '22'.to_i(4) == 10 < 10 assert_equal(false, f('22', 5, 10)) # 5進数表記: '22'.to_i(5) == 12 > 10 end end
で、このメソッドを繋ぎ込んで、適当な入力のテストケースを足して実行してみると、こんなエラーメッセージを出して落ちてしまう。
ArgumentError (invalid radix 37)
どうやら基数が 36 以下であるうちはよいのだが、 37 はダメらしい。まったく予期していなかった結果で、どうしてだ？ 素数だからか？ と無意味な当てずっぽうをはじめてしまいかねないほどにはパニックを起こしていた。
一呼吸おいて、インターフェースを調べてみるとちゃんと書いてあった。
Returns the result of interpreting leading characters in str as an integer base base (between 2 and 36). 1
「へええ！」と思いつつ、とはいえコンテスト中に深く考える余裕はなく、さっさと Ruby で実装する方針は諦めて自前の変換アルゴリズムを書いたのだった。
一晩あけてちゃんと考えてみると、当然の振る舞いというよりない。要するに、 [0-9a-z] の 36 要素を超えて全順序を定義することはもとよりできないというだけの話である。もちろん Integer#to_s でも同じことである。今回のケースでいえば、レシーバの文字列は 0-9 のみを含む、というのは問題文の制約にすぎない。そうでない自由な文字列を任意の値で基数変換するのは不可能であるから、結局のところ基数変換のロジックはユーザーが自前で用意するよりない。
ところで問題そのものの解法については、制限時間を10分残したところで二分探索する方針にようやく辿りついたが、実装にダラダラ手間取ってしまい、15分超過してようやく正解できた。単純に二分探索が手に馴染んでいないことが白日のもとにさらされたわけである。今回のコンテストで手痛い思いをしたので、次にあらわれたときには倒してやるからな、という気持ちでいる。
提出 #20343302 - SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)
新入社員になった
大学を出て以来はじめて会社に所属することになる。
内定が決まったときから興奮ばかりしてきた。当日を迎えて、いっそう興奮しているかというと、そういうわけでもない。むしろ身の引き締まる思いを新たにしている。不思議なものだ。
同期入社のひとたちはいろんなバックグラウンドを持っている。先輩社員のみなさんもそう。みんなとてもすごいひとにおもえる。自分はほんとうに井の中の蛙だったなあとおもう。要するに、いまになって不安になってきている。
初日から手を動かすことを求められないことに落ち着かなさを感じているのかもしれない。いままでいくつかの案件に携わったが、おおむね参画当日の午後にはすでに手を動かしはじめていた。初日にプルリクを開けるようにと、自分でも気合いをいれて臨んだものだった。
それが今日はなかった。
研修を受けた。経験のないスケールで成長するプロダクトのほんのわずかな概観を与えられた。圧倒される間に一日が終わった。しかもこれが一週間つづく。
はっきりいって、こんなに丁重に扱われた経験はない。一日でも早く活躍させてもらえるために、あえて最初の一週間を座学に費やすという逆説。あまりに懐が深い。
果たしてこんなに贅沢なことがあっていいのだろうか？ まだなんの貢献もしていないのに、こんな待遇を受ける価値があると思ってくれる根拠はなんだろう？ そんな倒錯した不安がいまになって訪れている。果たして自分は適格なのか？
しかしこれは僕の悩むことではないだろう。もし僕が力不足であったとして、それは僕の責任ではない。こちらの愚鈍のためにこちらが責められても困る。そして逆から見ると、これだけのオンボーディングプロセスを有する会社において、その手前の採用プロセスがガバガバということは考えづらい。だからきっと大丈夫だ。
そう思って寝る。
macOS で GUI アプリのインストールをスクリプト化する
Homebrew/homebrew-cask で homebrew 経由で GUI アプリをインストールできる。
もともと aws-vault や corretto などは cask でいれていたけれど、インストール可能な cask の一覧をみるとよりどりみどりだ。1password に evernote, workflowy といった生活必需品相当のアプリを環境構築スクリプトに入れ込むことができる。
list casks to fetch in homebrew.sh by sato11 · Pull Request #2 · sato11/dotfiles
ちょうど新しい PC を支給されたところなので使ってみたところ、実に楽チンにセットアップが終わって満足している。
