(本文)Recently, several middleware-based approaches have been proposed. If we implement all functionalities of database replication only in a middleware layer, we can avoid the high cost of modifying existing database servers or scratch-building. However, it is a big challenge to propose middleware which can enhance performance and scalability without modification of database servers because the restriction may cause extra overhead. Unfortunately, many existing middleware-based approaches suffer from several shortcomings, i.e., some cause a hidden deadlock, some provide only table-level locking, some rely on total order communication tools, and others need to modify existing database servers.

In this paper, we propose a new correctness criterion for eager replicated database systems called global snapshot isolation (GSI). GSI not only guarantees snapshot isolation to clients but also maintains consistency between database servers. We also propose two middlewares called DV-SI and Pangea to meet GSI. DV-SI provides table-level concurrency control and higher throughput by exploiting the property of snapshot isolation. Pangea provides tuple-level concurrency control and much higher throughput by exploiting the property of the first-updater-wins rule. We have implemented the prototypes of DV-SI and Pangea on top of PostgreSQL servers without modification. Because GSI also presents the guide of minimal implementation, DV-SI and Pangea use less than 2000 lines of C code.

Our experimental results with the TPC-W benchmark reveal that, compared to existing middlewares without modification of database servers, DV-SI and Pangea provide better performance in terms of throughput and scalability. More surprisingly, Pangea outperformed any other middleware in any workload.

本論文は「Replication Middleware for High Performance Database Systems」と題し、8つの章から構成されている。データベースレプリケーション、すなわちデータベースを複製する手法は、データベースシステムの高性能化と高信頼化の観点から有効であり、古くから多くの研究がなされてきた。近年ではこのレプリケーションの機能をミドルウェアのみで実現する研究もなされてきている。ミドルウェアのみで実現する手法は既存のデータベースサーバを無改造で利用できるため、実現が低コストである、データベースサーバのベンダーによる囲い込みを避けられる、データベースサーバとは独立して進化できる、異なるデータベースサーバを同時に利用できる、などの多くの利点がある。しかし、データベースサーバを改造しないという制約により、性能低下、拡張性の損失、などの問題が生じる。本論文は、このような問題を解決するために、ミドルウェアで順序制御しなければならない命令と守られるべき順序関係を明確にし、その順序制御を実現する2つのミドルウェアを提案している。さらに、TPC-Wベンチマークを用いた評価によって、提案した2つのミドルウェアの有効性を示している。

第1章「Introduction」では、本論文の背景と目的を述べ、本論文の構成を述べている。まず、eagerレプリケーションを選択した理由を述べ、既存のeagerレプリケーションミドルウェアの問題点を指摘している。また、トランザクション分離モデルの1つであるスナップショット分離を保証することの重要性についても触れている。

第2章「Eager Replication Middlewares」では、対象とするeager replication middlewareのモデルを明確化し、本論文における仮定を述べている。また、eager replicationでは、レプリカにまたがるデッドロックが起きる可能性があり、これを避けるためには競合する更新命令の実行順序を全てのレプリカで同一にする必要があることを議論している。

第3章「Proposal of Global Snapshot Isolation」では、デッドロックを避け、かつ、クライアントに対しはスナップショット分離を保証しつつレプリカ間でコンシステンシを維持するために、ミドルウェアで順序制御しなければならない命令とその順序を明確にしている。これをGlobal Snapshot Isolation(GSI)と呼び、データベースレプリケーションにおける新しいトランザクション分離モデルとして提案している。

第4章「Proposal of a Table-Level Locking Middleware」では、テーブルレベルの粒度で並行制御し、しかもGSIを保証する新しいミドルウェアDV-SIを提案している。

第5章「Proposal of a Tuple-Level Locking Middleware」では、タプルレベルの粒度で並行制御し、しかもGSIを保証する新しいミドルウェアPangeaを提案している。

第6章「Evaluation」では、データベースシステムの評価ベンチマークとして広く用いられているTPC-Wベンチマーク、およびシステムの特性をより詳細に明らかにするために作成した簡易プログラムを用いて、提案するミドルウェアの評価を行っている。TPC-Wベンチマークを使った評価では、ブラウジングミックス、ショッピングミックス、オーダリングミックスの全ての処理に対して、DV-SIは既存のミドルウェアよりも高いスループットを達成し、PangeaはDV-SIよりもさらに高いスループットを実現できることを示している。この結果から提案する2つのミドルウェアの有効性を明らかにしている。簡易プログラムを使った評価では、競合する更新が発生する確率を変えてPangeaとDV-SIの性能差の詳細な解析を行っている。その結果、競合する更新が発生する場合でもPangeaはDV-SIに比べて高いスループットを実現できることが分かり、タプルレベルの粒度で並行制御することの有効性を明らかにしている。

第7章「Related Work」では、従来のミドルウェアの研究とスナップショット分離に関する研究を述べている。

第8章「Conclusion」では、以上の成果を要約している。

以上を要するに、本論文はデータベースシステムの高性能化と高信頼化を目的とし、データベースレプリケーションにおける新しいトランザクション分離モデルとミドルウェアによる実現方法を提案しその有効性を明らかにしたものであり、非常に意義がある研究であり、その成果は工学的に貢献するところが大きいと考えられる。

よって本論文は博士(工学)の学位請求論文として合格と認められる。