Posts

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

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

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

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

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

宣言型言語Datalogを拡張した言語でネットワークプロトコルと分散システムを開発した7年間の経験から、次世代の並列分散プログラミング言語の基礎になる理論上の予想を4つ提唱した。 Datalogは、論理プログラミング言語Prologのサブセットの構文をもった言語である。 予想の説明に使われるDatalogの拡張言語Dedalusは、分散システムのノードが互いの時刻を直接的に推論できない性質を、送受信するデータから離れたノードの時刻を推論する問題に帰着する。

Bigtableは、数千のコモディティサーバ上でペタバイト級のデータをホスティングできる分散ストレージであり、行、列、タイムスタンプをキーとして値の文字列を保存する。 論文の発表された2005年時点で、検索エンジンのインデックス, Google Earth, Google Financeなどの多様なアプリケーションの実装に使用されている。

Aerospikeは、高い対障害性をもった分散データベースで、正式にはCitrusleafという。 CPU, DRAM, HDDやSSDを搭載したコモディティなサーバでクラスタを組める。 ノード同士はTCP/IPで通信し、シェアードナッシングなクラスタを構成する。 処理性能の向上のために、スケールアウトだけでなく、スケールアップも重視しており、ハードウェアを意識した実装で高速化をはかっている。

Spannerは、世界中のデータセンタにデータを複製する高可用な分散データベースで、外部整合性のある分散トランザクションを保証する。 ユーザからみると半リレーショナルなデータモデルのデータベースであり、各テーブルに一つ以上の順序つき主キーが必要なところがリレーショナルデータモデルと違う。 一方、内部は文字列とタイムスタンプの組をキーにしたキーバリューストアであり、Single Paxos状態機械でデータの一貫性を守りながら複数のデータセンタにデータを複製する。

Coddがリレーショナルデータモデルを提唱した70年の論文。 データをリレーション(SQLでのテーブル)として束ね、リレーションを順序なしのタプル(SQLの行)で構成する。