Consistent Hashing

Details and configuration considerations for using consistent hashing based routing

Consistent hashing based routing is a feature that can be used to distribute requests to a set of hosts in a cache friendly manner. By using Agile Content’s consistent distributed hash algorithm, the amount of cache redistribution is minimized within a set of hosts. Requests for a content will always be routed to the same set of hosts, the amount of which is configured by the spread factor, allowing high cache usage. When adding or removing hosts, the algorithm minimizes cache redistribution.

Say you have the host group [s1, s2, s3, s4, s5] and have configured spreadFactor = 3. A request for a content asset1 would then be routed to the same three hosts with one of them being selected randomly for each request. Requests for a different content asset2 would also be routed to one of three different hosts, most likely a different combination of hosts than requests for content asset1.

Example routing results with spreadFactor = 3:

  • Request for asset1 → route to one of [s1, s3, s4].
  • Request for asset2 → route to one of [s2, s4, s5].
  • Request for asset3 → route to one of [s1, s2, s5].

Since consistent hashing based routing ensures that requests for a specific content always get routed to the same set of hosts, the risk of cache misses are lowered on the hosts since they will be served the same content requests over and over again.

Note that the maximum value of spreadFactor is 64. Consequently, the highest amount of hosts you can use in a consistentHashing rule block is 64.

Three different hashing algorithms are available: MD5, SDBM and Murmur. The algorithm is chosen during configuration.

Configuration

Configuring consistent hashing based routing is easily done using confcli. Let’s configure the example described above:

confcli services.routing.rules -w
Running wizard for resource 'rules'

Hint: Hitting return will set a value to its default.
Enter '?' to receive the help string

rules : [
  rule can be one of
    1: allow
    2: consistentHashing
    3: contentPopularity
    4: deny
    5: firstMatch
    6: random
    7: rawGroup
    8: rawHost
    9: split
    10: weighted
  Choose element index or name: consistentHashing
  Adding a 'consistentHashing' element
    rule : {
      name (default: ): consistentHashingRule 
      type (default: consistentHashing): 
      spreadFactor (default: 1): 3
      hashAlgorithm (default: MD5):
      targets : [
        target : {
          target (default: ): s1
          enabled (default: True): 
        }
        Add another 'target' element to array 'targets'? [y/N]: y
        target : {
          target (default: ): s2
          enabled (default: True): 
        }
        Add another 'target' element to array 'targets'? [y/N]: y
        target : {
          target (default: ): s3
          enabled (default: True): 
        }
        Add another 'target' element to array 'targets'? [y/N]: y
        target : {
          target (default: ): s4
          enabled (default: True): 
        }
        Add another 'target' element to array 'targets'? [y/N]: y
        target : {
          target (default: ): s5
          enabled (default: True): 
        }
        Add another 'target' element to array 'targets'? [y/N]: n
      ]
    }
  Add another 'rule' element to array 'rules'? [y/N]: n
]
Generated config:
{
  "rules": [
    {
      "name": "consistentHashingRule",
      "type": "consistentHashing",
      "spreadFactor": 3,
      "hashAlgorithm": "MD5",
      "targets": [
        {
          "target": "s1",
          "enabled": true
        },
        {
          "target": "s2",
          "enabled": true
        },
        {
          "target": "s3",
          "enabled": true
        },
        {
          "target": "s4",
          "enabled": true
        },
        {
          "target": "s5",
          "enabled": true
        }
      ]
    }
  ]
}

Adding hosts

Adding a host to the list will give an additional target for the consistent hashing algorithm to route requests to. This will shift content distribution onto the new host.

confcli services.routing.rules.consistentHashingRule.targets -w
Running wizard for resource 'targets'

Hint: Hitting return will set a value to its default.
Enter '?' to receive the help string

targets : [
  target : {
    target (default: ): s6
    enabled (default: True): 
  }
  Add another 'target' element to array 'targets'? [y/N]: n
]
Generated config:
{
  "targets": [
    {
      "target": "s6",
      "enabled": true
    }
  ]
}
Merge and apply the config? [y/n]: y

Removing hosts

There is one very important caveat of using a consistent hashing rule block. As long as you don’t modify the list of hosts, the consistent hashing algorithm will keep routing requests to the same hosts. However, if you remove a host from the block in any position except the last, the consistent hashing algorithm’s behaviour will change and the algorithm cannot maintain a minimum amount of cache redistribution.

If you’re in a situation where you have to remove a host from the routing targets but want to keep the same consistent hashing behaviour, e.g. during very high load, you’ll have to toggle that target’s enabled field to false. E.g., disabling requests to s2 can be accomplished by:

$ confcli services.routing.rules.consistentHashingRule.targets.1.enabled false
services.routing.rules.consistentHashingRule.targets.1.enabled = False
$ confcli services.routing.rules.consistentHashingRule.targets.1
{
    "1": {
        "target": "s2",
        "enabled": false
    }
}

If you modify the list order or remove hosts, it is highly recommended to do so during moments where a higher rate of cache misses are acceptable.