MySQLのB-Treeインデックスを理解する
MySQLのインデックスには一般的にB-Treeインデックスというものが使われています。
BTreeはインデックスのアルゴリズムなのですが、今回は何故これが一般的なのかについてです。
B-Treeとは
インデックスは実テーブルのデータを素早く探す為の索引ですが、アルゴリズムによって大きく仕組みが異なります。
B-Treeは平衡木構造というデータ構造をもっています。
平衡木はバランスドツリーとも言われ、その名の通りツリー構造の高さを可能な限り等しくした形になっています。
二分探索木
平衡木は二分探索木という構造を元にして成り立っています。
二分探索木とは、ルートノードと呼ばれる根本のノードから分岐していくツリー状のデータ構造です。
この構造の特徴はバランスが整った構造になっている場合、計算量が少なくて済みます。
ただ、ちゃんと整っていればの話で、実際に運用してデータの削除や追加などが行われると歪な構造になっていきます。
平均計算量はlog nになりますが、最悪はn回計算しないといけなくなります。
これを解決するために平衡木というツリー構造があります。
平衡木を作るためのアルゴリズム
平衡木は二分探索木を基本として、いかに高さのバランスが均等になるかを考えられたものになります。
その中の一つのAVL木というツリー構造になります。
AVL木はツリーを回転させ高さを揃えるアルゴリズムです。
具体的には、データが葉に挿入されたとき、部分木の高さが2以上なら木を回転させ高さの差が1以内になるように調整されます。
こうすることで計算量がlog nになるようにします。
AVL木を利用し、多分岐の構造を持つのがB-Treeになります。
B-Treeインデックスの仕組み
B-TreeのAVL木の最もたる違いは、2以上の子ノードを持つ事が出来るという点になります。
木の深さを抑えて読み取り回数を減らすような構造にすることで、素早くデータの読み出しが可能になるからです。
ルートノードと中間ノードにはキーと子ノードへのポインタが格納され、実データはリーフノードに格納されるます。そして検索するときにルートからキーによってたどっていくノードを変える仕組みになっています。
つまり、データを各ノードで持たないので効率の良い、高速なデータ検索が可能となるという訳です。
terraformのベストプラクティスとは
terraformは手軽にファイルに書いて実行できますが、しばらくするとある事で悩む事になります。
それは・・・terraform自体の構成をどうするかという事です。
最初は同じファイルにどんどんリソースを定義していくと思います。それで数が増えたら種類毎にファイルを分けたりとか。
しかしこの方法だと同じディレクトリに全てのリソースが存在することになり、planするだけで全読み込みは結構無駄な感じがしてきます。
そこでディレクトリ構成をどうにかしようと思うのですが、私はどうすればいいのかが中々見つからずに頭を悩ませました。
なので今回はベストプラクティスは何か。について書いていきます。
環境が分けられている場合
最もやりやすいのがインフラ環境が分けられている場合です。
これはworkspaceを使って開発と本番環境を切り離すことで、同じ構成を別環境に構築できるので、開発→本番のフローで構成が異なる可能性がなくなります。
ただ、それぞれの環境で独自に定義したい場合は各workspaceにそれぞれリソースを定義していく必要があるので、多いとやや面倒です。
共通で利用したいリソース
モジュール機能を使う事でディレクトリ外のtfファイルを読み込み共通化して利用することができます。
これはworkspaceと違って汎用化できることが可能なので、使えるシチュエーションは多いと思います。
複数のtfファイルを管理する場合、例えばEC2だったらインスタンスタイプだけを変えたいときがあると思いますが、リソースの定義だけをしておいて、variablesなどで差異を吸収するという形で使う事でできます。
ただこれもモジュールのアンチパターンがあるので適当に定義するとあとから痛い目にあいます（経験談）
一つのリソースだけを定義したモジュールを作るのは最もたる例です。
単一モジュールだと、リソースが増えるにしたがってモジュールが増えていきますし、それだけ汎用性を失っていくことになります。
どこまで汎用化するのは中々難しいところがありますが、この辺りは運用しながら見極めていくしかありません。
インフラがスケールするに従って定義していく形になると思います。
今回はterraformのベストプラクティスについて考えてみました。
まだまだ使い始めて日が浅いので、どういうのが効率的かつスケーラブルなのかを日々考えていきたいと思います。
RESTfulAPIの冪等性について考える
RESTAPIの各メソッドの処理には冪等性であるべきものと、そうでないものがあります。
冪等性とは。についてはwikiさんによるとこういう事だそうです。
冪等 - Wikipedia
詳しく書いてありますが、要するに「何度同じ事をしても同じ結果になるということ」です。
この「同じ結果になる」ということがRESTAPIに関しては大切で、毎回GETの結果が変わっていたらAPIとして成り立ちません。
ではよく使うCRUD処理に関して、冪等性を検証してみましょう。
GET
GETは直感的に分かる通り、冪等性であるべきメソッドです。
毎回違う結果が返ってきたらそもそも意味を成しませんね。
PUT
更新するPUTも冪等性があります。
同じリソースを同じ内容で投げて更新をかけたら、何度繰り返しても同じ状態になります。
投げるパラメータを変えない限りはずっと同じです。
DELETE
削除も冪等性があると言えます。
と、ここで疑問を浮かべる方もいるかと思います。「一度目はちゃんと削除される、二回目は既に無いのを消そうとしているから違うのでは」と。
確かにレスポンスで言えば一度目は200、二度目以降は404が返ってくると予想できます。
しかしこれは正しい状態なのです。なぜならAPIの冪等性とは「リソースの状態」に注目するからです。
特定のレコードを消すDELTEメソッドを何度投げても他のレコードは消えず、データ自体は二度目以降も同じ状態になります。
なのでこれは冪等性のある処理と言えるのです。
POST
上記の前提で話をするのなら、POSTでCREATEする動作は冪等ではない挙動と言うことができます。
毎回新しいレコードを作成するのなら、リソースの状態は変わっていきます。
API設計においてのメリット
ここまで各メソッドの冪等性について説明してきましたが、何故これが担保されていると良いのか。と疑問を抱く方がいるかと思います。
簡単に言うと、「リソースの状態を気にせずAPIを叩く事ができるから」ということになります。
例えばSNSのようなアプリでユーザーをフォローする機能があったとします。
これを冪等性がないAPIで作ると、未フォローのユーザーか、フォロー済みなのかの状態で挙動を変える必要があります。
条件分岐で未フォローなら〜とか、フォロー済みのとき〜とかつける感じですね。
2パターンくらいしかない場合ならこれでいいかもしれませんが、ここにブロック機能がついてブロックされていたら〜とか条件を追加していくと、どんどん複雑になっていきます。
そこで冪等性があるAPIだと、「リクエストを投げたらフォローする」という形になるので、仕組みがシンプルになります。
叩く側も現在の状態を気にする必要はなく、開発を進める点でもスムーズになりますよね。
