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を実行する。カーネルを経由せずにメッセージのやり取りを行うことができる。
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/
感想
シンプルな設計でわかりやすいと思った。個人的には、卒研でInfiniBandを初めて使うことになった時、IPoIBやらSend/Recvやらなんやらと色々あって、どれを使えば良いのかよくわからなかったので、2章の各通信モデルの説明がとても参考になった。RDMAを使った分散KVSの設計は他にもherdやFaRM, HydraDBなどいろいろあるので、それぞれちゃんと論文を読んで理解したい。
