Pastry: A distributed hash table in Go

http://secondbit.org/blog/introducing-pastry/

by paddyforan • 14 years ago

97 70 14 years ago

Oh man, I was really, really just hoping for this. I've been avoiding putting one last piece into my server because I didn't want to use redis. I'm going to play with this in a couple hours.

paddyforan29• 14 years ago

Please do let me know how this works out for you.

And I mention it in the blog post, and I mention it in the README, but I feel I should reinforce this:

This. Is. Alpha. Please don't use it in your mission-critical code.

I'd like to run a lot more tests on it. I'd like other people to run tests on it and let me know what they think. This is my first time writing anything this complex, and I want any and all feedback I can get on it.

Thanks!

drivebyacct22• 14 years ago

Mission critical implies far more importance than this project deserves.

Spotted a typo on the line "OnNodeExit", "Applcation".

JulianMorrison7• 14 years ago

How are you planning to implement pub-sub on top of it?

simonw• 14 years ago

Why didn't you want to use redis?

If you're going to have any component that's a single point of failure, redis is a pretty good bet for it.

paddyforan29• 14 years ago

That it is. I love redis.

I just really didn't want to have a single point of failure. Really badly. Pastry has no single point of failure.

[edit] Realised this thread isn't actually all about me. Oops! Sorry for answering a question not directed at me.

ukd1• 14 years ago

Cool idea, but I wonder why they didn't use something like RabbitMQ which already exists and is proven?

paddyforan29• 14 years ago

I looked at it, I promise I did. Really wanted to avoid writing this if I could.

From what I can see in the docs, RabbitMQ is a client/server relationship. Meaning there is a server. Meaning a single point of failure and a bottleneck. I hate those more than I hate writing new software. Not because I think there is less danger of bugs in this than there is danger that the AMQP server will fall over... it just feels wrong to me.

I'm not saying, by any stretch of the imagination, somebody should use this over RabbitMQ. But if a distributed hash table is more suited to their needs, or if, like me, they're allergic to SPoFs and don't mind if the software is a little less mature if it means avoiding them... Well, now they have a package in Go they can use. If they want to.

JulianMorrison7• 14 years ago

0mq doesn't have a client/server relationship. http://www.zeromq.org/

jeremyjh4• 14 years ago

You didn't look very hard.

http://www.rabbitmq.com/ha.html

old_sound• 14 years ago

You'll have a single point of failure depending on how you orchestrate your architecture, not if you use RabbitMQ, ZeroMQ or whatever. There's no magic in the software world

rabbitmq3• 14 years ago

This does not make any sense. All software runs on machines. Each machine is potentially a 'single point of failure'. This sometimes is a problem, and sometimes is not.

Just because software runs on multiple machines it does not mean that there is 'no SPoF', for example in a distributed messaging system you need to replicate state, unless you don't mind losing it when you have a crash.

If you don't mind losing state, then it is very easy to run RabbitMQ on more than one server.

If you do mind losing state, then RabbitMQ provides several ways to use multiple servers in a decentralised and redundant manner. See eg http://www.rabbitmq.com/distributed.html

It is very easy to write a system with multiple components. The difficulty is preserving all the additional capability (eg uptime) while maintaining a coherent system. This role can be played by a "broker" which does NOT imply a single machine or "SPoF" - it can be a distributed service. See eg http://www.rabbitmq.com/blog/2010/09/22/broker-vs-brokerless...

Saavedro• 14 years ago

Should be aware of possible confusion with http://en.wikipedia.org/wiki/Pastry_(DHT)

paddyforan29• 14 years ago

Confusion is intentional. This is just an implementation of that algorithm, with a few tweaks (that are explained, along with their reasoning, in the README). I believe I even link to that Wikipedia page in the blog post and the README.

StavrosK4• 14 years ago

I didn't see anything in either the Wikipedia page or the code, but how do you achieve redundancy? Wikipedia says nodes can die with minimal or no loss of data, but I see everywhere that each message only goes to one node. Which is the case, and how is this achieved?

joelthelion3• 14 years ago

Hijacking the topic on P2P: is there a good library (any language will do) for P2P message passing (as opposed to information storing in a DHT)?

I'd like to experiment a decentralized twitter/reddit-like system using p2p message flooding and machine learning to weed out spam.

paddyforan29• 14 years ago

http://tent.io/ ?

joelthelion3• 14 years ago

If I'm not mistaken, this is like email: it's decentralized, but still based on a client/server architecture.

I'm asking about P2P, even if client/server might be a better answer to that specific problem.

joelthelion3• 14 years ago

BTW, do you know of any real projects using Tent? It does sound interesting.

Going back to P2P: building a flooding P2P library on top of a DHT seems like a total waste. But maybe the common parts could be extracted.

riffraff• 14 years ago

http://telehash.org/ possibly

graue2• 14 years ago

I was just looking at this as something that could be combined with Tent. From what I've heard, the v1 docs are inadequate to develop a working implementation, and this draft for version 2 of the spec isn't done, and hasn't been updated in awhile:

https://github.com/quartzjer/TeleHash/blob/master/org/v2.md

My conclusion was that TeleHash is a cool concept, but not a solid foundation you can build something on just yet.

jeremyjh4• 14 years ago

>We couldn’t seem to find any way to subscribe to events and publish events without a single point of failure.

Really? You think this doesn't exist? In fact, this is nothing but a deployment concern for any mature message broker.

http://www.rabbitmq.com/ha.html

http://activemq.apache.org/masterslave.html

http://hornetq.sourceforge.net/docs/hornetq-2.0.0.GA/user-ma...

There are lots more options than these, and you can also use heartbeat/lvs to take something like redis and make it HA.

I'm glad you had fun inventing your own distributed hash infrastructure, but please do not attempt to convince other people that there are no other options out there for reliable and highly available messaging.

paddyforan29• 14 years ago

Er. This seems a little overly hostile for something that amounted to "Hey, here's this fun thing I made. Anyone else want to play with it?"

Rather than arguing this point again, I'll just point at the other comment thread that addressed these concerns.

Fun fact: I didn't mention highly available messaging in the post at all. I mentioned single points of failure and bottlenecks. Those aren't quite the same.

jeremyjh4• 14 years ago

A highly available system has no single point of failure.

incision• 14 years ago

>Really? You think this doesn't exist?

That's not what the author said, "we couldn't find" is a personal judgement which leaves things wide open.

>I'm glad you had fun inventing your own distributed hash infrastructure, but please do not attempt to convince other people that there are no other options out there for reliable and highly available messaging.

That didn't happen.

matticakes2• 14 years ago

The focal point is discovery. Not other queues (or other libraries that can build queues). This is an interesting way to approach it, thanks for open sourcing.

We chose to solve the discovery problem a bit differently in NSQ (https://github.com/bitly/nsq) but I could certainly see some interesting opportunities to experiment with a distribute hash table approach as well.

paddyforan29• 14 years ago

I was very excited when I saw NSQ. I thought it would solve my problem splendidly. It seemed, from my reading of the docs, that it did not support multicast however. :(

I was very impressed with it, though. You guys did an awesome job, and I'm extremely flattered you stopped by to comment.

matticakes2• 14 years ago

It's a bit more explicit in NSQ but we essentially support multicast-like routing through "channels".

A "channel" receives a copy (at the source) of all the messages for a "topic" and has its own set of clients subscribed.

realrocker• 14 years ago

oh quiet you naysayers. just nod in appreciation of the hard work.

cnlwsu• 14 years ago

Interesting that the same group of people who were proponents and pioneers in NoSQL now dismissing libraries and new implementations to "solved" problems with "you can do that with {blank}"

spullara• 14 years ago

They were already using Redis and made this? They could have just partitioned and replicated them for scaling.

paddyforan29• 14 years ago

Yup. Totally could have made a choice I wasn't happy with.

Opted to make a choice I was happy with instead.

igrekel• 14 years ago

Next step: a tupplespace in Go?

Terretta• 14 years ago

> We couldn’t seem to find any way to subscribe to events and publish events without a single point of failure. We looked at everything we could find, and they all seemed to have this bottleneck.

“The Spread toolkit provides a high performance messaging service that is resilient to faults across local and wide area networks. Spread functions as a unified message bus for distributed applications, and provides highly tuned application-level multicast, group communication, and point to point support. Spread services range from reliable messaging to fully ordered messages with delivery guarantees.”

http://www.spread.org/

We use this for LAN event communication among standalone servers acting together, and WAN event communication among POPs acting together, for billions of events per month. Any server in a group dies, they elect a new master, so no SPoF.

What was it about your use case that made this feel like a single point of failure or bottleneck?

paddyforan29• 14 years ago

This sounds like something I would have loved to come across. It didn't come up in any google searches or any conversations with other software people who I talked to about this problem, so I didn't evaluate it. Quite simply, I had no idea it even existed.

lobster_johnson• 14 years ago

You sound very happy with Spread -- no complaints? We had nothing but trouble with it ourselves.

This was Spread 3.x somewhere around 2008, so it may have improved since then, but at that time it just seemed very flaky and slow. This was in a cluster of about 8 nodes, with 100-200 messages/second published by any given node at peak, so it should have been more than adequate.

The worst part was that it was silently losing messages, and there seemed to be no trivial way to recover, get statistics/queue information, or generally determine what was going wrong.

Pastry: A distributed hash table in Go

Related Stories