发布于 2016-03-30 13:27:02 | 115 次阅读 | 评论: 0 | 来源: 分享

这里有新鲜出炉的Redis 官方指南,程序狗速度看过来!

Redis Key-Value数据库

Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。


Redis哈希表的实现要点

哈希算法的选择

针对不同的key使用不同的hash算法,如对整型、字符串以及大小写敏感的字符串分别使用不同的hash算法;

整型的Hash算法使用的是Thomas Wang’s 32 Bit / 64 Bit Mix Function ,这是一种基于位移运算的散列方法。基于移位的散列是使用Key值进行移位操作。通常是结合左移和右移。每个移位过程的结果进行累加,最后移位的结果作为最终结果。这种方法的好处是避免了乘法运算,从而提高Hash函数本身的性能。

unsigned int dictIntHashFunction(unsigned int key)
{
    key += ~(key > 10);
    key +=  (key > 6);
    key += ~(key > 16);
    return key;
}

字符串使用的MurmurHash算法,MurmurHash算法具有高运算性能,低碰撞率的特点,由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年Appleby被Google雇佣,随后Google推出其变种的CityHash算法。

murmur是 multiply and rotate的意思,因为算法的核心就是不断的乘和移位(x *= m; k ^= k >> r;)

unsigned int dictGenHashFunction(const void *key, int len) {
    /* 'm' and 'r' are mixing constants generated offline.
     They're not really 'magic', they just happen to work well.  */
    uint32_t seed = dict_hash_function_seed;
    const uint32_t m = 0x5bd1e995;
    const int r = 24;

    /* Initialize the hash to a 'random' value */
    uint32_t h = seed ^ len;

    /* Mix 4 bytes at a time into the hash */
    const unsigned char *data = (const unsigned char *)key;

    while(len >= 4) {
        uint32_t k = *(uint32_t*)data;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += 4;
        len -= 4;
    }

    /* Handle the last few bytes of the input array  */
    switch(len) {
    case 3: h ^= data[2] > 13;
    h *= m;
    h ^= h >> 15;

    return (unsigned int)h;
}

一个好的hash算法需要满足两个条件:

1) 性能高,运算足够快;

2) 相邻的数据hash后分布广;即使输入的键是有规律的,算法仍然能给出一个很好的随机分布性;

比如:murmur计算”abc”是1118836419,”abd”是413429783。而使用Horner算法,”abc”是96354, “abd”就比它多1(96355);

rehash

负载因子 = 当前结点数/桶的大小,超过1表示肯定有碰撞了;碰撞的结点,通过链表拉链起来;

所有哈希表的初始桶的大小为4,根据负载因子的变化进行rehash,重新分配空间(扩展或收缩)

当hash表的负载因子超过1后,进行扩展(小于0.01时,进行收缩);

所谓扩展,就是新建一个hash表2,将桶的数量增大(具体增大为:第一个大于等于usedSize的2的n次冥);然后将hash表1中结点都转移到hash表2中;

rehash的触发条件:

当做BGSAVE或BGREWRITEEOF时,负载因子超过5时触发rehash,

没有BGSAVE或BGREWRITEEOF时,负载因子超过1时触发rehash;

在BGSAVE或BGREWRITEEOF时,使用到Linux的写时复制,如果这时候做rehash,将会好用更多的内存空间(没有变化的结点用一份,变化的结点复制一份)

渐进式rehash

一个hash表中的数据可能有几百上千万,不可能一次rehash转移完,需要分批逐渐转移;

在rehash的过程中,对redis的查询、更新操作首先会在hash0中查找,没有找到,然后转到hash1中操作;

对于插入操作,直接插入到hash1中;最终目标是将hash表1变为空表,rehash完成;

value的存储

键值对的实现,value 是一个union,对整型和字符串使用不同的存储对象;

// 键
void *key;

// 值
union {
    void *val;
    uint64_t u64;
    int64_t s64;
} v;

ref:
《Hash 函数概览》http://www.oschina.net/translate/state-of-hash-functions

《redis设计与实现》



相关阅读 :
Redis哈希表的实现要点
Redis哈希
Hash(哈希表)
哈希表
关于redis Key淘汰策略的实现方法
redis哈希和集合_动力节点Java学院整理
redis哈希类型_动力节点Java学院整理
java客户端Jedis操作Redis Sentinel 连接池的实现方法
详解Redis用链表实现消息队列
session 加入redis的实现代码
ubuntu 系统上为php加上redis 扩展的实现方法
Java中使用Jedis操作Redis的实现代码
最新网友评论  共有(0)条评论 发布评论 返回顶部

Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  广告服务