Announcing Accord: A Java implementation of Chord

Accord is a new java implementation of the Chord p2p lookup protocol. I’ve been working on this gradually over the past few months and recently received a large contribution of code from Marco Bazzoni who has joined the project.

The basic functionality behind Chord is actually quite simple: given a number of nodes, Chord will map a given piece of data onto the node most likely to contain the data you’re looking for. A rather basic example would be a situation whereby you have 100 nodes containing stock information and you’re trying to locate data based on a CUSIP number. How do you find the node with the data? Well, Chord solves this problem in an elegant fashion.

Based on the input value (your CUSIP number), Chord will make a SHA-1 digest (a 160-bit integer). Then, based on any “known” node in the cluster, the Chord algorithm will compare the digest with the identifier of the known node, which is not coincidentally also a SHA-1 digest of its network location. Using a partial routing table (the finger table) that each Chord node maintains, the node containing the data is located using log(N) messages. There are a lot of details about how node joins, departures and failures are handled - these are covered in the Chord Tech Report.

The beauty of Chord is that it’s fully distributed, which is important if you want something that’s both resilient and reliable.

Now, the reason why this caught my eye and prompted me to start Accord has to do with my work on Whirlycache. I spent a long time trying to figure out a good way to make Whirlycache distributed like some of the other open-source caching solutions. All of the other caches of any significance are using JGroups, but I didn’t want to go down this road.

First, let’s just pretend that there isn’t a problem with using LGPL java code to make this explanation simpler. Second, I see no point in making a new wheel when the new wheel looks exactly like all the other wheels. We have several examples of people making distributed caches based upon the same toolkit, so why create another? It seemed pointless and didn’t offer any opportunity for me to add anything new. I was also concerned with the fact that JGroups uses IP multicast, because my understanding of multicast is that its performance on a given network is greatly dependent on the local router’s ability to process multicast packets. Maybe that’s a misconception, so please correct me if I’m wrong about that.

But I was also influenced by Microsoft’s approach to locking in SQL Server clusters, which they call “shared-nothing” (here’s a quickie article just to give you the basics). Locking is a complex problem to deal with and distributed locking is an even tougher nut to crack, as anybody who has worked with enterprise level transactions will tell you. So the fact that I could totally decentralize my data, spread it across a bunch of nodes, reduce lock contention on the network level and still get the benefit of Whirlycache’s speed while operating inside each individual node really appealed to me. One reason why Whirlycache is the fastest in-memory object cache has to do with how we handle locking inside: there’s not a lot of it and the little locking that does happen occurs on a very granular level, so the chance of contention in all cases is very low.

How to handle data redundancy on the network is something that is unknown at this time as it pertains to Whirlycache, but I’m not too concerned about this. After all, we are speaking about caches, not authoritative data stores. If the cache gets cleared, the systems they support still need to be able to operate properly (maybe slowly, but still…)! Ideas about this should be directed at the Accord dev mailing list.

So while that gives you an idea of where Whirlycache will go, please keep in mind that Accord will live as a seperate entity and will be usable for whatever other projects you can dream up. After you have had a chance to read the Chord documentation, we’d love to get your help on the project.