search
HomeDatabaseMysql Tutoriallibmemcached一致性hash算法详解(2)

libmemcached一致性hash算法详解(2)

Jun 07, 2016 pm 03:26 PM
hashconsistencyalgorithmDetailed explanation

author: selfimpr blog: http://blog.csdn.net/lgg201 mail: lgg860911@yahoo.com.cn libmemcached一致性hash算法详解(1)----php-memcached客户端一致性哈希与crc算法共用产生的bug分析 这里就不废话了, 直接上代码: #include stdio.h#include stdlib.h#incl

author: selfimpr

blog: http://blog.csdn.net/lgg201

mail: lgg860911@yahoo.com.cn



libmemcached一致性hash算法详解(1)----php-memcached客户端一致性哈希与crc算法共用产生的bug分析


这里就不废话了, 直接上代码:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

/*---------------------------以下部分摘自libmemcached/crc.c--------------------------*/
static const uint32_t crc32tab[256] = {
  0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
  0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
  0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
  0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
  0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
  0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
  0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
  0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
  0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
  0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
  0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
  0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
  0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
  0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
  0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
  0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
  0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
  0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
  0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
  0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
  0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
  0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
  0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
  0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
  0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
  0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
  0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
  0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
  0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
  0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
  0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
  0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
  0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
  0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
  0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
  0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
  0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
  0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
  0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
  0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
  0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
  0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
  0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
  0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
  0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
  0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
  0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
  0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
  0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
  0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
  0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
  0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
  0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
  0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
  0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
  0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
  0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
  0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
  0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
  0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
  0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
};

uint32_t hash_crc32(const char *key, size_t key_length)
{
  uint32_t x;
  uint32_t crc= UINT32_MAX;

  for (x= 0; x > 8) ^ crc32tab[(crc ^ (key[x])) & 0xff];

  return ~crc;
}
/*---------------------------以上部分摘自libmemcached/crc.c--------------------------*/

//libmemcached中使用crc求hash值的方法
uint32_t memcached_hash_crc32(const char *key, size_t key_len) {
	return ((hash_crc32(key, key_len) >> 16) & 0x7fff);
}

/**
 * 模拟libmemcached的一致性hash算法中的点  
 * libmemcached中, 假设有A,B两台服务器, 则其一致性算法为:
 * 	1. 假设每台服务器100个点
 * 	2. 每个点是一个类似下面的server_t的结构, 一个字段存放server的索引, 一个字段存放值
 * 	3. 每个服务器构造自己对应的100个点时, 对host:port-i求hash值, 其中host为服务器地址, port为端口, i为0-99的数
 * 	4. 将两个服务器总共产生的200个点放入一个数组, 按照点的value(即上面求得的hash值)排序
 * 下面是拿到一个key进行分布时的策略
 * 	1. 对key求一个hash值
 * 	2. 从上面得到的服务器的200个点的数组中, 二分查找离这个key产生的hash值最近的点
 * 	3. 拿到这个点对应的服务器
 */
typedef struct _server {
	char host[128];
	uint32_t value;
} server_t;

//libmemcached中点的比较函数
int server_cmp(const void *s1, const void *s2) {
	server_t *cs1 = (server_t *)s1;
	server_t *cs2 = (server_t *)s2;
	if ( cs1->value == cs2->value ) return 0;
	else if ( cs1->value > cs2->value ) return 1;
	else return -1;
}

//打印从servers开始的n个点
void print_servers(const server_t *servers, int n) {
	int i = 0;
	while ( i host, (servers + i)->value);
		i ++;
	}
}
//构造示例性的2台服务器产生的点, libmemcached中的算法简化了就是如此
server_t *construct_servers() {
	server_t *servers = malloc(sizeof(server_t) * 200);
	int i = 0, j;
	int server_length = 0;
	char server[128];
	while ( i host, server);
			(servers + i * 100 + j)->value = memcached_hash_crc32(server, server_length);
		}
		i ++;
	}
	qsort(servers, 200, sizeof(server_t), server_cmp);
	//print_servers(servers, 200);
	return servers;
}
//给定一个key, 查找对应的服务器, libmemcached的查找算法简化板
void search(server_t *servers, int num, char *key, int key_len) {
	server_t *begin, *left, *middle, *right, *end;	
	begin = left = servers;
	end = right = servers + num;
	uint32_t hash;
	hash = memcached_hash_crc32(key, key_len);

	while (left value host);
}

//下面是模拟的一个分布测试程序
void main(void) {
	server_t *servers;
	uint32_t hash;
	char key[128];
	int i = 0, key_len;

	servers = construct_servers();

	while ( i <br>
<br>


</string.h></stdint.h></stdlib.h></stdio.h>
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
What are the differences in syntax between MySQL and other SQL dialects?What are the differences in syntax between MySQL and other SQL dialects?Apr 27, 2025 am 12:26 AM

MySQLdiffersfromotherSQLdialectsinsyntaxforLIMIT,auto-increment,stringcomparison,subqueries,andperformanceanalysis.1)MySQLusesLIMIT,whileSQLServerusesTOPandOracleusesROWNUM.2)MySQL'sAUTO_INCREMENTcontrastswithPostgreSQL'sSERIALandOracle'ssequenceandt

What is MySQL partitioning?What is MySQL partitioning?Apr 27, 2025 am 12:23 AM

MySQL partitioning improves performance and simplifies maintenance. 1) Divide large tables into small pieces by specific criteria (such as date ranges), 2) physically divide data into independent files, 3) MySQL can focus on related partitions when querying, 4) Query optimizer can skip unrelated partitions, 5) Choosing the right partition strategy and maintaining it regularly is key.

How do you grant and revoke privileges in MySQL?How do you grant and revoke privileges in MySQL?Apr 27, 2025 am 12:21 AM

How to grant and revoke permissions in MySQL? 1. Use the GRANT statement to grant permissions, such as GRANTALLPRIVILEGESONdatabase_name.TO'username'@'host'; 2. Use the REVOKE statement to revoke permissions, such as REVOKEALLPRIVILEGESONdatabase_name.FROM'username'@'host' to ensure timely communication of permission changes.

Explain the differences between InnoDB and MyISAM storage engines.Explain the differences between InnoDB and MyISAM storage engines.Apr 27, 2025 am 12:20 AM

InnoDB is suitable for applications that require transaction support and high concurrency, while MyISAM is suitable for applications that require more reads and less writes. 1.InnoDB supports transaction and bank-level locks, suitable for e-commerce and banking systems. 2.MyISAM provides fast read and indexing, suitable for blogging and content management systems.

What are the different types of JOINs in MySQL?What are the different types of JOINs in MySQL?Apr 27, 2025 am 12:13 AM

There are four main JOIN types in MySQL: INNERJOIN, LEFTJOIN, RIGHTJOIN and FULLOUTERJOIN. 1.INNERJOIN returns all rows in the two tables that meet the JOIN conditions. 2.LEFTJOIN returns all rows in the left table, even if there are no matching rows in the right table. 3. RIGHTJOIN is contrary to LEFTJOIN and returns all rows in the right table. 4.FULLOUTERJOIN returns all rows in the two tables that meet or do not meet JOIN conditions.

What are the different storage engines available in MySQL?What are the different storage engines available in MySQL?Apr 26, 2025 am 12:27 AM

MySQLoffersvariousstorageengines,eachsuitedfordifferentusecases:1)InnoDBisidealforapplicationsneedingACIDcomplianceandhighconcurrency,supportingtransactionsandforeignkeys.2)MyISAMisbestforread-heavyworkloads,lackingtransactionsupport.3)Memoryengineis

What are some common security vulnerabilities in MySQL?What are some common security vulnerabilities in MySQL?Apr 26, 2025 am 12:27 AM

Common security vulnerabilities in MySQL include SQL injection, weak passwords, improper permission configuration, and unupdated software. 1. SQL injection can be prevented by using preprocessing statements. 2. Weak passwords can be avoided by forcibly using strong password strategies. 3. Improper permission configuration can be resolved through regular review and adjustment of user permissions. 4. Unupdated software can be patched by regularly checking and updating the MySQL version.

How can you identify slow queries in MySQL?How can you identify slow queries in MySQL?Apr 26, 2025 am 12:15 AM

Identifying slow queries in MySQL can be achieved by enabling slow query logs and setting thresholds. 1. Enable slow query logs and set thresholds. 2. View and analyze slow query log files, and use tools such as mysqldumpslow or pt-query-digest for in-depth analysis. 3. Optimizing slow queries can be achieved through index optimization, query rewriting and avoiding the use of SELECT*.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools