Posts

Dryad: Distributed Data-Parallel Programs from Sequential building Blocks

DryadはMicrosoftで開発された分散コンピューティングエンジンであり、MapReduceに近い。 処理を点、処理結果を受け渡す通信経路を辺とするDAGで、分散処理を定義する。 通信経路にはファイル、TCP, FIFOを使え、実行環境は1台のマルチコアのコンピュータから数千台のコンピュータまでスケールできる。 MapReduceは入力と出力が一つでなければならないが、DryadはDAGであれば入力と出力が複数あってもかまわない。

The Chubby lock service for loosely-coupled distributed systems

Chubbyは、助言ロックをかけられるファイルを作れる低容量のストレージであり、分散システム向けのロックサービスとしてはたらく。 処理性能よりも高可用性と信頼性を重視し、ロックを保持する期間は数時間から数日にわたる長いものを想定する。 ロックされたファイルで実行環境の情報を共有でき、例えばリーダーの選出にも使える。 Chubbyは既存のアルゴリズムを集積であり、表題の論文は、新しいアルゴリズムよりも、Chubbyの設計や想定していた使用方法や実際の使われ方の解説に重点をおく。 Chubbyはロックサービスとして作られたが、ネームサーバとして最もよく使われる。 数千規模の互いに依存するプロセスがあり、プロセスが落ちたら新しいプロセスに置き換えるとする。 このとき、ネームサーバにDNSをつかうと、DNSは時間で失効するキャッシュ方式なので、TTLを短くし、落ちたプロセスにリクエストが届かないようにすると、DNSへの負荷が増える。 一方、Chubbyのキャッシュは時間ではなくファイルに変更されたときに無効になるので、Chubbyをネームサーバに使うことで、名前解決の負荷を減らすことができる。

Congestion Avoidance and Control

86年の10月に生じたインターネットの輻輳の反省から、4BSDに7つのTCPの輻輳制御のアルゴリズムが導入された。 うち5つは、送信したパケットが到達や消失でネットワークからなくなるまでウィンドウサイズ以上の新しいパケットを送らない原則を守るためにある。 この原則をconservation of packets principleという。

The Notion of Consistency and Predicate Locks in a Database System

トランザクションを並行実行するときに、直列実行した場合と同じ実行結果をえるには、各トランザクションがロックを解放後に新しいロックを獲得してはならないことを示した。 その場合もデッドロックがおきうるが、それは並列実行を終了するためにはいつロックをかければよいかという議論である。 ここでは、並列実行が終了した場合に直列実行と同じ結果になる一貫性を保証できるロックの順序を問う。

Parallel Database Systems: The Future of High Performance Database Systems

データベースの処理性能を上げる手段として、特殊なハードウェアをもちいたり、メモリやディスクを共有した複数のコンピュータを使ったりするよりも、安価で単純に実装できることから、汎用的なコンピュータによる水平パーティションのシェアードナッシング構成を支持した。 論文が発表された1992年の時点でTeradataやTandem NonStopなどのパーティンション化されたデータベースがある。

Chain Replication for Supporting High Throughput and Availability

ストレージサーバーに順番をつけ、順にオブジェクトを複製することで、ストレージサービスの一貫性を維持しつつスループットと可用性の向上をはかる。 ここでのストレージサービスは、オブジェクトを保存し、クエリに対して一つのオブジェクトを返し、アトミックに一つのオブジェクトを更新できるものをさす。 また、一貫性は、オブジェクトごとにクエリと更新を直列的に適用し、更新につづくクエリが更新内容結果になることを意味する。 末尾のサーバーがクエリを受信し、該当するオブジェクトをクライアントに返す。 先頭のサーバーが更新リクエストを受信し、順にサーバーのオブジェクトを更新し、末尾のサーバーが更新の結果をクライアントに返す。

Implementing Remote Procedure Calls

Xeroxのプログラミング環境Cedarのために開発されたRPCを解説した84年の論文である。 RPCの開発目的は、分散コンピューティングを簡単に実装できるようにする、通信時間を短くする、通信をセキュアにすることの3点である。 RPCは大部分でMesaが使われた。

Dremel: Interactive Analysis of Web-Scale Datasets

Dremelは2006年からGoogle社内で利用されているDWHで、社外にはBigQueryとして提供されている。 列指向の形式でデータを保存し、SQLに似た言語のクエリでデータを検索できる。 Dremelは、サーバーのクラスタを木構造に組織し、ルートで受理したクエリの処理を下層のサーバに分配し、その結果を集約することで処理を分散し高速化をはかる。

Is Rust Used Safely by Software Developers?

crates.ioに登録された15,097個のクレートにおけるunsafeキーワードの使用状況を調べた。 調査したクレートは、調査を開始した2018年9月時点でcrates.ioに登録された全クレートの81%にあたる。 unsafeを含むクレートは、そのうちの29%だったが、依存するクレートにあるunsafeも対象にすると、50%におよぶ。 crates.ioの総ダウンロード数のうち90%を占める473個の有名なクレートに限定すると、60%のクレートunsafeが含まれる。 2018年9月から2019年6月までの10ヶ月間でunsafeの使用傾向に変化はなく、unsafeの数が少し増えただけであった。 unsafeの用途の大半はunsafeで修飾されたRustの関数を呼び出すためだった。 なお、コンパイラで生成されたunsafeキーワードは集計に含まれていない。

Design Tradeoffs for SSD Performance

HDDの処理性能を測るためのシミュレーションソフトDiskSimをSSD向けに改造し、SSDの設計における選択肢の分類と選択にともなうトレードオフを報告する。 主要な選択肢は、論理アドレスと物理アドレスのマッピング、ページサイズ、オーバープロビジョニング、複数のpackageでcontrollerに接続するピンを共有するgangingがある。