Consistent hashing

Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not significantly change the mapping of keys to slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped. By using consistent hashing, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots.

Wiki: Consistent hashing

Theory: Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web

Practice: Web caching with consistent hashing

Finally, you may not know this, but you use consistent hashing every time you put something in your cart at Amazon.com. Their massively scalable data store, Dynamo, uses this technique. Or if you use Last.fm, you’ve used a great combination: consistent hashing + memcached.

DarkStar #1: Dynamic Adaptation of User Migration Policies in Distributed Virtual Environments

Dynamic Adaptation of User Migration Policies in Distributed Virtual Environments

Abstract

A distributed virtual environment (DVE) consists of multiple network nodes (servers), each of which can host many users that consume CPU resources on that node and communicate with users on other nodes. Users can be dynamically migrated between the nodes, and the ultimate goal for the migration policy is to minimize the average system response time perceived by the users. In order to achieve this, the user migration policy should minimize network communication while balancing the load among the nodes so CPU resources of the individual nodes are not overwhelmed. This paper considers a multiplayer online game as an example of a DVE and presents an adaptive distributed user migration policy, which uses Reinforcement Learning to tune itself and thus minimize the average system response time perceived by the users. Performance of the self tuning policy was compared on a simulator with the standard benchmark non-adaptive migration policy and with the optimal static user allocation policy in a variety of scenarios, and the self-tuning policy was shown to greatly outperform both benchmark policies, with performance difference increasing as the network became more overloaded. These results provide yet another demonstration of the power and generality of the methodology for designing adaptive distributed and scalable migration policies, which has already been applied successfully to several other domains [17, 18].

P.S. Wiki:Project Darkstar

DarkStar #0: Scalable Data Storage in Project Darkstar

Scalable Data Storage in Project Darkstar

Abstract
We present a new scheme for building scalable data storage for Project Darkstar, an infrastructure for building online games and virtual worlds. The approach promises to provide data storage with horizontal scaling that is tailored to the special requirements of online environments and that takes advantage of modern multi-core architectures and high throughput networking.
After a brief overview of Project Darkstar, we describe the overall architecture for a caching data store. Then we provide more detail on the individual components used in the solution. Finally, we suggest some of the additional facilities that will be required to bring the full experiment to completion.

P.S. Wiki:Project Darkstar

Some words about distributed frameworks

Some words about distributed frameworks in post Characterizing Enterprise Systems using the CAP theorem.
* RDBMS
* Amazon Dynamo
* Terracotta
* Oracle Coherence
* GigaSpaces
* Cassandra
* CouchDB
* Voldemort
* Google BigTable

STM in Scala

Scala 2.9, возможно, будет включать STM.
Reference implementation основана на CCSTM.

P.S. CCSTM: A Library-Based STM for Scala