±à¼ÍƼö: |
±¾ÎÄÖ÷Òª½éÉÜÁËÒ»ÖÂÐÔ Hash ÊÇʲô£¿¼°ÆäÔÚ¸ºÔؾùºâÖеÄÓ¦Óã¬Ï£Íû¶ÔÄúµÄѧϰÓÐËù°ïÖú¡£
±¾ÎÄÀ´×ÔÓÚ Î¢ÐŹ«ÖÚºÅJava±Ê¼ÇϺ£¬ÓÉLinda±à¼¡¢ÍƼö¡£ |
|
01¡¢¼ò½é
Ò»ÖÂÐÔHashÊÇÒ»ÖÖÌØÊâµÄHashËã·¨£¬ÓÉÓÚÆä¾ùºâÐÔ¡¢³Ö¾ÃÐÔµÄÓ³ÉäÌØµã£¬±»¹ã·ºµÄÓ¦ÓÃÓÚ¸ºÔؾùºâÁìÓò£¬ÈçnginxºÍmemcached¶¼²ÉÓÃÁËÒ»ÖÂÐÔHashÀ´×÷Ϊ¼¯Èº¸ºÔؾùºâµÄ·½°¸¡£
±¾ÎĽ«½éÉÜÒ»ÖÂÐÔHashµÄ»ù±¾Ë¼Â·£¬²¢ÌÖÂÛÆäÔÚ·Ö²¼Ê½»º´æ¼¯Èº¸ºÔؾùºâÖеÄÓ¦Óá£Í¬Ê±Ò²»á½øÐÐÏàÓ¦µÄ´úÂë²âÊÔÀ´ÑéÖ¤ÆäËã·¨ÌØÐÔ£¬²¢¸ø³öºÍÆäËû¸ºÔؾùºâ·½°¸µÄһЩ¶Ô±È¡£
02¡¢Ò»ÖÂÐÔHashËã·¨¼ò½é
ÔÚÁ˽âÒ»ÖÂÐÔHashË㷨֮ǰ£¬ÏÈÀ´ÌÖÂÛÒ»ÏÂHash±¾ÉíµÄÌØµã¡£ÆÕͨµÄHashº¯Êý×î´óµÄ×÷ÓÃÊÇÉ¢ÁУ¬»òÕß˵Êǽ«Ò»ÏµÁÐÔÚÐÎʽÉϾßÓÐÏàËÆÐÔÖʵÄÊý¾Ý£¬´òÉ¢³ÉËæ»úµÄ¡¢¾ùÔÈ·Ö²¼µÄÊý¾Ý¡£±ÈÈ磬¶Ô×Ö·û´®abcºÍabcd·Ö±ð½øÐÐmd5¼ÆË㣬µÃµ½µÄ½á¹ûÈçÏ£º

¿ÉÒÔ¿´µ½£¬Á½¸öÔÚÐÎʽÉϷdz£Ïà½üµÄÊý¾Ý¾¹ýmd5É¢Áк󣬱ä³ÉÁËÍêÈ«Ëæ»úµÄ×Ö·û´®¡£¸ºÔؾùºâÕýÊÇÀûÓÃÕâÒ»ÌØÐÔ£¬¶ÔÓÚ´óÁ¿Ëæ»úµÄÇëÇó»òµ÷Óã¬Í¨¹ýÒ»¶¨ÐÎʽµÄHash½«ËûÃǾùÔȵÄÉ¢ÁУ¬´Ó¶øÊµÏÖѹÁ¦µÄƽ¾ù»¯¡££¨µ±È»£¬²¢²»ÊÇֻҪʹÓÃÁËHash¾ÍÒ»¶¨Äܹ»»ñµÃ¾ùÔȵÄÉ¢ÁУ¬ºóÃæ»á·ÖÎöÕâÒ»µã¡££©
¾Ù¸öÀý×Ó£¬Èç¹ûÎÒÃǸøÃ¿¸öÇëÇóÉú³ÉÒ»¸öKey£¬Ö»ÒªÊ¹ÓÃÒ»¸ö·Ç³£¼òµ¥µÄHashËã·¨Group = Key
% NÀ´ÊµÏÖÇëÇóµÄ¸ºÔؾùºâ£¬ÈçÏ£º

£¨Èç¹û½«Key×÷Ϊ»º´æµÄKey£¬¶ÔÓ¦µÄGroup´¢´æ¸ÃKeyµÄValue£¬¾Í¿ÉÒÔʵÏÖÒ»¸ö·Ö²¼Ê½µÄ»º´æÏµÍ³£¬ºóÎĵľßÌåÀý×Ó¶¼½«»ùÓÚÕâ¸ö³¡¾°£©
²»ÄÑ·¢ÏÖ£¬ÕâÑùµÄHashÖ»Òª¼¯ÈºµÄÊýÁ¿N·¢Éú±ä»¯£¬Ö®Ç°µÄËùÓÐHashÓ³Éä¾Í»áÈ«²¿Ê§Ð§¡£
Èç¹û¼¯ÈºÖеÄÿ¸ö»úÆ÷ÌṩµÄ·þÎñûÓвî±ð£¬µ¹²»»á²úÉúʲôӰÏ죬µ«¶ÔÓÚ·Ö²¼Ê½»º´æÕâÑùµÄϵͳ¶øÑÔ£¬Ó³ÉäÈ«²¿Ê§Ð§¾ÍÒâζ×Å֮ǰµÄ»º´æÈ«²¿Ê§Ð§£¬ºó¹û½«»áÊÇÔÖÄÑÐԵġ£
Ò»ÖÂÐÔHashͨ¹ý¹¹½¨»·×´µÄHash¿Õ¼ä´úÌæÏßÐÔHash¿Õ¼äµÄ·½·¨½â¾öÁËÕâ¸öÎÊÌ⣬ÈçÏÂͼ£º

Õû¸öHash¿Õ¼ä±»¹¹½¨³ÉÒ»¸öÊ×βÏà½ÓµÄ»·£¬Ê¹ÓÃÒ»ÖÂÐÔHashʱÐèÒª½øÐÐÁ½´ÎÓ³Éä¡£
µÚÒ»´Î£¬¸øÃ¿¸ö½Úµã£¨¼¯Èº£©¼ÆËãHash£¬È»ºó¼Ç¼ËüÃǵÄHashÖµ£¬Õâ¾ÍÊÇËüÃÇÔÚ»·ÉϵÄλÖá£
µÚ¶þ´Î£¬¸øÃ¿¸öKey¼ÆËãHash£¬È»ºóÑØ×Å˳ʱÕëµÄ·½ÏòÕÒµ½»·ÉϵĵÚÒ»¸ö½Úµã£¬¾ÍÊǸÃKey´¢´æ¶ÔÓ¦µÄ¼¯Èº¡£·ÖÎöһϽڵãÔö¼ÓºÍɾ³ýʱ¶Ô¸ºÔؾùºâµÄÓ°Ï죬ÈçÏÂͼ£º

¿ÉÒÔ¿´µ½£¬µ±½Úµã±»É¾³ýʱ£¬ÆäÓà½ÚµãÔÚ»·ÉϵÄÓ³Éä²»»á·¢Éú¸Ä±ä£¬Ö»ÊÇÔÀ´´òÔÚ¶ÔÓ¦½ÚµãÉϵÄKeyÏÖÔÚ»á×ªÒÆµ½Ë³Ê±Õë·½ÏòµÄÏÂÒ»¸ö½ÚµãÉÏÈ¥¡£Ôö¼ÓÒ»¸ö½ÚµãÒ²ÊÇͬÑùµÄ£¬×îÖÕ¶¼Ö»ÓÐÉÙ²¿·ÖµÄKey·¢ÉúÁËʧЧ¡£²»¹ý·¢Éú½Úµã±ä¶¯ºó£¬ÕûÌåϵͳµÄѹÁ¦ÒѾ²»ÊǾùºâµÄÁË£¬ÏÂÎÄÖÐÌáµ½µÄ·½·¨½«»á½â¾öÕâ¸öÎÊÌâ¡£
03¡¢ÎÊÌâÓëÓÅ»¯
×î»ù±¾µÄÒ»ÖÂÐÔHashËã·¨Ö±½ÓÓ¦ÓÃÓÚ¸ºÔؾùºâϵͳ£¬Ð§¹ûÈÔÈ»ÊDz»ÀíÏëµÄ£¬´æÔÚÖî¶àÎÊÌ⣬ÏÂÃæ¾Í¶ÔÕâЩÎÊÌâ½øÐÐÖð¸ö·ÖÎö²¢Ñ°Çó¸üºÃµÄ½â¾ö·½°¸¡£
04¡¢Êý¾ÝÇãб
Èç¹û½ÚµãµÄÊýÁ¿ºÜÉÙ£¬¶øhash»·¿Õ¼äºÜ´ó£¨Ò»°ãÊÇ 0 ~ 2^32£©£¬Ö±½Ó½øÐÐÒ»ÖÂÐÔhashÉÏÈ¥£¬´ó²¿·ÖÇé¿öϽڵãÔÚ»·ÉϵÄλÖûáºÜ²»¾ùÔÈ£¬¼·ÔÚij¸öºÜСµÄÇøÓò¡£×îÖÕ¶Ô·Ö²¼Ê½»º´æÔì³ÉµÄÓ°Ïì¾ÍÊÇ£¬¼¯ÈºµÄÿ¸öʵÀýÉÏ´¢´æµÄ»º´æÊý¾ÝÁ¿²»Ò»Ö£¬»á·¢ÉúÑÏÖØµÄÊý¾ÝÇãб¡£
05¡¢»º´æÑ©±À
Èç¹ûÿ¸ö½ÚµãÔÚ»·ÉÏÖ»ÓÐÒ»¸ö½Úµã£¬ÄÇô¿ÉÒÔÏëÏ󣬵±Ä³Ò»¼¯Èº´Ó»·ÖÐÏûʧʱ£¬ËüÔ±¾Ëù¸ºÔðµÄÈÎÎñ½«È«²¿½»ÓÉ˳ʱÕë·½ÏòµÄÏÂÒ»¸ö¼¯Èº´¦Àí¡£ÀýÈ磬µ±group0Í˳öʱ£¬ËüÔ±¾Ëù¸ºÔðµÄ»º´æ½«È«²¿½»¸øgroup1´¦Àí¡£Õâ¾ÍÒâζ×Ågroup1µÄ·ÃÎÊѹÁ¦»á˲¼äÔö´ó¡£
ÉèÏëһϣ¬Èç¹ûgroup1ÒòΪѹÁ¦¹ý´ó¶ø±ÀÀ££¬ÄÇô¸ü´óµÄѹÁ¦ÓÖ»áÏògroup2ѹ¹ýÈ¥£¬×îÖÕ·þÎñѹÁ¦¾ÍÏñ¹öÑ©ÇòÒ»ÑùÔ½¹öÔ½´ó£¬×îÖÕµ¼ÖÂÑ©±À¡£
06¡¢ÒýÈëÐéÄâ½Úµã
½â¾öÉÏÊöÁ½¸öÎÊÌâ×îºÃµÄ°ì·¨¾ÍÊÇÀ©Õ¹Õû¸ö»·ÉϵĽڵãÊýÁ¿£¬Òò´ËÎÒÃÇÒýÈëÁËÐéÄâ½ÚµãµÄ¸ÅÄî¡£Ò»¸öʵ¼Ê½Úµã½«»áÓ³Éä¶à¸öÐéÄâ½Úµã£¬ÕâÑùHash»·ÉϵĿռä·Ö¸î¾Í»á±äµÃ¾ùÔÈ¡£Í¬Ê±£¬ÒýÈëÐéÄâ½Úµã»¹»áʹµÃ½ÚµãÔÚHash»·ÉϵÄ˳ÐòËæ»ú»¯£¬ÕâÒâζ×ŵ±Ò»¸öÕæÊµ½ÚµãʧЧÍ˳öºó£¬ËüÔÀ´Ëù³ÐÔØµÄѹÁ¦½«»á¾ùÔȵطÖÉ¢µ½ÆäËû½ÚµãÉÏÈ¥¡£ÈçÏÂͼ£º

07¡¢´úÂë²âÊÔ
ÏÖÔÚÎÒÃdz¢ÊÔ±àдһЩ²âÊÔ´úÂ룬À´¿´¿´Ò»ÖÂÐÔhashµÄʵ¼ÊЧ¹ûÊÇ·ñ·ûºÏÎÒÃÇÔ¤ÆÚ¡£Ê×ÏÈÎÒÃÇÐèÒªÒ»¸öÄܹ»¶ÔÊäÈë½øÐоùÔÈÉ¢ÁеÄHashËã·¨£¬¿É¹©Ñ¡ÔñµÄÓкܶ࣬memcached¹Ù·½Ê¹ÓÃÁË»ùÓÚmd5µÄKETAMAËã·¨£¬µ«ÕâÀï´¦ÓÚ¼ÆËãЧÂʵĿ¼ÂÇ£¬Ê¹ÓÃÁËFNV1_32_HASHËã·¨£¬ÈçÏ£º
public class
HashUtil {
/**
* ¼ÆËãHashÖµ, ʹÓÃFNV1_32_HASHËã·¨
* @param str
* @return
*/
public static int getHash(String str) {
final int p = 16777619;
int hash = (int)2166136261L;
for (int i = 0; i < str.length(); i++) {
hash =( hash ^ str.charAt(i) ) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
} |
ʵ¼ÊʹÓÃʱ¿ÉÒÔ¸ù¾ÝÐèÇóµ÷Õû¡£½Ó×ÅÐèҪʹÓÃÒ»ÖÖÊý¾Ý½á¹¹À´±£´æhash»·£¬¿ÉÒÔ²ÉÓõķ½°¸ÓкܶàÖÖ£¬×î¼òµ¥µÄÊDzÉÓÃÊý×é»òÁ´±í¡£µ«ÕâÑù²éÕÒµÄʱºòÐèÒª½øÐÐÅÅÐò£¬Èç¹û½ÚµãÊýÁ¿¶à£¬ËٶȾͿÉÄܱäµÃºÜÂý¡£
Õë¶Ô¼¯Èº¸ºÔؾùºâ״̬¶Á¶àдÉÙµÄ״̬£¬ºÜÈÝÒ×ÁªÏ뵽ʹÓöþ²æÆ½ºâÊ÷µÄ½á¹¹È¥´¢´æ£¬Êµ¼ÊÉÏ¿ÉÒÔʹÓÃTreeMap£¨ÄÚ²¿ÊµÏÖÊǺìºÚÊ÷£©À´×÷ΪHash»·µÄ´¢´æ½á¹¹¡£Ïȱàдһ¸ö×î¼òµ¥µÄ£¬ÎÞÐéÄâ½ÚµãµÄHash»·²âÊÔ£º
public class
ConsistentHashingWithoutVirtualNode {
/**
* ¼¯ÈºµØÖ·Áбí
*/
private static String[] groups = {
"192.168.0.0:111", "192.168.0.1:111",
"192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"
};
/**
* ÓÃÓÚ±£´æHash»·ÉϵĽڵã
*/
private static SortedMap<Integer, String>
sortedMap = new TreeMap<>();
/**
* ³õʼ»¯£¬½«ËùÓеķþÎñÆ÷¼ÓÈëHash»·ÖÐ
*/
static {
// ʹÓúìºÚÊ÷ʵÏÖ£¬²åÈëЧÂʱȽϲµ«ÊDzéÕÒЧÂʼ«¸ß
for (String group : groups) {
int hash = HashUtil.getHash(group);
System.out.println("[" + group +
"] launched @ " + hash);
sortedMap.put(hash, group);
}
}
/**
* ¼ÆËã¶ÔÓ¦µÄwidget¼ÓÔØÔÚÄĸögroupÉÏ
*
* @param widgetKey
* @return
*/
private static String getServer(String widgetKey)
{
int hash = HashUtil.getHash(widgetKey);
// ֻȡ³öËùÓдóÓÚ¸ÃhashÖµµÄ²¿·Ö¶ø²»±Ø±éÀúÕû¸öTree
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if (subMap == null || subMap.isEmpty()) {
// hashÖµÔÚ×îβ²¿£¬Ó¦¸ÃÓ³Éäµ½µÚÒ»¸ögroupÉÏ
return sortedMap.get(sortedMap.firstKey());
}
return subMap.get(subMap.firstKey());
}
public static void main(String[] args) {
// Éú³ÉËæ»úÊý½øÐвâÊÔ
Map<String, Integer> resMap = new HashMap<>();
for (int i = 0; i < 100000; i++) {
Integer widgetId = (int)(Math.random() * 10000);
String server = getServer(widgetId.toString());
if (resMap.containsKey(server)) {
resMap.put(server, resMap.get(server) + 1);
} else {
resMap.put(server, 1);
}
}
resMap.forEach(
(k, v) -> {
System.out.println("group " + k +
": " + v + "(" + v/1000.0D
+"%)");
}
);
}
} |
Éú³É10000¸öËæ»úÊý×Ö½øÐвâÊÔ£¬×îÖյõ½µÄѹÁ¦·Ö²¼Çé¿öÈçÏ£º
[192.168.0.1:111]
launched @ 8518713
[192.168.0.2:111] launched
@ 1361847097
[192.168.0.3:111] launched
@ 1171828661
[192.168.0.4:111] launched
@ 1764547046
group 192.168.0.2:111: 8572(8.572%)
group 192.168.0.1:111: 18693(18.693%)
group 192.168.0.4:111: 17764(17.764%)
group 192.168.0.3:111: 27870(27.87%)
group 192.168.0.0:111: 27101(27.101%)
|
¿ÉÒÔ¿´µ½Ñ¹Á¦»¹ÊDZȽϲ»Æ½¾ùµÄ£¬ËùÒÔÎÒÃǼÌÐø£¬ÒýÈëÐéÄâ½Úµã£º
public class
ConsistentHashingWithVirtualNode {
/**
* ¼¯ÈºµØÖ·Áбí
*/
private static String[] groups = {
"192.168.0.0:111", "192.168.0.1:111",
"192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"
};
/**
* ÕæÊµ¼¯ÈºÁбí
*/
private static List<String> realGroups
= new LinkedList<>();
/**
* ÐéÄâ½ÚµãÓ³Éä¹ØÏµ
*/
private static SortedMap<Integer, String>
virtualNodes = new TreeMap<>();
private static final int VIRTUAL_NODE_NUM =
1000;
static {
// ÏÈÌí¼ÓÕæÊµ½ÚµãÁбí
realGroups.addAll(Arrays.asList(groups));
// ½«ÐéÄâ½ÚµãÓ³Éäµ½Hash»·ÉÏ
for (String realGroup: realGroups) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++)
{
String virtualNodeName = getVirtualNodeName(realGroup,
i);
int hash = HashUtil.getHash(virtualNodeName);
System.out.println("[" + virtualNodeName
+ "] launched @ " + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
}
private static String getVirtualNodeName(String
realName, int num) {
return realName + "&&VN"
+ String.valueOf(num);
}
private static String getRealNodeName(String
virtualName) {
return virtualName.split("&&")[0];
}
private static String getServer(String widgetKey)
{
int hash = HashUtil.getHash(widgetKey);
// ֻȡ³öËùÓдóÓÚ¸ÃhashÖµµÄ²¿·Ö¶ø²»±Ø±éÀúÕû¸öTree
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
String virtualNodeName;
if (subMap == null || subMap.isEmpty()) {
// hashÖµÔÚ×îβ²¿£¬Ó¦¸ÃÓ³Éäµ½µÚÒ»¸ögroupÉÏ
virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
}else {
virtualNodeName = subMap.get(subMap.firstKey());
}
return getRealNodeName(virtualNodeName);
}
public static void main(String[] args) {
// Éú³ÉËæ»úÊý½øÐвâÊÔ
Map<String, Integer> resMap = new HashMap<>();
for (int i = 0; i < 100000; i++) {
Integer widgetId = i;
String group = getServer(widgetId.toString());
if (resMap.containsKey(group)) {
resMap.put(group, resMap.get(group) + 1);
} else {
resMap.put(group, 1);
}
}
resMap.forEach(
(k, v) -> {
System.out.println("group " + k +
": " + v + "(" + v/100000.0D
+"%)");
}
);
}
} |
ÕâÀïÕæÊµ½ÚµãºÍÐéÄâ½ÚµãµÄÓ³Éä²ÉÓÃÁË×Ö·û´®Æ´½ÓµÄ·½Ê½£¬ÕâÖÖ·½Ê½ËäÈ»¼òµ¥µ«ºÜÓÐЧ£¬memcached¹Ù·½Ò²ÊÇÕâôʵÏֵġ£½«ÐéÄâ½ÚµãµÄÊýÁ¿ÉèÖÃΪ1000£¬ÖØÐ²âÊÔѹÁ¦·Ö²¼Çé¿ö£¬½á¹ûÈçÏ£º
group 192.168.0.2:111:
18354(18.354%)
group 192.168.0.1:111: 20062(20.062%)
group 192.168.0.4:111: 20749(20.749%)
group 192.168.0.3:111: 20116(20.116%)
group 192.168.0.0:111: 20719(20.719%) |
¿ÉÒÔ¿´µ½»ù±¾ÒѾ´ïµ½Æ½¾ù·Ö²¼ÁË£¬½Ó׿ÌÐø²âÊÔɾ³ýºÍÔö¼Ó½Úµã¸øÕû¸ö·þÎñ´øÀ´µÄÓ°Ï죬Ïà¹Ø²âÊÔ´úÂëÈçÏ£º
p class="artcon">private
static void refreshHashCircle() { // µ±¼¯Èº±ä¶¯Ê±£¬Ë¢ÐÂhash»·£¬ÆäÓàµÄ¼¯ÈºÔÚhash»·ÉϵÄλÖò»»á·¢Éú±ä¶¯
virtualNodes.clear();
for (String realGroup: realGroups) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++)
{
String virtualNodeName = getVirtualNodeName(realGroup,
i);
int hash = HashUtil.getHash(virtualNodeName);
System.out.println("[" + virtualNodeName
+ "] launched @ " + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
}
private static void addGroup(String identifier)
{
realGroups.add(identifier);
refreshHashCircle();
}
private static void removeGroup(String identifier)
{
int i = 0;
for (String group:realGroups) {
if (group.equals(identifier)) {
realGroups.remove(i);
}
i++;
}
refreshHashCircle();
} |
²âÊÔɾ³ýÒ»¸ö¼¯ÈºÇ°ºóµÄѹÁ¦·Ö²¼ÈçÏ£º
running the normal
test.
group 192.168.0.2:111: 19144(19.144%)
group 192.168.0.1:111: 20244(20.244%)
group 192.168.0.4:111: 20923(20.923%)
group 192.168.0.3:111: 19811(19.811%)
group 192.168.0.0:111: 19878(19.878%)
removed a group, run test again.
group 192.168.0.2:111: 23409(23.409%)
group 192.168.0.1:111: 25628(25.628%)
group 192.168.0.4:111: 25583(25.583%)
group 192.168.0.0:111: 25380(25.38%) |
ͬʱ¼ÆËãÒ»ÏÂÏûʧµÄ¼¯ÈºÉϵÄKey×îÖÕÈçºÎ×ªÒÆµ½ÆäËû¼¯ÈºÉÏ£º
[192.168.0.1:111-192.168.0.4:111]
:5255
[192.168.0.1:111-192.168.0.3:111] :5090
[192.168.0.1:111-192.168.0.2:111] :5069
[192.168.0.1:111-192.168.0.0:111] :4938 |
¿É¼û£¬É¾³ý¼¯Èººó£¬¸Ã¼¯ÈºÉϵÄѹÁ¦¾ùÔȵطÖÉ¢¸øÁËÆäËû¼¯Èº£¬×îÖÕÕû¸ö¼¯ÈºÈÔ´¦ÓÚ¸ºÔؾùºâ״̬£¬·ûºÏÎÒÃǵÄÔ¤ÆÚ£¬×îºó¿´Ò»ÏÂÌí¼Ó¼¯ÈºµÄÇé¿ö¡£Ñ¹Á¦·Ö²¼£º
running the
normal test.
group 192.168.0.2:111: 18890(18.89%)
group 192.168.0.1:111: 20293(20.293%)
group 192.168.0.4:111: 21000(21.0%)
group 192.168.0.3:111: 19816(19.816%)
group 192.168.0.0:111: 20001(20.001%)
add a group, run test again.
group 192.168.0.2:111: 15524(15.524%)
group 192.168.0.7:111: 16928(16.928%)
group 192.168.0.1:111: 16888(16.888%)
group 192.168.0.4:111: 16965(16.965%)
group 192.168.0.3:111: 16768(16.768%)
group 192.168.0.0:111: 16927(16.927%) |
ѹÁ¦×ªÒÆ£º
[192.168.0.0:111-192.168.0.7:111]
:3102
[192.168.0.4:111-192.168.0.7:111] :4060
[192.168.0.2:111-192.168.0.7:111] :3313
[192.168.0.1:111-192.168.0.7:111] :3292
[192.168.0.3:111-192.168.0.7:111] :3261 |
×ÛÉÏ¿ÉÒԵóö½áÂÛ£¬ÔÚÒýÈë×ã¹»¶àµÄÐéÄâ½Úµãºó£¬Ò»ÖÂÐÔhash»¹ÊÇÄܹ»±È½ÏÍêÃÀµØÂú×ã¸ºÔØ¾ùºâÐèÒªµÄ¡£
08¡¢ÓÅÑÅËõÀ©ÈÝ
»º´æ·þÎñÆ÷¶ÔÓÚÐÔÄÜÓÐ׎ϸߵÄÒªÇó£¬Òò´ËÎÒÃÇÏ£ÍûÔÚÀ©ÈÝʱеļ¯ÈºÄܹ»½Ï¿ìµÄÌî³äºÃÊý¾Ý²¢¹¤×÷¡£µ«ÊÇ´ÓÒ»¸ö¼¯ÈºÆô¶¯£¬µ½ÕæÕý¼ÓÈë²¢¿ÉÒÔÌṩ·þÎñÖ®¼ä»¹´æÔÚ×Ų»Ð¡µÄʱ¼äÑÓ³Ù£¬ÒªÊµÏÖ¸üÓÅÑŵÄÀ©ÈÝ£¬ÎÒÃÇ¿ÉÒÔ´ÓÁ½¸ö·½Ãæ³ö·¢£º
1.¸ßƵKeyÔ¤ÈÈ
¸ºÔؾùºâÆ÷×÷Ϊ·Óɲ㣬ÊÇ¿ÉÒÔÊÕ¼¯²¢Í³¼ÆÃ¿¸ö»º´æKeyµÄ·ÃÎÊÆµÂʵģ¬Èç¹ûÄܹ»Î¬»¤Ò»·Ý¸ßƵ·ÃÎÊKeyµÄÁÐ±í£¬Ðµļ¯ÈºÔÚÆô¶¯Ê±¸ù¾ÝÕâ¸öÁбíÌáǰÀÈ¡¶ÔÓ¦KeyµÄ»º´æÖµ½øÐÐÔ¤ÈÈ£¬±ã¿ÉÒÔ´ó´ó¼õÉÙÒòΪÐÂÔö¼¯Èº¶øµ¼ÖµÄKeyʧЧ¡£
¾ßÌåµÄÉè¼Æ¿ÉÒÔͨ¹ý»º´æÀ´ÊµÏÖ£¬ÈçÏ£º

²»¹ýÕâ¸ö·½°¸ÔÚʵ¼ÊʹÓÃʱÓÐÒ»¸öºÜ´óµÄÏÞÖÆ£¬ÄǾÍÊÇ¸ßÆµKey±¾ÉíµÄ»º´æÊ§Ð§Ê±¼ä¿ÉẠ̈ܺܶ¬Ô¤ÈÈʱ´¢´æµÄValueÔÚʵ¼Ê±»·ÃÎʵ½Ê±¿ÉÄÜÒѾ±»¸üлòÕßʧЧ£¬´¦Àí²»µ±»áµ¼Ö³öÏÖÔàÊý¾Ý£¬Òò´ËʵÏÖÄѶȻ¹ÊÇÓÐһЩ´óµÄ¡£
2.ÀúÊ·Hash»·±£Áô
»Ø¹ËÒ»ÖÂÐÔHashµÄÀ©ÈÝ£¬²»ÄÑ·¢ÏÖÐÂÔö½Úµãºó£¬ËüËù¶ÔÓ¦µÄKeyÔÚÔÀ´µÄ½Úµã»¹»á±£ÁôÒ»¶Îʱ¼ä¡£Òò´ËÔÚÀ©ÈݵÄÑÓ³Ùʱ¼ä¶Î£¬Èç¹û¶ÔÓ¦µÄKey»º´æÔÚнڵãÉÏ»¹Ã»Óб»¼ÓÔØ£¬¿ÉÒÔÈ¥ÔÓеĽڵãÉϳ¢ÊÔ¶ÁÈ¡¡£
¾ÙÀý£¬¼ÙÉèÎÒÃÇÔÓÐ3¸ö¼¯Èº£¬ÏÖÔÚÒªÀ©Õ¹µ½6¸ö¼¯Èº£¬Õâ¾ÍÒâζ×ÅÔÓÐ50%µÄKey¶¼»áʧЧ£¨±»×ªÒƵ½Ð½ڵãÉÏ£©£¬Èç¹ûÎÒÃÇά»¤À©ÈÝǰºÍÀ©ÈݺóµÄÁ½¸öHash»·£¬ÔÚÀ©ÈݺóµÄHash»·ÉÏÕÒ²»µ½KeyµÄ´¢´æÊ±£¬ÏÈתÏòÀ©ÈÝǰµÄHash»·Ñ°ÕÒÒ»²¨£¬Èç¹ûÄܹ»ÕÒµ½¾Í·µ»Ø¶ÔÓ¦µÄÖµ²¢½«¸Ã»º´æÐ´ÈëеĽڵãÉÏ£¬ÕÒ²»µ½Ê±ÔÙ͸¹ý»º´æ£¬ÈçÏÂͼ£º

ÕâÑù×öµÄȱµãÊÇÔö¼ÓÁË»º´æ¶ÁÈ¡µÄʱ¼ä£¬µ«Ïà±ÈÓÚÖ±½Ó»÷´©»º´æ¶øÑÔ»¹ÊÇÒªºÃºÜ¶àµÄ¡£ÓŵãÔòÊÇ¿ÉÒÔËæÒâÀ©Èݶą̀»úÆ÷£¬¶ø²»»á²úÉú´óÃæ»ýµÄ»º´æÊ§Ð§¡£Ì¸ÍêÁËÀ©ÈÝ£¬ÔÙ̸̸ËõÈÝ¡£
1.ÈÛ¶Ï»úÖÆ
ËõÈݺó£¬Ê£Óà¸÷¸ö½ÚµãÉϵķÃÎÊѹÁ¦¶¼»áÓÐËùÔö¼Ó£¬´ËʱÈç¹ûij¸ö½ÚµãÒòΪѹÁ¦¹ý´ó¶øå´»ú£¬¾Í¿ÉÄÜ»áÒý·¢Á¬Ëø·´Ó¦¡£Òò´Ë×÷Ϊ¶µµ×·½°¸£¬Ó¦µ±¸øÃ¿¸ö¼¯ÈºÉèÁ¢¶ÔÓ¦ÈÛ¶Ï»úÖÆÀ´±£»¤·þÎñµÄÎȶ¨ÐÔ¡£
2.¶à¼¯ÈºLBµÄ¸üÐÂÑÓ³Ù
Õâ¸öÎÊÌâÔÚËõÈÝʱ±È½ÏÑÏÖØ£¬Èç¹ûÄãʹÓÃÒ»¸ö¼¯ÈºÀ´×÷Ϊ¸ºÔؾùºâ£¬²¢Ê¹ÓÃÒ»¸öÅäÖ÷þÎñÆ÷±ÈÈçConfigServerÀ´ÍÆËͼ¯Èº×´Ì¬ÒÔ¹¹½¨Hash»·£¬ÄÇôÔÚij¸ö¼¯ÈºÍ˳öʱÕâ¸ö״̬²¢²»Ò»¶¨»á±»Á¢¿Ìͬ²½µ½ËùÓеÄLBÉÏ£¬Õâ¾Í¿ÉÄܻᵼÖÂÒ»¸öÔÝʱµÄµ÷¶È²»Ò»Ö£¬ÈçÏÂͼ£º

Èç¹ûij̨LB´íÎ󵨽«ÇëÇó´òµ½ÁËÒѾÍ˳öµÄ¼¯ÈºÉÏ£¬¾Í»áµ¼Ö»º´æ»÷´©¡£½â¾öÕâ¸öÎÊÌâÖ÷ÒªÓÐÒÔϼ¸ÖÖ˼·£º
»ºÂýËõÈÝ£¬µÈµ½Hash»·Íêȫͬ²½ºóÔÙ²Ù×÷¡£¿ÉÒÔͨ¹ý¼àÌýÍ˳ö¼¯ÈºµÄ·ÃÎÊQPSÀ´ÊµÏÖÕâÒ»µã£¬µÈµ½¸Ã¼¯Èº¼¸ºõûÓÐQPSʱÔÙ½«Æä³·Ï¡£
ÊÖ¶¯É¾³ý£¬Èç¹ûHash»·É϶ÔÓ¦µÄ½ÚµãÕÒ²»µ½ÁË£¬¾ÍÊÖ¶¯½«Æä´ÓHash»·ÉÏɾ³ý£¬È»ºóÖØÐ½øÐе÷¶È£¬Õâ¸ö·½Ê½ÓÐÒ»¶¨µÄ·çÏÕ£¬¶ÔÓÚÍøÂç¶¶¶¯µÈÒì³£Çé¿ö¼æÈݵIJ»ÊǺܺá£
Ö÷¶¯ÀÈ¡ºÍÖØÊÔ£¬µ±Hash»·ÉϽڵãʧЧʱ£¬Ö÷¶¯´ÓZKÉÏÖØÐÂÀÈ¡¼¯Èº×´Ì¬À´¹¹½¨ÐÂHash»·£¬ÔÚÒ»¶¨´ÎÊýÄÚ¿ÉÒÔ½øÐжà´ÎÖØÊÔ¡£
09¡¢¶Ô±È£ºHashSlot
Á˽âÁËÒ»ÖÂÐÔHashËã·¨µÄÌØµãºó£¬ÎÒÃÇÒ²²»ÄÑ·¢ÏÖһЩ²»¾¡ÈËÒâµÄµØ·½£º
Õû¸ö·Ö²¼Ê½»º´æÐèÒªÒ»¸ö·ÓÉ·þÎñÀ´×ö¸ºÔؾùºâ£¬´æÔÚµ¥µãÎÊÌ⣨Èç¹û·ÓÉ·þÎñ¹ÒÁË£¬Õû¸ö»º´æÒ²¾ÍÁ¹ÁË£©
Hash»·ÉϵĽڵã·Ç³£¶à»òÕ߸üÐÂÆµ·±Ê±£¬²éÕÒÐÔÄÜ»á±È½ÏµÍÏÂ
Õë¶ÔÕâЩÎÊÌ⣬RedisÔÚʵÏÖ×Ô¼ºµÄ·Ö²¼Ê½¼¯Èº·½°¸Ê±£¬Éè¼ÆÁËȫеÄ˼·£º»ùÓÚP2P½á¹¹µÄHashSlotËã·¨£¬ÏÂÃæ¼òµ¥½éÉÜһϣº
1.ʹÓÃHashSlot
ÀàËÆÓÚHash»·£¬Redis Cluster²ÉÓÃHashSlotÀ´ÊµÏÖKeyÖµµÄ¾ùÔÈ·Ö²¼ºÍʵÀýµÄÔöɾ¹ÜÀí¡£
Ê×ÏÈĬÈÏ·ÖÅäÁË16384¸öSlot£¨Õâ¸ö´óСÕýºÃ¿ÉÒÔʹÓÃ2kbµÄ¿Õ¼ä±£´æ£©£¬Ã¿¸öSlotÏ൱ÓÚÒ»ÖÂÐÔHash»·ÉϵÄÒ»¸ö½Úµã¡£½ÓÈ뼯ȺµÄËùÓÐʵÀý½«¾ùÔȵØÕ¼ÓÐÕâЩSlot£¬¶ø×îÖÕµ±ÎÒÃÇSetÒ»¸öKeyʱ£¬Ê¹ÓÃCRC16(Key)
% 16384À´¼ÆËã³öÕâ¸öKeyÊôÓÚÄĸöSlot£¬²¢×îÖÕÓ³Éäµ½¶ÔÓ¦µÄʵÀýÉÏÈ¥¡£
ÄÇôµ±ÔöɾʵÀýʱ£¬SlotºÍʵÀý¼äµÄ¶ÔÓ¦ÒªÈçºÎ½øÐжÔÓ¦µÄ¸Ä¶¯ÄØ£¿
¾Ù¸öÀý×Ó£¬Ô±¾ÓÐ3¸ö½ÚµãA,B,C£¬ÄÇôһ¿ªÊ¼´´½¨¼¯ÈºÊ±SlotµÄ¸²¸ÇÇé¿öÊÇ£º
½ÚµãA 0£5460
½ÚµãB 5461£10922
½ÚµãC 10923£16383 |
ÏÖÔÚ¼ÙÉèÒªÔö¼ÓÒ»¸ö½ÚµãD£¬RedisClusterµÄ×ö·¨Êǽ«Ö®Ç°Ã¿Ì¨»úÆ÷ÉϵÄÒ»²¿·ÖSlotÒÆ¶¯µ½DÉÏ£¨×¢ÒâÕâ¸ö¹ý³ÌÒ²Òâζ×ÅÒª¶Ô½ÚµãDдÈëµÄKV´¢´æ£©£¬³É¹¦½ÓÈëºóSlotµÄ¸²¸ÇÇé¿ö½«±äΪÈçÏÂÇé¿ö£º
½ÚµãA 1365-5460
½ÚµãB 6827-10922
½ÚµãC 12288-16383
½ÚµãD 0-1364,5461-6826,10923-1228 |
ͬÀíɾ³ýÒ»¸ö½Úµã£¬¾ÍÊǽ«ÆäÔÀ´Õ¼ÓеÄSlotÒÔ¼°¶ÔÓ¦µÄKV´¢´æ¾ùÔȵع黹¸øÆäËû½Úµã¡£
2.P2P½ÚµãѰÕÒ
ÏÖÔÚÎÒÃÇ¿¼ÂÇÈçºÎʵÏÖÈ¥ÖÐÐÄ»¯µÄ·ÃÎÊ£¬Ò²¾ÍÊÇ˵ÎÞÂÛ·ÃÎʼ¯ÈºÖеÄÄĸö½Úµã£¬Äã¶¼Äܹ»Äõ½ÏëÒªµÄÊý¾Ý¡£ÆäʵÕâÓеãÀàËÆÓÚ·ÓÉÆ÷µÄ·ÓÉ±í£¬¾ßÌå˵À´¾ÍÊÇ£º
ÿ¸ö½Úµã¶¼±£´æÓÐÍêÕûµÄHashSlot - ½ÚµãÓ³Éä±í£¬Ò²¾ÍÊÇ˵£¬Ã¿¸ö½Úµã¶¼ÖªµÀ×Ô¼ºÓµÓÐÄÄЩSlot£¬ÒÔ¼°Ä³¸öÈ·¶¨µÄSlot¾¿¾¹¶ÔÓ¦×ÅÄĸö½Úµã¡£
ÎÞÂÛÏòÄĸö½Úµã·¢³öѰÕÒKeyµÄÇëÇ󣬸ýڵ㶼»áͨ¹ýCRC(Key) % 16384¼ÆËã¸ÃKey¾¿¾¹´æÔÚÓÚÄĸöSlot£¬²¢½«ÇëÇóת·¢ÖÁ¸ÃSlotËùÔڵĽڵ㡣
×ܽáһϾÍÊÇÁ½¸öÒªµã£ºÓ³Éä±íºÍÄÚ²¿×ª·¢£¬ÕâÊÇͨ¹ýÖøÃûµÄGossipÐÒé À´ÊµÏֵġ£
×îºóÎÒÃÇ¿ÉÒÔ¸ø³öRedis ClusterµÄϵͳ½á¹¹Í¼£¬ºÍÒ»ÖÂÐÔHash»·»¹ÊÇÓÐןÜÃ÷ÏÔµÄÇø±ðµÄ£º

¶Ô±Èһϣ¬HashSlot + P2PµÄ·½°¸½â¾öÁËÈ¥ÖÐÐÄ»¯µÄÎÊÌ⣬ͬʱҲÌṩÁ˸üºÃµÄ¶¯Ì¬À©Õ¹ÐÔ¡£µ«Ïà±ÈÓÚÒ»ÖÂÐÔHash¶øÑÔ£¬Æä½á¹¹¸ü¼Ó¸´ÔÓ£¬ÊµÏÖÉÏÒ²¸ü¼ÓÀ§ÄÑ¡£
¶øÔÚ֮ǰµÄ·ÖÎöÖÐÎÒÃÇÒ²ÄÜ¿´³ö£¬Ò»ÖÂÐÔHash·½°¸ÕûÌåÉÏ»¹ÊÇÓÐ×Ų»´íµÄ±íÏֵģ¬Òò´ËÔÚʵ¼ÊµÄϵͳӦÓÃÖУ¬¿ÉÒÔ¸ù¾Ý¿ª·¢³É±¾ºÍÐÔÄÜÒªÇóºÏÀíµØÑ¡Ôñ×îÊʺϵķ½°¸¡£×ÜÖ®£¬Á½Õß¶¼·Ç³£ÓÅÐ㣬ÖÁÓÚÓÃÄĸö¡¢ÔõôÓ㬾ÍÊÇÈÊÕß¼ûÈÊÖÇÕß¼ûÖǵÄÎÊÌâÁË¡£ |