論文メモ Translating Embeddings for Modeling Multi-relational Data
ナレッジグラフを低次元のベクトル空間に埋め込むアルゴリズムTransEを提案した。 エンティティは複数種類のラベルをもってよく、埋め込まれたエンティティやラベルの距離を計算することで、入力されたグラフに欠けているリンクを推定できる。
Posts
論文メモ 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 AuroraやDynamoで採用されている。 ファイルの読み込みや書き込みのトランザクションは、複製されたファイルのもつ票を集め、所定の数、クオーラムを越えたときのみ実行される。 これにより、読み込み、書き込みの線形の一貫性が保証され、実行中のトランザクションが高々一つであるかのように見せかけられる。
論文メモ Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases
AWSで提供されるRDBM, Amazon Auroraのアーキテクチャを解説した論文。 分散システムをクラウドにおく場合、計算やIOはノードに分散され、ボトルネックではなくなる。 そして、ボトルネックは、DBインスタンスとストレージ間のネットワークになる。 この仮説もと、プライマリインスタンスが、別テナントのストレージに直接Redoログを送ることで、レプリカインスタンスとストレージ間の負荷を減らし、処理性能の向上をはかる。 また、レプリケーションのために、MySQLがRedoログだけでなくバイナリログなど複数種類のログをスレーブに送るのに対し、AuroraはRedoログだけを転送する。 これにより、リカバリや縮退、フェールオーバの性能も向上している。
"One Size Fits All": An Idea Whose Time Has Come and Gone (2005)
2005年に発表された論文で、これまでのようにDBMSを様々なデータ中心のアプリケーションに利用することがデータベース市場で受け入れられなくなったと主張する。 データウェアハウスとストリーミング処理を例にとり、これらに特化したデータベースをDBMSで代用することの限界が説明されている。 表題の"One Size Fits All"はフリーサイズ、転じて、万能、汎用的を意味する。