9 ms·

Pastry: A distributed hash table in Go

97 points by paddyforan 14y ago

drivebyacct2 14y 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.
- paddyforan 14y 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!
  - drivebyacct2 14y ago
    Mission critical implies far more importance than this project deserves. Spotted a typo on the line "OnNodeExit", "Applcation".
    - paddyforan 14y ago
      Thanks! Fixed the typo. And I guess my point is, I've tested this. I can't seem to find any problems with it. But I do not have unit tests for the larger routing algorithm, only the routing within a Node. In my tests, it always worked out, but I would put my confidence in this at about 70%. In essence, I was ready to release this software to the Go community, have them kick it around a bit, see what came of it. I was not expecting a HN frontpage. So now I'm slightly panicked, and hoping to God that people don't think I'm an idiot for the rest of forever.
      - Intermernet 14y ago
        Calm those nerves :-) Now, you have the legions of HN to help. One of the joys of open source is that through building software, you also get to build communities. I have a feeling you'll be getting a fair bit of help on this project. It's generic enough to help in any number of applications and i'm sure many HN readers are currently trying to work out if they can apply this to any of their current projects. Best of luck, and thanks for adding another great instrument to Go's repertoire!
  - JulianMorrison 14y ago
    How are you planning to implement pub-sub on top of it?
    - paddyforan 14y ago
      I'll be using the Scribe algorithm, as defined by the authors of the Pastry algorithm: http://en.wikipedia.org/wiki/Pastry_(DHT)#SCRIBE http://en.wikipedia.org/wiki/Pastry_(DHT)#SCRIBE The basic gist of it is similar to a phone tree. You route a message subscribing to a topic, basing the message ID on the topic name. As the message routes through the network, each Node stores the information about who is subscribed. When an event happens, that information is passed back through to the subscribed nodes. I may have to tweak it a little, as I did Pastry, but I'm pretty sure the same basic concept will work for my needs.
- simonw 14y 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.
  - paddyforan 14y 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 14y ago
Cool idea, but I wonder why they didn't use something like RabbitMQ which already exists and is proven?
- paddyforan 14y 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.
  - JulianMorrison 14y ago
    0mq doesn't have a client/server relationship. http://www.zeromq.org/ http://www.zeromq.org/
    - brian_cloutier 14y ago
      What does it have?
      - JulianMorrison 14y ago
        Peer-to-peer connections analogous to TCP. In the case of pub/sub all subscribers connect to the publisher. http://zguide2.zeromq.org/page:all http://zguide2.zeromq.org/page:all
        paddyforan 14y ago
        I guess I was wrong about hard-coding the IPs. Maybe? It doesn't have many-to-many baked in, though. That I can see, at least. It looks like I may have been able to make this work, but the setup would be a little complex. ... because a distributed hash table is not complex at all. -_-
Saavedro 14y ago
Should be aware of possible confusion with http://en.wikipedia.org/wiki/Pastry_(DHT) http://en.wikipedia.org/wiki/Pastry_(DHT)
- paddyforan 14y 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.
  - StavrosK 14y 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?
    - paddyforan 14y ago
      They both are the case. Well, sort of. The messages can go to any number of nodes as part of the routing, but they're only considered "delivered" at one node. However, nodes can die with minimal loss of data. The problem is you're confusing the messages for data. As far as Pastry is concerned, your messages are not data that it should retain. They are one-off communications. The only data that Pastry is concerned with storing is the state of the cluster; that is to say, Pastry only considers "data" the information about enough nodes to reliably be able to route a message to any node in the cluster. Your messages, by default, are lost the moment they are sent, forwarded, or delivered. The node stops caring about them at that point. However, on top of this framework you can build applications that do care about the data in the messages. Before a message is forwarded, it fires off a callback to any application that cares to listen for it. When a message is delivered, it fires off a callback to any application that cares to listen to it. You can register callbacks that store this information, then build your own redundancy frameworks on top of that to store the data you'd like to retain. If you're interested in this, I'd recommend paper on PAST. It's a high availability storage system built on Pastry: http://research.microsoft.com/en-us/um/people/antr/PAST/hotos.pdf http://research.microsoft.com/en-us/um/people/antr/PAST/hoto...
joelthelion 14y 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.
- paddyforan 14y ago
  http://tent.io/ http://tent.io/ ?
  - joelthelion 14y 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.
    - paddyforan 14y ago
      Hm. That's the closest I've got. How's your Go? You can build one on Pastry. :)
  - joelthelion 14y 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.
    - paddyforan 14y ago
      Not off the top of my head, no. Sorry. :( I know there's http://tent.is http://tent.is, and there's a Go client for Tent out there, but that's really all I know about it.
    - graue 14y ago
      Yup. There's a microblogging app (Twitter clone) called TentStatus, available hosted at https://tent.is https://tent.is, or run your own instance of the code: https://github.com/tent/tent-status https://github.com/tent/tent-status. Several people are working on iOS and Android apps to support the microblogging use case. There's Essayist, a (very alpha) long-form blogging app, hosted at http://essayist.mndj.me http://essayist.mndj.me, code at https://github.com/mwanji/essayist https://github.com/mwanji/essayist Meanwhile, the inventors of Tent have 5 people working 60+ hours a week running Tent.is and developing the protocol and apps for it. They haven't revealed what's next, though it sounds like some non-status apps are in the works.
jeremyjh 14y 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://www.rabbitmq.com/ha.html http://activemq.apache.org/masterslave.html http://activemq.apache.org/masterslave.html http://hornetq.sourceforge.net/docs/hornetq-2.0.0.GA/user-manual/en/html/ha.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.
- paddyforan 14y 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.
  - jeremyjh 14y ago
    A highly available system has no single point of failure.
    - paddyforan 14y ago
      It can, however, have bottlenecks. All of your solutions, based on the conversation below, separate the messaging into its own service. Which isn't really how I want to work with my software. I guess the best way I can describe it is as a different aesthetic. There are certainly ways to accomplish the same thing, technologically, but they all feel wrong to me. Introducing a message queue, with a broker, and needing to implement HA on that simply to remove that single point of failure... That feels like a workaround to me. I prefer working with a decentralised pub/sub framework. Personally. Personally, that difference is worth the development time and lack of maturity. To me. Which is why I slapped an alpha label on the project. Why I made no attempt to convince people they should switch over, or even that my way was objectively better than any other way. I had an itch. I scratched it. I released the backscratcher I used as open source so other people with the same itch could scratch it. I'm not sure why some people think this is a contemptible act.
matticakes 14y 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 https://github.com/bitly/nsq) but I could certainly see some interesting opportunities to experiment with a distribute hash table approach as well.
- paddyforan 14y 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.
  - matticakes 14y 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.
    - paddyforan 14y ago
      Hm. Very interesting, I'll have to take another look and get a better understanding of it.
realrocker 14y ago
oh quiet you naysayers. just nod in appreciation of the hard work.
- cnlwsu 14y 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}"
deleted 14y ago
[deleted]
spullara 14y ago
They were already using Redis and made this? They could have just partitioned and replicated them for scaling.
- paddyforan 14y ago
  Yup. Totally could have made a choice I wasn't happy with. Opted to make a choice I was happy with instead.
igrekel 14y ago
Next step: a tupplespace in Go?
Terretta 14y 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/ 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?
- paddyforan 14y 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 14y 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.

97 points by paddyforan 14y 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.

paddyforan 14y 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!
- drivebyacct2 14y ago
  Mission critical implies far more importance than this project deserves. Spotted a typo on the line "OnNodeExit", "Applcation".
  - paddyforan 14y ago
    Thanks! Fixed the typo. And I guess my point is, I've tested this. I can't seem to find any problems with it. But I do not have unit tests for the larger routing algorithm, only the routing within a Node. In my tests, it always worked out, but I would put my confidence in this at about 70%. In essence, I was ready to release this software to the Go community, have them kick it around a bit, see what came of it. I was not expecting a HN frontpage. So now I'm slightly panicked, and hoping to God that people don't think I'm an idiot for the rest of forever.
    - Intermernet 14y ago
      Calm those nerves :-) Now, you have the legions of HN to help. One of the joys of open source is that through building software, you also get to build communities. I have a feeling you'll be getting a fair bit of help on this project. It's generic enough to help in any number of applications and i'm sure many HN readers are currently trying to work out if they can apply this to any of their current projects. Best of luck, and thanks for adding another great instrument to Go's repertoire!
- JulianMorrison 14y ago
  How are you planning to implement pub-sub on top of it?
  - paddyforan 14y ago
    I'll be using the Scribe algorithm, as defined by the authors of the Pastry algorithm: http://en.wikipedia.org/wiki/Pastry_(DHT)#SCRIBE http://en.wikipedia.org/wiki/Pastry_(DHT)#SCRIBE The basic gist of it is similar to a phone tree. You route a message subscribing to a topic, basing the message ID on the topic name. As the message routes through the network, each Node stores the information about who is subscribed. When an event happens, that information is passed back through to the subscribed nodes. I may have to tweak it a little, as I did Pastry, but I'm pretty sure the same basic concept will work for my needs.
simonw 14y 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.
- paddyforan 14y 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 14y ago

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

paddyforan 14y 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.
- JulianMorrison 14y ago
  0mq doesn't have a client/server relationship. http://www.zeromq.org/ http://www.zeromq.org/
  - brian_cloutier 14y ago
    What does it have?
    - JulianMorrison 14y ago
      Peer-to-peer connections analogous to TCP. In the case of pub/sub all subscribers connect to the publisher. http://zguide2.zeromq.org/page:all http://zguide2.zeromq.org/page:all
      - paddyforan 14y ago
        I guess I was wrong about hard-coding the IPs. Maybe? It doesn't have many-to-many baked in, though. That I can see, at least. It looks like I may have been able to make this work, but the setup would be a little complex. ... because a distributed hash table is not complex at all. -_-

Saavedro 14y ago

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

paddyforan 14y 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.
- StavrosK 14y 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?
  - paddyforan 14y ago
    They both are the case. Well, sort of. The messages can go to any number of nodes as part of the routing, but they're only considered "delivered" at one node. However, nodes can die with minimal loss of data. The problem is you're confusing the messages for data. As far as Pastry is concerned, your messages are not data that it should retain. They are one-off communications. The only data that Pastry is concerned with storing is the state of the cluster; that is to say, Pastry only considers "data" the information about enough nodes to reliably be able to route a message to any node in the cluster. Your messages, by default, are lost the moment they are sent, forwarded, or delivered. The node stops caring about them at that point. However, on top of this framework you can build applications that do care about the data in the messages. Before a message is forwarded, it fires off a callback to any application that cares to listen for it. When a message is delivered, it fires off a callback to any application that cares to listen to it. You can register callbacks that store this information, then build your own redundancy frameworks on top of that to store the data you'd like to retain. If you're interested in this, I'd recommend paper on PAST. It's a high availability storage system built on Pastry: http://research.microsoft.com/en-us/um/people/antr/PAST/hotos.pdf http://research.microsoft.com/en-us/um/people/antr/PAST/hoto...

joelthelion 14y 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.

paddyforan 14y ago
http://tent.io/ http://tent.io/ ?
- joelthelion 14y 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.
  - paddyforan 14y ago
    Hm. That's the closest I've got. How's your Go? You can build one on Pastry. :)
- joelthelion 14y 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.
  - paddyforan 14y ago
    Not off the top of my head, no. Sorry. :( I know there's http://tent.is http://tent.is, and there's a Go client for Tent out there, but that's really all I know about it.
  - graue 14y ago
    Yup. There's a microblogging app (Twitter clone) called TentStatus, available hosted at https://tent.is https://tent.is, or run your own instance of the code: https://github.com/tent/tent-status https://github.com/tent/tent-status. Several people are working on iOS and Android apps to support the microblogging use case. There's Essayist, a (very alpha) long-form blogging app, hosted at http://essayist.mndj.me http://essayist.mndj.me, code at https://github.com/mwanji/essayist https://github.com/mwanji/essayist Meanwhile, the inventors of Tent have 5 people working 60+ hours a week running Tent.is and developing the protocol and apps for it. They haven't revealed what's next, though it sounds like some non-status apps are in the works.

jeremyjh 14y 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://www.rabbitmq.com/ha.html http://activemq.apache.org/masterslave.html http://activemq.apache.org/masterslave.html http://hornetq.sourceforge.net/docs/hornetq-2.0.0.GA/user-manual/en/html/ha.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.

paddyforan 14y 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.
- jeremyjh 14y ago
  A highly available system has no single point of failure.
  - paddyforan 14y ago
    It can, however, have bottlenecks. All of your solutions, based on the conversation below, separate the messaging into its own service. Which isn't really how I want to work with my software. I guess the best way I can describe it is as a different aesthetic. There are certainly ways to accomplish the same thing, technologically, but they all feel wrong to me. Introducing a message queue, with a broker, and needing to implement HA on that simply to remove that single point of failure... That feels like a workaround to me. I prefer working with a decentralised pub/sub framework. Personally. Personally, that difference is worth the development time and lack of maturity. To me. Which is why I slapped an alpha label on the project. Why I made no attempt to convince people they should switch over, or even that my way was objectively better than any other way. I had an itch. I scratched it. I released the backscratcher I used as open source so other people with the same itch could scratch it. I'm not sure why some people think this is a contemptible act.

matticakes 14y 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 https://github.com/bitly/nsq) but I could certainly see some interesting opportunities to experiment with a distribute hash table approach as well.

paddyforan 14y 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.
- matticakes 14y 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.
  - paddyforan 14y ago
    Hm. Very interesting, I'll have to take another look and get a better understanding of it.

realrocker 14y ago

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

cnlwsu 14y 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}"

deleted 14y ago

[deleted]

spullara 14y ago

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

paddyforan 14y ago
Yup. Totally could have made a choice I wasn't happy with. Opted to make a choice I was happy with instead.

igrekel 14y ago

Next step: a tupplespace in Go?

Terretta 14y 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/ 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?

paddyforan 14y 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 14y 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.