A Framework for Supporting DBMS-like Indexes in the Cloud

Gang Chen, Hoang Tam Vo, Sai Wu, Beng Chin Ooi, M. Tamer Özsu

Abstract

Cloud storage systems like Dynamo and Cassandra excel at primary key lookups but struggle with ad-hoc queries, often resorting to inefficient full-table scans. This paper introduces an extensible framework that leverages Cayley graphs to support diverse database-style indexes (e.g., B+-trees, Hash indexes) in the cloud. By providing a unified abstraction for peer-to-peer routing, the framework enables efficient range and multi-dimensional queries while maintaining linear scalability and decoupling indexing logic from the underlying storage layer.

Introduction

Modern cloud environments require high-performance data retrieval beyond simple key-value lookups. However, implementing distributed secondary indexes is complex, often requiring bespoke network overlays for different query types. This paper addresses the need for a "Database as a Service" (DaaS) that is extensible and efficient, hiding the underlying network complexity from users while avoiding the performance bottlenecks of sequential scans.

The Cayley Graph Framework

The core innovation of this framework is the use of Cayley Graphs as a mathematical foundation. The authors observed that many popular P2P routing protocols, such as Chord and BATON, are specific instances of Cayley graphs. This realization allows for a unified infrastructure where different indexing logic—such as Hash for exact matches or B+-trees for range queries—can be mapped onto the same underlying network.

The proposed indexing framework architecture, showing the decoupling of index nodes from the storage service via a Cayley overlay.

The system architecture consists of several key components:

  • Unified Abstraction: Maps various index types onto a generalized Cayley graph.
  • Data Mapping: Employs uniform and sampling-based mapping to ensure balanced index distribution, even with skewed data.
  • Self-Tuning: Uses "shortcut" connections and a knapsack-based memory management algorithm to optimize performance.
  • Decoupled Storage: The indexing service operates independently of the storage layer (e.g., HDFS), allowing independent scaling.

Key Insights: Index Covering and Skew Management

A significant finding is the effectiveness of index covering. By embedding a portion of the actual data within the index entry, the system can resolve queries without additional slow disk reads from the primary database. Furthermore, the sampling-based mapping strategy effectively mitigates "data skew," preventing individual nodes from becoming performance bottlenecks in highly non-uniform datasets.

Performance and Scalability

The framework was evaluated using TPC-W benchmarks, synthetic data, and real-world spatial data generators. The results demonstrate substantial performance gains over traditional methods.

Performance comparison between full table scans and the indexed approach across varying data sizes.

Key results include:

  • Massive Speedups: The indexed approach is orders of magnitude faster than parallel full table scans using MapReduce. For instance, finding records in a 10GB table takes milliseconds compared to 23 seconds with MapReduce.
  • Linear Scalability: Query latency remains nearly flat as the system scales from 16 to 256 nodes on Amazon EC2.
  • Efficient Joins: Index-based equi-joins outperform MapReduce by avoiding the expensive data "shuffle" phase.

Conclusion and Future Work

While the framework offers significant advantages in query performance and extensibility, it faces challenges regarding the consistency-performance trade-off. Maintaining multiple synchronized secondary indexes during high-frequency updates is computationally expensive. Future research will focus on refining recovery protocols and exploring relaxed consistency models to further enhance update efficiency in large-scale cloud deployments.

Summary updated

BibTeX
@article{chen2011framework,
  author = {Gang Chen and Hoang Tam Vo and Sai Wu and Beng Chin Ooi and M. Tamer Özsu},
  title = {{A Framework for Supporting DBMS-like Indexes in the Cloud}},
  journal = {Proc. VLDB Endow.},
  year = {2011},
}
Figure