Uploaded image for project: 'Couchbase Server'
  1. Couchbase Server
  2. MB-7630

Alternative consistent hashing mapping mechanism

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Minor
    • Resolution: Won't Fix
    • Affects Version/s: techdebt-backlog
    • Fix Version/s: feature-backlog
    • Component/s: couchbase-bucket
    • Security Level: Public
    • Labels:
      None

      Description

      The current code implements Ketama which builds a sorted list of 100 or 160 hash points per server, and then performs a logarithmic search for the server with the closest point.

      Consider the following alternative: Given N servers, create an array of N*(N-1) entries, and fill it with servers in such a way that each server appears (N-1) times, and adjacent server pairs occur exactly once. For example, for N=3 with servers A,B,C, one possible arrangement is servers := [ A, B, C, A, C, B ]

      When mapping a key, calculate its hash as usual, then use s = servers[ hash(key) % N*(N-1) ] to determine the mapping.

      When a server fails, remap keys to the next server in the array: e.g. when B fails, the array is modified to [ A, C, C, A, C, A ]. Assuming a uniform key hash function, this guarantees an even redistribution of keys

      The mapping function is simpler and more performant than the Ketama approach, while also exhibiting better cache locality.
      Using 8 bits per server, this approach would only require 65K to support up to 256 servers.

      Weighted consistent hashing can be implemented in a similar fashion, varying the frequency of servers in the array according to their weight.

        Attachments

        No reviews matched the request. Check your Options in the drop-down menu of this sections header.

          Activity

            People

            • Assignee:
              steve Steve Yen
              Reporter:
              jbemmel Jeroen van Bemmel
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Gerrit Reviews

                There are no open Gerrit changes