Computer Science Research - Projekte

Scalaris

Distributed Transactional Key-Value Store

Description

Global online services have millions of customers with thousands of servers located throughout the world. At this scale, components fail continuously and it is difficult to maintain a consistent state while hiding failures from the application. Peer-to-peer protocols provide self-management by replicating services among peers, but they are mostly limited to write-once/read-many data sharing. To extend them beyond the typical file sharing, the support of fast transactions on distributed hash tables (DHTs) is an important yet missing feature. We designed and implemented a distributed key/value store based on a DHT that supports consistent writes. Our system comprises three layers, all of them implemented in Erlang: At the bottom, a structured overlay network with logarithmic routing performance builds the basis for a multi-dimensional key/value store. In contrast to many other DHTs, our overlay stores the keys in lexicographical order, hence range queries are possible. The middle layer implements the ACID properties (atomicity, concurrency, isolation, durability) in the face of concurrent write operations. It uses an improved Paxos Commit protocol with a low communication overhead that has been optimally integrated into the overlay. The top layer hosts the application, a distributed key/value store. This layer can be used as a scalable, fault-tolerant backend for online services like shopping, banking, data sharing, online gaming, or social networks. Our work is similar to Amazon's SimpleDB, but additionally supports full ACID properties. Dynamo, in contrast, restricts itself to eventual consistency only. As a test case, we chose Wikipedia, the free encyclopedia, that anyone can edit. Our implementation serves approx. 2,500 transactions per second with just 16 CPUs, which is better than the public Wikipedia. Further information can be found here.

Members

Thorsten Schütt, Florian Schintke, Alexander Reinefeld

Partners

SICS

Videos, Slides
A. Reinefeld	Building a transactional distributed data store with Erlang	Erlang eXchange 2008, June 2008	Video
T. Schütt	Scalable Wikipedia with Erlang	Google Scalability Conference 2008, June 2008	Video
Publications
T. Schütt, F. Schintke, A. Reinefeld	Scalaris: Reliable Transactional P2P Key/Value Store - Web 2.0 Hosting with Erlang and Java	7th ACM SIGPLAN Erlang Workshop, Victoria, September 2008.
T. Schütt, M. Moser, S. Plantikow, F. Schintke, A. Reinefeld	A Transactional Scalable Distributed Data Store: Wikipedia on a DHT	1st IEEE International Scalable Computing Challenge, SCALE 2008, Lyon, (first price award winning paper), May 2008
T. Shafaat, M. Moser, A. Ghodsi, T. Schütt, S. Haridi, A. Reinefeld	On Consistency of Data in Structured Overlay Networks	CoreGRID Integration Workshop, Heraklion, Springer LNCS, April, 2008	pdf
S. Plantikow, A. Reinefeld, F. Schintke	Transactions and Concurrency Control for Peer-to-Peer Wikis: An evaluation	Special CoreGrid volume, Springer Verlag, 2008
T. Schütt, F. Schintke, A. Reinefeld	Range Queries on Structured Overlay Networks	Journal on Computer Communications, vol. 31, no 2, Elsevier, pp 280-291, February 2008.
S. Plantikow, A. Reinefeld, F. Schintke	Transactions for Distributed Wikis on Structured Overlays	18th IFIP/IEEE Distributed Systems: Operations and Management (DSOM 2007), San José, CA, USA, October 29-31, October 2007
T. Schütt, F. Schintke, A. Reinefeld	A Structured Overlay for Multi-dimensional Range Queries	Euro-Par 2007, Parallel Processing, 13th International Euro-Par Conference, Rennes, France, Springer LNCS 4641, pp. 503 - 513, August 2007
M. Moser, S. Haridi	Atomic Commitment in Transactional DHTs	1st CoreGRID Symposium, Rennes, France, August, 2007	pdf
T. Schütt, F. Schintke, A. Reinefeld	Structured Overlay without Consistent Hashing: Empirical Results	In Proceedings of the Sixth Workshop on Global and Peer-to-Peer Computing (GP2PC 2006), Singapore, May 2006.	pdf, bib