Special Features:

HOW TO DEAL W/ DISTRIBUTED COLLECTIONS AND SETS USING JavaSpaces
By Avi Kapuya

Distributed Environments

Many distributed applications require data structures such as collections, sets, sorted sets, etc. in order to enable very fast work mode for different modules in the applications.

One of the examples I'm focusing in this article is from the financial world and is called "The Order Book". The Order Book is merely a list of orders posted to a marketplace by different sellers and buyers of merchandise in this marketplace. The Order is used very often. In fact, it is used every time someone looks at prices in the market or wishes to buy or sell stocks or options or even FX and browsing or updating the Order Book occurs thousands, or even hundreds of thousands times per second on the trading system, and many times, access to the Order Book is done in order to perform scans and searches using parameters such as price and time of arrival. For architects, the only way to provide reasonable access time to that part of the system is to have the Order Book in memory, as long as it is possible.

Today's prices of memory for servers, though, enable to have large amount of memory available for the applications, providing much better performance overall; especially, when memory is utilized properly by that application. Event based programming allows system designers to create very efficient design for In memory Order Books or any other collections, which are updated and queried at very high rates, however, in many cases, even such high performance provided by in-memory data collections is not enough and creating highly available, properly load balanced systems is getting to be very complicated and expensive. New level of performance and simplicity can only be achieved by introducing new approach and as a result, new paradigm and tools to move to the next level. The situation described here is similar to the development of aviation in the last era, starting from propeller engine that could drive an airplane to a certain speed and could carry limited weight.

Those old flying machines were sufficient for the time, but when more passengers and merchandise had to be flown at higher speeds, those engines failed and held the aviation industry back, until a new engine emerged, the Jet Engine. The Jet Engine was practically a miracle; It is very simple, consumes less fuel, can reach much higher speeds and carry much more weight. It is a significant improvement in every aspect of operation.

Computers today are already withholding the Jet engines within them in the form of multitude of ultra fast CPU's, loads of memory, fast storage and networking. However, Jet engines cannot fly themselves, and one engine cannot fly a Jumbo jet. It is necessary to add up few engines, plus a suitable body and wings, than it takes a well designed control and management system, which includes failover, high availability and load balancing, only than we can have that marvelous creation called Jumbo Jet, which can carry hundreds of people fast and safe to their destinations.

High performance information systems designers are facing a major dilemma these days, "should we get a bigger box?" or should we break the "We need a bigger box" paradigm and restructure our systems into distributed ones. The funny thing is, bigger boxes don't do the job anymore. The only conclusion is that systems must be redesigned in order to be able to work not only on multiple boxes but in many cases, on top of a geographically distributed network. Distributed Systems essentials

The first tools required by system designers are Data Collections and Sets, and in this article I will discuss a paradigm that handles those Data structures and others in distributed environments and gain memory level performance but in much larger scale. Let's start with an illustration:

Seen here, is a set of three servers, running the same applications. Within each application instance, there is an embedded JavaSpaces instance and a Sorted Set. The three JavaSpaces instances are configured to replicate objects from their space to all the other spaces in that cluster (simple replication configuration). Zooming into one of the servers, here is what we see:

Entries are written locally to the Sorted Set and are inserted into the set immediately. In addition, the Set update methods are also updating the JavaSpaces objects, essentially, writing or updating (using take and write) the object into the space. To avoid feedback of update into the set again, it is necessary to filter entries that are written locally by the Event Listener. The result of this sequence of operations is that locally, the set is updated immediately, the state of the space is than updated and the operations and new entries are replicated to other spaces located on other servers. As a result, on the other servers, the notification triggers update of the local set with the new object. In a very short time, the system is fully synchronized, yet we have not touched the issue of locking and ownership, I'll dedicate a section for these two important subjects.

Locking And Ownership Or "Single System Image" On Top Of Peer To Peer Clusters Of Memory

Single System image is a requirement many system designers put in place to avoid data inconsistency, however, it must be stated strongly that SSI and performance is a contradiction in terms due to long update cycles and information retrieval in SSI solutions, therefore, the paradigms we are demonstrating here provides most of the SSI requirements and for a very small price. It is clear that true SSI system cannot serve the operation of a large or even medium scale exchanges or banks. With the right design in place, one that takes in consideration the possibility of information being "stale" for a short time (between few milliseconds to 0.1 second), those systems can perform much faster than any other architecture. If you think about it, the same problems exist in databases, users are retrieving information from the databases and update it, by the time the transaction is committed other users see old data; The phenomena is called "Dirty Read." The solution provided here to attack this issue is ownership.

Ownership ties objects to specific servers in terms of modifications. Ownership can prevent from different entities to update an object at the same time. The method to implement ownership using JavaSpaces is by having the Write and Take operations use Hash-based distribution so operations on specific Entry with specific ID is always routed to the same space. Some JavaSpaces providers offers operation level load balancing, which is based on the Entry's hash code and can be set by the system designer. The performance is gained by allowing read operations from collections in a very fast manner (memory level Hashtable or Treeset), reaching up to hundreds of thousands of operations per second. When an entry is updated, the operations are directed to a specific space, which is the "owner" of that entry. Once updated, the updated information is distributed across the cluster and the collections are fully synchronized in a very short time. There are also extensions to the basic API offered by JavaSpaces such as atomic update with lock or batch JavaSpaces operations (writing / reading multiple entries in one call), which can be used to optimize the work with distributed shared memory and gain even better performance. The benefits of the Distributed Collections architecture is in the ability to work with in-memory collections and sets, defined by the system designer and have those objects distributed across multiple servers. The performance gain in using these paradigms is 2-3 orders of magnitude faster than using databases or other "propeller" solutions.

How Is High Availability, Load Balancing And Failover Achieved?

High availability, load balancing and failover are solved by using the Jini framework, which is using smart proxies on the client side. Those smart proxies are instantiated objects loaded from the server that the client connects to. Those objects are in fact connectors to a service, in the case of JavaSpaces, they are connectors to the space, which can and in few implementations indeed contain load balancing, high availability and failover policies, according to the configuration on the JavaSpaces cluster.

Jini lookup services allow clients to look for and discover space instances as they start and register in Jini lookup services, so in fact, when a client tries to connect to a Jini service, they don't have to know the exact network address they need to connect to, only the service they are looking for. In the case of JavaSpaces, each space, which is a member of the cluster, provides the client with the cluster different policies for failover, high availability and load balancing. On the configuration side, advanced implementations of clustered JavaSpaces such as GigaSpaces, enables to create different cluster configurations, which include replication, full or partial, of entries as well as replication of operations. It provides different out-of-the-box load balancing and failover policies such as round robin, hash based and more. Some implementations even offer replication matrixes with different replication policies between different servers which are asymmetric, such as one way replication or replication of specific type of information and other lower resolution relationships between spaces. JavaSpaces can also be configured to persist information into databases, rather than have everything in memory. This type of configuration is particularly useful for large amounts of data, which is difficult to keep even on multiple machines and can serve for recovery of data in case of system shutdown.