0、作业内容
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
1、普通Hash算法
1-1、算法原理
一个好的Hash算法，需要满足以下条件：
关键字Key的hash值【均匀分布】在哈希结构上，从而减少冲突（collision）；这里的冲突指关键字不相等，但哈希值相等，即 key1 ≠ key2，但是 hash(key1) = hash(key2)；
常用的Hash函数实现：
1、直接地址法：取关键字或关键字的某个线性函数值为哈希地址。即：
H(key) = key 或 H(key) = a * key + b
其中 a 和 b 为常数（这种哈希函数叫做自身函数）；
2、数字分析法：关键字以R为基数，并且哈希表中可能出现的【关键字事先知道】，则可取关键字的【若干数位】组成哈希地址；
3、平方取中法：取关键字平方后的中间几位为哈希地址；
4、折叠法：将关键字分割成【位数相同】的几部分（最后一部分的位数可以不同），然后取这几部分的【叠加和】作为哈希地址，该方法称为折叠法（folding）；使用场景：关键字位数很多，而且关键字中每一位上数据分布大致均匀时；
5、除留取余法：取关键字被某个【不大于】哈希表表长的数，将这个数作为除数，关键字作为被除数，所得【余数】为哈希地址；即 H(key) = key MOD p， p ≤ 哈希表长度；
注意：使用除留取余法时，对除数的选择很重要，一旦选择不好，会产生较大冲突；
6、随机数法：选择一个随机函数，取关键字的随机函数值为哈希地址，即 H(key) = random(key)，其中 random 为 随机函数；通常，当关键字长度不等时适合用随机数法构造哈希函数；
1-2、算法复杂度
1-3、算法实现
(1) 计算Key值的HashCode，在Java中，Integer 和 String 类型都重写了 hashCode() 方法，在HashMap等结构中，判断一个 key 是否存在，或者 get某个key的值，都依赖 key的hashCode() 方法，因此一般都建议使用【包装类型】或者字符串String 作为 Map的key；
(2) 根据HashCode值，用哈希表的数组长度作为除数，即 HashCode mod 数组长度 取模，取模后的结果就是Key在哈希表中的地址；
(3) 哈希表中存放的值不是对象的Value，而是对象存放的地址指针，根据地址指针获取实际的对象；
(4) 不同的Key取模后的地址可能出现一样，这个现象称之为【冲突（collision）】，Java中 HashMap 和 ConcurrentHashMap 使用 链表或红黑树 来解决Hash冲突的问题；
1-4、哈希算法Java的HashMap实现
Java的HashMap是哈希函数的一个实现，实现 Map<K, V> 接口，通过计算K的hashCode获得在哈希表中的下标，然后根据下标随机访问，得到具体的Value，代码如下：
(1) 根据Key值取得Key的hashCode；
(2) 再用【hashCode的向右位移16位的结果】与hashCode取【异或(^)】计算；
(3) 得到的hash值从哈希表（Node<K，V>[]）中查询值；
1-5、余数Hash函数的问题
1-5-1、Rehash影响大量数据
以水平分库分表具体，电商系统的客户数量增加，假如根据客户ID（customer_id）进行分库，分成3个数据库（D0, D1, D2），假如有三个客户 CustomerA，CustomerB，CustomerC
CustomerA 客户号取模后 存在 D0 库；
CustomerB 客户号取模后 存在 D1 库；
CustomerC 客户号取模后 存在 D2 库；
当业务持续增长，需要新增数据库以缓解Database的压力，假如增加一台数据库，数据库总数为4，假如目前的用户总数为1亿，则需要对客户号除4取模，影响全部数据；带来的问题就是需要做全量的数据迁移，如果是生存环境，迁移数据需要时间和成本，还需要考虑用户持续增长问题，在这过程中开发成本和迁移成本都很高；
问题总结：服务器扩容或者缩容时，需要对Key重新hash，有可能导致Key的分布不均匀；
如何通过加
1-5-2、热点问题（Hot Spot）
《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》这篇论文中是这样定义热点问题：
Hot spots occur any time a large number of clients wish to simultaneously access data
from a single server. If the site is not provisioned to deal with all of these clients
simultaneously, service may be degraded or lost.
所谓热点，就是在任意时刻有大量客户端【同时（simultaneously）】【从一个服务（from a single server）】访问数据；如果网站不提供解决客户端同时请求的办法，服务将会降级或者丢失（不可用）；
如果用hash取模的方式，将数据分散在不同缓存，有可能在某一时刻，大部分请求都会访问到一台缓存服务器上，如果请求超过一台机器的上限，服务将出现延迟或不可用，很可能影响用户体验；
2、一致性Hash算法（Consistent Hash）
2-1、一致性Hash算法
2-1-1、一致性Hash算法的特性
考虑到分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来，如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务，这是值得考虑的，尤其实在设计分布式缓存系统时，如果某台服务器失效，对于整个系统来说如果不采用合适的算法来保证一致性，那么缓存于系统中的所有数据都可能会失效【即由于系统节点数目变少，客户端在请求某一对象时需要重新计算其hash值（通常与系统中的节点数目有关），由于hash值已经改变，所以很可能找不到保存该对象的服务器节点】，因此一致性hash就显得至关重要，良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面：
· 平衡性（Balance）
【平衡性】是指哈希的结果能够尽可能分布到所有的缓存中去，这样可以使得所有的缓存空间都得到利用。
· 单调性（Monotonicity）
This reflects one intuition about consistency:
when the set of usable buckets changes,
items should only move if necessary to preserve an even distribution
单调性是指如果已经有一些内容通过哈希分派到了相应的缓存中，又有新的缓存节点加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓存中去，而不会被映射到旧的缓存集合中的其他缓存。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod (P)，在上式中，P表示全部缓存的数量。不难看出，当缓存节点数量发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓存空间发生变化时，所有的映射关系需要在系统内全部更新。单调性就是要求哈希算法能够应对这种情况。
· 分散性（Spread）
在分布式环境中，终端有可能看不到所有的缓存，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓存上时，由于不同终端所见的缓存范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓存节点。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓存节点，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
对于所有客户端而言，一个对象分配的不同缓存节点的数量要尽量小（over all the client views, the total number of different caches to which a object is assigned is small）；
· 负载（Load）
负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓存节点，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
没有缓存被分配不合理数量的对象（no one cache is assigned an unreasonable number of objects）；
· 平滑性（Smoothness）
平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。（When a machine is added to or removed from the set of caches, the expected fraction of objects that must be moved to a new cache is the minimum needed to maintain a balanced load across the caches）
2-1-2、概念
一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。
解决什么问题：在分布式系统中，防止服务器扩容或缩容，数据不一致问题；
实现方式：
简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希空间环如下，这个结构也被称为【哈希环】：
一致性哈希环
1、构造一个环形结构；
2、哈希环上的值范围是 0 - 2^32-1；
3、服务器节点取hash值放到环上；
4、当要查找某个key在哪台服务器上，先对Key取Hash值，值落在环上，如果这个值恰好等于某个服务器的hash值，就直接访问这台服务器；如果Key的Hash值与任意一台服务器的Hash值都不相等，沿着哈希环【顺时针】查找，最近的一个服务器节点就是这个Key值要访问的节点；
2-1-3、一致性Hash的缓存节点分布
一致性Hash算法也是使用取模的思想，传统的取模是用【机器数量】进行取模，而一致性Hash算法是对
2^32进行取模；
假设分布式缓存集群有4台机器，那么对这4台机器用2^32取模，然后将机器的模数放到哈希环上：
2-1-4、一致性Hash的缓存对象分布
假如有4个对象，Object A、Object B、Object C、Object D，获得对象值存放在具体的节点的过程：
1、计算对象的Hash值；
2、根据Hash值在哈希环上查询，如果命中缓存节点的Hash值，则直接从该缓存节点获取数据；
3、如果没有获取到，则【按顺时针】访问哈希环，在访问过程中遇到的第一个节点就是存放这个值的缓存节点
具体内容参考下图：
2-1-5、增加缓存节点
假如新增一个节点NodeX，此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X 。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向遇到的第一台服务器）之间数据，其它数据也不会受到影响。
综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
2-1-6、移除缓存节点
在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响；
2-2、虚拟节点一致性Hash算法
虽然一致性缓存在节点新增或移除，影响数据较小，但却带来较严重的问题：
因为缓存节点都是使用内存服务器，而内存资源本身就比较稀缺，带来的问题就是一个分布式缓存集群的节点数量是有限的，一般不会部署服务器较少，而每台机器在哈希环上的位置也不固定，这就导致假如机器取模后，节点分部不均匀而造成数据倾斜问题；
例如，集群中只有两台缓存服务器，在Hash环上的分布如下：
此时大量数据集中到Node A上，而只有极少量会定位到Node B上
为了解决这种【数据倾斜】问题，一致性哈希算法引入了【虚拟节点机制】，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点；
在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。
通过虚拟节点找到一个对象的过程：
1、计算Key的Hash值；
2、根据Hash值找到对应的虚拟节点；
3、根据虚拟节点获得真实节点；
3、Redis集群分Slot实现
Redis集群预先分好【16384个桶】，当需要在Redis集群中放置一个key-value时，根据CRC16(key) mod 16384 的值，决定将一个Key放到哪个桶中；
Redis-Cluster把所有的物理节点映射到【0-16383】slot上（不一定是平均分配），cluster负责维护slot与服务器的映射关系；
客户端与Redis节点直连，客户端不需要连接集群所有节点，连接集群中任何一个可用节点即可；
所有的Redis节点彼此互联；
需要注意的是，对于槽位的转移和分派，Redis集群是不会自动进行的，而是需要人工配置的。所以Redis集群的高可用是依赖于节点的主从复制与主从间的自动故障转移。
分区是可以自定义大小，自定义位置的。Redis 集群包含了16384
另外在容错性和扩展性上与一致性哈希一样，都是对受影响的数据进行转移而不影响其它的数据。而哈希槽本质上是对槽位的转移，把故障节点负责的槽位转移到其他正常的节点上。扩展节点也是一样，把其他节点上的槽位转移到新的节点上。
4、一致性Hash算法实现（Java）
4-1、ID生成问题
为了保证ID（关键字）能均匀分布到哈希环上，如果数据较小，比如从0-100万，将会造成取模后散列不均匀，因为比2^32位小，当除以2^32后，模数仍然是原数据本身，为了得到更好的哈希值，数据值最好大于2^32；
在分布式生成Long型64位ID比较好的方法就是Snowflake算法，具体代码参考：
* Snowflake算法生成id的结果是一个64bit大小的整数，其中：
* 第1位是标志位，因为二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为0
* 41bit-时间戳，用来记录时间戳，毫秒级
* 10bit-工作机器id，用来记录工作机器id，2^10可以表示1024个节点，包括5位dataCenterId和5位workerId
* 12bit-序列号，序列号，用来记录同毫秒内产生的不同id，2^12 -1 = 4096，表示同一机器同一时间截（毫秒)内产生的4095个ID序号
* <p>
* Snowflake 可以保证：
* 1、所有生成的id按时间趋势递增；
* 2、整个分布式系统内不会产生重复id（因为有dataCenterId和workerId来做区分）；
*/
public class Snowflake {
* 初始时间戳, 2020-01-01 00:00:00
*/
private static final long START_TIME = 1577808000000L;
* 数据中心长度为5位
*/
private static final long DATA_CENTER_ID_BITS = 5L;
private static final long MAX_DATA_CENTER_ID = ~(-1L << DATA_CENTER_ID_BITS);
* 长度为5位
*/
private static final long WORKER_ID_BITS = 5L;
private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);
* 序列号id长度
*/
private static final long SEQUENCE_BITS = 12L;
* 机器ID向左移12位
*/
private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
* 序列号最大值
*/
private static final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);
* 数据id需要左移位数 12 + 5 = 17位
*/
private static final long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;
* 时间戳需要左移位数 12 + 5 + 5 = 22位
*/
private static final long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;
* 上次时间戳，初始值为负数
*/
private long lastTimestamp = -1L;
* 数据中心ID，与工作ID相加刚好是10位
*/
private final long dataCenterId;
* 工作ID
*/
private final long workerId;
* 12位序号为
*/
private long sequence;
public Snowflake(long workerId, long dataCenterId, long sequence) {
if (workerId > MAX_WORKER_ID || workerId < 0) {
throw new IllegalArgumentException("worker Id can't be greater than " + MAX_WORKER_ID + " or less than 0");
}
if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
throw new IllegalArgumentException("dataCenter Id can't be greater than " + MAX_DATA_CENTER_ID + " or less than 0");
}
this.workerId = workerId;
this.dataCenterId = dataCenterId;
this.sequence = sequence;
}
public long getWorkerId() {
return workerId;
}
public long getDataCenterId() {
return dataCenterId;
}
public long getTimestamp() {
return System.currentTimeMillis();
}
* 下一个ID生成算法
*
* @return ID
*/
public synchronized long nextId() {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & SEQUENCE_MASK;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
* 返回结果：
* (timestamp - twepoch) << timestampLeftShift) 表示将时间戳减去初始时间戳，再左移相应位数
* (datacenterId << datacenterIdShift) 表示将数据id左移相应位数
* (workerId << workerIdShift) 表示将工作id左移相应位数
* | 是按位或运算符，例如：x | y，只有当x，y都为0的时候结果才为0，其它情况结果都为1。
* 因为个部分只有相应位上的值有意义，其它位上都是0，所以将各部分的值进行 | 运算就能得到最终拼接好的id
*/
return ((timestamp - START_TIME) << TIMESTAMP_LEFT_SHIFT) |
(dataCenterId << DATA_CENTER_ID_SHIFT) |
(workerId << WORKER_ID_SHIFT) |
sequence;
}
* 获取时间戳，并与上次时间戳比较
*
* @param lastTimestamp 上一次时间戳
* @return 下一时间戳
*/
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
* 获取系统时间戳
*
* @return 时间戳
*/
private long timeGen() {
return System.currentTimeMillis();
}
}
4-2、简单一致性Hash
public class ConsistentHash {
* 一致性Hash算法按【顺时方向】遍历环，每个节点排列是有序的
*/
private static SortedMap<Integer, String> hashNodes = new TreeMap<Integer, String>();
* 一致性Hash算法，使用【0 ~ 2^32-1】的值形成环形结构，使用2^32进行取模
*/
private static final int MODE_NUMBER = 2^32;
* 构造函数，计算每个节点的Hash值
*
* @param serverNodes 服务节点
*/
public ConsistentHash(List<Node> serverNodes) {
for (Node node : serverNodes) {
hashNodes.put(getHash(node.getIp()), node.getIp());
}
}
public String getNode(String key) {
int hashCode = getHash(key);
SortedMap<Integer, String> selectedNodes = hashNodes.tailMap(hashCode);
if (selectedNodes.isEmpty()) {
int firstKey = hashNodes.firstKey();
return hashNodes.get(firstKey);
}
return hashNodes.get(selectedNodes.firstKey());
}
private int getHash(String key) {
int hashCode = Math.abs(key.hashCode());
return hashCode % MODE_NUMBER;
}
}
* 节点
*/
class Node {
private final String ip;
public Node(String ip) {
this.ip = ip;
}
public String getIp() {
return ip;
}
}
4-3、虚拟节点一致性Hash算法
* 带虚拟节点的一致性Hash算法
*/
public class VirtualNodeConsistentHash {
* 一致性Hash算法，使用【0 ~ 2^32-1】的值形成环形结构，使用2^32进行取模
*/
private static final int MODE_NUMBER = 2 ^ 32;
* 一致性Hash算法按【顺时方向】遍历环，每个节点排列是有序的
*/
private static final SortedMap<Integer, VirtualNode> virtualNodes = new TreeMap<Integer, VirtualNode>();
* @param trueNodes 真实节点
* @param virtualNodeNumber 一个真实对应虚拟节点数量
*/
public VirtualNodeConsistentHash(List<TrueNode> trueNodes, int virtualNodeNumber) {
for (TrueNode trueNode : trueNodes) {
for (int i = 0; i < virtualNodeNumber; i++) {
VirtualNode virtualNode = new VirtualNode(trueNode, i);
virtualNodes.put(getHash(virtualNode.getVirtualIp()), virtualNode);
}
}
}
public String getTrueNode(String key) {
int hashCode = getHash(key);
if (!virtualNodes.containsKey(hashCode)) {
SortedMap<Integer, VirtualNode> selectNodes = virtualNodes.tailMap(hashCode);
Integer hitHash = selectNodes.isEmpty() ? virtualNodes.firstKey() : selectNodes.firstKey();
return virtualNodes.get(hitHash).getTrueIp();;
}
return virtualNodes.get(hashCode).getTrueIp();
}
private int getHash(String key) {
int hashCode = Math.abs(key.hashCode());
return hashCode % MODE_NUMBER;
}
}
* 真实节点
*/
class TrueNode {
private final String ip;
public TrueNode(String ip) {
this.ip = ip;
}
public String getIp() {
return ip;
}
}
* 虚拟节点
*/
class VirtualNode {
private final TrueNode trueNode;
private final int nodeNumber;
public VirtualNode(TrueNode trueNode, int nodeNumber) {
this.trueNode = trueNode;
this.nodeNumber = nodeNumber;
}
public String getVirtualIp() {
return this.trueNode.getIp() + nodeNumber;
}
public String getTrueIp() {
return trueNode.getIp();
}
}
4-4、一致性Hash分布效果（计算标准差）
标准差，执行多次标准差值的范围在 37000 - 38000；
* 计算Key-Value发布在节点的标准差
* 1、统计每个节点分布key的数量；
* 2、计算标准差；
*/
public class KeyValueNodeStandardDeviation {
* 定义10个节点，并且初始化IP
*/
private static final List<Node> NODES = new ArrayList<Node>(10);
static {
NODES.add(new Node("192.168.0.0"));
NODES.add(new Node("192.168.0.1"));
NODES.add(new Node("192.168.0.2"));
NODES.add(new Node("192.168.0.3"));
NODES.add(new Node("192.168.0.4"));
NODES.add(new Node("192.168.0.5"));
NODES.add(new Node("192.168.0.6"));
NODES.add(new Node("192.168.0.7"));
NODES.add(new Node("192.168.0.8"));
NODES.add(new Node("192.168.0.9"));
}
public static void main(String[] args) {
ConsistentHash consistentHash = new ConsistentHash(NODES);
Map<String, Integer> nodeCounts = new HashMap<String, Integer>();
int keyValueCount = 1000000;
Snowflake snowflake = new Snowflake(1, 1, 0);
for (int i = 0; i < keyValueCount; i++) {
String nodeIp = consistentHash.getNode(String.valueOf(snowflake.nextId()));
if (nodeCounts.containsKey(nodeIp)) {
int count = nodeCounts.get(nodeIp);
nodeCounts.put(nodeIp, count + 1);
} else {
nodeCounts.put(nodeIp, 1);
}
}
System.out.println(computeStandardDeviation(nodeCounts.values(), keyValueCount, NODES.size()));
}
private static String computeStandardDeviation(Collection<Integer> values, Integer average, int count) {
double sum = 0;
for (Integer value : values) {
sum += (value - average) * (value - average);
}
return BigDecimal.valueOf(Math.sqrt(sum/count)).setScale(2, RoundingMode.CEILING).toEngineeringString();
}
}
4-5、带有虚拟节点一致性Hash分布效果（计算标准差）
执行结果，多次执行，标准差值的范围 在 > 11700 && < 11800；
package org.java.distribute.algorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
* 使用虚拟节点的标准差
*/
public class KeyValueVirtualNodeStandardDeviation {
* 定义10个节点，并且初始化IP
*/
private static final List<TrueNode> NODES = new ArrayList<TrueNode>(10);
static {
NODES.add(new TrueNode("192.168.0.0"));
NODES.add(new TrueNode("192.168.0.1"));
NODES.add(new TrueNode("192.168.0.2"));
NODES.add(new TrueNode("192.168.0.3"));
NODES.add(new TrueNode("192.168.0.4"));
NODES.add(new TrueNode("192.168.0.5"));
NODES.add(new TrueNode("192.168.0.6"));
NODES.add(new TrueNode("192.168.0.7"));
NODES.add(new TrueNode("192.168.0.8"));
NODES.add(new TrueNode("192.168.0.9"));
}
public static void main(String[] args) {
VirtualNodeConsistentHash virtualNodeConsistentHash = new VirtualNodeConsistentHash(NODES, 10);
Map<String, Integer> nodeCounts = new HashMap<String, Integer>();
int keyValueCount = 1000000;
Snowflake snowflake = new Snowflake(1, 1, 0);
for (int i = 0; i < keyValueCount; i++) {
String nodeIp = virtualNodeConsistentHash.getTrueNode(String.valueOf(snowflake.nextId()));
if (nodeCounts.containsKey(nodeIp)) {
int count = nodeCounts.get(nodeIp);
nodeCounts.put(nodeIp, count + 1);
} else {
nodeCounts.put(nodeIp, 1);
}
}
System.out.println(StandardDeviation.compute(nodeCounts.values(), 10000, NODES.size() * 10));
}
}
标准差公式：
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Collection;
public class StandardDeviation {
private StandardDeviation() {
}
* 标准差公式 = sqrt( ((x1-x)^2 +(x2-x)^2 +......(xn-x)^2) / n )
*
* @param sampleValues 样本值
* @param average 平均值
* @param total 总数
* @return 标准差
*/
public static String compute(Collection<Integer> sampleValues, Integer average, int total) {
double sum = 0;
for (Integer value : sampleValues) {
sum += (value - average) * (value - average);
}
return BigDecimal.valueOf(Math.sqrt(sum/total)).setScale(2, RoundingMode.CEILING).toEngineeringString();
}
}
评论