hashutil

Documentation

Index

• func ConsistentHash(key uint64, numShards uint16) uint16
• func Hash(v interface{}, opts *HashOptions) (uint64, error)
• func Keccak256(data ...[]byte) []byte
• func Keccak512(data ...[]byte) []byte
• func MD5(data string) string
• func MD5Verify(data string, v string) bool
• func Sha1(data ...[]byte) []byte
• func Sha256(data ...[]byte) []byte
• func Sha512(data ...[]byte) []byte
• type ErrNotStringer
  • func (ens *ErrNotStringer) Error() string
• type HashOptions
• type Includable
• type IncludableMap

Functions

func ConsistentHash

func ConsistentHash(key uint64, numShards uint16) uint16

ConsistentHash is a space efficient permutation-based consistent hashing function. This implementation supports up to a maximum of (1 << 16 - 1), 65535, number of shards.

Implementation details:

Unlike the standard ring-based algorithm (e.g., as described in dynamo db), this algorithm relays on shard permutations to determine the key's shard mapping. The idea is as follow:

1. Assume there exist a set of shard ids, S, which contains every possible shard ids in the universe (in this case 0 .. 65535).
2. Now suppose, A (a subset of S), is the set of available shard ids, and we want to find the shard mapping for key, K
3. Use K as the pseudorandom generator's seed, and generate a random permutation of S using variable-base permutation encoding (see http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms for additional details)
4. Ignore all shard ids in the permutation that are not in set A
5. Finally, use the first shard id as K's shard mapping.

NOTE: Because each key generates a different permutation, the data distribution is generally more uniform than the standard algorithm (The standard algorithm works around this issue by adding more points to the ring, which unfortunately uses even more memory).

Complexity: this algorithm is O(1) in theory (because the max shard id is known), but O(n) in practice.

Example:

1. Assume S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and A = {0, 1, 2, 3, 4}.
2. Now suppose K = 31415 and perm(S, K) = (3, 1, 9, 4, 7, 5, 8, 2, 0, 6).
3. After ignoring S - A, the remaining ids are (3, 1, 4, 2, 0)
4. Therefore, the key belongs to shard 3.

func Hash

func Hash(v interface{}, opts *HashOptions) (uint64, error)

Hash returns the hash value of an arbitrary value.

If opts is nil, then default options will be used. See HashOptions for the default values. The same *HashOptions value cannot be used concurrently. None of the values within a *HashOptions struct are safe to read/write while hashing is being done.

Notes on the value:

• Unexported fields on structs are ignored and do not affect the hash value.

• Adding an exported field to a struct with the zero value will change the hash value.

For structs, the hashing can be controlled using tags. For example:

struct {
    Name string
    UUID string `hash:"ignore"`
}

The available tag values are:

• "ignore" or "-" - The field will be ignored and not affect the hash code.

• "set" - The field will be treated as a set, where ordering doesn't affect the hash code. This only works for slices.

• "string" - The field will be hashed as a string, only works when the field implements fmt.Stringer

func Keccak256

func Keccak256(data ...[]byte) []byte

Keccak256 calculates and returns the Keccak256 hash of the input data.

func Keccak512

func Keccak512(data ...[]byte) []byte

Keccak512 calculates and returns the Keccak512 hash of the input data.

func MD5

func MD5(data string) string

MD5 md5 encryption

func MD5Verify

func MD5Verify(data string, v string) bool

MD5Verify md5 verify

func Sha1

func Sha1(data ...[]byte) []byte

func Sha256

func Sha256(data ...[]byte) []byte

func Sha512

func Sha512(data ...[]byte) []byte

Types

type ErrNotStringer

type ErrNotStringer struct {
	Field string
}

ErrNotStringer is returned when there's an error with hash:"string"

func (*ErrNotStringer) Error

func (ens *ErrNotStringer) Error() string

Error implements error for ErrNotStringer

type HashOptions

type HashOptions struct {
	// Hasher is the hash function to use. If this isn't set, it will
	// default to FNV.
	Hasher hash.Hash64

	// TagName is the struct tag to look at when hashing the structure.
	// By default this is "hash".
	TagName string

	// ZeroNil is flag determining if nil pointer should be treated equal
	// to a zero value of pointed type. By default this is false.
	ZeroNil bool
}

HashOptions are options that are available for hashing.

type Includable

type Includable interface {
	HashInclude(field string, v interface{}) (bool, error)
}

Includable is an interface that can optionally be implemented by a struct. It will be called for each field in the struct to check whether it should be included in the hash.

type IncludableMap

type IncludableMap interface {
	HashIncludeMap(field string, k, v interface{}) (bool, error)
}

IncludableMap is an interface that can optionally be implemented by a struct. It will be called when a map-type field is found to ask the struct if the map item should be included in the hash.