Posts

論文メモ Availability in Globally Distributed Storage Systems

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

論文メモ What You Always Wanted to Know About Datalog

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

論文メモ Translating Embeddings for Modeling Multi-relational Data

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

論文メモ The Declarative Imperative

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

論文メモ Bigtable: A Distributed Storage System for Structured Data

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

論文メモ Aerospike: Architecture of a Real-Time Operational Database

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

論文メモ Spanner: Google's Globally Distributed Database

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

論文メモ A Relational Model of Data for Large Shared Data Banks

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

論文メモ On Designing and Deploying Internet-Scale Services

MSNとWindows Liveで培われたシステム管理者による運用負担を減らすためのベストプラクティス集。 07年に発表された。 プラクティス集は、10のグループに分かれ、それぞれ複数のアドバイスからなる。 特徴的な内容に絞って以下に要約する。

論文メモ Weighted Voting for Replicated Data

1979年に発表されたレプリケーション管理のクオーラムモデルのアルゴリズムの論文で、以前紹介したようにAmazon AuroraDynamoで採用されている。 ファイルの読み込みや書き込みのトランザクションは、複製されたファイルのもつ票を集め、所定の数、クオーラムを越えたときのみ実行される。 これにより、読み込み、書き込みの線形の一貫性が保証され、実行中のトランザクションが高々一つであるかのように見せかけられる。