如何做一个国产数据库(五) hash一致性算法

分布式

我们做的是分布式数据库，也就是我们的节点会有很多个。 那么数据应该存储到哪个节点上呢，如何计算？

hash 一致性算法

使用hash一致性算法可以使用多个节点，hash的节点值为ip地址，算法： unsigned int hvalue = hash(ip); hash函数计算出一个四字节整型数，按照0----2的32次方排列。那么，就可以计算输入值来放到什么位置了。

unsigned int xxx = hash(输入值)；

我们把所有节点放到list里面 #include

list allnode; 算法特别简单，把计算出来的值按照顺时针走，走到哪个节点，就放到哪个节点里面。 为了防止节点出错，冗余算法就是： 1、按照顺时针和逆时针都放入值，这样，在多个节点都有值，假定有n个节点，单个节点出错时，那么取数据出错的概念为0。 2、两个非相邻节点出错时，出错概率依然为0，大大降低了风险。 其他还可以使用校验算法，将多个节点的值进行校验

hash算法

一下为其他hash的算法，为了计算正确，后面的prime为素数。

#include 
#include 
#include 
//注意prime是素数
static int rotating_hash(const char *key, int prime)
{
	size_t hash, i;
	size_t len = strlen(key);
	for (hash = len, i = 0; i