php数据流计算hash php流量统计

php的memcached分布式hash算法,如何解决分布不均?crc32这个算法没办法把key值均匀的分布出去

memcached的总结和分布式一致性hash

当前很多大型的web系统为了减轻数据库服务器负载，会采用memchached作为缓存系统以提高响应速度。

目录： （）

memchached简介

hash

取模

一致性hash

虚拟节点

源码解析

参考资料

1. memchached简介

memcached是一个开源的高性能分布式内存对象缓存系统。

其实思想还是比较简单的，实现包括server端（memcached开源项目一般只单指server端）和client端两部分:

server端本质是一个in-memory key-value store，通过在内存中维护一个大的hashmap用来存储小块的任意数据，对外通过统一的简单接口（memcached protocol）来提供操作。

client端是一个library，负责处理memcached protocol的网络通信细节，与memcached server通信，针对各种语言的不同实现分装了易用的API实现了与不同语言平台的集成。

web系统则通过client库来使用memcached进行对象缓存。

2. hash

memcached的分布式主要体现在client端，对于server端，仅仅是部署多个memcached server组成集群，每个server独自维护自己的数据（互相之间没有任何通信），通过daemon监听端口等待client端的请求。

而在client端，通过一致的hash算法，将要存储的数据分布到某个特定的server上进行存储，后续读取查询使用同样的hash算法即可定位。

client端可以采用各种hash算法来定位server：

取模

最简单的hash算法

targetServer = serverList[hash(key) % serverList.size]

直接用key的hash值（计算key的hash值的方法可以自由选择，比如算法CRC32、MD5,甚至本地hash系统，如java的hashcode）模上server总数来定位目标server。这种算法不仅简单，而且具有不错的随机分布特性。

但是问题也很明显，server总数不能轻易变化。因为如果增加/减少memcached server的数量，对原先存储的所有key的后续查询都将定位到别的server上，导致所有的cache都不能被命中而失效。

一致性hash

为了解决这个问题，需要采用一致性hash算法（consistent hash）

相对于取模的算法，一致性hash算法除了计算key的hash值外，还会计算每个server对应的hash值，然后将这些hash值映射到一个有限的值域上（比如0~2^32）。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到，则直接把具有最小hash值的server作为目标server。

为了方便理解，可以把这个有限值域理解成一个环，值顺时针递增。

如上图所示，集群中一共有5个memcached server，已通过server的hash值分布到环中。

如果现在有一个写入cache的请求，首先计算x=hash(key)，映射到环中，然后从x顺时针查找，把找到的第一个server作为目标server来存储cache，如果超过了2^32仍然找不到，则命中第一个server。比如x的值介于A~B之间，那么命中的server节点应该是B节点

可以看到，通过这种算法，对于同一个key，存储和后续的查询都会定位到同一个memcached server上。

那么它是怎么解决增/删server导致的cache不能命中的问题呢？

假设，现在增加一个server F，如下图

此时，cache不能命中的问题仍然存在，但是只存在于B~F之间的位置（由C变成了F），其他位置（包括F~C）的cache的命中不受影响（删除server的情况类似）。尽管仍然有cache不能命中的存在，但是相对于取模的方式已经大幅减少了不能命中的cache数量。

虚拟节点

但是，这种算法相对于取模方式也有一个缺陷：当server数量很少时，很可能他们在环中的分布不是特别均匀，进而导致cache不能均匀分布到所有的server上。

如图，一共有3台server – 1，2，4。命中4的几率远远高于1和2。

为解决这个问题，需要使用虚拟节点的思想：为每个物理节点（server）在环上分配100～200个点，这样环上的节点较多，就能抑制分布不均匀。

当为cache定位目标server时，如果定位到虚拟节点上，就表示cache真正的存储位置是在该虚拟节点代表的实际物理server上。

另外，如果每个实际server的负载能力不同，可以赋予不同的权重，根据权重分配不同数量的虚拟节点。

// 采用有序map来模拟环

this.consistentBuckets = new TreeMap();

MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值

// 计算总权重

if ( this.totalWeight for ( int i = 0; i this.weights.length; i++ )

this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];

} else if ( this.weights == null ) {

this.totalWeight = this.servers.length;

}

// 为每个server分配虚拟节点

for ( int i = 0; i servers.length; i++ ) {

// 计算当前server的权重

int thisWeight = 1;

if ( this.weights != null this.weights[i] != null )

thisWeight = this.weights[i];

// factor用来控制每个server分配的虚拟节点数量

// 权重都相同时，factor=40

// 权重不同时，factor=40*server总数*该server权重所占的百分比

// 总的来说，权重越大，factor越大，可以分配越多的虚拟节点

double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );

for ( long j = 0; j factor; j++ ) {

// 每个server有factor个hash值

// 使用server的域名或IP加上编号来计算hash值

// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值：

// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor

byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );

// 每个hash值生成4个虚拟节点

for ( int h = 0 ; h 4; h++ ) {

Long k =

((long)(d[3+h*4]0xFF) 24)

| ((long)(d[2+h*4]0xFF) 16)

| ((long)(d[1+h*4]0xFF) 8 )

| ((long)(d[0+h*4]0xFF));

// 在环上保存节点

consistentBuckets.put( k, servers[i] );

}

}

// 每个server一共分配4*factor个虚拟节点

}

// 采用有序map来模拟环

this.consistentBuckets = new TreeMap();

MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值

// 计算总权重

if ( this.totalWeight for ( int i = 0; i this.weights.length; i++ )

this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];

} else if ( this.weights == null ) {

this.totalWeight = this.servers.length;

}

// 为每个server分配虚拟节点

for ( int i = 0; i servers.length; i++ ) {

// 计算当前server的权重

int thisWeight = 1;

if ( this.weights != null this.weights[i] != null )

thisWeight = this.weights[i];

// factor用来控制每个server分配的虚拟节点数量

// 权重都相同时，factor=40

// 权重不同时，factor=40*server总数*该server权重所占的百分比

// 总的来说，权重越大，factor越大，可以分配越多的虚拟节点

double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );

for ( long j = 0; j factor; j++ ) {

// 每个server有factor个hash值

// 使用server的域名或IP加上编号来计算hash值

// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值：

// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor

byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );

// 每个hash值生成4个虚拟节点

for ( int h = 0 ; h 4; h++ ) {

Long k =

((long)(d[3+h*4]0xFF) 24)

| ((long)(d[2+h*4]0xFF) 16)

| ((long)(d[1+h*4]0xFF) 8 )

| ((long)(d[0+h*4]0xFF));

// 在环上保存节点

consistentBuckets.put( k, servers[i] );

}

}

// 每个server一共分配4*factor个虚拟节点

}

// 用MD5来计算key的hash值

MessageDigest md5 = MD5.get();

md5.reset();

md5.update( key.getBytes() );

byte[] bKey = md5.digest();

// 取MD5值的低32位作为key的hash值

long hv = ((long)(bKey[3]0xFF) 24) | ((long)(bKey[2]0xFF) 16) | ((long)(bKey[1]0xFF) 8 ) | (long)(bKey[0]0xFF);

// hv的tailMap的第一个虚拟节点对应的即是目标server

SortedMap tmap = this.consistentBuckets.tailMap( hv );

return ( tmap.isEmpty() ) ? this.consistentBuckets.firstKey() : tmap.firstKey();

更多问题到问题求助专区（）

相关问答

Q1: php代码hash解析

将给定php数据流计算hash的明文密码通过加"盐"(干扰码)后php数据流计算hash，再经过哈希算法的sha512算法结果与哈希算法whirlpool算法的两个值进行与运算php数据流计算hash，将结果返回。

举例：（示例一下php数据流计算hash，例子未必形象）

假如你输入一个密码：123456

通过运算（自定义一个干扰码 abcd@!#$）

1、hash（"abcd@!#$","123456"）

2、用hash算法的sha512算法对（abcd@!#$123456）进行加密取得值a

3、用hash算法的whirlpool算法对（abcd@!#$123456）进行加密取得值b

4、将a和b进行二进制位与运算得到c

5、将c转化为十六进制数返回

通过该方法可以将用户的输入的明文进行加密，多用于用户密码的存储和比较。说白了就是只有输入的用户知道密码的明文，程序设计者、数据库管理员、黑客就算拿到加密的密文也不会知道（短时间内）密码的明文。

例外：如果黑客知道了使用的盐（干扰码）和算法，当然可以自己创建一个新的彩虹表，通过高性能计算是有可能将明文碰撞出来的，当然你可以个直接找到用户强迫php数据流计算hash他说出来～嘿嘿嘿～

Q2: PHP mysql 实现hash分区的问题

当分片索引不是纯整型的字符串时，只接受整型的内置 hash 算法是无法使用的。为此，stringhash 按照用户定义的起点和终点去截取分片索引字段中的部分字符，根据当中每个字符的二进制 unicode 值换算出一个长整型数值，然后就直接调用内置 hash 算法求解分片路由：先求模得到逻辑分片号，再根据逻辑分片号直接映射到物理分片。

用户需要在 rule.xml 中定义 partitionLength[] 和 partitionCount[] 两个数组和 hashSlice 二元组。

在 DBLE 的启动阶段，点乘两个数组得到模数，也是逻辑分片的数量

并且根据两个数组的叉乘，得到各个逻辑分片到物理分片的映射表（物理分片数量由 partitionCount[] 数组的元素值之和）

此外根据 hashSlice 二元组，约定把分片索引值中的第 4 字符到第 5 字符（字符串以 0 开始编号，编号 3 到编号 4 等于第 4 字符到第 5 字符）字符串用于 “字符串-整型”的转换

在 DBLE 的运行过程中，用户访问使用这个算法的表时，WHERE 子句中的分片索引值会被提取出来，取当中的第 4 个字符到第 5 字符，送入下一步

设置一个初始值为 0 的累计值，逐个取字符，把累计值乘以 31，再把这个字符的 unicode 值当成长整型加入到累计值中，如此类推直至处理完截取出来的所有字符，此时的累计值就能够代表用户的分片索引值，完成了 “字符串-整型” 的转换

对上一步的累计值进行求模，得到逻辑分片号

再根据逻辑分片号，查映射表，直接得到物理分片号

与MyCat的类似分片算法对比

请点击输入图片描述

两种算法在string转化为int之后，和 hash 分区算法相同，区别也继承了 hash 算法的区别。

开发注意点

【分片索引】1. 必须是字符串

【分片索引】2. 最大物理分片配置方法是，让 partitionCount[] 数组和等于 2880

例如：

property name="partitionLength"1/propertyproperty name="partitionCount"2880/property

或

property name="partitionLength"1,1/propertyproperty name="partitionCount"1440,1440/property

【分片索引】3. 最小物理分片配置方法是，让 partitionCount[] 数组和等于 1

例如

property name="partitionLength"2880/propertyproperty name="partitionCount"1/property

【分片索引】4. partitionLength 和 partitionCount 被当做两个逗号分隔的一维数组，它们之间的点乘必须在 [1, 2880] 范围内

【分片索引】5. partitionLength 和 partitionCount 的配置对顺序敏感

property name="partitionLength"512,256/propertyproperty name="partitionCount"1,2/property

和

property name="partitionLength"256,512/propertyproperty name="partitionCount"2,1/property

是不同的分片结果

【分片索引】6. 分片索引字段长度小于用户指定的截取长度时，截取长度会安全减少到符合分片索引字段长度

【数据分布】1. 分片索引字段截取越长则越有利于数据均匀分布

【数据分布】2. 分片索引字段的内容重复率越低则越有利于数据均匀分布

运维注意点

【扩容】1. 预先过量分片，并且不改变 partitionCount 和 partitionLength 点乘结果，也不改变截取设置 hashSlice 时，可以避免数据再平衡，只需进行涉及数据的迁移

【扩容】2. 若需要改变 partitionCount 和 partitionLength 点乘结果或改变截取设置 hashSlice 时，需要数据再平衡

【缩容】1. 预先过量分片，并且不改变 partitionCount 和 partitionLength 点乘结果，也不改变截取设置 hashSlice 时，可以避免数据再平衡，只需进行涉及数据的迁移

【缩容】2. 若需要改变 partitionCount 和 partitionLength 点乘结果或改变截取设置 hashSlice 时，需要数据再平衡

配置注意点

【配置项】1. 在 rule.xml 中，可配置项为 property name="partitionLength"  、property name="partitionCount" 和 property name="hashSlice"

【配置项】2.在 rule.xml 中配置 property name="partitionLength" 标签

内容形式为：物理分片持有的虚拟分片数[,物理分片持有的虚拟分片数,...物理分片持有的虚拟分片数]

物理分片持有的虚拟分片数必须是整型，物理分片持有的虚拟分片数从左到右与同顺序的物理分片数对应，partitionLength 和partitionCount 的点乘结果必须在 [1, 2880] 范围内

【配置项】3. 在 rule.xml 中配置 property name="partitionCount" 标签

内容形式为：物理分片数[,物理分片数,...物理分片数]

其中物理分片数必须是整型，物理分片数按从左到右的顺序与同顺序的物理分片持有的虚拟分片数对应，物理分片的编号从左到右连续递进，partitionLength 和 partitionCount 的点乘结果必须在 [1, 2880] 范围内

【配置项】4. partitionLength 和 partitionCount 的语义是：持有partitionLength[i] 个虚拟分片的物理分片有 partitionCount[i] 个

例如

property name="partitionLength"512,256/propertyproperty name="partitionCount"1,2/property

语义是持有 512 个逻辑分片的物理分片有 1 个，紧随其后，持有 256 个逻辑分片的物理分片有 2 个

【配置项】5.partitionLength 和 partitionCount 都对书写顺序敏感，

例如

property name="partitionLength"512,256/propertyproperty name="partitionCount"1,2/property

分片结果是第一个物理分片持有头512个逻辑分片，第二个物理分片持有紧接着的256个逻辑分片，第三个物理分片持有最后256个逻辑分片，相对的

property name="partitionLength"256,512/propertyproperty name="partitionCount"2,1/property

分片结果则是第一个物理分片持有头 256 个逻辑分片，第二个物理分片持有紧接着的 256 个逻辑分片，第三个物理分片持有最后 512 个逻辑分片

【配置项】6.partitionLength[] 的元素全部为 1 时，这时候partitionCount 数组和等于 partitionLength 和 partitionCount 的点乘，物理分片和逻辑分片就会一一对应，该分片算法等效于直接取余

【配置项】7.在 rule.xml 中配置标签，从分片索引字段的第几个字符开始截取到第几个字符：

若希望从首字符开始截取 k 个字符（ k 为正整数），配置的内容形式可以为“ 0 : k ”、“ k ”或“ : k ”；

若希望从末字符开始截取 k 个字符（ k 为正整数），则配置的内容形式可以为“ -k : 0 ”、“ -k ”或“ -k : ”；

若希望从头第 m 个字符起算截取 n 个字符（ m 和 n 都是正整数），则先计算出 i = m - 1 和 j = i + n - 1，配置的内容形式为“ i : j ”；

若希望从尾第 m 个字符起算截取从尾算起的 n 个字符（ m 和 n 都是正整数），则先计算出 i = -m + n - 1，配置的内容形式可以为“ -m : i ”；

若希望不截取，则配置的内容形式可以为“ 0 : 0 ”、“ 0 : ”、“ : 0 ”或 “ : ”

关于php数据流计算hash和php流量统计的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。