Redis: Remote Dictionary Server
五种基础数据结构：string, list, hash, set, zset
1.基础数据结构
string
内部表示就是一个字符数组。动态的字符串，可修改，采用预分配冗余空间的方式来减少内存的频繁分配；扩容都是加倍的，最大长度是512M
//批量kv:
mset name1 boy name2 girl name3 unkown
mget name1 name2 name3
value为整数时可以incr，范围在signed long最小值和最大值之间，超过会报错。
bitmap(位图)：字符串有多个字节组成，每个字节由8bit组成，所以可以将一个字符串看作是多个bit组合
list
类似于java里的linkedlist（插入删除O(1)，查找O(n)）
- lindex:相当于java链表的get(index)，O(n)查找，性能低
- ltrim:start_index, end_index，截取一个区间
上述两个都是O(n)操作，性能低，慎用。
quickList:首先在列表元素特别少的情况下，会使用一块连续的内存存储：zipList（压缩列表），当数据多时才改成quickList，将多个ziplist串起来用：
ziplist <-> ziplist <-> ziplist ....
hash
相当于java里的hashmap,数组+链表
redis为了追求高性能，采用了渐进式rehash策略：在rehash时会保留两个hash结构，查询时会同时查询两个hash，然后在后续的定时任务及hash操作指令中循序渐进地将旧hash内容一点点迁移，迁移完了就用新hash。
- hset k k1 v1
- hincrby k k1 1
set
相当于java里的hashset
sadd, smembers, sismembers, scard
zset
相当于java sorted map和hashmap的结合体
可以存储粉丝列表，value用用户ID，score是关注时间
- zadd zrange books 0 -1 zscard
- zscore books 'java' //获取指定value的score
容器指型数据结构的通用规则：create时没有就创建，drop时没有就销毁
过期时间 key，当重新set后过期时间会失效
2.分布式锁
redis2.8版本中作者加入了set指令扩展参数setnx和expire可以在一起执行：set lock:key true ex5 nx
分布式锁不能解决超时问题
释放：
if(redis.call("get", KEYS[1]) == AVG[1]) then
return redis.call("del", KEYS[1])
else
return 0
end
可以实现可重入性锁：Map<key, count> ... threadlocal
3.延时队列
blpop/brpop：阻塞读，队列无数据时会进入休眠
实现：可以用zset：消息体序列化成一个字符串作为value，消息的到期处理时间作为score，用多个线程轮询获取到期时间的任务进行处理（多线程保证可用性）
4.位图
0 1 0 1 0 1
零存整取：
- setbit s 1 1
- setbit s 2 1
- setbit s 4 1
零取：
- getbit s 1
bitcount：指定范围内1的个数 ---- 可以统计用户签到多少天
bitpos：指定范围内出现的第一个0或者1 ---- 哪一天开始签到
bitfield：redis3.2以后支持
- bitfield key get u4 0 //从第1个位开始读取4位无符号
- bitfield key get i3 2 //从第3位开始读3位有符号
- bitfield key set u8 8 97 //从第9位开始将接下来的8个位用无符号97代替
- incrby 对指定范围的位进行自增操作，提供了溢出策略指令overflow，只影响接下来的第一条指令：
- wrap（折返）
- fail（报错不执行）
- sat（饱和截断）：超过范围就停留在最大/最小
5.HyperLogLog
非精确的去重计数方案，标准误差0.81%
- pfadd：增加计数
- pfcount：统计计数
- pfmerge：多个pf累加形成一个ps
它需要占据12KB的存储空间（不适合单用户数据去重）
原理？？？为啥需要12KB??
6.Bloom Filter
非精确的set，contains可能会误判
说某个值存在时 -> 不一定存在
说某个值不存在时 -> 一定不存在
redis4.0作为一个插件：bf.add，bf.exists，bf,madd，bf.mexists
size过大会浪费空间，过小误判率会提高
应用：
- 爬虫系统中对url进行去重，已经爬过的就不需要再爬了
- NoSql中降低IO请求
- 邮箱，垃圾邮件
7.限流
可以用redis进行简单限流：系统限定某个行为用户指定时间内只能发生N次
demo？？？
8.GeoHash
redis3.2增加了地理位置Geo模块
地图元素的位置数据使用二维经纬度表示，经度[-180, 180]，纬度[-90，90]
附近人：一般是通过矩形区域来限定元素数量，再排序：
select id from positions where x0 - r < x < x0 + r and y0 - r < y < y0 + r
但这种不适合高并发
业界较为通用的地理位置距离排序算法是Geohash（redis也是）：
二刀法：
00 | 01
————
10 | 11
redis里经纬度使用52位的整数进行编码放入zset中，zset的score是Geohash的52位整数，value是元素的key：
- 通过zset的score排序就可以获得坐标附近的其他元素；
- 通过score还原坐标值就可以得到元素的原始坐标。
使用？？？
9.SCAN
redis2.8以上版本支持
scan 0 match key* count 100
scan采用高位进位加法避免扩容/缩容时重复遍历或遗漏
- 普通加法：0000 -> 0001 -> 0010 -> 0011
- 高位进位加法：0000 -> 1000 -> 0100 -> 1100
tips:
a mod 8 == a & (8 - 1) == a & 7
a mod 16 == a & (16 - 1) == a & 15
a mod 32 == a & (32 - 1) == a & 31
10.字典扩容
采用渐进式rehash的方式
如何定位大Key:
- 使用scan对扫描出的每个key，使用type获取其类型，然后用对应数据结构的len或者size获得大小，将排名前n的返回
- redis-cli -h 127.0.0.1 -p 3679 --bigkeys -i 0.1 每隔100条scan指令就会休眠0.1秒
11.线程I/O模型
- 非阻塞I/O在套接字对象上提供了选项Non_Bloking
- 事件轮询（多路复用）
- 指令队列：redis将每个client socket都关联了一个指令队列，先到先服务
- 响应队列：。。。关联一个响应队列。。。
- 定时任务：被记录在一个最小堆中，最快要执行的在顶端。
12.通信协议
RESP：Redis Serialization Protocol
redis作者认为数据库的瓶颈在于自身逻辑而不在网络流量，单节点在跑满一个CPU核心下可达10w/s的qps
