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 mysoline 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.

3 thoughts on “Announcing Accord: A Java implementation of Chord”

  1. Hello,
    I am a software engineer from Samsung SDS co, Ltd in south Korea.

    I am interested in chord algorithm and try to convert chord source to version of windows with C++(MFC).

    After searching information about it, I looked up your project(accord).

    It is very simple and readable, but because I am not good at Java program, chord, and so on, I have many questions.

    I hope to get much information about questions as follows, if you don’t mind :

    1. Is this project finished ?(that is, chord algorithm is implemented completely except for application ?)

    2. In my opinion, it consists of two parts and they are complete source seperately ?

    3. Your source is more understandable than Mr. Macro’s one for me. I wonder whether “src” folder is enough to understand your project?

    4. For testing chord algorithm, is there any Text to guide to check it ?(How do I consist of test environment ?)

    5. I think this is a library with API for chord algorithm. Are there other applications using this or sample codes for it ?

    and so on …

    Could you give me advice ?

    Best regards,

    Doh, Munhwan.

  2. 1) No, it is not yet finished, unfortunately.

    2) I’m not sure what the two parts are that you refer to.

    3) Yes, if you read the source code and can understand that, you can probably get an idea of how it works.

    4) I did some work on the test cases, but it’s not complete and is probably buggy.

    5) Nobody is using it, as far as I know, since it is not complete.

  3. Dear Jacob,

    Im Sravanthi, masters student in CS. I would like to see how chord works. I have studied the theoritical concepts and i do have an idea of how it actually works but i would like to view how the chord protocol works in real and also what will happen when a node suddenly leaves the network without informimg any others( i mean what happens to the fingertables associated with that node which left abruptly). Please let me be a part of your project

Comments are closed.