Hashtags

Hashtags

Motivation

The limitation of the Dyno pipelines is that they do not allow to perform pipelines across different keys (i.e. a pipeline can be extended across operations of the same key). This may affect projects that want to gain higher performance by using Redis pipelines.

To get around this limitation we want to add the support of Hash Tags such that we can do a pipeline operation in the value defined in the hashtag. This will bypass the limitation of Dyno that pipelines can be done in the same key as pipelines will be created on the hashtag, and therefore significantly improve the performance.

What is a Hashtag?

Hash Tags enables you to use part of the key for calculating the hash. When the hashtag is present, we use part of the key within the tag as the key to being used for consistent hashing. Otherwise, we use the full key as is. Hashtags enable you to map different keys to the same server as long as the part of the key within the tag is the same.

For example, the configuration of server pool beta, also shown below, specifies a two character hash_tag string - "{}". This means that keys "user:{user1}:ids" and "user:{user1}:tweets" map to the same server because we compute the hash on "user1". For a key like "user:user1:ids", we use the entire string "user:user1:ids" to compute the hash and it may map to a different server. A Dynomite YML file could look like:

beta:
  listen: 127.0.0.1:22122
  hash: fnv1a_64
  hash_tag: "{}"
  distribution: ketama
  auto_eject_hosts: false
  timeout: 400
  redis: true
  servers:
   - 127.0.0.1:6380:1 server1
   - 127.0.0.1:6381:1 server2
   - 127.0.0.1:6382:1 server3
   - 127.0.0.1:6383:1 server4

Fundamentally, hashtags allow the client to deterministically positions keys instead of only being dependent on the token-aware algorithm. In other words, it combines the best of both worlds. However, if used in incorrectly it may create hot spots.

Implementation

• To ensure the proper support of hashtags we have to make sure they are enabled on the Dynomite side. The first component is for Dyno to get information of the hashtag delimiter from Dynomite-manager. Dynomite-manager will write in Dynomite's YAML the supported hashtag. See the HttpEndpointBasedTokenMapSupplier.
• Currently, in a normal operation when a hashtag is defined at the Dynomite layer, we will try to extra the key from the hashtag. For example, if the key is foo-{bar}, we will use the bar as the value on which to perform the murmur hash function and determine the node to send the data.
• In a pipeline operation we have added the proper checks such that when there is a hashtag we make sure that check that each pipeline uses the same hashed value (not the same key).

What can you use for a hashtag?

The guarantees are that a hashtag can only be two characters, i.e. {} or []. Dynomite-manager would not provide the proper hashtags if it is larger than two characters. From that we perform StringUtils.substringBetween(key,Character.toString(hashtag.charAt(0)), Character.toString(hashtag.charAt(1))); to extract hash value to use to get the token (test cases added).

What if I do not use Dynomite-manager?

Dyno is not dependent on Dynomite-manager. As long as the following information are provided to Dyno, hashtags would work

  {
     "dc": "us-east-1",		  
     "hostname": "ec2-00-208-431-144.compute-1.amazonaws.com",
     "ip": "54.208.235.30",
     "rack": "dyno_ioannis--useast1d",
     "token": "1383429731",
     "zone": "us-east-1d",
     "hashtag" : "{}"
 }