http://ayende.comAyende @ RahienCopyright (C) Ayende Rahien 2004 - 2021 (c) 202660Cali, In your case, you don't actually have a problem. You have a single point of truth, so you can sync around that. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment35http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment35Mon, 13 Apr 2009 15:04:56 GMTAyende, I also commented on your newer post about NChord before reading this post. Chord was really designed for a variety of high churn networks... because it was inspired by peer-to-peer file sharing architecture. There are nodes in a Chord network which you could not make Leaders (or supernodes) due to latency concerns so your first-come leader strategy would break, but your business requirements gets around that problem. A supernode infrastructure is much more efficient like you point out in these articles. Anyway, I'm working on fault tolerance for calendar of events aggregation at work and I decided that during leader failure all nodes would race each other to become the new leader. I use the database to queue up leader candidates and then broadcast leader status across the cluster when the new leader takes over. The database is fault tolerant and IMHO is perfect for this task IF like in my case your identity strategy is sequence. Otherwise I don't think it would work. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment34http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment34Mon, 13 Apr 2009 07:44:16 GMTMost of the commercial distributed caches have persistence capabilities. You might want tot check out GigaSpaces and Coherence (now under Oracle). http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment33http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment33Fri, 10 Apr 2009 12:18:01 GMTBystrik, Caching solutions aren't really good, I need something with persistence options. When the entire aggregate is under a key it is _really_ fast. The problem with most RDMBS is that they don't scale wide very easily. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment32http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment32Fri, 10 Apr 2009 04:54:16 GMTInteresting problem but did you considered other options? NCache, NVelocity...I have not done any performance measurements yet therefore I'm curious how fast is retrieving data from distributed hash across network in comparison with RDB. When you have entire aggregate(in DDD meaning) under one key it must be amazing fast. However, execute complex queries against such data store seems to be difficult as well as handling references. The performance gain in such scenarios(complex queries) might not be reasonable... http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment31http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment31Fri, 10 Apr 2009 04:48:56 GMTPaul, Yes, but the imbalance is small enough for us not to care about it. As for 5 nodes: 1 - 0-205 (primary), 820 - 1024 (secondary), 616- 820 (tertiary) 2 - 205 - 410 (p), 0 - 205 (s) 820 - 1024 (t) 3 - 410 - 615 (p), 205 - 410 (s), 0 - 205 (t) 4 - 615 - 820 (p), 410 - 615 (s), 205 - 410 (t) 5 - 820 - 1024 (p), 615 - 820 (s), 410 - 615(t) There is _very_ small imbalance here, the last node has 204 ranges instead of 205. But every node is primary, secondary and tertiary. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment30http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment30Wed, 08 Apr 2009 19:36:34 GMTErik, This is just one detail of how to find the nodes, I am aware of this. I am more concerned with detecting and transparently moving data in the presence of failure or new nodes. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment29http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment29Wed, 08 Apr 2009 16:28:41 GMTSo it does this partionining now with the imbalance? One other thing, if you have 5 nodes, I don't think there is any topology that allows each not to have a primary, secondary and tertiarty data. One node would have to have only a primary and secondary, or primary, secondary, tertiary and 4th store? http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment28http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment28Wed, 08 Apr 2009 08:18:53 GMTVery interesting stuff. For resharding when nodes join, take a look at consistent hashing: [http://en.wikipedia.org/wiki/Consistent_hashing](http://en.wikipedia.org/wiki/Consistent_hashing) [www.spiteful.com/.../programmers-toolbox-part-3...](http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/) Regards, Erik http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment27http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment27Wed, 08 Apr 2009 07:05:58 GMTreally good discussion my thought would be to have a controller node of some sort (similar to your watch dog idea) the controller node would of course be backed up by another node for fail-safe operations but... this controller node would be the one that indicates who the leader is (if more than one node comes on like) but would also be responsible for holding or containing the ranges my thought here would be that the ranges would be fed into the nodes as designations rather than a single node (the leader) trying to determine it as nodes come up the controller would determine what ranges should should be re-partitioned and how then when the controller re-hashes the ranges the DHT would flow through it rather than an ack-nack with the lead controller does that make sense? so node 1 is on-line with all of the ranges available to it as node 2 is being brought up (before the topology is changed mind you), the controller would re-hash the ranges and request the data from node 1 for the ranges going to node 2 if there is an error or some transmission error then node 2 has still not been activated and no topology has changed (mind you... i don't think that it would be necessary to remove data from the nodes for specific ranges since those ranges would "fall off" after the topology is changed) the only issue here (as i am thinking about it) would be that while the ranges and topology are changing (or nodes are being brought up) the controller nodes would have to get any updates or additions to smartly invalidate those ranges for a second pass (like an active pass through) eh... this approach might be a little nieve and more than likely introduce too many moving parts http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment26http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment26Tue, 07 Apr 2009 19:56:23 GMTOmer, A lot of the data that I store is keyed and non relational. Shopping cart information, search information, etc. That _is_ the business problem that we are solving. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment25http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment25Tue, 07 Apr 2009 17:28:35 GMTPaul, Yes, there would be some small imbalance, but for a 7 node cluster, we are talking about two nodes with 147 ranges and five nodes with 146, that is not really problematic from my view point. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment24http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment24Tue, 07 Apr 2009 17:26:40 GMTOren, All the examples you gave (session store, saga state, cache, etc...) are from the domain of the infrastructure. I fully understand how your DHT solution fits that domain. I was curios in the _business_ problem you're working on that needs all that heavy infrastructure. It's not a matter of not understanding the problem or the solution. I'm just curios about what made you write this. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment23http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment23Tue, 07 Apr 2009 16:05:51 GMTEach node has a primary and secondary and tertiary range of nodes it maintains incase any one of the nodes fails. The ranges that each node are split is 1024 / nodes, for your 4 node example. Each range is 256 = 1024 / 4. Backed up on two other machines. If you have 5 nodes 1024 / 5 does not fit , so the ranges that each node looks after will be unbalanced. Infact, I made a mistake when I said even number, does the number of nodes have to be a ^2? To be fair I have not seen the code (is it available) so I am making wild assumptions http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment22http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment22Tue, 07 Apr 2009 15:23:53 GMTUm, I am not seeing how you reached that conclusion. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment21http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment21Tue, 07 Apr 2009 15:08:42 GMTJust out of curiosity, is it me or can you only have an even number of nodes in your network? That is your DHT couldn't consist of 3,5 or 7 nodes as the ranges would be unbalanced. Paul. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment20http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment20Tue, 07 Apr 2009 15:04:31 GMTSession store, saga state, highly efficent key based retrieval for state of current operations, cache. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment19http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment19Tue, 07 Apr 2009 15:02:37 GMTOren - I'll "rehash" my question: What is the problem that you're trying to solve with a "Key value store for items in a distributed network that can survive nodes coming up and down". Having a dynamic DHT like you're describing is neat, but what is your real-world "business" problem that made you write it for? http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment18http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment18Tue, 07 Apr 2009 14:50:05 GMTDon, I did, but they all make assumptions about the type of network that you do, which is not relevant to where I want to use the DHT. The DHT is going to be used most often on the LAN, or, at worst, across data centers. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment17http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment17Tue, 07 Apr 2009 13:29:37 GMTAndy, 1024 gives me 1024 nodes in the cluster, more than enough. I am aware of network partitioning, and I'll write some tests for it, but I don't know how to deal with it right now. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment16http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment16Tue, 07 Apr 2009 13:16:54 GMTTapio, I thought that my design did just that, the leader controls the network topology. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment15http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment15Tue, 07 Apr 2009 13:15:35 GMTHave you tried looking into the design of Bittorrent's overlay network? It is what they use for "dynamically distributed network of nodes" in their DHT implementation. There are a number of open source Bittorrent implementations. The Mono guys have one, BitSharp [http://www.mono-project.com/Bitsharp](http://www.mono-project.com/Bitsharp). Lately I've been messing with BitSharp and the Memcached client Enyim.Caching (which also uses a DHT). http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment14http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment14Tue, 07 Apr 2009 11:58:53 GMT- 1024 buckets isn't enough, try going higher - another uncommon but real scenario is network partioning (ie a vlan config somewhere gets borked and suddenly half the computers are split and isolated from the other half). In this case, there needs to be a recovery case for when the two isolated networks are rejoined http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment13http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment13Tue, 07 Apr 2009 04:34:00 GMTOren, Your design does not really remove the rehashing problem. Instead of rehashing keys, you end up moving ranges from one node to another. My idea of of mod operator to find out the owner-node of a range was a very bad anyway. That would easily cause the primary, secondary and tertiary nodes be the same node. Hash the keys using a fixed-length range-array and use your master to control the topology of nodes and ranges. That way you'll never have to rehash keys. The failure behavior is something you have to think about. If a node goes down because of too heavy traffic and the master decides to change the topoplogy, the failure could escalate to other nodes very fast and bring all nodes down. Tapio http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment12http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment12Tue, 07 Apr 2009 03:47:47 GMTAndy, I took a _very_ quick peek into NChord, and... the code base makes me nervous. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment11http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment11Tue, 07 Apr 2009 01:24:41 GMTTapio, Using the second mod would mean that I am still vulnerable to rehashing issues. I prefer to have a much more explicit control over the issue, rather then just use mods. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment10http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment10Tue, 07 Apr 2009 01:18:52 GMTVictor, I am not going to handle this scenario. When the leader come back up, it is going to be a regular node under the new leader. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment9http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment9Tue, 07 Apr 2009 01:17:18 GMTOmer, Key value store for items in a distributed network that can survive nodes coming up and down. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment8http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment8Tue, 07 Apr 2009 01:16:16 GMTAndy, No, I didn't know about this. I'll take a look, looks very interesting. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment7http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment7Tue, 07 Apr 2009 01:15:38 GMTV, That is not a problem, the client always goes to the same node for the same value. http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment6http://ayende.com/3934/designing-rhino-dht-a-fault-tolerant-dynamically-distributed-hash-table#comment6Tue, 07 Apr 2009 01:11:45 GMT