月度归档:2013年10月

读了点 redis 的源码

很早之前边对 redis 有所耳闻,但了解不多,直到前不久看到《V2EX 从过去一年半中学到的几件事》这篇文章。文中提到 redis 可以替换掉 Mysql 而单独使用,吃惊了不少,准备下决心研究一下 redis. 加上前不久看过部分 twemcache (twemcache 是 twitter 的 memcache 改写版,以下简称 memcache)的源码,所以这里结合这两者分享一下心得。

redis 是一种纯内存的、key-value 的数据库,NO-SQL 的一种。它的 value 支持 string(字符串)、list(链表)、set(集合)、zset(sorted set –有序集合)和hashs(哈希类型)。redis  还支持持久化和主从复制。

相比之下,memcache 就纯粹多了。memcache 是一种纯内存的 key-value 缓存系统,value 类型只是一段 buffer,不支持持久化,不支持主从复制。

redis 和 memcache 都是使用 ANSI C 实现的,代码质量和可读性很高,非常有学习价值。

redis 中的数据结构

我读 redis 源码时主要读的是 redis 内部使用的一些基本数据结构。这些数据结构都是非常通用的。

sds:Simple Dynamic String,简单动态字符串。是 Redis 底层所使用的字符串表示, 它被用在几乎所有的 Redis 模块中。它很简单,就是一个带长度的、能自动扩展的、基于堆内存的字符串,并且兼容 C 中的字符串。

adlist: 双向链表,链表这东西已经被无数程序员实现过无数次了,无需多讲。

dict: 字典,有趣的是它扩容的过程。每个字典内部有两个 hash 表,一般用第一个,当发现 hash 表容量太大需要扩容时,创建第二个 hash 表。这时候不能一下子把第一个 hash 表里面的数据全部导入到第二个 hash 表,因为这样可能会导致阻塞。而是在每次执行查找或添加等操作时,从第一个 hash 表迁移一个节点到第二个 hash 表,这样像愚公移山一样直到扩容完毕。

skiplist: 跳跃表,这个数据结构也很有意思它,它是一种有序链表,加上随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。它的原理可以查看这篇文章 http://dsqiu.iteye.com/blog/1705530

ziplist: 一种压缩链表 ,使用压缩型的数据结构,减去指针的消耗,能够显著的减小对内存的使用。list, map, zset 在数据量小于特定值时,都是使用的 ziplist 以降低内存的消耗。

另外还有 intset, zipmap 等数据结构,不做多述。

 redis 的主从复制

redis 的 master, slaver 实现的可以说是相当优雅,浑然天成。关于主从复制与同步的问题,之前在工作中也遇到过,但苦于没找到一个更好的解决方案。主从结构的同步需要一次全量同步和后续的增量同步,同步的关键在于顺序,比如先 del 一个 key, 然后 add 这个 key, 如果同步成先 add 然后 del 的话,数据就不一致了。redis 的做法是,在收到同步请求之后,利用其持久化的能力,生成一个 RDB 内存 dump 文件,在生成 RDB 文件的同时,维护一个从这时候开始所有所有写操作的链表。RDB 文件生成好后,发送给 slaver, 然后再把生成 RDB 文件时所有的写操作命令发送给 slaver 执行 ,这样 slaver 就完成了一次全量更新。接下来 master 每次执行写操作时都会同步给 slaver。

redis 与 memcache

关于内存分配:memcache 的主要卖点便是其内存的分配。memcache 实现自己的内存分配是因为 glibc 自带的 malloc/free 性能太差,并且容易出现内存碎片。memcache 通过被称为 slab 的内存分配机制对内存进行管理。而 redis 没有自己分配内存,而是使用了第三方的内存分配器。redis 源码自带了 jemalloc, 也可以使用 google 的 tcmalloc, 这两者性能都很高,并且几乎 不会出现内存碎片问题。

关于事件处理:memcache 使用了开源的 libevent  进行事件的处理,包括网络IO和定时器。而 redis 则根据其不依赖的原则,实现了自己的事件处理库,对 epoll 等函数进行了封装。

关于配置:memcache 使用 getopt 进行命令行解析,只支持命令行参数形式配置,不支持配置文件。而 redis 同时支持配置文件和命令行。redis 解析命令行时,没有使用 getopt 等标准化命令行解析工具,而是自己通过 strcmp 进行解析,一开始觉得这个做法相当丑陋,后来发现自己误解了 redis 作者的苦衷了。redis 把除了 –help –version 等基本参数之外的其他 — 开头的参数,去除前面的 –,加入到一个字符串中。如果有配置文件,也把这个文件的内容一并读进这个字符串,然后由统一的函数对这个字符串进行配置解析。这样,就统一了配置文件和命令行参数,只要配置文件中有的,都可以通过命令行进行配置,个人觉得非常巧妙。

关于线程:memcache 是多线程的,由一个主线程处理连接,调度其他线程处理请求,充分利用多核 CPU 的能力。而 redis 是单进程的。严格说来,redis 是线程和进程混合的,它使用线程来进行 fsync ,也使用多进程利用 fork 的 copy-on-write 特性进实现 RDB 的持久化。但redis 在处理请求时,是单线程的。为什么不使用多线程,一个是因为对于处理内存数据,单线程已经够快了,另外,单线程能够提供一定的事务特征。为了充分利用资源可以在单台机器上起多个 redis 实例。

redis 的性能

redis 自带了基准测试工具 redis-benchmark 测试常用命令的性能,根据测试,一般的 GET SET 命令单 CLIENT 阻塞调用时,都可以达到上万次每秒,可以说大部分场合已经足够使用了。

参考:

redis 官方文档

Redis 设计与实现

Mysql 中的 utf8

最近遇到了一个奇怪的问题,在向  Mysql 插入一个 UTF-8 字符串时,字符串被截断了。打印 执行的 SQL 发现,是断在了一个无法显示的字符上。一开始怀疑是非法 UTF-8 编码,但通过 hexdump 发现,它是一个合法的 utf-8 字符,编码长度是 4 个字节。然后将其解码为 Unicode 编码,google 了一下,原来是一个 Emoji 表情(Emoji 是一种特殊的 Unicode 编码,常见于 ios 和 android 手机上)。

为什么遇到 Emoji 表情会被截断呢,在我的理解中,Mysql 的 utf8 应该可以接受任何合法的 UTF-8 字符串的。经同事提醒,Mysql 早期版本只支持最长 3 个字节的 UTF-8。查了下文档,果然如此:

  • utf8, a UTF-8 encoding of the Unicode character set using one to three bytes per character.

不只是老版本的 Mysql,最新版本的 Mysql 仍是如此。三个字节的 UTF-8 最大能编码的 Unicode 字符是 0xffff,也就是 Unicode 中的基本多文种平面(BMP)。也就是说,任何不在基本多文本平面的 Unicode字符,都无法使用 Mysql 的 utf8 字符集存储。包括上述的 Emoji 表情,和很多不常用的汉字,以及任何新增的 Unicode 字符等等。

此 utf8 非彼 UTF-8.

UTF-8 是 Unicode 的一种传输编码格式(8-bit Unicode Transformation Format)。最初的 UTF-8 格式使用一至六个字节,最大能编码 31 位字符。最新的 UTF-8 规范只使用一到四个字节,最大能编码21位,正好能够表示所有的 17个 Unicode 平面。

utf8 是 Mysql 中的一种字符集,只支持最长三个字节的 UTF-8字符,也就是 Unicode 中的基本多文本平面。

Mysql 中的 utf8 为什么只支持持最长三个字节的 UTF-8字符呢?我想了一下,可能是因为 Mysql 刚开始开发那会,Unicode 还没有辅助平面这一说呢。那时候,Unicode 委员会还做着 “65535 个字符足够全世界用了”的美梦。Mysql 中的字符串长度算的是字符数而非字节数,对于 CHAR 数据类型来说,需要为字符串保留足够的长。当使用 utf8 字符集时,需要保留的长度就是 utf8 最长字符长度乘以字符串长度,所以这里理所当然的限制了 utf8 最大长度为 3,比如 CHAR(100)  Mysql 会保留 300字节长度。至于后续的版本为什么不对 4 字节长度的 UTF-8 字符提供支持,我想一个是为了向后兼容性的考虑,还有就是基本多文种平面之外的字符确实很少用到。

要在 Mysql 中保存 4 字节长度的 UTF-8 字符,需要使用 utf8mb4 字符集,但只有 5.5 版本以后的才支持。我觉得,为了获取更好的兼容性,应该总是使用 utf8mb4 而非 utf8.  对于 CHAR 类型数据,utf8mb4 会多消耗一些空间,根据 Mysql 官方建议,使用 VARCHAR  替代 CHAR。

C 语言中的变长数组

或许这是很多 C 程序员都不知到的特性:C 语言中可以定义变长数组。也就是说,定义数组时,数组的长度可以是变量,而不一定非要是常量。比如:

    int len = 100;
    char str[len];

这个特性无疑是非常有用的。比如在不知到数组的长度时,要么定义一个足够大的数组,要么使用内存分配函数如 malloc 函数获取适当大小的内存,但需要记得 free. 使用变长数组,使得这个过程变得优雅和简化。

这个特性是在 C99 中加入 C 的标准中的,事实上,GNU C 在之前已经支持这种写法了。vc 对 C99 的支持一直不怎么热心,所以 VC 中并不支持这种写法。所以如果代码又跨平台的需求,最好不要使用变长数组,并且最好只使用 C89 的特征。

需要注意的是,变长数组只能是局部变量,不能是静态变量和全局变量,因为这两者的长度是编译时决定的,而变长数组的长度要到运行时才能确定。变长数组是局部变量,所以是有生命周期的,其生命周期仅在当前域内,即 {} 内。

变长数组使用的内存是栈内存,所以需要注意数组长度不能太大超过栈内存大小限制。linux 上可以用 ulimit -s 查看栈大小,一般为 8M.