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の設計は他にもherdやFaRM, HydraDBなどいろいろあるので、それぞれちゃんと論文を読んで理解したい。

参考文献

http://news.cs.nyu.edu/~jinyang/pub/pilaf-usenix13.pdf
InfiniBand プログラムに必要な基本的な概念
Cuckoo Hashing - Radium Software

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

PostgreSQLにおけるPAXページレイアウトの実装

PostgreSQL

この記事は PostgreSQL Advent Calendar 2014 の12月24日担当分です。

筑波大学情報科学類の情報特別演習（担当：川島先生、対象は2年生 or 3年生）で「PostgreSQLにPAXを実装」というテーマがありましたのでやってみました。中途半端で拙い内容ですが、そのご報告を致します。コメントやアドバイスを頂けたら嬉しいです。

ページレイアウト

RDBMSのデータはテーブルとしてモデル化されています。テーブルには縦と横があるので二次元とみなすことができます。一方、ストレージ中のアドレス空間は一次元です。そのため、ストレージにデータを格納するには、テーブルを縦に切るか、あるいは横に切るかする必要があります。横に切るページレイアウトはNSM (N-ary Storage Model）と呼ばれ、縦に切るページレイアウトはDSM（Decomposition Storage Model）と呼ばれます。PostgreSQLはNSMを採用しています。

PAXレイアウト

さて、NSMを用いるとScan処理等においてCPUキャッシュ使用率が低くなるために性能が劣化する可能性があることが、2001年にWeaving Relations for Cache Performanceで指摘されました。この論文の著者らはNSMとページコンテンツは同一（但し属性数と行数が同じ場合のみ）だがページ内のレイアウトがDSMライクになっているPAXというページレイアウトを提案しています。PAXを用いればCPUキャッシュミス率をNSMに比して削減できることが論文中に示されています。当時はDBMSのボトルネックといえばI/Oのみが考えられていたのにCPUキャッシュミスが新しいボトルネックになる点を未来に先駆けて示した点で、この論文は示唆に富んでいると思います。PAXには性能改善だけでなく、実装が容易であることが述べられています。著者の発表資料（10枚目）には "low-implementation-cost, high-impact" と述べられており、先般の論文（2ページ、第二段落）には次のように記載されています。

"Finally, PAX has several additional advantages. Implementing PAX on a DBMS that uses NSM requires only changes to the page-level data manipulation code.
PAX can be used as an alternative data layout, and the storage manager can decide to use PAX or not when storing a relation, based solely on the number of attributes."

Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, and Marios Skounakis. 2001. Weaving Relations for Cache Performance. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB '01), Peter M. G. Apers, Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Kotagiri Ramamohanarao, and Richard Thomas Snodgrass (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 169-180.

実装例の調査

そうすると実装は簡単なのかなぁと思いました。でも色々探したのですが、PostgreSQLにおけるPAX実装のコードを見つけることができませんでした。こちらの先生の授業でこちらの方が実装していたようですが、詳細な資料がありません。また、A hybrid page layout integrating PAX and NSMとQuery processing techniques for solid state drivesでは実装しているようですが、やはり詳細な資料がありません。仕方がないので自力で作ることになりました。

実装

select id from test_32 where age = 20;

を対象問合せとしました。この問合せは実行プランになると下記のようになります。

                       QUERY PLAN
--------------------------------------------------------
 Seq Scan on test_32  (cost=0.00..16.38 rows=3 width=4)
   Filter: (age = 20)

この一番下の演算子はExecSeqScanです。ExecSeqScanの主たる動作モジュール(workhorse)はSeqNextです。この中に次の記載がありました。

 66         tuple = heap_getnext(scandesc, direction);

そのため、heap_getnextを辿ってみました。この中には heapgettup と heapgettup_pagemode があります。今回はページアクセスをしますので、heapgettup_pagemodeを辿ってみました。

ここで残念なことに気づきました。下記から明らかなようにタプルのデータはページ内データへのポインタとなっていたのです。下記の場所でページ内タプルへのポインタが与えられた後、ExecQualまでこのポインタは保持され、ExecQualでようやくselection operatorが処理される実装になっていました。このためにページはまずpin downされ、クエリプロセスが終わった段階でpin upされる模様です。これには驚きました。なぜならば高性能化のために selection operator が物理的なオペレータの最下層まで push down されることは常識だと思っていたからです。つまり下記の場所においてselectionが実行され、その結果が真となるタプルへのポインタのみが与えられるのだと思っていました。PAX実装の戦略として、PAXページのスキャン結果が真となるタプルを動的に構成してt_dataに与えようと思っていましたので、これには困りました。

 831                 tuple->t_data = (HeapTupleHeader) PageGetItem((Page) dp, lpp);

そこでPostgreSQLのデフォルト実装（NSM）において t_data を malloc & memcpy することにしました。PAXにおいても同様にしました．これによりPAXと同等な比較ができるようになったと考えています。

コード

作った結果をこちら (Github)に掲載しました。

性能

利用したPostgreSQLのバージョンは9.3.5です。キャッシュミス測定ツールにはPAPIを利用しました。性能測定ツールとしては oprofile, operf, perf, vTune, PAPIを試してみました。その結果vTuneとPAPIが類似した結果を示しました。他の方にこの結果を追試して頂くことを考えまして
PAPIを採用しました。PAPI周りのコードはexecMain.cのstandard_ExecutorRun()内に埋め込みました。CPUはIntel(R) Core(TM) i7-2760QM CPU @ 2.40GHzです。実験結果を下記に示します。

実験結果（結果タプル数が4、"select id from test_32 where age = 20"、10回の平均）
Layout L1D Cache Miss
NSM 571.2
PAX 606.4

Layout L2D Cache Miss
NSM 347.5
PAX 358.5

Layout L3 Total Cache Miss
NSM 406.6
PAX 355
実験結果（結果タプル数が1、"select id from test_32 where age = 20 and sc10 = 19"、10回の平均）
Layout L1D Cache Miss
NSM 580.2
PAX 634.1

Layout L2D Cache Miss
NSM 345.7
PAX 355.8

Layout L3 Total Cache Miss
NSM 327.7
PAX 336.2

結果タプル数が4の場合，L3（Last Level Cache）においてはPAXのキャッシュミス率が少しだけ低くなる現象を観察できました。しかし結果タプル数が1の場合にはPAXはNSMに負けています。これは不要なExecQual処理を行うためだと考えています。つまりデフォルトではExecQualでselection処理を行うのですが、我々のPAX実装ではもっと深部で行いますのでExecQualは不要です。しかし整合性のためにExecQualを残してあるので、無駄な処理が行われてしまいます。この問題は本日までに解決できませんでした。

問題

現状の実装には少なくとも下記の問題があることがわかっています。これらの問題を今後、検討して行きたいと思います。

  1. メモリ確保：PostgreSQLは一番下のレイヤーでmallocをしませんが、今回は実装の都合上mallocをしてしまいました．属性アドレス変換アルゴリズムを構築すればこの問題は解決できるかもしれません。Weaving Relations for Cache Performanceには "To reconstruct a record one needs to perform a mini-join among minipages, which incurs minimal cost because it does not have to look beyond the page" 等と書いてありますのでタプル再構成がPAXでは基本なのかもしれませんが、少なくともPostgreSQLでタプル再構成方式は不適切だと思います。ちなみに論文が発表された頃のPostgreSQLのコードも同様です。Shoreだと事情が異なるのかもしれません。
  2. 不要なExecQual：PAX実装ではExecQualでselection evaluationをする必要はありません。しかし現実装ではそれを行ってしまっているので無駄なオーバーヘッドになってしまっています。この無駄な処理をなくせば PAX の性能はもっと向上するように思います。
  3. カラム数：カラム数が増えるとミニページが増えます。ミニページがkのときに必要なポインタ数（ページヘッダー内）はkとなります。従ってミニページが多いとNSMよりも必要なデータ容量が増えてしまいますので、I/O回数が増大して性能が劣化するように考えられます。この問題をどうやって解決するべきか、現状ではアイディアはありません。

感想

  1. PostgreSQLは selection pushdown をもっと真面目に実装すべきだと思います。このままでは Big Scan 時に性能が悪くなります。
  2. PostgreSQLにPAXを実装することは不自然なように感じています。Read only DBMSであり、バッファ容量を2倍使って良いならば、PAXページを横に準備しておいて、それを用いたselection結果のNSM内タプルへのポインタを返すという実装方式がありえます。最初はこの方式で実装しました。しかしPostgreSQLは主記憶DBではないし空間性能悪化率に対する時間性能改善率がかなり悪いので、この実装方式について私は否定的です（但し性能は明確に向上しました）
  3. 私にとってはPAXの実装は簡単じゃなかったです。Weaving Relations for Cache Performanceの著者にとっては簡単らしいので凄いプログラマーだな～と思いました。