Uploaded image for project: 'Cassandra'
  1. Cassandra
  2. CASSANDRA-7032

Improve vnode allocation

    XMLWordPrintableJSON

Details

    Description

      It's been known for a little while that random vnode allocation causes hotspots of ownership. It should be possible to improve dramatically on this with deterministic allocation. I have quickly thrown together a simple greedy algorithm that allocates vnodes efficiently, and will repair hotspots in a randomly allocated cluster gradually as more nodes are added, and also ensures that token ranges are fairly evenly spread between nodes (somewhat tunably so). The allocation still permits slight discrepancies in ownership, but it is bound by the inverse of the size of the cluster (as opposed to random allocation, which strangely gets worse as the cluster size increases). I'm sure there is a decent dynamic programming solution to this that would be even better.

      If on joining the ring a new node were to CAS a shared table where a canonical allocation of token ranges lives after running this (or a similar) algorithm, we could then get guaranteed bounds on the ownership distribution in a cluster. This will also help for CASSANDRA-6696.

      Attachments

        1. TestVNodeAllocation.java
          9 kB
          Benedict Elliott Smith
        2. TestVNodeAllocation.java
          10 kB
          Benedict Elliott Smith
        3. TestVNodeAllocation.java
          21 kB
          Branimir Lambov
        4. TestVNodeAllocation.java
          47 kB
          Branimir Lambov
        5. TestVNodeAllocation.java
          61 kB
          Branimir Lambov
        6. TestVNodeAllocation.java
          63 kB
          Branimir Lambov

        Issue Links

          Activity

            People

              blambov Branimir Lambov
              benedict Benedict Elliott Smith
              Branimir Lambov
              Benedict Elliott Smith
              Votes:
              0 Vote for this issue
              Watchers:
              25 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: