11 Replies Latest reply on Jan 10, 2011 6:56 AM by manik

    Lack of 'Virtual node' in infinispan consistent hash?

    changgeng

      Hi,

       

      In our test with infinispan 4.2.0.Final, we found that the data on the cluster is a very non-uniform distribution. With 14 entries in a 6 nodes cluster, one node got 11 entries, 3 nodes got one each, and the other two nodes got node.

       

      I read the code of AbstractWheelConsistentHash, it seems infinispan doesn't using the virtual node idea, that when adding a new node, it will be mapped to several virtual nodes to achieve a better distribution. I think the following log entry can show this.

       

      2011-01-04 06:22:07,165 TRACE [org.infinispan.distribution.ch.AbstractWheelConsistentHash](OOB-19,ana,perf-srm6-57520) Position are: {29=perf-srm4-51743, 1664=perf-srm3-10713, 2063=perf-srm-45067, 2594=perf-srm6-57520, 4055=perf-srm2-58295, 4477=perf-srm5-54}

       

      Could the developer confirm if that is true and provide any resolution to gain a better distribution?

       

      Thank you.

        • 1. Re: Lack of 'Virtual node' in infinispan consistent hash?
          mircea.markus

          Changgeng Li wrote:

           

          In our test with infinispan 4.2.0.Final, we found that the data on the cluster is a very non-uniform distribution. With 14 entries in a 6 nodes cluster, one node got 11 entries, 3 nodes got one each, and the other two nodes got node.

          Infinispan does not use Virtual Nodes for enhancing distribution, but a Murmur hash implementation which should do fine: https://issues.jboss.org/browse/ISPN-350. Mind increasing the number of keys to a higher value and give it a try? My hope is that the distribution evens at that point.

          • 2. Re: Lack of 'Virtual node' in infinispan consistent hash?
            changgeng

            From the log line I posted it seems the node 'perf-srm4' need to take care more than half of the total hash space.(10240+29-4477=5792)

            I guess this will lead to the inequality no matter how many keys we actually have.

             

            We have another unit test to show that no virtual nodes does matter. In this test case we insert 400,000 keys into a 10 nodes cluster. The key is just a string with some sequential number.

             

            2011-01-04 17:26:27,150 TRACE [org.infinispan.distribution.ch.AbstractWheelConsistentHash](OOB-19,ana-cluster,localhost-7452)- Position are: {1229=localhost-51442, 3738=localhost-42490, 5045=localhost-618, 5234=localhost-64081, 6974=localhost-1753, 7309=localhost-18065, 8078=localhost-51869, 8577=localhost-10387, 8631=localhost-7452, 9933=localhost-13245}

             

            In the end one of the node has 40 times than the one with bad luck.

             

            cache 1 size:51153(localhost-618)
            cache 2 size:50978(localhost-13245)
            cache 3 size:2140(localhost-7452)
            cache 4 size:29705(localhost-51869)
            cache 5 size:97834(localhost-42490)
            cache 6 size:7268(localhost-64081)
            cache 7 size:19366(localhost-10387)
            cache 8 size:13103(localhost-18065)
            cache 9 size:68440(localhost-1753)
            cache 10 size:60013(localhost-51442)

            total size:400000   min:2140     max:97834 

            • 3. Re: Lack of 'Virtual node' in infinispan consistent hash?
              manik

              We will be moving to MurmurHash3 in Infinispan 5.0. 

               

              https://issues.jboss.org/browse/ISPN-859

               

              If you wish, you could try a MurmurHash3 impl in place of MurmurHash2 in the src code and see if it improves distribution spread for you?

              • 4. Re: Lack of 'Virtual node' in infinispan consistent hash?
                changgeng

                Though MumurHash3 fixed some flaw in murmurHash2, I think it still can not guarantee that for any number of nodes the distrbution is acceptable. Let's assume we have 4 nodes that spread on the hash space ideally, and the normalized hash of them are 0, 2560, 5120, and 7680. When adding a new node in this cluster,the best case will be 3 of the five nodes takes care a quarter of the hash space each, and the other 2 nodes take 1/8 each.

                • 5. Re: Lack of 'Virtual node' in infinispan consistent hash?
                  galder.zamarreno

                  But with that approach, you get a lot more rebalancing going on compared to when you don't try to make distribution balanced. The current approach of nodes sticking to a hash and not moving regardless of nodes joining/leaving results in rebalancing only involving the two neighbouring nodes, hence reducing traffic during the rebalancing process.

                  • 6. Re: Lack of 'Virtual node' in infinispan consistent hash?
                    changgeng

                    It will be a lot of nodes need to communicate with each other, but the total amount of data that needs to be relocated won't be more. The current situation will require much more node to be able to hold the data in memory than necessary.

                    • 7. Re: Lack of 'Virtual node' in infinispan consistent hash?
                      mircea.markus

                      Interesting. The fact that multiple nodes would provide state is not necessary a bad thing, as state transfer might happen in parallel and faster. 

                      • 8. Re: Lack of 'Virtual node' in infinispan consistent hash?
                        mircea.markus
                        I guess this will lead to the inequality no matter how many keys we actually have.

                        My hope was that 14 keys was just not enough to study distribution. 400k is though.

                        • 9. Re: Lack of 'Virtual node' in infinispan consistent hash?
                          manik

                          I'm not so sure.  For larger grids, this would almost certainly be worse.  E.g., 1000 nodes needing to rehash "a little bit".  Also, it isn't a case of 999 nodes sending 1 node some stuff; it is all 1000 nodes moving a bit, and potentially having to take ownership of some new state.

                           

                          Using vnodes is the correct approach here, however it is non-trivial.

                           

                          Then again, since we now have ISPN-180 thanks to Mircea, vnodes will be easier to implement since our ConsistentHash impl is now able to skip nodes that are deemed colocated.  (It would also need to skip vnodes that are deemed colocated).  So the remaining work - apart from creating and placing vnodes on the wheel - would be in modifying the rehashing code to optimise rehashes between vnodes to use an internal mapping change rather than a full-on rehash.

                          • 10. Lack of 'Virtual node' in infinispan consistent hash?
                            changgeng

                            When is this going to be done? Is there any jira for it?

                            • 11. Lack of 'Virtual node' in infinispan consistent hash?
                              manik

                              Not as yet.  Feel free to create one and vote for it.