Redis二进制位数组-Hamming Weight算法

BITCOUNT命令计算二进制位数组的一个步骤,是利用variable-precision SWAR算法来实现的,即计算Hamming Weight(简写为HW)的值。

https://www.cnblogs.com/NaLanZiYi-LinEr/p/11876246.html

{{{code

unit32_t swar(unit32_t i) {

//步骤1 每两个二进制位为一组进行分组,各组的十进制表示就是该组的HW

i = (i & 0x55555555) + ((i >> 1) & 0x55555555);

//步骤2 每四个二进制位为一组进行分组,各组的十进制表示就是该组的HW

i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

//步骤3 每八个二进制位为一组进行分组,各组的十进制表示就是该组的HW

i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);

//步骤4 i*0x01010101语句计算出HW并记录在二进制位的高八位,>> 24通过右移运算,将HW移动到最低八位,就是最终的HW

i = (i*0x01010101) >> 24;

return i;

}

/}}}

 

Redis设计与实现

一、简单动态字符串-SDS(10)√
1、sds跟c字符串的区别
二、链表-listNode(3)√
1、数据结构
三、字典(14)
1、扩容
2、收缩
3、渐进式rehash
四、跳跃表 skiplist(7)
1、有序集合的实现之一
2、节点层高是1~32的随机数
3、节点从小到大排序
五、整数集合(5)
1、集合键的底层实现之一
2、有序、无重复
3、支持升级,不支持降级
六、压缩列表(7)
1、列表键和哈希键的实现之一
2、可能引发连锁更新(250~253字节)
七、对象(28)
1、字符串对象:int、raw、embstr
2、列表对象:ziplist、linkedlist
3、哈希对象:ziplist、hashtable
4、集合对象:intset、hastable
5、有序集合对象:ziplist、skiplist
八、数据库(27)
1、由dict和expires两个字典组成,保存键值对和过期时间
2、使用惰性删除和定期删除两种策略
3、SAVE-阻塞服务器;BGSAVE-非阻塞
4、AOF、RDB都不会包含过期的键
九、RDB持久化(19)
1、保存所有键值对
2、压缩的二进制文件
3、满足任意一条保存条件时自动执行BGSAVE
十、AOF持久化(12)
1、保存所有命令请求,按照命令请求协议格式保存
2、重写可以产生一个新的AOF文件,并覆盖旧文件,但体积更小
3、BGREWRITEAOF会创建一个缓冲区,重写完成后追加到AOF文件末尾
十一、事件(10)
1、事件分为文件事件和时间时间
2、文件事件处理器基于Reactor模式实现
3、文件事件套接字:可应答、可写、可读;文件事件分为读事件和写事件
4、时间事件分为定期事件和周期性事件
5、serverCron函数是周期性事件
十二、客户端(12)
1、服务器数据结构里使用clients链表,连接多个客户端
2、输入缓冲区记录了客户端发送的命令
3、缓冲区分固定大小缓冲区和可变大小缓冲区
4、输出缓冲区分两种,硬限制和软限制
5、载入AOF文件使用伪客户端方式
十三、服务器(20)
1、命令的生命周期:发送-分析-查找命令函数-执行命令-返回结果
2、serverCron函数默认100毫秒执行一次
3、服务器启动:初始化状态-载入服务器配置-初始化服务器数据结构-还原数据库状态-执行事件循环
十四、复制(20)
1、部分重同步通过复制偏移量、复制积压缓冲区、服务器运行ID三个部分来实现
2、复制开始的时候,从服务器是主服务器的客户端;复制操作后期,主从服务器会互相成为对方的客户端
3、主服务器通过向从服务器传播命令来更新从服务器状态,保持主从一致;从服务器通过向主服务器发送命令来保持心跳,以及命令丢失检测
十五、Sentinel(25)
1、Sentinel会创建主服务器的命令连接和订阅(_sentinel:hello_)连接,sentinel之间只有命令连接
2、Sentinel会通过订阅频道自动发现其他sentinel的存在
3、Sentinel以1次/s的频率向实例发送ping命令,根据回复判断是否主观下线
3、判断主管下线时会询问其他sentinel是否同意,当手机到足够多的主观下线投票后,会将主服务器判定为客观下线,并发起故障转移操作
十六、集群(43)
1、集群中有16384个槽(0~16383),可以分别指派给各个节点,每个节点都会记录自己以及其他节点所指派的槽
2、节点接到一个命令后,会检查这个键对应的槽是否是自己,如果不是则返回moved错误,该错误可以指引客户端转向正在负责相关槽的节点
3、redis-trib负责重新分片,关键是将某个槽的所有键从一个节点转移到另一个节点
4、集群里从节点用于复制主节点,并在主节点下线时,代替主节点继续处理命令
5、节点通过接收和发送消息来通信,常见的消息有MEET PING PONG PUBLISH FAIL
十七、发布与订阅(14)
1、pubsub_channels和pubsub_pattens分别保存频道订阅和模式订阅的关系
2、SUBSCRIBE UNSUBSCRIBE两个命令处理频道订阅的关联和解除关系
3、PSUBSCRIBE PUNSUBSCRIBE两个命令处理模式订阅的关联和解除关系
4、PUSLISH 命令通过访问pubsub_channels字典来发送消息,通过访问pubsub_pattens链表来发送消息
十八、事物(15)
1、多个命令会被列入事务队列中,先进先出顺序执行
2、带有WATCH命令的事务,会将客户端和被监视的键在db.watched_keys字典中进行关联,当键被修改时client.flags REDIS_DIRTY_CAS会打开;cas打开时服务器会拒绝执行事务
3、reidis不支持事务回滚
十九、Lua脚本(21)
1、服务器启动时会对内嵌的Lua环境执行一系列的修改操作
2、Redis使用脚本字典保存所有被EVAL命令执行过的或者被SCRIPT LOAD命令载入过的脚本
3、EVAL命令为客户端输入的脚本在Lua环境中定义一个函数,通过调用这个函数来执行脚本
4、服务器执行脚本前会未Lua环境设置一个超时处理钩子,当出现超时后可以发送SCRIPT KILL通过钩子停止脚本;或者发送SHUTDOWN nosave命令让钩子关闭整个服务器
5、主服务器在复制EVALSHA命令时,必须确保所有从服务器已经载入了EVALSHA命令指定的脚本,否则主服务器会将EVALSHA命令替换成等效的EVAL命令
二十、排序(17)
1、SORT命令通过将被排序键包含的元素载入到数组里,然后对数组进行排序
2、SORT命令的排序操作由快速排序算法实现
3、SORT命令同时使用多个选项时,先执行排序操作(ALPHA、ASC、DESC、BY),然后执行LIMIT选项,之后执行GET选项,再之后执行STORE选项,除GET选项外,调整选项的顺序不会影响排序结果
二十一、二进制位数组(15)
1、使用SDS来保存位数组
2、使用逆序来保存,因为逆序简化了SETBIT命令的实现,可以在不移动现有二级制位的情况下,对数组进行扩展
3、BITCOUNT使用了查表法和variable-precision SWAR算法来优化命令的执行效率
4、BITOP命令包含,AND OR XOR NOT四种,使用C语言内置的位操作实现
二十二、慢查询日志(7)
1、慢查询日志记录在slowlog链表中
2、新的日志会添加在slowlog的表头,如果日志数量超过slowlog-max-len则删除
二十三、监视器(2)
1、monitor命令可以将客户端变成监视器,并打印所有服务器处理的命令请求
2、服务器将所有监视器记录在monitors链表中
3、服务器遍历链表发送命令给监视器