Posts

Log-structured file system(LFS)は、91年に提唱されたHDD向けのファイルシステムであり、バッファリングした変更をディスクの連続領域に一度に書き込むことで、小さなファイルを大量に高速で書き込める。 また、クラッシュからのリカバリも、ディスク全体ではなくチェックポイント以降に追記された箇所だけを検査すればよいので、高速になる。

ARIES/IMは、B+木への直列化可能性のある並行処理とログ先行書き込み(Write-Ahead Logging, WAL)による復元を実現する。 ARIES/IMのベースには、先行研究のARIESがある。 復元手順はARIESとほとんど変わらない。 キーの参照先にあるデータのレコードとキーを同じロックで保護したり、ロックの代わりにラッチを使ったりすることで、ロックの頻度を下げ、B+木の高速化を実現する。

B木とその派生データ構造のサーベイ論文で、とくにB+木に重点がおかれている。 B+木は、全てのキーを葉におき、葉を隣接リストでつなぐことで、B木が不得手なシーケンシャルなアクセスを改善する。 これにより、定数オーダーの時間と空間計算量で逐次的にキーにアクセスにできる。 ランダムな検索、挿入、削除にかかる時間、空間計算量はB木と変わらない。 以降はB木のデータ構造を前提としてB+木の概要を説明する。B木について知りたい場合は、B木のオリジナル論文の解説記事を見てほしい。

Robust Random Cut Forest(RRCT)はストリームデータ向きの異常検知の手法で、Amazon SageMakerから提供されている。 バッチデータと違い、ストリームデータは新たなデータが随時追加、修正される。 RRCTは、特徴の値でデータを2分するノードからなる木の集合であり、データを追加したときに木の集合であるモデルを大きく複雑するものを異常と判定する。

1972年に発表されたB木のオリジナルの論文。 \(I\)をインデックスの大きさ、\(k\)をハードウェア依存の値とすると、検索、挿入、削除の時間計算量は\(\log_kI\)になる。 ここでのインデックスは、固定長の\((x, \alpha)\)を要素とする連想配列で、最大\(2k\)個のキーを格納できる連続したページ上にある。 \(\alpha\)には、データを保存した1つ以上のレコードへのポインタが格納される。

要素がハッシュ空間にあるかを高速に調べる手法で、ブルームフィルタの名で知られる。 偽陽性を許容し、ハッシュ値の保持に必要な空間を小さすることで、管理できるデータ件数を増やす。 例えば、データベースのストレージで使われており、検索するキーがデータベースに存在するか事前に確かめ、存在しないキーのための不要なディスクの読み取りを省いている。 偽陰性の誤りはない。

SSDのランダムな書き込みを高速化するために、インデックスのためのデータ構造FD-treeを提案した。 FD-treeのエントリ数が\(n\), ページサイズが\(B\)であれば、ランダムな読み込みと書き込みの計算量はともに\(\mathcal{O}(\log_B(n))\)になる。

Isolation Forestは、完全二分木による異常検知の手法で、iForestともよばれる。時間計算量が線形で、ハイパーパラメタがわずか2つで、メモリ効率がよい。 時間、空間計算量が少なく高次元のデータに向く。

TAOは、Facebookで開発されたソーシャルグラフのためのマルチリージョンの分散システムで、秒間10億件の読み込みと数百万件の書き込みの性能を発揮する。 Facebookは、もともとソーシャルグラフを、MySQLに保存し、memcacheでキャッシュし、PHPで問いあわせるシステムで構成していた。 TAOは、そのシステムの現状を引きつぎ、MySQLをストレージに採用している。

COVID19でソフトウェア開発者が在宅稼動(WFH)をはじめたことによる稼動時間の使い方、良好性(Well-being), 生産性の変化を調査した。 ロックダウンを実施した国々のエンジニア500名の中から、2020年4月20日から26日の一波について192名、2020年5月4日から10日の二波について184名を選び、サンプルを集めた。 結果、会社での勤務とWFHの間で、稼動時間の使い方はほぼ変わっていないかった。 また、一波において休憩と生産性の間に負の相関がみられたが、それ以外では良好性、生産性、社会性、心理の4つと特定の業務内容の間に相関関係はみられなかった。 結果、組織やエンジニアにとってWFHそれ自体が課題になるわけではないと結論づけている。