読者です 読者をやめる 読者になる 読者になる

Pilaf: Lightning-fast Cloud Infrastructure using RDMA

 最近、RDMA (Remote Direct Memory Access) を使った分散KVSの論文をいくつか読んだので、ここにまとめていきたいと思います。今回は2013年のUSENIX Annual Technical Conferenceで発表されたPilafという美味しそうな名前の分散KVSの論文
http://news.cs.nyu.edu/~jinyang/pub/pilaf-usenix13.pdf
について、簡単にまとめます。

概要

 RDMA Operation (Write/Read) を利用することで、クライアントはサーバのCPUを介さず直接メモリにアクセスし、データの読み書きを行うことができる。これにより、低レイテンシ、高スループット、CPUオーバーヘッドの削減を達成することができる。しかし、複数クライアントがそれぞれ勝手にサーバのメモリを読み書きすると、メモリアクセスの競合が起きてしまうので設計を考える必要がある。
 この論文では、getオペレーションはRDMA Readを使い、putオペレーションはSend/Recv Verbsを使うという設計を提案している。

InfiniBandを使った通信

 InfiniBandには複数の通信サービス、通信モデルが用意されている。その中でも特に代表的なものを幾つか見ていく。

IP over InfiniBand (IPoIB)

 InfiniBand上でIP ネットワーク層を構成するサービス。IPoIBを使うことで、Socketを使った既存のプログラムからでもInfiniBandを利用することができるが、パケットはカーネルを経由してアプリケーションに渡される。

Send/Recv Verbs

 User Verbs API*1を使った通信モデルの1つ。送信側(ローカル側)はSend operationを実行し、受信側(リモート側)はRecv operationを実行する。カーネルを経由せずにメッセージのやり取りを行うことができる。

RDMA Write/Read

 User Verbs APIを使った通信モデルの1つ。送信側(ローカル側)はSend operationを実行するが、受信側(リモート側)でRecv operationを実行する必要はない。従って、カーネルを経由せず、リモートのCPUも全く介さずにデータを送受信することができる。

比較

 論文では、この3つ + TCP/IP (Ethernet 1Gbps)に対して、ベンチマークを取ってレイテンシとスループットを比較している。IPoIBがTCP/IP (Ethernet 1Gbps)に近い性能を示しており、カーネルを経由するパケット処理によって性能が出ないことが示されている。RDMA Write/Readが一番良い性能を示し、Send/Recv Verbsがその次に良い性能を示している。

Pilafの設計

put

 putオペレーションはSend/Recv Verbsで行われる。クライアントはサーバにputリクエストを送り、サーバがそれを処理する。RDMA Writeを使わずにSend/Recv Verbsを使うことで、リモートのメモリに対する書き込みの競合が起きないようにしている。

get

 getオペレーションはクライアントがRDMA Readでサーバのメモリを直接読み込む。クライアントはまずkeyに対応するハッシュエントリを取得する。ハッシュエントリにはkey-valueのアドレスが含まれているので、それを使ってkey-valueを取得する。

read-write race

 getオペレーションをRDMA Readで行うため、クライアントが発行したRDMA Readとサーバによるputリクエストの処理との間でメモリアクセスが競合する可能性がある。この問題に対して、Pilafではデータにチェックサムを付けることで、クライアント側でinconsistentな読み込みを検知できるようにしている。

cuckoo hashing

 シンプルに分離連鎖法を用いてハッシュテーブルの探索を行った場合、ハッシュテーブルの空きが少なくなるにつれてハッシュの衝突が頻発し、探索時間が増えてしまう。そこで、Pilafでは、探索が必ず定数時間で終わるCuckoo hashingを用いる。

実装

 C++で実装し、メモリマネージメントはSQLiteのmem5を利用している。チェックサムにはCRC64を使っている。実装は公開されていないが、論文著者のChristopherさんに連絡すれば見せてもらえるかもしれない。
http://ns3.fs.net/projects/pilaf/

評価

 Yahoo! Cloud Serving Benchmark (YCSB) を使って性能評価を行っている。peak throughputは 1.3 million ops/sec

感想

 シンプルな設計でわかりやすいと思った。個人的には、卒研でInfiniBandを初めて使うことになった時、IPoIBやらSend/Recvやらなんやらと色々あって、どれを使えば良いのかよくわからなかったので、2章の各通信モデルの説明がとても参考になった。RDMAを使った分散KVSの設計は他にもherdFaRM, HydraDBなどいろいろあるので、それぞれちゃんと論文を読んで理解したい。

*1:ユーザーレベルで通信を行うためのAPI