Posts

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それ自体が課題になるわけではないと結論づけている。

分散トレーシングシステムDapperをGoogle社内で開発、デプロイ、運用した知見がまとめられている。 運用期間は2年にわたる。 Dapperをもとに、TwitterはZipkinを、UberはJaegerを開発した。 Dapper以前に開発されたMagpieやX-Traceとの違いは、サンプリングされたリクエストのみをトレースし負荷を下げるられたり、少数の共通ライブラリだけを測定対象したりする点にある。

ナレッジグラフの未知のリンクを予測するモデルは、一般に大きなグラフをあつかえるようにネットワークを浅くし、処理性能の高速化をはかる。一方、代償として層の深いモデルと比べて表現力を欠く。 提唱されるネットワークConvEは、畳み込み層をつかった深めのネットワークで予測性能の向上をはかる。 層が深くなると計算コストの増加や過学習が課題になるが、先行研究のDistMultやR-GCNと比べたConvEのパラメタ数は1/8や1/17であり、パラメタ効率がよい。

データベースのトランザクション制御Multiversion Concurrency Control(MVCC, 多版型同時実行制御) 下のトランザクションが逐次実行と等価な結果になる条件を定義した。 また、その定義を既存のMVCCのアルゴリズム3つにあてはめ、アルゴリズムの正しさを確かめた。

The Part-Time Parliamentで提唱された分散含意アルゴリズムPaxosをLamport自身が平易に解説した。 エージェントの処理速度やメッセージが配信されるまでの長さに仮定はない。 メッセージは複製、喪失してもよい。 他方で、ビザンチン将軍問題は扱わず、メッセージが壊れることは考えない。

プロセスが1つでもクラッシュしうる場合には常に含意を保証できる完全な非同期アルゴリズムは存在しないことを示した。 この定理はFLP帰結とよばれる。 FLPは、著者Fischer, Lynch, Patersonの頭文字に由来する。 ここでの完全は、プロセスの処理速度やメッセージの配信遅延に仮定をおかず、同期クロックがないためにタイムアウトを使えず、ほかのプロセスが別のプロセスの障害を検知できないことを意味する。 いいかえると、含意アルゴリズムを実装するには上のいずれかを仮定しなければないことを示した。

Googleの分散ストレージで生じた障害の統計をとり、ストレージの可用性の予測モデルを提唱した。 ディスク、ノード、ラックなどハードウェアの粒度を変えて、粒度ごとの平均故障間隔を計測し、故障原因を分類した。 2分のウィンドウで生じた障害をグループにまとめると、ほとんどの障害が同時多発的な障害の一部であった。 20以上のノードを巻き込む大きな障害では、別々のラックにあるノードに障害が起きるよりも、特定のラックのノードに障害が起きることが多かった。

論理型のデータベースのクエリ言語Datalogの構文、意味論、最適化が解説されている。 最適化の節はサーベイ論文の形式で、最適化を分類し、各種類の先行研究に案内がある。

ナレッジグラフを低次元のベクトル空間に埋め込むアルゴリズムTransEを提案した。 エンティティは複数種類のラベルをもってよく、埋め込まれたエンティティやラベルの距離を計算することで、入力されたグラフに欠けているリンクを推定できる。