分散データベースの２相コミット

２相コミット (２フェーズコミット) とは

複数のデータベースの内容を更新する時に、処理が矛盾しないように整合性を保つための手法。 具体的には、複数のデータベースを更新する前に、全てのデータベースが更新可能かどうかを確かめてから、一斉に更新を行う。

２相コミットの処理ステップ

1. マスターのサーバーから複数のデータベースへ更新可能か否かを問い合わせる
2. それぞれのデータベースは自身が更新可能か否かをマスターのサーバーへ返す
3. マスターのサーバーは全てのデータベースが更新可能であることを確認した後に、一斉にデータベースの更新を行う
4. 更新処理の途中であるデータベースが更新処理を失敗した場合、失敗したということをマスターのサーバーへ返す。
5. 失敗を知ったサーバーは全てのデータベースへ、ロールバックの指示を出し前の状態へ戻す。

更新可能か問い合わせるフェーズと、実際に更新するフェーズがあることから２フェーズコミットと呼ばれる。

バッファサイズの計算

バッファとは

バッファとは、処理速度の異なる装置間にデータを転送する際に、速度のギャップを埋めるためにデータを一時的に蓄える機能。

例

以下のような転送を考える。

装置A ---送信量S---> バッファ ---受信量R---> 装置B

装置Aは１秒当たり送信量Sに対して、装置Bの受信量はRである。また、S > Rの時、装置Bは受け止めきれない。 この時、バッファでは１秒間でS - Rのデータ量を位置保存すれば装置Bがパンパンになることを防げる。

バッファサイズの計算

上記の条件で、T秒間データを転送すると、バッファサイズはT * (S - R)必要になる。

仮想記憶システムのページング方式

主記憶

CPUが直接書き込みができるメインメモリの事。

仮想記憶

主記憶上にある実記憶領域の１部を必要に応じてハードディスクなどに退避させることで、見かけ上、物理的な容量より大きな主記憶領域を利用できるようにする仕組み。

ページング方式

仮想記憶システムにおいて、主記憶からハードディスク上にデータを退避させる時に、ページと呼ばれる一定の大きさの区画に分割して、ページ単位で内容を管理する方式。

主記憶の容量がパンパンになってきたら、使っていないページをハードディスクに退避させて、新しい容量を確保する。そのページを使いたくなったらハードディスクから取り出し、また新たなページをハードディスク退避させる。これによって実容量より大きな容量を使うことができる。

RAID (Redundant Array of Inexpensive Disks)

RAIDとは

RAIDとは、複数の磁気ディスクを並列に接続して、信頼性の向上やアクセスの拘束を図る手法。 RAIDには複数の種類がある。

RAID 0

RAID 0とは、データを複数のディスクに細分化して書き込み、アクセスを高速化する方式。(ストライピング)

RAID 1

RAID 1とは、データを複数のディスクに２重に書き込む方式。(ミラーリング)

RAID 5

RAID 5とは、データとパリティデータを複数のディスクに分散して書き込む方式。

パリティとは

パリティとはデータの一部が破損した場合に、復元するためのコード。RAID 5はRAID 0と同様にデータを分散させて保存している。つまり同じデータは複数のディスクに保存されていない。RAID 0の場合は、あるディスクが破損した場合は、そのディスクに保存されたデータは復元することはできないが、RAID 5の場合は、パリティと残りのデータを元に破損したデータを復元することができる。

キャッシュメモリの書き込み方式

キャッシュメモリの書き込み方式

キャッシュメモリへの書き込み方式には、ライトスルー方式とライトバック方式がある.

ライトスルー方式

プロセッサがメモリにデータを書き込む際、キャッシュと主記憶に同時に書き込む方式。 書き込み処理は高速化できない。

メリットとしては、キャッシュと主記憶の一貫性を保つことができる。

ライトバック方式

書き込みデータをキャッシュに一旦加え、あとでまとめて主記憶に書き込む。 メリットとして、主記憶へのアクセス頻度が減るので、書き込み時のメモリアクセスが高速化できる。

MIPS計算

MIPS計算

MIPSとは、プロセッサが１秒間に実行する命令数を百万単位(10⁶)で表したもの。

問題

動作クロック周波数が700MHzのCPUで、目入れ実行に必要なクロック数及び、その命令の出現率が表に示す値である場合、このCPUの性能は約何MIPSか

命令の種別	命令実行に必要なクロック数	出現率(%)
レジスタ間演算	4	30
メモリ・レジス間演算	8	60
無条件分岐	10	10

クロック(クロック周波数)とは

CPUが命令を処理する時のテンポのようなもの。クロック周波数が高ければ高いほど、一度に多くこのことができる。つまり性能が良いことになる。 今回の問題では、クロック周波数が700MHzのCPUなので、１秒間に700 * 10⁶回クロックが打たれることになる。言い換えると１回のクロックは1/700*10⁶秒で発生することになる。

表を見てみると、レジスタ間演算という命令を実行するのに必要なクロック数は４つ。これが30％の確率で行われる。今回は３つの命令が存在するので、このCPUでの命令実行に必要なクロック数の平均を出してみる。

命令実行に必要なクロック数の平均 = 4 * 0.3 + 8 * 0.6 + 10 * 0.1 = 7 クロック

今回の問題で問われていることは、このCPUが１秒間で何回の命令を実行できるかである。１回の命令で平均７クロック発生するので、クロック数が700MHzのCPUでは、

MIPS = 700 * 10⁶ / 7 = 100 * 10⁶ = 100MIPS

となる。

Binary Search Tree Iterator in LeetCode

問題

Binary Search Treeにおけるイテレータを実装する問題。next()メソッドで取得できる値は現時点での最小値となる。

Binary Search Tree Iterator - LeetCode

ソースコード