Jump to Navigation

hyperdex 不同数据类型hash算法

hyperdex使用hyperspace hashing算法对记录的每个字段做哈希, 并且所有字段的哈希值作为每个维度的值映射到多维度空间中的一个点上。

通过化分多维空间的方式,把所有的记录分布到不同的存储节点上,实现hyperdex的分布式NoSQL功能。

对于hyperdex的实现,它所支持的土原子数据类型各自有不同的哈希算法,

原子类型有float,int64,string,每种类型的哈希算法如下:

一、hyperdex数据类型

字符串,长度限制???

int64类型,

float类型,

二、hyperdex容器数据类型

list列表类型,

set集合类型,

map映射类型,

三、不同数据类型的hash值计算

字符串类型hash算法

使用cityhash算法计算该字段值的hash值。

int64类型hash算法

unpack64le 把值高字节与低字节交换位置,64位为8个字节,即1,8交换,2,7交换,3,6交换,4,5交换

float 即小数类型hash算法,

使用unpack64le,8字节前后对调

然后, hyperdex判断针对无穷大/小,是否是数字,0和正常小数分别做处理。

如果是>0的无穷大/小数,则结果为固定值, out = 0xfff0000000000000ULL + 2;

如果是其他的无穷大/小数,则结果为固定值 out = 0;

如果不是数字,则结果为固定值, out = 0xfff0000000000000ULL + 3;

如果等于0,则结果为固定值, out = 0x8000000000000000ULL + 1;

如果是其他正常的数字,则使用ieee754_double类型的标准处理,

            ieee754_double d;

            d.d = x;

            uint64_t sign = d.ieee.negative ^ 0x1;

            uint64_t exp  = d.ieee.exponent;

            uint64_t frac = d.ieee.mantissa0;

            frac <<= 32;
            frac |= d.ieee.mantissa1;

            uint64_t shift = 2;

            if (x < 0) {
                exp  ^= 0x7ffULL;
                frac ^= 0xfffffffffffffULL;
                shift = 1;
            }

            out = (sign << 63) | (exp << 52) | (frac);
            out += shift;

复合类型

复合类型,list,set,map,集合中的数据类型必须一致。
复合类型的字段不能做hash,也就是应该不算作一个维度。

记录hash算法:

一条记录的hash结果会需要保存在一个hash数组中,在hyperdex中为uint64[]。

它并不是把所有字段的hash值再计算成一个值。

这个hash数组可用于查找这条记录所在的region,或者是根据根据某几个字段查找区域内匹配的记录。

这个hash数组实际对应多维空间的不同维度。

添加新评论

Plain text

  • 不允许HTML标记。
  • 自动将网址与电子邮件地址转变为链接。
  • 自动断行和分段。
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Enter the characters shown in the image.


Main menu 2

Story | by Dr. Radut