MEDIUM: backend: Enhance hash-type directive with an algorithm options
Summary:
In testing at tumblr, we found that using djb2 hashing instead of the
default sdbm hashing resulted is better workload distribution to our backends.
This commit implements a change, that allows the user to specify the hash
function they want to use. It does not limit itself to consistent hashing
scenarios.
The supported hash functions are sdbm (default), and djb2.
For a discussion of the feature and analysis, see mailing list thread
"Consistent hashing alternative to sdbm" :
http://marc.info/?l=haproxy&m=138213693909219
Note: This change does NOT make changes to new features, for instance,
applying an avalance hashing always being performed before applying
consistent hashing.
diff --git a/doc/configuration.txt b/doc/configuration.txt
index ba8057f..643afd9 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -2496,45 +2496,65 @@
simplify it.
-hash-type <method>
+hash-type <method> <function>
Specify a method to use for mapping hashes to servers
May be used in sections : defaults | frontend | listen | backend
yes | no | yes | yes
Arguments :
- map-based the hash table is a static array containing all alive servers.
- The hashes will be very smooth, will consider weights, but will
- be static in that weight changes while a server is up will be
- ignored. This means that there will be no slow start. Also,
- since a server is selected by its position in the array, most
- mappings are changed when the server count changes. This means
- that when a server goes up or down, or when a server is added
- to a farm, most connections will be redistributed to different
- servers. This can be inconvenient with caches for instance.
+ <method> is the method used to select a server from the hash computed by
+ the <function> :
- avalanche this mechanism uses the default map-based hashing described
- above but applies a full avalanche hash before performing the
- mapping. The result is a slightly less smooth hash for most
- situations, but the hash becomes better than pure map-based
- hashes when the number of servers is a multiple of the size of
- the input set. When using URI hash with a number of servers
- multiple of 64, it's desirable to change the hash type to
- this value.
+ map-based the hash table is a static array containing all alive servers.
+ The hashes will be very smooth, will consider weights, but
+ will be static in that weight changes while a server is up
+ will be ignored. This means that there will be no slow start.
+ Also, since a server is selected by its position in the array,
+ most mappings are changed when the server count changes. This
+ means that when a server goes up or down, or when a server is
+ added to a farm, most connections will be redistributed to
+ different servers. This can be inconvenient with caches for
+ instance.
- consistent the hash table is a tree filled with many occurrences of each
- server. The hash key is looked up in the tree and the closest
- server is chosen. This hash is dynamic, it supports changing
- weights while the servers are up, so it is compatible with the
- slow start feature. It has the advantage that when a server
- goes up or down, only its associations are moved. When a server
- is added to the farm, only a few part of the mappings are
- redistributed, making it an ideal algorithm for caches.
- However, due to its principle, the algorithm will never be very
- smooth and it may sometimes be necessary to adjust a server's
- weight or its ID to get a more balanced distribution. In order
- to get the same distribution on multiple load balancers, it is
- important that all servers have the same IDs.
+ avalanche this mechanism uses the default map-based hashing described
+ above but applies a full avalanche hash before performing the
+ mapping. The result is a slightly less smooth hash for most
+ situations, but the hash becomes better than pure map-based
+ hashes when the number of servers is a multiple of the size of
+ the input set. When using URI hash with a number of servers
+ multiple of 64, it's desirable to change the hash type to
+ this value.
+
+ consistent the hash table is a tree filled with many occurrences of each
+ server. The hash key is looked up in the tree and the closest
+ server is chosen. This hash is dynamic, it supports changing
+ weights while the servers are up, so it is compatible with the
+ slow start feature. It has the advantage that when a server
+ goes up or down, only its associations are moved. When a
+ server is added to the farm, only a few part of the mappings
+ are redistributed, making it an ideal method for caches.
+ However, due to its principle, the distribution will never be
+ very smooth and it may sometimes be necessary to adjust a
+ server's weight or its ID to get a more balanced distribution.
+ In order to get the same distribution on multiple load
+ balancers, it is important that all servers have the exact
+ same IDs. Note: by default, a full avalanche hash is always
+ performed before applying the consistent hash.
+
+ <function> is the hash function to be used :
+
+ sdbm this function was created intially for sdbm (a public-domain
+ reimplementation of ndbm) database library. It was found to do
+ well in scrambling bits, causing better distribution of the keys
+ and fewer splits. It also happens to be a good general hashing
+ function with good distribution.
+
+ djb2 this function was first proposed by Dan Bernstein many years ago
+ on comp.lang.c. Studies have shown that for certain workload this
+ function provides a better distribution than sdbm.
- The default hash type is "map-based" and is recommended for most usages.
+ The default hash type is "map-based" and is recommended for most usages. The
+ default function is "sdbm", the selection of a function should be based on
+ the range of the values being hashed.
See also : "balance", "server"