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

[PJP]: Dynamic Class Loading in the Java Virtual Machine

Sheng Liang and Gilad Bracha, "Dynamic Class Loading in the Java Virtual Machine", ACM OOPSLA'98, pp.36-44, 1998.

Abstract
Class loaders are a powerful mechanism for dynamically loading software components on the Java platform. They are unusual in supporting all of the following features: laziness, type-safe linkage, user-defined extensibility, and multiple communicating namespaces.
We present the notion of class loaders and demonstrate some of their interesting uses. In addition,we discuss howto maintain type safety in the presence of user-defined dynamic class loading.

P.S. Найдено в tutorial on Javassist.
P.P.S. Интересный пример:
MyClassLoader myLoader = new MyClassLoader();
Class clazz = myLoader.loadClass("Box");
Object obj = clazz.newInstance();
Box b = (Box)obj; // this always throws ClassCastException.
Так как не до конца определено, кто же загрузчик класса Box (в той части, где - 'Box b = (Box)...').

An Approach to Internal Domain-Specific Languages in Java

An Approach to Internal Domain-Specific Languages in Java
from author of Fest-Assert [here, here].

P.S. Fest-Assert is good example of Internal DSL in Java. In some sence is competitor of Hamcrest.

P.P.S. Yeep, i like Internal DSL and wrote about it: here about ApacheCamel, here about Hamcrest.

Some numbers from Oracle

On the performance side, Oracle boasts that one rack can serve over 1M HTTP requests/s and can process over 1.8M Java messages/s.

Larry Ellison mentioned during Oracle OpenWorld keynote that China runs its entire railway ticketing system on one Exalogic and one could run the entire Facebook web layer on a couple of those

TPC history

Some notes on TPC history.
With tho articles:
1985: A Measure of Transaction Processing Power
2005: Thousands of DebitCredit Transactions-Per-Second: Easy and Inexpensive

P.S. TPC from tpc.org is the most popular transaction performance test.

An Analysis of Linux Scalability to Many Cores

An Analysis of Linux Scalability to Many Cores

ABSTRACT
This paper analyzes the scalability of seven system applications (Exim, memcached, Apache, PostgreSQL, gmake, Psearchy, and MapReduce) running on Linux on a 48-core computer. Except for gmake, all applications trigger scalability bottlenecks inside a recent Linux kernel. Using mostly standard parallel programming techniques — this paper introduces one new technique, sloppy counters — these bottlenecks can be removed from the kernel or avoided by changing the applications slightly. Modifying the kernel required in total 3002 lines of code changes. A speculative conclusion from this analysis is that there is no scalability reason to give up on traditional operating system organizations just yet.

P.S. From MIT reseachers

Набираем программистов

Господа и дамы, GridDynamics в Харькове открыл несколько позиций по J2EE всех уровней (стажер, junior, middle, senior, architect).

Кто заинтересован встретится со мной за чаем и узнать на какие проекты берем, стек технологий и т.д. - пишите на Golovach.Ivan@gmail.com.

P.S. Все проекты под кластер(10-100 машин) и с использованием In Memory Data Grid.
P.P.S. Особо жду тех, кто осилил в прошлом году мои лекции:)
P.P.P.S. Стажеров и juniors менторить буду, скорее всего, я.
P.P.P.P.S. Большинство заказчиков из Штатов/Калифорнии (eBay, PayPal, Macys, Cisco, Bank of America), так что есть возможность передать привер Арни лично:)

Erlang vs. Scala

Erlang vs. Scala

Размерность частично-упорядоченных множеств

Теорема
Порядковая и мультипликативная размерность частично-упорядоченного множества совпадают.

P.S. Размерность частично-упорядоченного множества можно интерпретировать
- как степень параллельности процессов в системе
- как размерность времени системы
(детальнее смотри в книге на стр. 58).

[Book]: Великолепная книга по распределенным системам - "Distributed Computing - Principles, Algorithms, and Systems"

Великолепная книга по распределенным системам - "Distributed Computing - Principles, Algorithms, and Systems".

Докладываю на IT Jam.

Докладываю на IT Jam в Guru section по теме "The principal limitations on the scalability of distributed systems".

Software Transactional Memory for Large Scale Clusters

Software Transactional Memory for Large Scale Clusters

Abstract
While there has been extensive work on the design of software transactional memory (STM) for cache coherent shared memory systems, there has been no work on the design of an STM system for very large scale platforms containing potentially thousands of nodes. In this work, we present Cluster-STM, an STM designed for high performance on large-scale commodity clusters. Our design addresses several novel issues posed by this domain, including aggregating communication, managing locality, and distributing transactional metadata onto the nodes. We also re-evaluate several STMdesign choices previously studied for cache-coherent machines and conclude that, in some cases, different choices are appropriate on clusters. Finally, we show that our design scales well up to 512 processors. This is because on a cluster, the main barrier to STMscalability is the remote communication overhead imposed by the STM operations, and our design aggregates most of that communication with the communication of the underlying data.

HPCS languages: X10(IBM), Fortress(Sun), Chapel(Cray)

Beyond Locks and Messages: The Future of Concurrent Programming

Conclusions
Here’s the tongue-in-cheek summary of the trends which, if you believe that the HPCS effort provides a glimpse of the future, will soon be entering the mainstream:
1. Threads are out (demoted to latency controlling status), tasks (and semi-implicit parallelism) are in.
2. Message passing is out (demoted to implementation detail), shared address space is in.
3. Locks are out (demoted to low-level status), transactional memory is in.

[PJP]: Web Services Are Not Distributed Objects

"Web Services Are Not Distributed Objects"
Werner Vogels, Cornell University

Abstract
Web services are frequently described as the latest incarnation of distributed object technology. This misconception, perpetuated by people from both industry and academia, seriously limits broader acceptance of the true Web services architecture. Although the architects of many distributed and Internet systems have been vocal about the differences between Web services and distributed objects, dispelling the myth that they are closely related appears difficult.
Many believe that Web services is a distributed systems technology that relies on some form of distributed object technology. Unfortunately, this is not the only common misconception about Web services. In this article, I seek to clarify several widely held beliefs about the technology that are partially or completely wrong.

SEDA: An Architecture for WellConditioned, Scalable Internet Services

SEDA: An Architecture for WellConditioned, Scalable Internet Services

Abstract
We propose a new design for highly concurrent Internet services, which we call the staged event-driven architecture (SEDA). SEDA is intended to support massive concurrency demands and simplify the construction of well-conditioned services. In SEDA, applications consist of a network of event-driven stages connected by explicit queues. This architecture allows services to be well-conditioned to load, preventing resources from being overcommitted when demand exceeds service capacity. SEDA makes use of a set of dynamic resource controllers to keep stages within their operating regime despite large fluctuations in load. We describe several control mechanisms for automatic tuning and load conditioning, including thread pool sizing, event batching, and adaptive load shedding. We present the SEDA design and an implementation of an Internet services platform based on this architecture. We evaluate the use of SEDA through two applications: a high-performance HTTP server and a packet router for the Gnutella peer-to-peer file sharing network. These results show that SEDA applications exhibit higher performance than traditional service designs, and are robust to huge variations in load.

List of important publications in theoretical computer science

List of important publications in theoretical computer science:

# 1 Computability
# 2 Computational complexity theory
# 3 Algorithms
# 4 Algorithmic information theory
# 5 Information theory
# 6 Formal verification