class Redis::KeyHash

Namespace for key-hashing methods.

Constants

VERSION

Public Class Methods

all_in_one_slot!(*keys, namespace: nil, styles: DEFAULT_STYLES) click to toggle source

Like all_in_one_slot?, mismatch raises Redis::ImpendingCrossSlotError.

@param keys String keys to be tested

@param namespace String or nil if non-nil, applied as a prefix to all keys as per the redis-namespace gem before testing.

@param styles Array of Symbols and/or Regexps as per hash_tag().

@return true if all of keys will hash to the same slot in all of the styles, false if there is any doubt.

@return true if all of keys provably have the same hash_slot under all styles by virtue of having a single hash_tag.

@raises Redis::ImpendingCrossSlotError if, for any styles, the keys have a different hash_tag hence will not provably have the same hash_slot

# File lib/redis/key_hash.rb, line 96
def self.all_in_one_slot!(*keys, namespace: nil, styles: DEFAULT_STYLES)
  namespaced_keys   = keys
  if namespace
    #
    # Although Redis::Namespace.add_namespace is private, I have
    # confirmed that when namespace is the empty string, "key"
    # maps to ":key".
    #
    # That is, namespace nil has no effect, but namespace ''
    # results in a ':' prepended to every key.
    #
    # Naturally, this can affect the key's hash tag.
    #
    namespaced_keys = keys.map { |key| "#{namespace}:#{key}" }
  end
  problems          = []
  styles.each do |style|
    tags            = namespaced_keys.map do |namespaced_key|
      hash_tag(namespaced_key,style: style)
    end.uniq
    next if tags.size <= 1
    problems << "style #{style} sees tags #{tags.join(',')}"
  end
  if 0 != problems.size
    raise Redis::ImpendingCrossSlotError.new(
            namespace,
            keys,
            namespaced_keys,
            problems
          )
  end
  true
end
all_in_one_slot?(*keys, namespace: nil, styles: DEFAULT_STYLES) click to toggle source

Tests whether all of keys will hash to the same slot in all specified sharding styles.

@param keys String keys to be tested

@param namespace String or nil if non-nil, applied as a prefix to all keys as per the redis-namespace gem before testing.

@param styles Array of Symbols and/or Regexps as per hash_tag().

@return true if all of keys provably have the same hash_slot under all styles by virtue of having a single hash_tag, false otherwise.

# File lib/redis/key_hash.rb, line 69
def self.all_in_one_slot?(*keys, namespace: nil, styles: DEFAULT_STYLES)
  all_in_one_slot!(*keys, namespace: namespace, styles: styles)
rescue Redis::ImpendingCrossSlotError
  return false
else
  return true
end
crc16(key) click to toggle source

Computes the Redis crc16 for a given key, as per the reference implementation provided in redis.io/topics/cluster-spec.

This implementation is taken largely from that reference document, changed only slightly to port to Ruby.

@param String key

@param non-negative Integer the crc16 which Redis will use to compute a hash_key.

# File lib/redis/key_hash.rb, line 185
def self.crc16(key)
  crc = 0
  key.each_char do |char|
    crc = ((crc<<8) & 0xFFFF) ^ CRC16TAB[((crc>>8) ^ char.ord) & 0x00FF]
  end
  crc
end
hash_slot(key, style: DEFAULT_STYLE) click to toggle source

Computes the Redis hash_slot for a given key.

Uses :style as per hash_tag, but performs hashing as per RC only. We know through documentation and experimentation that RC uses crc16() and modulo 16384. We do not know what RLEC does, but until we have a better model we assume it is the same. This is probably a false assumption since the RLEC docs state that the number of shards can vary from cluster to cluster. But for many analyses, using the same hash as RC is still useful.

@param String key to be hashed

@param Symbol :rc or :rlec or Regexp which defines one capture group

@param non-negative Integer the hash which Redis will use to slot key

# File lib/redis/key_hash.rb, line 169
def self.hash_slot(key, style: DEFAULT_STYLE)
  tag = hash_tag(key, style: style)
  crc16(tag) % 16384
end
hash_tag(key, style: DEFAULT_STYLE) click to toggle source

Computes the hash tag for a given key under a given Redis clustering algorithm.

@param String key to be hashed

@param Symbol :rc or rlec or Regexp which defines one capture group

@param String the tag extracted from key as appropriate for :style.

# File lib/redis/key_hash.rb, line 139
def self.hash_tag(key, style: DEFAULT_STYLE)
  regexp = nil
  if KNOWN_STYLES.key?(style)
    regexp = KNOWN_STYLES[style] # some are predefined
  elsif style.is_a?(Regexp)
    regexp = style               # you can define your own
  end
  if !regexp
    raise ArgumentError, "bogus style #{style}"
  end
  match = regexp.match(key)
  match ? match[1] : key
end