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
基于因果森林算法的决策定位应用基于因果森林算法的决策定位应用Apr 08, 2023 am 11:21 AM

译者 | 朱先忠​审校 | 孙淑娟​在我之前的​​博客​​中,我们已经了解了如何使用因果树来评估政策的异质处理效应。如果你还没有阅读过,我建议你在阅读本文前先读一遍,因为我们在本文中认为你已经了解了此文中的部分与本文相关的内容。为什么是异质处理效应(HTE:heterogenous treatment effects)呢?首先,对异质处理效应的估计允许我们根据它们的预期结果(疾病、公司收入、客户满意度等)选择提供处理(药物、广告、产品等)的用户(患者、用户、客户等)。换句话说,估计HTE有助于我

Mango:基于Python环境的贝叶斯优化新方法Mango:基于Python环境的贝叶斯优化新方法Apr 08, 2023 pm 12:44 PM

译者 | 朱先忠审校 | 孙淑娟引言模型超参数(或模型设置)的优化可能是训练机器学习算法中最重要的一步,因为它可以找到最小化模型损失函数的最佳参数。这一步对于构建不易过拟合的泛化模型也是必不可少的。优化模型超参数的最著名技术是穷举网格搜索和随机网格搜索。在第一种方法中,搜索空间被定义为跨越每个模型超参数的域的网格。通过在网格的每个点上训练模型来获得最优超参数。尽管网格搜索非常容易实现,但它在计算上变得昂贵,尤其是当要优化的变量数量很大时。另一方面,随机网格搜索是一种更快的优化方法,可以提供更好的

php如何实现Redis的Hash操作php如何实现Redis的Hash操作May 30, 2023 am 08:58 AM

Hash操作//为hash表中的字段赋值。成功返回1,失败返回0。若hash表不存在会先创建表再赋值,若字段已存在会覆盖旧值。$ret=$redis->hSet(&#39;user&#39;,&#39;realname&#39;,&#39;jetwu&#39;);//获取hash表中指定字段的值。若hash表不存在则返回false。$ret=$redis->hGet(&#39;user&#39;,&#39;rea

Laravel开发:如何使用Laravel Hash生成密码散列?Laravel开发:如何使用Laravel Hash生成密码散列?Jun 17, 2023 am 10:59 AM

Laravel是目前最为流行的PHPweb框架之一,为开发人员提供了许多强大的功能和组件,其中LaravelHash也是其中之一。LaravelHash是一个用于密码散列的PHP库,其可以用于保护密码的安全,并使应用程序的用户数据更加安全。在本文中,我们将了解LaravelHash的工作原理以及如何使用它来对密码进行散列和验证。前置知识在学习Lara

使用Pytorch实现对比学习SimCLR 进行自监督预训练使用Pytorch实现对比学习SimCLR 进行自监督预训练Apr 10, 2023 pm 02:11 PM

SimCLR(Simple Framework for Contrastive Learning of Representations)是一种学习图像表示的自监督技术。 与传统的监督学习方法不同,SimCLR 不依赖标记数据来学习有用的表示。 它利用对比学习框架来学习一组有用的特征,这些特征可以从未标记的图像中捕获高级语义信息。SimCLR 已被证明在各种图像分类基准上优于最先进的无监督学习方法。 并且它学习到的表示可以很容易地转移到下游任务,例如对象检测、语义分割和小样本学习,只需在较小的标记

​盒马供应链算法实战​盒马供应链算法实战Apr 10, 2023 pm 09:11 PM

一、盒马供应链介绍1、盒马商业模式盒马是一个技术创新的公司,更是一个消费驱动的公司,回归消费者价值:买的到、买的好、买的方便、买的放心、买的开心。盒马包含盒马鲜生、X 会员店、盒马超云、盒马邻里等多种业务模式,其中最核心的商业模式是线上线下一体化,最快 30 分钟到家的 O2O(即盒马鲜生)模式。2、盒马经营品类介绍盒马精选全球品质商品,追求极致新鲜;结合品类特点和消费者购物体验预期,为不同品类选择最为高效的经营模式。盒马生鲜的销售占比达 60%~70%,是最核心的品类,该品类的特点是用户预期时

研究表明强化学习模型容易受到成员推理攻击研究表明强化学习模型容易受到成员推理攻击Apr 09, 2023 pm 08:01 PM

​译者 | 李睿 审校 | 孙淑娟​随着机器学习成为人们每天都在使用的很多应用程序的一部分,人们越来越关注如何识别和解决机器学习模型的安全和隐私方面的威胁。 然而,不同机器学习范式面临的安全威胁各不相同,机器学习安全的某些领域仍未得到充分研究。尤其是强化学习算法的安全性近年来并未受到太多关注。 加拿大的麦吉尔大学、机器学习实验室(MILA)和滑铁卢大学的研究人员开展了一项新研究,主要侧重于深度强化学习算法的隐私威胁。研究人员提出了一个框架,用于测试强化学习模型对成员推理攻击的脆弱性。 研究

数据科学家必须了解的六大聚类算法数据科学家必须了解的六大聚类算法Apr 08, 2023 pm 11:31 PM

目前如谷歌新闻等很多应用都将聚类算法作为主要的实现手段,它们能利用大量的未标注数据构建强大的主题聚类。本文从最基础的 K 均值聚类到基于密度的强大方法介绍了 6 类主流方法,它们各有擅长领域与情景,且基本思想并不一定限于聚类方法。本文将从简单高效的 K 均值聚类开始,依次介绍均值漂移聚类、基于密度的聚类、利用高斯混合和最大期望方法聚类、层次聚类和适用于结构化数据的图团体检测。我们不仅会分析基本的实现概念,同时还会给出每种算法的优缺点以明确实际的应用场景。聚类是一种包括数据点分组的机器学习技术。给

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

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
1 months agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),