Memcached 与Redis (2): Redis 的数据类

1. Redis 与Memcached 的对比

1.1 数据Eviction

• 作用是删除旧数据来释放空间.
• Memcached 适用LRU(Least Recently Used) 来任意地腾出新数据需要的空间.
• Redis �适用惰性+定期策略来获取更好的控制.
  • 定时删除. 使用定时器对内存友好但是CPU不友好.
  • 惰性删除. 仅当取key时才进行删除. 对CPU友好.
  • 定期删除. 难点是确定删除操作执行的时长和频率.

1.2 存储的对象

• Memcached 中的key 要小于250B, value 要小于1MB. 且仅支持String 类型.
• Redis 中的key 和value 的最大尺寸都是512MB. 支持六种数据类型.

2. Redis 的数据类型

2.1 简单动态字符串(SDS: Simple Dynamic String)

• C字符串只用在只读的地方.
  • 获取长度复杂度为O(N).
  • 不记录长度导致很容易造成buffer overflow.
    • 典型的场景: strcat(s1,s2).
• SDS 结构体
  struct sdshdr = len + free + char[] buf;
  • 解决了C字符串的问题:
    • 获取字符串长度的复杂度为O(1).
    • 自动扩展的空间分配策略, 杜绝了发生buffer overflow的可能性.
  • 减少修改字符串时带来的内存重新分配次数.
    • 空间预分配.
      • 修改后,若SDS的长度小于1M, 那么free=len; 若大于1M, 那么free=1M.
      • 将连续增长N次字符串所需的内存重新分配次数减少为最多N次.
    • 惰性空间释放.
      • 优化SDS缩短操作. 使用free 记录缩短的字节.
      • 在有需要时,可以真正地释放free空间.
  • 二进制安全(char[]).
    • 可以保存任意格式的二进制数据.
    • C字符串必须符合某种编码,以\0结尾, 所以只能保存文本.
  • 兼容部分C字符串函数
    • 因为以\0为结尾.可以应用诸如strcasecmp,strcat 字符串的操作.

2.2 链表

typeof struct listNode { prev, next, value};
typeof struct list{ head, tail, len, dup, free, match};

• 特性:
  • 高效的节点重排, 顺序性的节点访问方式.
  • 双端,无环,多态.
  • 将一组value绑定到single key上.
  • 双向链表,支持反向查找和遍历.
• 适用场景:
  • 显式最新项目列表: 维持newest 100用户/新闻.
  • shared queue.
  • twitter的关注列表,粉丝列表.
  • 消息队列.

2.3 字典

dictEntry{ key, union{void*,int64_t,uint64_t} next};
dictht{ *table, size, sizemask, used};
dict{ type, privatedata, ht[2],trehashidx};

• 实现细节
  • type为类型特定函数(不同用途的字典有不同的特定函数).
  • ht[1]仅在做过rehash后才会有值.

• 哈希算法.
  • 先hashFunction(key)计算出hash值, 然后根据hash值和sizemask计算出在table中的索引值.
• 解决key collision.
  • 将hash值相同的多个key(使用next)链接成表.
• rehash. 当负载因子大于1时自动扩展,小于0.1时自动收缩.
  • load_factor = ht[0].used/ht[0].size.
  • 过程: 为ht[1]进行空间分配 -> 将h[0]上的键值对rehash后保存到ht[1]上 -> 释放ht[0] -> 交换ht[1/0].
• 渐进式rehash.
  • 在数据量大时,避免rehash对服务器性能造成影响.
  • 在rehash期间, 每次对字典的更新操作时, 顺带将rehashidx上的键值对rehash至ht[1]. 直至完成为-1.

2.4 跳跃表

  zskiplist{ header, tail, level, length}. 
  zskiplistNode{ level[], backward, score,obj}

• 实现细节
  • level不含header的层高, 等于前进指针 + 跨度.
    • 遍历时,会沿着前进指针进行.
    • 当创建节点时,根据power law(越大的树出现的概率越小),随机生成1~32j的level值.
    • 跨度用以计算rank. 在查找节点时,将访问过的层跨度累加就是rank.
  • backward 用于反项遍历时, 指向前一个节点.
    • 当只有一个时, 只能后退至前一个.
  • 节点按照score从小到大排列.
    • 相同score的多个节点, 以obj的字典序从小到大排序.

2.4 Set

• 无重复的List.

• 内部实现: value=null的HashMap. 通过计算hash来快速排重.
• 适用场景:
  • 跟踪friends/tags. 提供了判断某成员是否在set内的接口.
  • 所有粉丝,关注人的集合.交集,并集,差集,来实现共同关注,共同爱好.

2.5 Sorted Set

• 内部实现: HashMap(成员到score的映射)和SkipList(所有成员,获得较高的查找效率).
  • 每个value关联score字段,并使用score进行sort.
• 插入有序,自动排序.
• �适用场景:
  • score来跟踪时间序列,基于game score来rank player.
  • 高分跟踪.
  • 带权重的队列.

2.6 整数集合

  inset{ encoding, length, contents[]};

• 实现细节
  • encoding指定int16/32/64.
  • contents中值以从小到大排列, 且无重复.

• 升级: 添加的新元素超出现有encoding的max时.
  • 首先会扩充contents的空间.
  • 优势: 提升灵活性, 节省内存.
  • 同时,不支持降级.
  • 升级后, 编码会一直保持在升级后的状态.