分布式存储及应用系统架构分析 文件更改摘要: 修订记录 日期 修订说明 修订人 批准人 2010-4-4 创建 龙兴平 龙兴平 (MSN: lxp8@sina.com) 第 2 页 共 83 页 2010-4-27 目录 1 Memcached 1.1 Memcached 架构 memcached 是高性能的分布式内存缓存服务器。 一般的使用目的是,通过缓存数据库查询结 果,减少数据库访问次数,以提高动态 Web 应用的速度、 提高可扩展性。 龙兴平 (MSN: lxp8@sina.com) 第 3 页 共 83 页 2010-4-27 1.2 Memcache 实现分析理解 1.2.1 实现结构 Speed Of course, the primary motivation for caching is speed, so Memcached is designed to be as fast as possible. The initial prototype of Memcached was written in Perl. Although I love Perl, the prototype was laughably slow and bloated. Perl trades off memory usage for everything, so a lot of precious memory was wasted, and Perl can't handle tons of network connections at once. The current version is written in C as a single-process, single-threaded, asynchronous I/O, event-based d?mon. For portability and speed, we use libevent (see the on-line Resources section) for event notification. The advantage of libevent is that it picks the best available strategy for dealing with file descriptors at runtime. For example, it chooses kqueue on BSD and epoll on Linux 2.6, which are efficient when dealing with thousands of concurrent connections. On other systems, libevent falls back to the traditional poll and select methods. Inside Memcached, all algorithms are O(1). That is, the runtime of the algorithms and CPU used never varies with the number of concurrent clients, at least when using kqueue or epoll, or with the size of the data or any other factor. Of note, Memcached uses a slab allocator for memory allocation. Early versions of Memcached used the malloc from glibc and ended up falling on their faces after about a week, eating up a lot of CPU space due to address space fragmentation. A slab allocator allocates only large chunks of memory, slicing them up into little chunks for particular classes of items, then maintaining 龙兴平 (MSN: lxp8@sina.com) 第 4 页 共 83 页 2010-4-27 freelists for each class whenever an object is freed. See the Bonwick paper in Resources for more details. Memcached currently generates slab classes for all power-of-two sizes from 64 bytes to 1MB, and it allocates an object of the smallest size that can hold a submitted item. As a result of using a slab allocator, we can guarantee performance over any length of time. Indeed, we've had production Memcached servers up for 4–5 months at a time, averaging 7,000 queries/second, without problems and maintaining consistently low CPU usage. Another key requirement for Memcached was that it be lockless. All objects are multiversioned internally and reference counted, so no client can block any other client's actions. If one client is updating an object stored in Memcached while a dozen others are downloading it, even with one client on a lossy network connection dropping half its packets, nobody has to wait for anybody else. A final optimization worth noting is that the protocol allows fetching multiple keys at once. This is useful if your application knows it needs to load a few hundred keys. Instead of retrieving them all sequentially, which would take a fraction of a second in network round-trips, the application can fetch them all in one request. When necessary, the client libraries automatically split multi-key loads from the application into separate parallel multi-key loads to the Memcached instances. Alternatively, applications can provide explicit hash values with keys to keep groups of data on the same instance. That also saves the client library a bit of CPU time by not needing to calculate hash values. Ref: http://www.linuxjournal.com/article/7451?page=0,2 Memcached 是 danga.com(运营 LiveJournal 的技术团队)开发的一套分布式内存对象缓存 系统,用于在动态系统中减少数据库负载,提升性能。关于这个东西,相信很多人都用过, 本文意在通过对 memcached 的实现及代码分析,获得对这个出色的开源软件更深入的了解, 并可以根据我们的需要对其进行更进一步的优化。末了将通过对 BSM_Memcache 扩展的分 析,加深对 memcached 的使用方式理解。 本文的部分内容可能需要比较好的数学基础作为辅助。 ◎Memcached 是什么 在阐述这个问题之前,我们首先要清楚它“不是什么”。很多人把它当作和 SharedMemory 那种形式的存储载体来使用,虽然 memcached 使用了同样的“Key=>Value”方式组织数据, 但是它和共享内存、APC 等本地缓存有非常大的区别。Memcached 是分布式的,也就是说 它不是本地的。它基于网络连接(当然它也可以使用 localhost)方式完成服务,本身它是一 个独立于应用的程序或守护进程(Daemon 方式)。 Memcached 使用 libevent 库实现网络连接服务,理论上可以处理无限多的连接,但是它和 Apache 不同,它更多的时候是面向稳定的持续连接的,所以它实际的并发能力是有限制的。 在保守情况下 memcached 的最大同时连接数为 200,这和 Linux 线程能力有关系,这个数值 龙兴平 (MSN: lxp8@sina.com) 第 5 页 共 83 页 2010-4-27 是可以调整的。关于 libevent 可以参考相关文档。 Memcached 内存使用方式也和 APC 不同。 APC 是基于共享内存和 MMAP 的,memcachd 有自己的内存分配算法和管理方式,它和共 享内存没有关系,也没有共享内存的限制,通常情况下,每个 memcached 进程可以管理 2GB 的内存空间,如果需要更多的空间,可以增加进程数。 ◎Memcached 适合什么场合 在很多时候,memcached 都被滥用了,这当然少不了对它的抱怨。我经常在论坛上看见有 人发贴,类似于“如何提高效率”,回复是“用 memcached”,至于怎么用,用在哪里,用 来干什么一句没有。memcached 不是万能的,它也不是适用在所有场合。 Memcached 是“分布式”的内存对象缓存系统,那么就是说,那些不需要“分布”的,不 需要共享的,或者干脆规模小到只有一台服务器的应用,memcached 不会带来任何好处, 相反还会拖慢系统效率,因为网络连接同样需要资源,即使是 UNIX 本地连接也一样。 在 我之前的测试数据中显示,memcached 本地读写速度要比直接 PHP 内存数组慢几十倍,而 APC、共享内存方式都和直接数组差不多。可见,如果只是本地级缓存,使用 memcached 是非常不划算的。 Memcached 在很多时候都是作为数据库前端 cache 使用的。因为它比数据库少了很多 SQL 解析、磁盘操作等开销,而且它是使用内存来管理数据的,所以它可以提供比直接读取数 据库更好的性能,在大型系统中,访问同样的数据是很频繁的,memcached 可以大大降低 数据库压力,使系统执行效率提升。另外,memcached 也经常作为服务器之间数据共享的 存储媒介,例如在 SSO 系统中保存系统单点登陆状态的数据就可以保存在 memcached 中, 被多个应用共享。 需要注意的是,memcached 使用内存管理数据,所以它是易失的,当服务器重启,或者 memcached 进程中止,数据便会丢失,所以 memcached 不能用来持久保存数据。很多人的 错误理解,memcached 的性能非常好,好到了内存和硬盘的对比程度,其实 memcached 使 用内存并不会得到成百上千的读写速度提高,它的实际瓶颈在于网络连接,它和使用磁盘 的数据库系统相比,好处在于它本身非常“轻”,因为没有过多的开销和直接的读写方式, 它可以轻松应付非常大的数据交换量,所以经常会出现两条千兆网络带宽都满负荷了, memcached 进程本身并不占用多少 CPU 资源的情况。 ◎Memcached 的工作方式 以下的部分中,读者最好能准备一份 memcached 的源代码。 Memcached 是传统的网络服务程序,如果启动的时候使用了-d 参数,它会以守护进程的方 式执行。创建守护进程由 daemon.c 完成,这个程序只有一个 daemon 函数,这个函数很简 单(如无特殊说明,代码以 1.2.1 为准): CODE: #include #include 龙兴平 (MSN: lxp8@sina.com) 第 6 页 共 83 页 2010-4-27 #include int daemon(nochdir, noclose) int nochdir, noclose; { int fd; switch (fork()) { case -1: return (-1); case 0: break; default: _exit(0); } if (setsid() == -1) return (-1); if (!nochdir) (void)chdir(”/”); if (!noclose && (fd = open(”/dev/null”, O_RDWR, 0)) != -1) { (void)dup2(fd, STDIN_FILENO); (void)dup2(fd, STDOUT_FILENO); (void)dup2(fd, STDERR_FILENO); if (fd > STDERR_FILENO) (void)close(fd); } return (0); } 这个函数 fork 了整个进程之后,父进程就退出,接着重新定位 STDIN 、 STDOUT 、 STDERR 到空设备, daemon 就建立成功了。 Memcached 本身的启动过程,在 memcached.c 的 main 函数中顺序如下: 1 、调用 settings_init() 设定初始化参数 2 、从启动命令中读取参数来设置 setting 值 3 、设定 LIMIT 参数 4 、开始网络 socket 监听(如果非 socketpath 存在)( 1.2 之后支持 UDP 方式) 5 、检查用户身份( Memcached 不允许 root 身份启动) 6 、如果有 socketpath 存在,开启 UNIX 本地连接(Sock 管道) 7 、如果以 -d 方式启动,创建守护进程(如上调用 daemon 函数) 龙兴平 (MSN: lxp8@sina.com) 第 7 页 共 83 页 2010-4-27 8 、初始化 item 、 event 、状态信息、 hash 、连接、 slab 9 、如设置中 managed 生效,创建 bucket 数组 10 、检查是否需要锁定内存页 11 、初始化信号、连接、删除队列 12 、如果 daemon 方式,处理进程 ID 13 、event 开始,启动过程结束, main 函数进入循环。 在 daemon 方式中,因为 stderr 已经被定向到黑洞,所以不会反馈执行中的可见错误信息。 memcached.c 的主循环函数是 drive_machine ,传入参数是指向当前的连接的结构指针,根 据 state 成员的状态来决定动作。 Memcached 使用一套自定义的协议完成数据交换,它的 protocol 文档可以参考: http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt 在 API 中,换行符号统一为\r\n ◎Memcached 的内存管理方式 Memcached 有一个很有特色的内存管理方式,为了提高效率,它使用预申请和分组的方式 管理内存空间,而并不是每次需要写入数据的时候去 malloc,删除数据的时候 free 一个指 针。Memcached 使用 slab->chunk 的组织方式管理内存。 1.1 和 1.2 的 slabs.c 中的 slab 空间划分算法有一些不同,后面会分别介绍。 Slab 可以理解为一个内存块,一个 slab 是 memcached 一次申请内存的最小单位,在 memcached 中,一个 slab 的大小默认为 1048576 字节 (1MB), 所以 memcached 都是整 MB 的使用内存。每一个 slab 被划分为若干个 chunk,每个 chunk 里保存一个 item,每个 item 同时包含了 item 结构体、key 和 value(注意在 memcached 中的 value 是只有字符串的)。slab 按照自己的 id 分别组成链表,这些链表又按 id 挂在一个 slabclass 数组上,整个结构看起来 有点像二维数组。slabclass 的长度在 1.1 中是 21,在 1.2 中是 200。 slab 有一个初始 chunk 大小,1.1 中是 1 字节,1.2 中是 80 字节,1.2 中有一个 factor 值,默 认为 1.25 在 1.1 中,chunk 大小表示为初始大小*2^n,n 为 classid,即:id 为 0 的 slab,每 chunk 大 小 1 字节,id 为 1 的 slab,每 chunk 大小 2 字节,id 为 2 的 slab,每 chunk 大小 4 字节…… id 为 20 的 slab,每 chunk 大小为 1MB,就是说 id 为 20 的 slab 里只有一个 chunk: CODE: void slabs_init(size_t limit) { int i; int size=1; 龙兴平 (MSN: lxp8@sina.com) 第 8 页 共 83 页 2010-4-27 mem_limit = limit; for(i=0; i<=POWER_LARGEST; i++, size*=2) { slabclass[i].size = size; slabclass[i].perslab = POWER_BLOCK / size; slabclass[i].slots = 0; slabclass[i].sl_curr = slabclass[i].sl_total = slabclass[i].slabs = 0; slabclass[i].end_page_ptr = 0; slabclass[i].end_page_free = 0; slabclass[i].slab_list = 0; slabclass[i].list_size = 0; slabclass[i].killing = 0; } /* for the test suite: faking of how much we’ve already malloc’d */ { char *t_initial_malloc = getenv(”T_MEMD_INITIAL_MALLOC”); if (t_initial_malloc) { mem_malloced = atol(getenv(”T_MEMD_INITIAL_MALLOC”)); } } /* pre-allocate slabs by default, unless the environment variable for testing is set to something non-zero */ { char *pre_alloc = getenv(”T_MEMD_SLABS_ALLOC”); if (!pre_alloc || atoi(pre_alloc)) { slabs_preallocate(limit / POWER_BLOCK); } } } 在 1.2 中,chunk 大小表示为初始大小*f^n,f 为 factor,在 memcached.c 中定义,n 为 classid, 同时,201 个头不是全部都要初始化的,因为 factor 可变,初始化只循环到计算出的大小达 到 slab 大小的一半为止,而且它是从 id1 开始的,即:id 为 1 的 slab,每 chunk 大小 80 字 节,id 为 2 的 slab,每 chunk 大小 80*f,id 为 3 的 slab,每 chunk 大小 80*f^2,初始化大小 有一个修正值 CHUNK_ALIGN_BYTES ,用来保证 n-byte 排列 (保证结果是 CHUNK_ALIGN_BYTES 的整倍数)。这样,在标准情况下,memcached1.2 会初始化到 id40, 这个 slab 中每个 chunk 大小为 504692,每个 slab 中有两个 chunk。最后,slab_init 函数会在 最后补足一个 id41,它是整块的,也就是这个 slab 中只有一个 1MB 大的 chunk: CODE: void slabs_init(size_t limit, double factor) { int i = POWER_SMALLEST – 1; unsigned int size = sizeof(item) + settings.chunk_size; 龙兴平 (MSN: lxp8@sina.com) 第 9 页 共 83 页 2010-4-27 /* Factor of 2.0 means use the default memcached behavior */ if (factor == 2.0 && size < 128) size = 128; mem_limit = limit; memset(slabclass, 0, sizeof(slabclass)); while (++i < POWER_LARGEST && size <= POWER_BLOCK / 2) { /* Make sure items are always n-byte aligned */ if (size % CHUNK_ALIGN_BYTES) size += CHUNK_ALIGN_BYTES – (size % CHUNK_ALIGN_BYTES); slabclass[i].size = size; slabclass[i].perslab = POWER_BLOCK / slabclass[i].size; size *= factor; if (settings.verbose > 1) { fprintf(stderr, “slab class %3d: chunk size %6d perslab %5d\n”, i, slabclass[i].size, slabclass[i].perslab); } } power_largest = i; slabclass[power_largest].size = POWER_BLOCK; slabclass[power_largest].perslab = 1; /* for the test suite: faking of how much we’ve already malloc’d */ { char *t_initial_malloc = getenv(”T_MEMD_INITIAL_MALLOC”); if (t_initial_malloc) { mem_malloced = atol(getenv(”T_MEMD_INITIAL_MALLOC”)); } } #ifndef DONT_PREALLOC_SLABS { char *pre_alloc = getenv(”T_MEMD_SLABS_ALLOC”); if (!pre_alloc || atoi(pre_alloc)) { slabs_preallocate(limit / POWER_BLOCK); } } #endif } 龙兴平 (MSN: lxp8@sina.com) 第 10 页 共 83 页 2010-4-27 由上可以看出,memcached 的内存分配是有冗余的,当一个 slab 不能被它所拥有的 chunk 大小整除时,slab 尾部剩余的空间就被丢弃了,如 id40 中,两个 chunk 占用了 1009384 字 节,这个 slab 一共有 1MB,那么就有 39192 字节被浪费了。 Memcached 使用这种方式来分配内存,是为了可以快速的通过 item 长度定位出 slab 的 classid,有一点类似 hash,因为 item 的长度是可以计算的,比如一个 item 的长度是 300 字 节, 在 1.2 中就可以得到它应该保存在 id7 的 slab 中,因为按照上面的计算方法,id6 的 chunk 大小是 252 字节,id7 的 chunk 大小是 316 字节,id8 的 chunk 大小是 396 字节,表示所有 252 到 316 字节的 item 都应该保存在 id7 中。同理,在 1.1 中,也可以计算得到它出于 256 和 512 之间,应该放在 chunk_size 为 512 的 id9 中(32 位系统)。 Memcached初始化的时候,会初始化 slab(前面可以看到,在 main 函数中调用了 slabs_init())。 它会在 slabs_init()中检查一个常量 DONT_PREALLOC_SLABS,如果这个没有被定义,说 明使用预分配内存方式初始化 slab,这样在所有已经定义过的 slabclass 中,每一个 id 创建 一个 slab。这样就表示,1.2 在默认的环境中启动进程后要分配 41MB 的 slab 空间,在这个 过程里,memcached 的第二个内存冗余发生了,因为有可能一个 id 根本没有被使用过,但 是它也默认申请了一个 slab,每个 slab 会用掉 1MB 内存 当一个 slab 用光后,又有新的 item 要插入这个 id,那么它就会重新申请新的 slab,申请新 的 slab 时,对应 id 的 slab 链表就要增长,这个链表是成倍增长的,在函数 grow_slab_list 函数中,这个链的长度从 1 变成 2,从 2 变成 4,从 4 变成 8……: CODE: static int grow_slab_list (unsigned int id) { slabclass_t *p = &slabclass[id]; if (p->slabs == p->list_size) { size_t new_size = p->list_size ? p->list_size * 2 : 16; void *new_list = realloc(p->slab_list, new_size*sizeof(void*)); if (new_list == 0) return 0; p->list_size = new_size; p->slab_list = new_list; } return 1; } 在定位 item 时,都是使用 slabs_clsid 函数,传入参数为 item 大小,返回值为 classid,由这 个过程可以看出,memcached 的第三个内存冗余发生在保存 item 的过程中,item 总是小于 或等于 chunk 大小的,当 item 小于 chunk 大小时,就又发生了空间浪费。 ◎Memcached 的 NewHash 算法 Memcached 的 item 保存基于一个大的 hash 表,它的实际地址就是 slab 中的 chunk 偏移,但 是它的定位是依靠对 key 做 hash 的结果,在 primary_hashtable 中找到的。在 assoc.c 和 items.c 中定义了所有的 hash 和 item 操作。 龙兴平 (MSN: lxp8@sina.com) 第 11 页 共 83 页 2010-4-27 Memcached 使用了一个叫做 NewHash 的算法,它的效果很好,效率也很高。1.1 和 1.2 的 NewHash 有一些不同,主要的实现方式还是一样的,1.2 的 hash 函数是经过整理优化的, 适应性更好一些。 NewHash 的原型参考:http://burtleburtle.net/bob/hash/evahash.html。数学家总是有点奇怪, 呵呵~ 为了变换方便,定义了 u4 和 u1 两种数据类型,u4 就是无符号的长整形,u1 就是无符号 char(0-255)。 具体代码可以参考 1.1 和 1.2 源码包。 注意这里的 hashtable 长度,1.1 和 1.2 也是有区别的,1.1 中定义了 HASHPOWER 常量为 20,hashtable 表长为 hashsize(HASHPOWER),就是 4MB(hashsize 是一个宏,表示 1 右移 n 位) , 1.2 中是变量 16,即 hashtable 表长 65536: CODE: typedef unsigned long int ub4; /* unsigned 4-byte quantities */ typedef unsigned char ub1; /* unsigned 1-byte quantities */ #define hashsize(n) ((ub4)1<<(n)) #define hashmask(n) (hashsize(n)-1) 在 assoc_init()中,会对 primary_hashtable 做初始化,对应的 hash 操作包括:assoc_find()、 assoc_expand()、assoc_move_next_bucket()、assoc_insert()、assoc_delete(),对应于 item 的读 写操作。其中 assoc_find()是根据 key 和 key 长寻找对应的 item 地址的函数(注意在 C 中, 很多时候都是同时直接传入字符串和字符串长度,而不是在函数内部做 strlen),返回的是 item 结构指针,它的数据地址在 slab 中的某个 chunk 上。 items.c 是数据项的操作程序,每一个完整的 item 包括几个部分,在 item_make_header()中定 义为: key:键 nkey:键长 flags:用户定义的 flag(其实这个 flag 在 memcached 中没有启用) nbytes:值长(包括换行符号\r\n) suffix:后缀 Buffer nsuffix:后缀长 一个完整的 item 长度是键长+值长+后缀长+item 结构大小(32 字节),item 操作就是根 据这个长度来计算 slab 的 classid 的。 hashtable 中的每一个桶上挂着一个双链表,item_init()的时候已经初始化了 heads、tails、sizes 三个数组为0,这三个数组的大小都为常量LARGEST_ID(默认为255,这个值需要配合factor 来修改),在每次 item_assoc()的时候,它会首先尝试从 slab 中获取一块空闲的 chunk,如果 龙兴平 (MSN: lxp8@sina.com) 第 12 页 共 83 页 2010-4-27 没有可用的 chunk,会在链表中扫描 50 次,以得到一个被 LRU 踢掉的 item,将它 unlink, 然后将需要插入的 item 插入链表中。 注意 item 的 refcount 成员。item 被 unlink 之后只是从链表上摘掉,不是立刻就被 free 的, 只是将它放到删除队列中(item_unlink_q()函数)。 item 对应一些读写操作,包括 remove、update、replace,当然最重要的就是 alloc 操作。 item 还有一个特性就是它有过期时间,这是 memcached 的一个很有用的特性,很多应用都 是依赖于 memcached 的 item 过期,比如 session 存储、操作锁等。item_flush_expired()函数 就是扫描表中的 item,对过期的 item 执行 unlink 操作,当然这只是一个回收动作,实际上 在 get 的时候还要进行时间判断: CODE: /* expires items that are more recent than the oldest_live setting. */ void item_flush_expired() { int i; item *iter, *next; if (! settings.oldest_live) return; for (i = 0; i < LARGEST_ID; i++) { /* The LRU is sorted in decreasing time order, and an item’s timestamp * is never newer than its last access time, so we only need to walk * back until we hit an item older than the oldest_live time. * The oldest_live checking will auto-expire the remaining items. */ for (iter = heads[i]; iter != NULL; iter = next) { if (iter->time >= settings.oldest_live) { next = iter->next; if ((iter->it_flags & ITEM_SLABBED) == 0) { item_unlink(iter); } } else { /* We’ve hit the first old item. Continue to the next queue. */ break; } } } } CODE: /* wrapper around assoc_find which does the lazy expiration/deletion logic */ item *get_item_notedeleted(char *key, size_t nkey, int *delete_locked) { 龙兴平 (MSN: lxp8@sina.com) 第 13 页 共 83 页 2010-4-27 item *it = assoc_find(key, nkey); if (delete_locked) *delete_locked = 0; if (it && (it->it_flags & ITEM_DELETED)) { /* it’s flagged as delete-locked. let’s see if that condition is past due, and the 5-second delete_timer just hasn’t gotten to it yet… */ if (! item_delete_lock_over(it)) { if (delete_locked) *delete_locked = 1; it = 0; } } if (it && settings.oldest_live && settings.oldest_live <= current_time && it->time <= settings.oldest_live) { item_unlink(it); it = 0; } if (it && it->exptime && it->exptime <= current_time) { item_unlink(it); it = 0; } return it; } Memcached 的内存管理方式是非常精巧和高效的,它很大程度上减少了直接 alloc 系统内存 的次数,降低函数开销和内存碎片产生几率,虽然这种方式会造成一些冗余浪费,但是这 种浪费在大型系统应用中是微不足道的。 ◎Memcached 的理论参数计算方式 影响 memcached 工作的几个参数有: 常量 REALTIME_MAXDELTA 60*60*24*30 最大 30 天的过期时间 conn_init()中的 freetotal(=200) 最大同时连接数 常量 KEY_MAX_LENGTH 250 最大键长 settings.factor(=1.25) factor 将影响 chunk 的步进大小 settings.maxconns(=1024) 龙兴平 (MSN: lxp8@sina.com) 第 14 页 共 83 页 2010-4-27 最大软连接 settings.chunk_size(=48) 一个保守估计的 key+value 长度,用来生成 id1 中的 chunk 长度(1.2)。 id1 的 chunk 长度等 于这个数值加上 item 结构体的长度(32),即默认的 80 字节。 常量 POWER_SMALLEST 1 最小 classid(1.2) 常量 POWER_LARGEST 200 最大 classid(1.2) 常量 POWER_BLOCK 1048576 默认 slab 大小 常量 CHUNK_ALIGN_BYTES (sizeof(void *)) 保证 chunk 大小是这个数值的整数倍,防止越界(void *的长度在不同系统上不一样,在标 准 32 位系统上是 4) 常量 ITEM_UPDATE_INTERVAL 60 队列刷新间隔 常量 LARGEST_ID 255 最大 item 链表数(这个值不能比最大的 classid 小) 变量 hashpower(在 1.1 中是常量 HASHPOWER) 决定 hashtable 的大小 根据上面介绍的内容及参数设定,可以计算出的一些结果: 1、在 memcached 中可以保存的 item 个数是没有软件上限的,之前我的 100 万的说法是错 误的。 2、假设 NewHash 算法碰撞均匀,查找 item 的循环次数是 item 总数除以 hashtable 大小(由 hashpower 决定),是线性的。 3、Memcached 限制了可以接受的最大 item 是 1MB,大于 1MB 的数据不予理会。 4、Memcached 的空间利用率和数据特性有很大的关系,又与 DONT_PREALLOC_SLABS 常量有关。 在最差情况下,有 198 个 slab 会被浪费(所有 item 都集中在一个 slab 中,199 个 id 全部分配满)。 ◎Memcached 的定长优化 根据上面几节的描述,多少对 memcached 有了一个比较深入的认识。在深入认识的基础上 才好对它进行优化。 龙兴平 (MSN: lxp8@sina.com) 第 15 页 共 83 页 2010-4-27 Memcached 本身是为变长数据设计的,根据数据特性,可以说它是“面向大众”的设计, 但是很多时候,我们的数据并不是这样的“普遍”,典型的情况中,一种是非均匀分布,即 数据长度集中在几个区域内(如保存用户 Session);另一种更极端的状态是等长数据(如 定长键值,定长数据,多见于访问、在线统计或执行锁)。 这里主要研究一下定长数据的优化方案(1.2),集中分布的变长数据仅供参考,实现起来也 很容易。 解决定长数据,首先需要解决的是 slab 的分配问题,第一个需要确认的是我们不需要那么 多不同 chunk 长度的 slab,为了最大限度地利用资源,最好 chunk 和 item 等长,所以首先 要计算 item 长度。 在之前已经有了计算 item 长度的算法,需要注意的是,除了字符串长度外,还要加上 item 结构的长度 32 字节。 假设我们已经计算出需要保存 200 字节的等长数据。 接下来是要修改 slab 的 classid 和 chunk 长度的关系。在原始版本中,chunk 长度和 classid 是有对应关系的,现在如果把所有的 chunk 都定为 200 个字节,那么这个关系就不存在了, 我们需要重新确定这二者的关系。一种方法是,整个存储结构只使用一个固定的 id,即只 使用 199 个槽中的 1 个,在这种条件下,就一定要定义 DONT_PREALLOC_SLABS 来避免 另外的预分配浪费。另一种方法是建立一个 hash 关系,来从 item 确定 classid,不能使用长 度来做键,可以使用 key 的 NewHash 结果等不定数据,或者直接根据 key 来做 hash(定长 数据的 key 也一定等长)。这里简单起见,选择第一种方法,这种方法的不足之处在于只使 用一个 id,在数据量非常大的情况下,slab 链会很长(因为所有数据都挤在一条链上了), 遍历起来的代价比较高。 前面介绍了三种空间冗余,设置 chunk 长度等于 item 长度,解决了第一种空间浪费问题, 不预申请空间解决了第二种空间浪费问题,那么对于第一种问题(slab 内剩余)如何解决呢, 这就需要修改 POWER_BLOCK 常量,使得每一个 slab 大小正好等于 chunk 长度的整数倍, 这样一个 slab 就可以正好划分成 n 个 chunk。这个数值应该比较接近 1MB,过大的话同样 会造成冗余,过小的话会造成次数过多的 alloc,根据 chunk 长度为 200,选择 1000000 作为 POWER_BLOCK 的值,这样一个 slab 就是 100 万字节,不是 1048576。三个冗余问题都解 决了,空间利用率会大大提升。 修改 slabs_clsid 函数,让它直接返回一个定值(比如 1 ): CODE: unsigned int slabs_clsid(size_t size) { return 1; } 修改 slabs_init 函数,去掉循环创建所有 classid 属性的部分,直接添加 slabclass[1]: CODE: 龙兴平 (MSN: lxp8@sina.com) 第 16 页 共 83 页 2010-4-27 slabclass[1].size = 200; //每 chunk200 字节 slabclass[1].perslab = 5000; //1000000/200 ◎Memcached 客户端 Memcached 是一个服务程序,使用的时候可以根据它的协议,连接到 memcached 服务器上, 发送命令给服务进程,就可以操作上面的数据。为了方便使用,memcached 有很多个客户 端程序可以使用,对应于各种语言,有各种语言的客户端。基于 C 语言的有 libmemcache、 APR_Memcache;基于 Perl 的有 Cache::Memcached;另外还有 Python、Ruby、Java、C#等 语言的支持。PHP 的客户端是最多的,不光有 mcache 和 PECL memcache 两个扩展,还有 大把的由 PHP 编写的封装类,下面介绍一下在 PHP 中使用 memcached 的方法: mcache 扩展是基于 libmemcache 再封装的。libmemcache 一直没有发布 stable 版本,目前版 本是 1.4.0-rc2,可以在这里找到。libmemcache 有一个很不好的特性,就是会向 stderr 写很 多错误信息,一般的,作为 lib 使用的时候,stderr 一般都会被定向到其它地方,比如 Apache 的错误日志,而且 libmemcache 会自杀,可能会导致异常,不过它的性能还是很好的。 mcache 扩展最后更新到 1.2.0-beta10,作者大概是离职了,不光停止更新,连网站也打不开 了(~_~),只能到其它地方去获取这个不负责的扩展了。解压后安装方法如常:phpize & configure & make & make install,一定要先安装 libmemcache。使用这个扩展很简单: CODE: add_server(‘localhost’, 11211); // 添加一个服务进程 $mc->add_server(‘localhost’, 11212); // 添加第二个服务进程 $mc->set(‘key1′, ‘Hello’); // 写入 key1 => Hello $mc->set(‘key2′, ‘World’, 10); // 写入 key2 => World,10 秒过期 $mc->set(‘arr1′, array(‘Hello’, ‘World’)); // 写入一个数组 $key1 = $mc->get(‘key1′); // 获取’key1′的值,赋给$key1 $key2 = $mc->get(‘key2′); // 获取’key2′的值,赋给$key2,如果超过 10 秒,就取 不到了 $arr1 = $mc->get(‘arr1′); // 获取’arr1′数组 $mc->delete(‘arr1′); // 删除’arr1′ $mc->flush_all(); // 删掉所有数据 $stats = $mc->stats(); // 获取服务器信息 var_dump($stats); // 服务器信息是一个数组 ?> 这个扩展的好处是可以很方便地实现分布式存储和负载均衡,因为它可以添加多个服务地 址,数据在保存的时候是会根据 hash 结果定位到某台服务器上的,这也是 libmemcache 的 特性。libmemcache 支持集中 hash 方式,包括 CRC32、ELF 和 Perl hash。 PECL memcache 是 PECL 发布的扩展,目前最新版本是 2.1.0,可以在 pecl 网站得到。 memcache 扩展的使用方法可以在新一些的 PHP 手册中找到,它和 mcache 很像,真的很像: 龙兴平 (MSN: lxp8@sina.com) 第 17 页 共 83 页 2010-4-27 CODE: connect(‘localhost’, 11211) or die (“Could not connect”); $version = $memcache->getVersion(); echo “Server’s version: ”.$version.“n”; $tmp_object = new stdClass; $tmp_object->str_attr = ‘test’; $tmp_object->int_attr = 123; $memcache->set(‘key’, $tmp_object, false, 10) or die (“Failed to save data at the server”); echo “Store data in the cache (data will expire in 10 seconds)n”; $get_result = $memcache->get(‘key’); echo “Data from the cache:n”; var_dump($get_result); ?> 这个扩展是使用 php 的 stream 直接连接 memcached 服务器并通过 socket 发送命令的。它不 像 libmemcache 那样完善,也不支持 add_server 这种分布操作,但是因为它不依赖其它的外 界程序,兼容性要好一些,也比较稳定。至于效率,差别不是很大。 另外,有很多的 PHP class 可以使用,比如 MemcacheClient.inc.php,phpclasses.org 上可以找 到很多,一般都是对 perl client API 的再封装,使用方式很像。 ◎BSM_Memcache 从 C client 来说,APR_Memcache 是一个很成熟很稳定的 client 程序,支持线程锁和原子级 操作,保证运行的稳定性。不过它是基于 APR 的( APR 将在最后一节介绍),没有 libmemcache 的应用范围广,目前也没有很多基于它开发的程序,现有的多是一些 Apache Module,因为 它不能脱离 APR 环境运行。但是 APR 倒是可以脱离 Apache 单独安装的,在 APR 网站上可 以下载 APR 和 APR-util,不需要有 Apache,可以直接安装,而且它是跨平台的。 BSM_Memcache 是我在 BS.Magic 项目中开发的一个基于 APR_Memcache 的 PHP 扩展,说 起来有点拗口,至少它把 APR 扯进了 PHP 扩展中。这个程序很简单,也没做太多的功能, 只是一种形式的尝试,它支持服务器分组。 和 mcache 扩展支持多服务器分布存储不同,BSM_Memcache 支持多组服务器,每一组内的 服务器还是按照 hash 方式来分布保存数据,但是两个组中保存的数据是一样的,也就是实 现了热备,它不会因为一台服务器发生单点故障导致数据无法获取,除非所有的服务器组 龙兴平 (MSN: lxp8@sina.com) 第 18 页 共 83 页 2010-4-27 都损坏(例如机房停电)。当然实现这个功能的代价就是性能上的牺牲,在每次添加删除数 据的时候都要扫描所有的组,在 get 数据的时候会随机选择一组服务器开始轮询,一直到找 到数据为止,正常情况下一次就可以获取得到。 BSM_Memcache 只支持这几个函数: CODE: zend_function_entry bsm_memcache_functions[] = { PHP_FE(mc_get, NULL) PHP_FE(mc_set, NULL) PHP_FE(mc_del, NULL) PHP_FE(mc_add_group, NULL) PHP_FE(mc_add_server, NULL) PHP_FE(mc_shutdown, NULL) {NULL, NULL, NULL} }; mc_add_group 函数返回一个整形(其实应该是一个 object,我偷懒了~_~)作为组 ID, mc_add_server 的时候要提供两个参数,一个是组 ID,一个是服务器地址(ADDRORT)。 CODE: /** * Add a server group */ PHP_FUNCTION(mc_add_group) { apr_int32_t group_id; apr_status_t rv; if (0 != ZEND_NUM_ARGS()) { WRONG_PARAM_COUNT; RETURN_NULL(); } group_id = free_group_id(); if (-1 == group_id) { RETURN_FALSE; } apr_memcache_t *mc; rv = apr_memcache_create(p, MAX_G_SERVER, 0, &mc); add_group(group_id, mc); 龙兴平 (MSN: lxp8@sina.com) 第 19 页 共 83 页 2010-4-27 RETURN_DOUBLE(group_id); } CODE: /** * Add a server into group */ PHP_FUNCTION(mc_add_server) { apr_status_t rv; apr_int32_t group_id; double g; char *srv_str; int srv_str_l; if (2 != ZEND_NUM_ARGS()) { WRONG_PARAM_COUNT; } if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, “ds”, &g, &srv_str, &srv_str_l) == FAILURE) { RETURN_FALSE; } group_id = (apr_int32_t) g; if (-1 == is_validate_group(group_id)) { RETURN_FALSE; } char *host, *scope; apr_port_t port; rv = apr_parse_addr_port(&host, &scope, &port, srv_str, p); if (APR_SUCCESS == rv) { // Create this server object apr_memcache_server_t *st; rv = apr_memcache_server_create(p, host, port, 0, 64, 1024, 600, &st); 龙兴平 (MSN: lxp8@sina.com) 第 20 页 共 83 页 2010-4-27 if (APR_SUCCESS == rv) { if (NULL == mc_groups[group_id]) { RETURN_FALSE; } // Add server rv = apr_memcache_add_server(mc_groups[group_id], st); if (APR_SUCCESS == rv) { RETURN_TRUE; } } } RETURN_FALSE; } 在 set 和 del 数据的时候,要循环所有的组: CODE: /** * Store item into all groups */ PHP_FUNCTION(mc_set) { char *key, *value; int key_l, value_l; double ttl = 0; double set_ct = 0; if (2 != ZEND_NUM_ARGS()) { WRONG_PARAM_COUNT; } if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, “ss|d”, &key, &key_l, &value, &value_l, ttl) == FAILURE) { RETURN_FALSE; } // Write data into every object 龙兴平 (MSN: lxp8@sina.com) 第 21 页 共 83 页 2010-4-27 apr_int32_t i = 0; if (ttl < 0) { ttl = 0; } apr_status_t rv; for (i = 0; i < MAX_GROUP; i++) { if (0 == is_validate_group(i)) { // Write it! rv = apr_memcache_add(mc_groups[i], key, value, value_l, (apr_uint32_t) ttl, 0); if (APR_SUCCESS == rv) { set_ct++; } } } RETURN_DOUBLE(set_ct); } 在 mc_get 中,首先要随机选择一个组,然后从这个组开始轮询: CODE: /** * Fetch a item from a random group */ PHP_FUNCTION(mc_get) { char *key, *value = NULL; int key_l; apr_size_t value_l; if (1 != ZEND_NUM_ARGS()) { WRONG_PARAM_COUNT; } if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, “s”, &key, &key_l) == FAILURE) { RETURN_MULL(); 龙兴平 (MSN: lxp8@sina.com) 第 22 页 共 83 页 2010-4-27 } // I will try … // Random read apr_int32_t curr_group_id = random_group(); apr_int32_t i = 0; apr_int32_t try = 0; apr_uint32_t flag; apr_memcache_t *oper; apr_status_t rv; for (i = 0; i < MAX_GROUP; i++) { try = i + curr_group_id; try = try % MAX_GROUP; if (0 == is_validate_group(try)) { // Get a value oper = mc_groups[try]; rv = apr_memcache_getp(mc_groups[try], p, (const char *) key, &value, &value_l, 0); if (APR_SUCCESS == rv) { RETURN_STRING(value, 1); } } } RETURN_FALSE; } CODE: /** * Random group id * For mc_get() */ apr_int32_t random_group() { struct timeval tv; struct timezone tz; int usec; gettimeofday(&tv, &tz); 龙兴平 (MSN: lxp8@sina.com) 第 23 页 共 83 页 2010-4-27 usec = tv.tv_usec; int curr = usec % count_group(); return (apr_int32_t) curr; } BSM_Memcache 的使用方式和其它的 client 类似: CODE: APR_Memcache 的相关资料可以在这里找到,BSM_Memcache 可以在本站下载。 ◎APR 环境介绍 APR 的全称:Apache Portable Runtime。它是 Apache 软件基金会创建并维持的一套跨平台 的 C 语言库。它从 Apache httpd1.x 中抽取出来并独立于 httpd 之外,Apache httpd2.x 就是建 立在 APR 上。APR 提供了很多方便的 API 接口可供使用,包括如内存池、字符串操作、网 络、数组、hash 表等实用的功能。开发 Apache2 Module 要接触很多 APR 函数,当然 APR 可以独立安装独立使用,可以用来写自己的应用程序,不一定是 Apache httpd 的相关开发。 ref:http://www.54np.com/ 1.2.2 内存分配管理 Memcached 快么? 非常快。Memcached 使用了 libevent(如果可以的话,在 linux 下使用 epoll)来均衡任何数 量的打开链接,使用非阻塞的网络 I/O,对内部对象实现引用计数(因此,针对多样的客户端, 对象可以处在多样的状态), 使用自己的页块分配器和哈希表, 因此虚拟内存不会产生碎 龙兴平 (MSN: lxp8@sina.com) 第 24 页 共 83 页 2010-4-27 片并且虚拟内存分配的时间复杂度可以保证为 O(1).。 Danga Interactive 为提升 Danga Interactive 的速度研发了 Memcached。目前,LiveJournal.com 每天已经在向一百万用户提供多达两千万次的页面访问。而这些,是由一个由 web 服务器 和数据库服务器组成的集群完成的。Memcached 几乎完全放弃了任何数据都从数据库读取 的方式,同时,它还缩短了用户查看页面的速度、更好的资源分配方式,以及 Memcache 失效时对数据库的访问速度。 龙兴平 (MSN: lxp8@sina.com) 第 25 页 共 83 页 2010-4-27 Slab Allocation 机制:整理内存以便重复使用 最近的 memcached 默认情况下采用了名为 Slab Allocator 的机制分配、管理内存。 在该机 制出现以前,内存的分配是通过对所有记录简单地进行 malloc 和 free 来进行的。 但是,这 种方式会导致内存碎片,加重操作系统内存管理器的负担,最坏的情况下, 会导致操作系 统比 memcached 进程本身还慢。Slab Allocator 就是为解决该问题而诞生的。 下面来看看 Slab Allocator 的原理。下面是 memcached 文档中的 slab allocator 的目标: the primary goal of the slabs subsystem in memcached was to eliminate memory fragmentation issues totally by using fixed-size memory chunks coming from a few predetermined size classes. 也就是说,Slab Allocator 的基本原理是按照预先规定的大小,将分配的内存分割成特定长 度的块, 以完全解决内存碎片问题。 Slab Allocation 的原理相当简单。 将分配的内存分割成各种尺寸的块(chunk), 并把尺寸 相同的块分成组(chunk 的集合)(图 1)。 1.2.3 在 Slab 中缓存记录的原理 下面说明 memcached 如何针对客户端发送的数据选择 slab 并缓存到 chunk 中。 memcached 根据收到的数据的大小,选择最适合数据大小的 slab(图 2)。 memcached 中保存 着 slab 内空闲 chunk 的列表,根据该列表选择 chunk, 然后将数据缓存于其中。 龙兴平 (MSN: lxp8@sina.com) 第 26 页 共 83 页 2010-4-27 1.2.4 Slab Allocator 的缺点 Slab Allocator 解决了当初的内存碎片问题,但新的机制也给 memcached 带来了新的问 题。 这个问题就是,由于分配的是特定长度的内存,因此无法有效利用分配的内存。 例如,将 100 字节的数据缓存到 128 字节的 chunk 中,剩余的 28 字节就浪费了(图 3)。 图 3 chunk 空间的使用 对于该问题目前还没有完美的解决方案,但在文档中记载了比较有效的解决方案。 龙兴平 (MSN: lxp8@sina.com) 第 27 页 共 83 页 2010-4-27 The most efficient way to reduce the waste is to use a list of size classes that closely matches (if that's at all possible) common sizes of objects that the clients of this particular installation of memcached are likely to store. 就是说,如果预先知道客户端发送的数据的公用大小,或者仅缓存大小相同的数据的情况 下, 只要使用适合数据大小的组的列表,就可以减少浪费。 但是很遗憾,现在还不能进行任何调优,只能期待以后的版本了。 但是,我们可以调节 slab class 的大小的差别。 接下来说明 growth factor 选项。 1.2.5 memcached 在数据删除方面有效利用资源 1.2.6 数据不会真正从 memcached 中消失 上次介绍过, memcached 不会释放已分配的内存。记录超时后,客户端就无法再看见该记录 (invisible,透明), 其存储空间即可重复使用。 1.2.7 Lazy Expiration memcached 内部不会监视记录是否过期,而是在 get 时查看记录的时间戳,检查记录是否过期。 这 种技术被称为 lazy(惰性)expiration。因此,memcached 不会在过期监视上耗费 CPU 时间。 1.2.8LRU:从缓存中有效删除数据的原理 memcached 会优先使用已超时的记录的空间,但即使如此,也会发生追加新记录时空间不足的情况, 此时就要使用名为 Least Recently Used(LRU)机制来分配空间。 顾名思义,这是删除“最近最少 使用”的记录的机制。 因此,当 memcached 的内存空间不足时(无法从 slab class 获取到新的空 间时),就从最近未被使用的记录中搜索,并将其空间分配给新的记录。 从缓存的实用角度来看, 该模型十分理想。 不过,有些情况下 LRU 机制反倒会造成麻烦。memcached 启动时通过“-M”参数可以禁止 LRU,如 下所示: $ memcached -M -m 1024 启动时必须注意的是,小写的“-m”选项是用来指定最大内存大小的。不指定具体数值则使用默认值 64MB。 龙兴平 (MSN: lxp8@sina.com) 第 28 页 共 83 页 2010-4-27 指定“-M”参数启动后,内存用尽时 memcached 会返回错误。 话说回来,memcached 毕竟不是存 储器,而是缓存,所以推荐使用 LRU。 1.3 memcached 的最新发展方向 memcached 的 roadmap 上有两个大的目标。一个是二进制协议的策划和实现,另一个是外部引擎 的加载功能。 1.3.1 关于二进制协议 使用二进制协议的理由是它不需要文本协议的解析处理,使得原本高速的 memcached 的性能更上 一层楼, 还能减少文本协议的漏洞。目前已大部分实现,开发用的代码库中已包含了该功能。 memcached 的下载页面上有代码库的链接。 • http://danga.com/memcached/download.bml 1.3.2 二进制协议的格式 协议的包为 24 字节的帧,其后面是键和无结构数据(Unstructured Data)。 实际的格式如下(引 自协议文档): Byte/ 0 | 1 | 2 | 3 | / | | | | |0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7| +---------------+---------------+---------------+---------------+ 0/ HEADER / / / / / / / +---------------+---------------+---------------+---------------+ 24/ COMMAND-SPECIFIC EXTRAS (as needed) / +/ (note length in th extras length header field) / +---------------+---------------+---------------+---------------+ 龙兴平 (MSN: lxp8@sina.com) 第 29 页 共 83 页 2010-4-27 m/ Key (as needed) / +/ (note length in key length header field) / +---------------+---------------+---------------+---------------+ n/ Value (as needed) / +/ (note length is total body length header field, minus / +/ sum of the extras and key length body fields) / +---------------+---------------+---------------+---------------+ Total 24 bytes 如上所示,包格式十分简单。需要注意的是,占据了 16 字节的头部(HEADER)分为 请 求头 ( Request Header)和响应头(Response Header)两种。 头部中包含了表示包的有效性的 Magic 字节、命 令种类、键长度、值长度等信息,格式如下: Request Header Byte/ 0 | 1 | 2 | 3 | / | | | | |0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7| +---------------+---------------+---------------+---------------+ 0| Magic | Opcode | Key length | +---------------+---------------+---------------+---------------+ 4| Extras length | Data type | Reserved | +---------------+---------------+---------------+---------------+ 8| Total body length | +---------------+---------------+---------------+---------------+ 12| Opaque | +---------------+---------------+---------------+---------------+ 16| CAS | 龙兴平 (MSN: lxp8@sina.com) 第 30 页 共 83 页 2010-4-27 | | +---------------+---------------+---------------+---------------+ Response Header Byte/ 0 | 1 | 2 | 3 | / | | | | |0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7| +---------------+---------------+---------------+---------------+ 0| Magic | Opcode | Key Length | +---------------+---------------+---------------+---------------+ 4| Extras length | Data type | Status | +---------------+---------------+---------------+---------------+ 8| Total body length | +---------------+---------------+---------------+---------------+ 12| Opaque | +---------------+---------------+---------------+---------------+ 16| CAS | | | +---------------+---------------+---------------+---------------+ 如希望了解各个部分的详细内容,可以 checkout 出 memcached 的二进制协议的代码树, 参考其 中的 docs 文件夹中的 protocol_binary.txt 文档。 1.3.3 HEADER 中引人注目的地方 看到 HEADER 格式后我的感想是,键的上限太大了!现在的 memcached 规格中,键长度最大为 250 字节, 但二进制协议中键的大小用 2 字节表示。因此,理论上最大可使用 65536 字节 (216)长的键。 尽管 250 字节以上的键并不会太常用,二进制协议发布之后就可 以使用巨大的键了。 龙兴平 (MSN: lxp8@sina.com) 第 31 页 共 83 页 2010-4-27 二进制协议从下一版本 1.3 系列开始支持。 1.4 外部引擎支持 我去年曾经试验性地将 memcached 的存储层改造成了可扩展的(pluggable)。 • http://alpha.mixi.co.jp/blog/?p=129 MySQL 的 Brian Aker 看到这个改造之后,就将代码发到了 memcached 的邮件列表。 memcached 的开发者也十分感兴趣,就放到了 roadmap 中。现在由我和 memcached 的开发者 Trond Norbye 协同开发(规格设计、实现和测试)。 和国外协同开发时时差是个大问题,但抱着相同的愿景, 最 后终于可以将可扩展架构的原型公布了。 代码库可以从 memcached 的下载页面 上访问。 1.4.1 外部引擎支持的必要性 世界上有许多 memcached 的派生软件,其理由是希望永久保存数据、实现数据冗余等, 即使牺牲 一些性能也在所不惜。我在开发 memcached 之前,在 mixi 的研发部也曾经 考虑过重新发明 memcached。 外部引擎的加载机制能封装 memcached 的网络功能、事件处理等复杂的处理。 因此,现阶段通过 强制手段或重新设计等方式使 memcached 和存储引擎合作的困难 就会烟消云散,尝试各种引擎就 会变得轻而易举了。 1.4.2 简单 API 设计的成功的关键 该项目中我们最重视的是 API 设计。函数过多,会使引擎开发者感到麻烦; 过于复杂,实现引擎的 门槛就会过高。因此,最初版本的接口函数只有 13 个。 具体内容限于篇幅,这里就省略了,仅说 明一下引擎应当完成的操作: • 引擎信息(版本等) • 引擎初始化 • 引擎关闭 • 引擎的统计信息 • 在容量方面,测试给定记录能否保存 • 为 item(记录)结构分配内存 • 释放 item(记录)的内存 • 删除记录 • 保存记录 • 回收记录 • 更新记录的时间戳 • 数学运算处理 • 数据的 flush 龙兴平 (MSN: lxp8@sina.com) 第 32 页 共 83 页 2010-4-27 对详细规格有兴趣的读者,可以 checkout engine 项目的代码,阅读器中的 engine.h。 1.4.3 重新审视现在的体系 memcached 支持外部存储的难点是,网络和事件处理相关的代码(核心服务器)与 内存存储的代 码紧密关联。这种现象也称为 tightly coupled(紧密耦合)。 必须将内存存储的代码从核心服务器 中独立出来,才能灵活地支持外部引擎。 因此,基于我们设计的 API,memcached 被重构成下面 的样子: 重构之后,我们与 1.2.5 版、二进制协议支持版等进行了性能对比,证实了它不会造成性能影响。 在考虑如何支持外部引擎加载时,让 memcached 进行并行控制(concurrency control)的方案是 最为容易的, 但是对于引擎而言,并行控制正是性能的真谛,因此我们采用了将多线程支持完全交 给引擎的设计方案。 以后的改进,会使得 memcached 的应用范围更为广泛。 龙兴平 (MSN: lxp8@sina.com) 第 33 页 共 83 页 2010-4-27 1.5 分布处理 1.5.1 Memcached 的特点 Memcached 的缓存是一种分布式的,可以让不同主机上的多个用户同时访问, 因此解决了 共享内存只能单机应用的局限,更不会出现使用数据库做类似事情的时候,磁盘开销和阻 塞的发生。 1.5.2 分布式算法 memcached 不互相通信的分布式 memcached 尽管是“分布式”缓存服务器,但服务器端并没有分布式功能。 各个 memcached 不会互相通信以共享信息。那么,怎样进行分布式呢? 这完全取决于客户端的实现。本连 载也将介绍 memcached 的分布式。 龙兴平 (MSN: lxp8@sina.com) 第 34 页 共 83 页 2010-4-27 主要的分布式 node 定位 hash 算法为:CRC,一致性 hash 1.6 memcached 的分布式 正如第 1 次中介绍的那样, memcached 虽然称为“分布式”缓存服务器,但服务器端并没 有“分布式”功能。 服务器端仅包括 第 2 次、 第 3 次 前坂介绍的内存存储功能,其实现非 常简单。 至于 memcached 的分布式,则是完全由客户端程序库实现的。 这种分布式是 memcached 的最大特点。 1.6.1 memcached 的分布式是什么意思? 这里多次使用了“分布式”这个词,但并未做详细解释。 现在开始简单地介绍一下其原理, 各个客户端的实现基本相同。 下面假设 memcached 服务器有 node1~node3 三台, 应用程序要保存键名为 “tokyo”“kanagawa”“chiba”“saitama”“gunma” 的数据。 龙兴平 (MSN: lxp8@sina.com) 第 35 页 共 83 页 2010-4-27 图 1 分布式简介:准备 首先向 memcached 中添加“tokyo”。将“tokyo”传给客户端程序库后, 客户端实现的算法 就会根据“键”来决定保存数据的 memcached 服务器。 服务器选定后,即命令它保存 “tokyo”及其值。 龙兴平 (MSN: lxp8@sina.com) 第 36 页 共 83 页 2010-4-27 图 2 分布式简介:添加时 同样,“kanagawa”“chiba”“saitama”“gunma”都是先选择服务器再保存。 接下来获取保存的数据。获取时也要将要获取的键“tokyo”传递给函数库。 函数库通过与 数据保存时相同的算法,根据“键”选择服务器。 使用的算法相同,就能选中与保存时相同 的服务器,然后发送 get 命令。 只要数据没有因为某些原因被删除,就能获得保存的值。 龙兴平 (MSN: lxp8@sina.com) 第 37 页 共 83 页 2010-4-27 图 3 分布式简介:获取时 这样,将不同的键保存到不同的服务器上,就实现了 memcached 的分布式。 memcached 服务器增多后,键就会分散,即使一台 memcached 服务器发生故障 无法连接,也不会影 响其他的缓存,系统依然能继续运行。 接下来介绍第 1 次 中提到的 Perl 客户端函数库 Cache::Memcached 实现的分布式方法。 1.7 Cache::Memcached 的分布式方法 Perl 的 memcached 客户端函数库 Cache::Memcached 是 memcached 的作者 Brad Fitzpatrick 的作品,可以说是原装的函数库了。 • Cache::Memcached - search.cpan.org 龙兴平 (MSN: lxp8@sina.com) 第 38 页 共 83 页 2010-4-27 该函数库实现了分布式功能,是 memcached 标准的分布式方法。 1.7.1 根据余数计算分散 Cache::Memcached 的分布式方法简单来说,就是“根据服务器台数的余数进行分散”。 求 得键的整数哈希值,再除以服务器台数,根据其余数来选择服务器。 下面将 Cache::Memcached 简化成以下的 Perl 脚本来进行说明。 use strict; use warnings; use String::CRC32; my @nodes = ('node1','node2','node3'); my @keys = ('tokyo', 'kanagawa', 'chiba', 'saitama', 'gunma'); foreach my $key (@keys) { my $crc = crc32($key); # CRC 値 my $mod = $crc % ( $#nodes + 1 ); my $server = $nodes[ $mod ]; # 根据余数选择服务器 printf "%s => %s\n", $key, $server; } Cache::Memcached 在求哈希值时使用了 CRC。 • String::CRC32 - search.cpan.org 首先求得字符串的 CRC 值,根据该值除以服务器节点数目得到的余数决定服务器。 上面 的代码执行后输入以下结果: 龙兴平 (MSN: lxp8@sina.com) 第 39 页 共 83 页 2010-4-27 tokyo => node2 kanagawa => node3 chiba => node2 saitama => node1 gunma => node1 根据该结果,“tokyo”分散到 node2,“kanagawa”分散到 node3 等。 多说一句,当选择 的服务器无法连接时,Cache::Memcached 会将连接次数 添加到键之后,再次计算哈希 值并尝试连接。这个动作称为 rehash。 不希望 rehash 时可以在生成 Cache::Memcached 对象时指定“rehash => 0”选项。 1.7.2 根据余数计算分散的缺点 余数计算的方法简单,数据的分散性也相当优秀,但也有其缺点。 那就是当添加或移除服 务器时,缓存重组的代价相当巨大。 添加服务器后,余数就会产生巨变,这样就无法获取 与保存时相同的服务器, 从而影响缓存的命中率。用 Perl 写段代码来验证其代价。 use strict; use warnings; use String::CRC32; my @nodes = @ARGV; my @keys = ('a'..'z'); my %nodes; foreach my $key ( @keys ) { my $hash = crc32($key); my $mod = $hash % ( $#nodes + 1 ); 龙兴平 (MSN: lxp8@sina.com) 第 40 页 共 83 页 2010-4-27 my $server = $nodes[ $mod ]; push @{ $nodes{ $server } }, $key; } foreach my $node ( sort keys %nodes ) { printf "%s: %s\n", $node, join ",", @{ $nodes{$node} }; } 这段 Perl 脚本演示了将“a”到“z”的键保存到 memcached 并访问的情况。 将其保存为 mod.pl 并执行。 首先,当服务器只有三台时: $ mod.pl node1 node2 nod3 node1: a,c,d,e,h,j,n,u,w,x node2: g,i,k,l,p,r,s,y node3: b,f,m,o,q,t,v,z 结果如上,node1 保存 a、c、d、e……,node2 保存 g、i、k……, 每台服务器都保存 了 8 个到 10 个数据。 接下来增加一台 memcached 服务器。 $ mod.pl node1 node2 node3 node4 node1: d,f,m,o,t,v node2: b,i,k,p,r,y node3: e,g,l,n,u,w node4: a,c,h,j,q,s,x,z 龙兴平 (MSN: lxp8@sina.com) 第 41 页 共 83 页 2010-4-27 添加了 node4。可见,只有 d、i、k、p、r、y 命中了。像这样,添加节点后 键分散到的 服务器会发生巨大变化。26 个键中只有六个在访问原来的服务器, 其他的全都移到了其 他服务器。命中率降低到 23%。在 Web 应用程序中使用 memcached 时, 在添加 memcached 服务器的瞬间缓存效率会大幅度下降,负载会集中到数据库服务器上, 有可 能会发生无法提供正常服务的情况。 mixi 的 Web 应用程序运用中也有这个问题,导致无法添加 memcached 服务器。 但由于 使用了新的分布式方法,现在可以轻而易举地添加 memcached 服务器了。 这种分布式方 法称为 Consistent Hashing。 1.8 Consistent Hashing 关于 Consistent Hashing 的思想,mixi 株式会社的开发 blog 等许多地方都介绍过, 这 里只简单地说明一下。 • mixi Engineers' Blog - スマートな分散で快適キャッシュライフ • ConsistentHashing - コンシステント ハッシュ法 1.8.1 Consistent Hashing 的简单说明 Consistent Hashing 如下所示:首先求出 memcached 服务器(节点)的哈希值, 并将 其配置到 0~232 的圆(continuum)上。 然后用同样的方法求出存储数据的键的哈希值, 并映射到圆上。 然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服 务器上。 如果超过 232 仍然找不到服务器,就会保存到第一台 memcached 服务器上。 龙兴平 (MSN: lxp8@sina.com) 第 42 页 共 83 页 2010-4-27 图 4 Consistent Hashing:基本原理 从上图的状态中添加一台 memcached 服务器。余数分布式算法由于保存键的服务器会发 生巨大变化 而影响缓存的命中率,但 Consistent Hashing 中,只有在 continuum 上增 加服务器的地点逆时针方向的 第一台服务器上的键会受到影响。 龙兴平 (MSN: lxp8@sina.com) 第 43 页 共 83 页 2010-4-27 图 5 Consistent Hashing:添加服务器 因此,Consistent Hashing 最大限度地抑制了键的重新分布。 而且,有的 Consistent Hashing 的实现方法还采用了虚拟节点的思想。 使用一般的 hash 函数的话,服务器的映 射地点的分布非常不均匀。 因此,使用虚拟节点的思想,为每个物理节点(服务器) 在 continuum 上分配 100~200 个点。这样就能抑制分布不均匀, 最大限度地减小服务器 增减时的缓存重新分布。 通过下文中介绍的使用 Consistent Hashing 算法的 memcached 客户端函数库进行测试 的结果是, 由服务器台数(n)和增加的服务器台数(m)计算增加服务器后的命中率计 算公式如下: (1 - n/(n+m)) * 100 龙兴平 (MSN: lxp8@sina.com) 第 44 页 共 83 页 2010-4-27 1.8.2 支持 Consistent Hashing 的函数库 本连载中多次介绍的 Cache::Memcached 虽然不支持 Consistent Hashing, 但已有几 个客户端函数库支持了这种新的分布式算法。 第一个支持 Consistent Hashing 和虚拟节 点的 memcached 客户端函数库是 名为 libketama 的 PHP 库,由 last.fm 开发。 • libketama - a consistent hashing algo for memcache clients – RJ ブログ - Users at Last.fm 至于 Perl 客户端,连载的第 1 次 中介绍过的 Cache::Memcached::Fast 和 Cache::Memcached::libmemcached 支持 Consistent Hashing。 • Cache::Memcached::Fast - search.cpan.org • Cache::Memcached::libmemcached - search.cpan.org 两者的接口都与 Cache::Memcached 几乎相同,如果正在使用 Cache::Memcached, 那 么就可以方便地替换过来。Cache::Memcached::Fast 重新实现了 libketama, 使用 Consistent Hashing 创建对象时可以指定 ketama_points 选项。 my $memcached = Cache::Memcached::Fast->new({ servers => ["",""], ketama_points => 150 }); 另外,Cache::Memcached::libmemcached 是一个使用了 Brain Aker 开发的 C 函数库 libmemcached 的 Perl 模块。 libmemcached 本身支持几种分布式算法,也支持 Consistent Hashing, 其 Perl 绑定也支持 Consistent Hashing。 龙兴平 (MSN: lxp8@sina.com) 第 45 页 共 83 页 2010-4-27 • Tangent Software: libmemcached 1.9 Memcached 故障处理 1.9.1 故障的类型: 1. 一台 Memcached 服务器宕机 2. 一台 Memcached 服务器处理超时 3. 一台 Memcached 服务器的网络不可用或者短时间闪断 4. 1.9.2 Rehash 处理机制 1.10 Memcached 应用 1.10.1 应用说明 memcached 是一套分布式的快取系统,当初是 Danga Interactive 为了 LiveJournal 所发展的, 但目前被许多软件(如 MediaWiki)所使用。这是一套开放源代码软件,以 BSD license 授 权释出。 memcached 缺乏认证以及安全管制,这代表应该将 memcached 服务器放置在防火墙后。 memcached 的 API 使用三十二位元的循环冗余校验(CRC-32)计算键值后,将资料分散在 不同的机器上。当表格满了以后,接下来新增的资料会以 LRU 机制替换掉。由于 memcached 通常只是当作快取系统使用,所以使用 memcached 的应用程式在写回较慢的系统时(像是 后端的数据库)需要额外的程式码更新 memcached 内的资料。 1.10.2 应用案例 Digg Facebook(同时也回馈了许多程式码) Meetup.com(提供 memcached 对 Java 的连线函式库) Slashdot Wikipedia 龙兴平 (MSN: lxp8@sina.com) 第 46 页 共 83 页 2010-4-27 龙兴平 (MSN: lxp8@sina.com) 第 47 页 共 83 页 2010-4-27 龙兴平 (MSN: lxp8@sina.com) 第 48 页 共 83 页 2010-4-27 1.10.3 mixi 案例研究 mixi 在提供服务的初期阶段就使用了 memcached。 随着网站访问量的急剧增加,单纯为数据库添 加 slave 已无法满足需要,因此引入了 memcached。 此外,我们也从增加可扩展性的方面进行了 验证,证明了 memcached 的速度和稳定性都能满足需要。 现在,memcached 已成为 mixi 服务 中非常重要的组成部分。 Ref: http://tech.idv2.com/2008/07/31/memcached-005/ 1.10.4 Fotolog Fotolog 的缓存技术 非确定性缓存你不确定你要的数据缓存中有没有,你也不知道是不是过期了,于是你就试 探性的问 memcached,我要的什么什么数据你那有吗?我可不要过期的数据啊,memcached 告诉你说有并且给你,你就开心了,如果没有呢,你就要从数据库或者别的地方去获取了, 这是 memcached 典型的应用。主要应用在:1.复杂的数据需要多次读取,你的数据库做了 分片处理,从多个数据库中获取数据并组合起来是一个非常大的开销,你大可以把这些数 据取出来之后存到 memcached 中 龙兴平 (MSN: lxp8@sina.com) 第 49 页 共 83 页 2010-4-27 2.mysql query cache 的一个好的替代方案,这样数据库其他部门改变了,只要自己没改变就 没问题(注意数据库更新的问题,后面会提到) 3.把关系或者列表缓存起来,比如某个栏目下的多篇文章列表 4.被多个页面调用并且获取起来很慢的数据,或者是更新很慢的数据,比如文章浏览排行榜 5.如果 cache 的开销超过重新获取的开销,那么不要缓存它吧 6.标签云和自动建议(类似 google sugest) 例如:当一个用户上传一个图片,这个用户的好友页面上都要列出这张图片来,那么把它 缓存起来吧。 潜在问题: memcached 消耗的主要是服务器内存,对 CPU 消耗很小,所以 Fotolog 把 memcached 部署 在他们的应用服务器上(貌似我们也是这样),他们遇到了 CPU 搞到 90%的使用率(怎么 会那么高?哪出问题了吧)、内存回收(这是个大问题)等等问题。 状态缓存把应用服务的当前状态存在 memcached 中主要应用在:1.“昂贵”的操作,开销 大的操作 2.sessions 会话,Flickr 把 session 存在数据库中,个人感觉还是存 memcached 比较“便宜” 些,如果 memecached 服务器 down 掉了,那么重新登录吧。 3.记录用户在线信息(我们也是这样做的) 确定性缓存对于某些特定数据库的全部内容,都缓存到 memcached,有一个专门的应用服 务来保障你要的数据都在 memcached 中,其他应用服务直接从 memcached 中获取数据而不 去取数据库,因为数据库已经全部保存到 memcached 中并保持同步。主要应用在:1.读取 伸展,所有的读取都从 memcached 中获得,数据库没有负载 2.”永不过期“(相对的)的数据,比如行政规划数据,变动很小吧 3.经常调用的内容 4.用户的认证信息 5.用户的概要信息 6.用户的参数设置 7.用户当前常用的媒体文件列表,比如用户的图片 8.用户登录,不走数据库,只走 memcached(个人觉得这个不太好,登录信息还是需要持久 龙兴平 (MSN: lxp8@sina.com) 第 50 页 共 83 页 2010-4-27 化的,用类似 BDB 这样效果也不错) 使用方式: 1.多个专门的缓存池而不是一个大的缓存服务器,多个缓存池保障了高可用性,一个缓存实 例挂掉了走其他的缓存实例,所有的缓存实例挂掉了,走数据库(估计数据库抗不住^_^) 2.所有的缓存池都用程序来维护,比如数据库有更新时,程序自动把更新后的内容同步到多 个缓存实例中 3.服务器重启之后,缓存要比网站先启动,这就意味着当网站已经启动了,所有的缓存都可 用 4.读取的请求可以负载均衡到多个缓存实例中去,高性能,高可靠性 潜在的问题: 1.你需要足够多的内存来存储那么多的数据 2.数据以行记录数据,而 memcached 以对象来存储数据,你的逻辑要把行列的数据转换成 缓存对象 3.要维护多个缓存实例非常麻烦,Fotolog 用 Java/Hibernate,他们自己写了个客户端来轮询 4.管理多个缓存实例会增加应用程序的许多开销,但这些开销相对于多个缓存得到的好处来 说算不了什么 主动缓存数据魔法般的出现在缓存中,当数据库中有更新的时候,缓存立马填充,更新的 数据被调用的可能性更高(比如一篇新文章,看的的人当然多),是非确定性缓存的一种变 形(原文是 It’s non-deterministic caching with a twist.我觉得这样翻译怪怪的)。主要应用在: 1.预填充缓存:让 memcached 尽可能的少调用 mysql 如果内容不展现的话。 2.“预热”缓存:当你需要跨数据中心复制的时候 1.11 Memcached 优点 1.12 Memcached 缺点 龙兴平 (MSN: lxp8@sina.com) 第 51 页 共 83 页 2010-4-27 1.13 Memcached 性能 2 Sina Memcached BDB 2.1 系统架构 2.1.1 实现结构 龙兴平 (MSN: lxp8@sina.com) 第 52 页 共 83 页 2010-4-27 3 Tokyo Tyrant 3.1 系统架构实现 3.2 简介和特点 Tokyo Tyrant 加上 Tokyo Cabinet,构成了一款支持高并发的分布式持久存储系统,对 任何原有 Memcached 客户端来讲,可以将 Tokyo Tyrant 看成是一个 Memcached,但是,它 的数据是可以持久存储的。这一点,跟新浪的 Memcachedb 性质一样。 http://www.oschina.net/p/tokyo+tyrant Tokyo Tyrant 是 Tokyo Cabinet 数据库网络接口。它拥 有 Memcached 兼容协议,也可以通过 HTTP 协议进行数据交换。 http://www.oschina.net/docs/article/11606 利用 Tokyo Tyrant 构建兼容 Memcached 协议、支持 故障转移、高并发的分布式 key-value 持久存储系统。 TC 和 TT 的开发者是日本人 Mikio Hirabayashi,主要被用在日本最大的 SNS 网站 mixi.jp 上,TC 发展的时间最早,现在已经是一个非常成熟的项目,也是 Kye-Va lue 数据库领域最 大的热点,现在被广泛的应用在很多很多网站上。TC 是一个高性能的存储引擎,而 TT 提 供了多线程高并发服务器,性能也非常出色,每秒可以处理 4-5 万次读写操作。 TC 除了支持 Key-Va lue 存储之外,还支持保存 Hashtable 数据类型,因此很像一个简单 的数据库表,并且还支持基于 column 的条件查询, 分页查询和排序功能,基本上相当于 支持单表的基础查询功能了,所以可以简单的替代关系数据库的很多操作,这也是 TC 受到 大家欢迎的主要原因之一,有一个 Ruby 的项目 miyazakiresistance 将 TT 的 hashtable 的操 龙兴平 (MSN: lxp8@sina.com) 第 53 页 共 83 页 2010-4-27 作封装成和 ActiveRecord 一样的操作,用起来非常爽。 TC/TT 在 mixi 的实际应用当中,存储了 2000 万条以上的数据,同时支撑了上万个并发连接, 是一个久经考验的项目。TC 在保证了极高的并发读写性能 的同时,具有可靠的数据持久 化机制,同时还支持类似关系数据库表结构的 hashtable 以及简单的条件,分页和排序操作, 是一个很棒的 NoSQL 数据 库。 Tokyo Tyrant 是由同一作者开发的 Tokyo Cabinet 数据库网络接口。它拥有 Memcached 兼 容协议,也可以通过 HTTP 协议进行数据交换。Tokyo Tyrant 加上 Tokyo Cabinet,构成了 一款支持高并发的分布式持久存储系统,对任何原有 Memcached 客户端来讲,可以将 Tokyo Tyrant 看成是一个 Memcached,但是,它的数据是可以持久存储的。这一点,跟新浪的 Memcachedb 性质一样。 相比 Memcachedb 而言,Tokyo Tyrant 具有以下优势: 3.2.1 故障转移 Tokyo Tyrant 支持双机互为主辅模式,主辅库均可读写,而 Memcachedb 目前支持类似 MySQL 主辅库同步的方式实现读写分离,支持“主服务器可读写、辅助服务器只读”模式。 这里使用 $memcache->addServer 而不是 $memcache->connect 去连接 Tokyo Tyrant 服务 器,是因为当 Memcache 客户端使用 addServer 服务器池时,是根据“crc32(key) % current_server_num”哈希算法将 key 哈希到不同的服务器的,PHP、C 和 python 的客户 端都是如此的算法。Memcache 客户端的 addserver 具有故障转移机制,当 addserver 了 2 台 Memcached 服务器,而其中 1 台宕机了,那么 current_server_num 会由原先的 2 变成 1。 3.2.2 日志文件体积小 Tokyo Tyrant 用于主辅同步的日志文件比较小,大约是数据库文件的 1.3 倍,而 Memcachedb 的同步日志文件非常大,如果不定期清理,很容易将磁盘写满。 龙兴平 (MSN: lxp8@sina.com) 第 54 页 共 83 页 2010-4-27 3.2.3 超大数据量下表现出色 但是,Tokyo Tyrant 也有缺点:在 32 位操作系统下,作为 Tokyo Tyrant 后端存储的 Tokyo Cabinet 数据库单个文件不能超过 2G,而 64 位操作系统则不受这一限制。所以,如 果使用 Tokyo Tyrant,推荐在 64 位 CPU、操作系统上安装运行。 TC/TT 在 mixi 的实际应用当中,存储了 2000 万条以上的数据,同时支撑了上万个并发 连接,是一个久经考验的项目。TC 在保证了极高的并发读写性能 的同时,具有可靠的数 据持久化机制,同时还支持类似关系数据库表结构的 hashtable 以及简单的条件,分页和排 序操作,是一个很棒的 NoSQL 数据 库。 3.2.4 性能高 TC 是一个高性能的存储引擎,而 TT 提供了多线程高并发服务器,性能也非常出色, 每秒可以处理 4-5 万次读写操作。该数据库读写非常快,哈希模式写入 100 万条数据只需 0.643 秒,读取 100 万条数据只需 0.773 秒,是 Berkeley DB 等 DBM 的几倍。 TC 主要的缺点是没有 scale 的能力,如果单机无法满足要求,只能通过主从复制的方 式扩展,另外有人提到 TC 的性能会随着数据量的增加而下降,当数据量 上亿条以后,性 能会有比较明显的下降。 4 Redis Redis 是一个很新的项目,刚刚发布了 1.0 版本。Redis 本质上是一个 Key-Va lue 类型的内存 数据库,很像 memcached,整个数据库统 统加载在内存当中进行操作,定期通过异步操作 把数据库数据 flush 到硬盘上进行保存。因为是纯内存操作,Redis 的性能非常出色,每秒 可以处理超过 10 万次读写操作,是我知道的性能最快的 Key-Va lue D B。 Redis 的出色之处不仅仅是性能,Redis 最大的魅力是支持保存 List 链表和 Set 集合的数据结 构,而且还支持对 List 进行各种操作,例如 从 List 两端 push 和 pop 数据,取 List 区间, 排序等等,对 Set 支持各种集合的并集交集操作,此外单个 value 的最大限制是 1GB,不像 memcached 只能保存 1MB 的数据,因此 Redis 可以用来实现很多有用的功能,比方说用他 的 List 来做 FIFO 双向链表,实现一个轻量级的高性 能消息队列服务,用他的 Set 可以做 高性能的 tag 系统等等。另外 Redis 也可以对存入的 Key-Va l ue 设置 expire 时间,因此也可 以被当作一 个功能加强版的 memcached 来用。 Redis 的主要缺点是数据库容量受到物理内存的限制,不能用作海量数据的高性能读写,并 且它没有原生的可扩展机制,不具有 scale(可扩展)能 力,要依赖客户端来实现分布式读 写,因此 Redis 适合的场景主要局限在较小数据量的高性能操作和运算上。目前使用 Redis 的网站有 github,Engine Yard。 龙兴平 (MSN: lxp8@sina.com) 第 55 页 共 83 页 2010-4-27 Redis 和 Memcached 类似,可当作 Memcached 来使用,但是比较 Memcached 多一个 永久存储的功能。 5 Facebook Memcached MySQL 5.1 MySQL Sharding 策略 从 Shard 到 Sharding "Shard" 这个词英文的意思是"碎片",而作为数据库相关的技术用语,似乎最早见于 大型多人在线角色扮演游戏(MMORPG)中。"Sharding" 姑且称之为"分片"。 Sharding 不是一门新技术,而是一个相对简朴的软件理念。如您所知,MySQL 5 之 后才有了数据表分区功能,那么在此之前,很多 MySQL 的潜在用户都对 MySQL 的扩展 性有所顾虑,而是否具备分区功能就成了衡量一个数据库可扩展性与否的一个关键指标(当 然不是唯一指标)。数据库扩展性是一个永恒的话题,MySQL 的推广者经常会被问到:如 在单一数据库上处理应用数据捉襟见肘而需要进行分区化之类的处理,是如何办到的呢? 答案是:Sharding。 Sharding 不是一个某个特定数据库软件附属的功能,而是在具体技术细节之上的抽象 处理,是水平扩展(Scale Out,亦或横向扩展、向外扩展)的解决方案,其主要目的是为突 破单节点数据库服务器的 I/O 能力限制,解决数据库扩展性问题。 事关数据库扩展性 说起数据库扩展性,这是个非常大的话题。目前的商业数据都有自己的扩展性解决方 案,在过去相对来说比较成熟,但是随着互联网的高速发展,不可避免的会带来一些计算 模式上的演变,这样很多主流商业系统也难免暴露出一些不足之处。比如 Oracle 的 RAC 是采用共享存储机制,对于 I/O 密集型的应用,瓶颈很容易落在存储上,这样的机制决定 后续扩容只能是 Scale Up(向上扩展) 类型,对于硬件成本、开发人员的要求、维护成本 都相对比较高。 Sharding 基本上是针对开源数据库的扩展性解决方案,很少有听说商业数据库进行 Sharding 的。目前业界的趋势基本上是拥抱 Scale Out,逐渐从 Scale Up 中解放出来。 Sharding 的应用场景 任何技术都是在合适的场合下能发挥应有的作用。 Sharding 也一样。联机游戏、IM、 BSP 都是比较适合 Sharding 的应用场景。其共性是抽象出来的数据对象之间的关联数据 很小。比如 IM ,每个用户如果抽象成一个数据对象,完全可以独立存储在任何一个地方, 数据对象是 Share Nothing 的;再比如 Blog 服务提供商的站点内容,基本为用户生成内 容(UGC),完全可以把不同的用户隔离到不同的存储集合,而对用户来说是透明的。 龙兴平 (MSN: lxp8@sina.com) 第 56 页 共 83 页 2010-4-27 这个"Share Nothing"是从数据库集群中借用的概念,举例来说,有些类型的数据粒 度之间就不是"Share Nothing" 的,比如类似交易记录的历史表信息,如果一条记录中既 包含卖家信息与买家信息,如果随着时间推移,买、卖家会分别与其它用户继续进行交易, 这样不可避免的两个买卖家的信息会分布到不同的 Sharding DB 上,而这时如果针对买卖 家查询,就会跨越更多的 Sharding,开销就会比较大。 Sharding 并不是数据库扩展方案的银弹,也有其不适合的场景,比如处理事务型的应 用就会非常复杂。对于跨不同 DB 的事务,很难保证完整性,得不偿失。所以,采用什么 样的 Sharding 形式,不是生搬硬套的。 Sharding 与数据库分区(Partition)的区别 有的时候,Sharding 也被近似等同于水平分区(Horizontal Partitioning),网上很多 地方也用 水平分区来指代 Sharding,但我个人认为二者之间实际上还是有区别的。的确, Sharding 的思想是从分区的思想而来,但数据库分区基本上是数据对象级别的处理,比 如表和索引的分区,每个子数据集上能够有不同的物理存储属性,还是单个数据库范围内 的操作,而 Sharding 是能够跨数据库,甚至跨越物理机器的。(见对比表格) Sharding 策略 数据 Sharding 的策略与分区表的方式有很多类似的地方,有基于表、ID 范围、数 据产生的时间或是 SOA 下理念下的基于服务等众多方式可选择。而与传统的表分区方式不 同的是,Sharding 策略和业务结合的更为紧密,成功的 Sharding 必须对自己的业务足 够熟悉,进行众多可行性分析的基础上进行,"业务逻辑驱动"。 Sharding 实现案例分析:Digg 网站 作为风头正劲的 Web 2.0 网站之一的 Digg.com,虽然用户群庞大,但网站数据库 数据并非海量,去年同期主数据大约只有 30GB 的样子,现在应该更大一些,但应该不会 出现数量级上增长,数据库软件采用 MySQL 5.x。Digg.com 的 IO 压力非常大,而且是 读集中的应用(98%的 IO 是读请求)。因为提供的是新闻类服务,这类数据有其自身特点, 最近时间段的数据往往是读压力最大的部分。 龙兴平 (MSN: lxp8@sina.com) 第 57 页 共 83 页 2010-4-27 根据业务特点,Digg.com 根据时间范围对主要的业务数据做 Sharding,把不到 10% 的"热"数据有效隔离开来,同时对这部分数据用以更好的硬件,提供更好的用户体验。 而 另 外 90%的数据因用户很少访问,所以尽管访问速度稍慢一点,对用户来说,影响也很小。 通过 Sharding,Digg 达到了预期效果。 现有的 Sharding 软件简介 现在 Sharding 相关的软件实现其实不少,基于数据库层、DAO 层、不同语言下也都 不乏案例。限于篇幅,作一下简要的介绍。 MySQL Proxy + HSCALE 一套比较有潜力的方案。其中 MySQL Proxy (http://forge.mysql.com/wiki/MySQL_Proxy) 是用 Lua 脚本实现的,介于客户端与 服务器端之间,扮演 Proxy 的角色,提供查询分析、失败接管、查询过滤、调整等功能。 目前的 0.6 版本还做不到读、写分离。HSCALE 则是针对 MySQL Proxy 插件,也是用 Lua 实现的,对 Sharding 过程简化了许多。需要指出的是,MySQL Proxy 与 HSCALE 各 自会带来一定的开销,但这个开销与集中式数据处理方式单条查询的开销还是要小的。 Hibernate Shards 这是 Google 技术团队贡献的项目(http://www.hibernate.org/414.html),该项目 是在对 Google 财务系统数据 Sharding 过程中诞生的。因为是在框架层实现的,所以有 其独特的特性:标准的 Hibernate 编程模型,会用 Hibernate 就能搞定,技术成本较低; 相对弹性的 Sharding 策略以及支持虚拟 Shard 等。 Spock Proxy 这也是在实际需求中产生的一个开源项目。Spock(http://www.spock.com/)是一 个人员查找的 Web 2.0 网站。通过对自己的单一 DB 进行有效 Sharding 化 而产生了 Spock Proxy(http://spockproxy.sourceforge.net/ ) 项目,Spock Proxy 算得上 MySQL Proxy 的一个分支,提供基于范围的 Sharding 机制。Spock 是基于 Rails 的, 所以 Spock Proxy 也是基于 Rails 构建,关注 RoR 的朋友不应错过这个项目。 HiveDB 上面介绍了 RoR 的实现,HiveDB (http://www.hivedb.org/)则是基于 Java 的实 现,另外,稍有不同的是,这个项目背后有商业公司支持。 PL/Proxy 前面几个都是针对 MySQL 的 Sharding 方案,PL/Proxy 则是针对 PostgreSQL 的, 设计思想类似 Teradata 的 Hash 机制,数据存储对客户端是透明的,客户请求发送到 PL/Proxy 后,由这里分布式存储过程调用,统一分发。PL/Proxy 的设计初衷就是在这一 层充当"数据总线"的职责,所以,当数据吞吐量支撑不住的时候,只需要增加更多的 PL/Proxy 服务器即可。大名鼎鼎的 Skype 用的就是 PL/Proxy 的解决方案。 Pyshards http://code.google.com/p/pyshards/wiki/Pyshards 这是个基于 Python 的解 决方案。该工具的设计目标还有个 Re-balancing 在里面,这倒是个比较激进的想法。目 前只支持 MySQL 数据库。 龙兴平 (MSN: lxp8@sina.com) 第 58 页 共 83 页 2010-4-27 结束语 Sharding 是一项仍处于高速发展中的"老"技术,随着 Web 2.0 的发展,Sahrding 逐渐从比较"虚"的概念变成比较"实"的运用思路,开放源代码软件大潮也给 Sharding 注入 新的活力,相信会有越来越多的项目采用 Sharding 技术,也会有更多成熟的 Sharding 方案和数据库附加软件涌现。 你的站点 Sharding 了么? 原文出处:http://www.dbanotes.net/database/database_sharding.html 程序员 200807 期:『开源数据库 Sharding(分片)技术』,分布式数据库之路 http://hi.baidu.com/zeorliu/blog/item/fe3f13d7773543dba144df41.html http://forge.mysql.com/wiki/MySQL_Proxy 6 Facebook Cassandra 6.1 简介 Cassandra 是一个开源的分布式数据库,结合了 Dynamo 的 K ey/ Va l ue 与 Bigtable 的面向 列的特点。 6.1.1 Cassandra 的特点如下: 1. 灵活的 schema 不需要象数据库一样预先设计 schema,增加或者删除字段非常方便(on the fly)。 2. 支持 range 查询 可以对 Key 进行范围查询。 3. 高可用,可扩展 单点故障不影响集群服务,可线性扩展。 我们可以将 Cassandra 的数据模型想象成一个四维或者五维的 Hash。 Apache Cassandra 是一套开源分布式数据库管理系统。它最初由 Facebook 开发,用于 储存特别大的数据。Facebook 目前在使用此系统。 主要特性: 分布式 基于 column 的结构化 高伸展性 Cassandra 的主要特点就是它不是一个数据库,而是由一堆数据库节点共同构成的一个 分布式网络服务,对 Cassandra 的一个写操作,会被复制到其他节点上去,对 Cassandra 的 龙兴平 (MSN: lxp8@sina.com) 第 59 页 共 83 页 2010-4-27 读操作,也会被路由到某个节点上面去读取。对于一个 Cassandra 群集来说,扩展性能 是 比较简单的事情,只管在群集里面添加节点就可以了。 Cassandra 是一个混合型的非关系的数据库,类似于 Google 的 BigTable。其主要功能比 Dynomite(分布式的 Key-Va lue 存 储系统)更丰富,但支持度却不如文档存储 MongoDB (介于关系数据库和非关系数据库之间的开源产品,是非关系数据库当中功能最丰富,最 像关系数据库 的。支持的数据结构非常松散,是类似 json 的 bjson 格式,因此可以存储比 较复杂的数据类型。)Cassandra 最初由 Facebook 开发,后转变成了开源项目。它是一个网 络社交云计算方面理想的数据库。以 Amazon 专有的完全分布式的 Dynamo 为基础,结合了 Google BigTable 基于列族(Column Family)的数据模型。P2P 去中心化的存储。很多方面 都可以称之为 Dynamo 2.0。 功能 Cassandra 的主要特点就是它不是一个数据库,而是由一堆数据库节点共同构成的一个 分布 式网络服务,对 Cassandra 的一个写操作,会被复制到其他节点上去,对 Cassandra 的读操作,也会被路由到某个节点上面去读取。对于一个 Cassandra 群集来说,扩展性能 是 比较简单的事情,只管在群集里面添加节点就可以了。 这里有很多理由来选择 Cassandra 用于您的网站。 和其他数据库比较,有几个突出特点: 模式灵活 :使用 Cassandra,像文档存储,你不必提前解决记录中的字段。你可以在系 统运行时随意的添加或移除字段。这是一个惊人的效率提升,特别是在大型部 署上。 真正的可扩展性 :Cassandra 是纯粹意义上的水平扩展。为给集群添加更多容量,可以 指向另一台电脑。你不必重启任何进程,改变应用查询,或手动迁移任何数据。 多数据中心识别 :你可以调整你的节点布局来避免某一个数据中心起火,一个备用的 数据中心将至少有每条记录的完全复制。 一些使 Cassandra 提高竞争力的其他功能: 范围查询 :如果你不喜欢全部的键值查询,则可以设置键的范围来查询。 列表数据结构 :在混合模式可以将超级列添加到 5 维。对于每个用户的索引,这是非 常方便的。 分布式写操作 :有可以在任何地方任何时间集中读或写任何数据。并且不会有任何单 点失败 6.2 系统架构 龙兴平 (MSN: lxp8@sina.com) 第 60 页 共 83 页 2010-4-27 Ref: http://wiki.apache.org/cassandra/ArchitectureOverview 6.3 1、目的 满足大数据量、大量随机的读写操作应用场景下的数据存储需求。更是用于实时在线应用。 6.4 2、功能概要 BigTable 存储结构+Dynomo 分布式模型 多副本 高可用 易增量扩展 最终一致性 最小化管理 6.5 3、数据类型描述 Column 字段,包含 name,value, timestamp 和 isMarkedForDelete SuperColumn 包含多个字段的字段,字段(IColumn)内部又是由多个字段组成 龙兴平 (MSN: lxp8@sina.com) 第 61 页 共 83 页 2010-4-27 ColumnFamily 字段集合,类似于数据库中一行,Column name 到 IColumn 的 Map addColumn(输入 IColumn):若不存在或者时间戳较旧,使用新 IColumn addColumns(输入 ColumnFamily):依次对每个 IColumn 做 addColumn resolve 过程: 字段集合的合并。将每一个 ColumnFamily 做 addColumns,然后再更新 DeletionTime Row key 和 ColumnFamily 的键值对 [使用的 name->value 的 map,无固定 schema,一行中可以有任意多个 column,且每行的 column 可不同] [每个 IColumn 可能本身又是一个 map] [每一个 Column 都有自己的时间戳,用于记录合并时作判断] Keyspace 一般是应用名称,可认为是逻辑的表,对于每一个 Keyspace 可以配置其副本策略、 ColumnFamily(即表结构),缓存等 6.6 4、Partitioning 一致性哈西:输出区间为一个环,每个点管理一个区间,key 找该区间确定点。点的退出或 者加入之影响该点相邻区间的点。 针对基本的一致性哈西分布不均匀且不能根据节点能力强弱分配的缺点,Dynamo 是让每个 点管理环中的多个位置,而 Cassandra 是让负载轻的节点可以在环上 Move 来均衡负载。 Partitioner 类型 RandomPartitioner:对 key 做 MD5 再生成 BigIntegerToken OrderPreservingPartitioner:直接用 key 生成 StringToken CollatingOrderPreservingPartitioner:对 key 做 getCollationKey 后生成 BytesToken,貌似优势 是字符串比较比 StringToken 快 生成 Tok en 后,AbstractReplicationStrategy 的 getReadStorageEndPoints 用 Token 取得位置信 息[对 TokenMetadata 生成的 Collections 查 binarySearch,找到 index 或者插入点选为 Master 点,该点再根据副本策略选取其他副本位置] 龙兴平 (MSN: lxp8@sina.com) 第 62 页 共 83 页 2010-4-27 6.7 5、副本机制 6.7.1 NWR 表决方式来提升一致性。 N——副本个数,N 为配置的 ReplicationFactor W——每次保证写入的个数,W 的选取: 输入:naturalTargets,即 N;hintedTargets,备选集合总数,包含了故障节点的备份点; ConsistencyLevel,一致性级别 bootstrapTargets 为 hintedTargets 和 naturalTargets 的差值, 如果级别为 ConsistencyLevel.ANY,W 等于 1 如果级别为 ConsistencyLevel.ONE,W 等于 bootstrapTargets+1 如果级别为 ConsistencyLevel.QUORUM,W 等于(naturalTargets/2)+bootstrapTargets+1, 即大多数 如果级别为 ConsistencyLevel.DCQUORUM 或者 DCQUORUMSYNC , W 等于 naturalTargets 如果级别为 ConsistencyLevel.ALL,W 等于 bootstrapTargets+naturalTargets R——每次读取多少个副本来作为备选集,R 的选取:weakRead 为 1,strongRead 输入: naturalTargets=hintedTargets=ReplicationFactor,备选集合总数;ConsistencyLevel,一致性 级别,类似的: 如果级别为 ConsistencyLevel.ANY,R 等于 1 如果级别为 ConsistencyLevel.ONE,R 等于 1 如果级别为 ConsistencyLevel.QUORUM,R 等于(naturalTargets/2)1,即大多数 如果级别为 ConsistencyLevel.DCQUORUM 或者 DCQUORUMSYNC , R 等于 naturalTargets 如果级别为 ConsistencyLevel.ALL,R 等于 naturalTargets 6.7.2 副本策略 RackUnawareStrategy:不考虑机柜因素,从 Tok en 位置依次取 N 个 RackAwareStrategy:考虑机柜因素,在 primaryToken 之外,先找一个处于不同数据中心的 点,然后在不同机柜找 DatacenterShardStategy:要保证(N-1)%2 个点与 primaryToken 不再同一个数据中心 6.8 6、故障和扩展 故障和扩展将导致节点的状态和管理区间发生变化,需要机制来检测和同步这些变化。 龙兴平 (MSN: lxp8@sina.com) 第 63 页 共 83 页 2010-4-27 6.8.1 路由更新 管理员手工进行节点的加入和移除,Gossip 协议节点间同步路由的变化(list 发送给其他节 点,收到 list 的节点合并两个 list) "/Storage/Seeds/Seed"配置中包含多个 seed 信息,以此作为 Gossip 通信的起点。 6.8.2 数据迁移 节点加入时, 新节点在 bootstrapping 阶段根据自己管理的区间,去相应的位置索取数据。 从路由信息计算出自己要管理区间当前所在位置 Multimap,然后 对每个位置请求 Collection 节点移除时, 根据 Gossiper 检测出的节点变化发现节点被移除,根据移除节点找出需要变更的区间中 需要变更为自己管理的区间,为这些区间找到源位置,然后对每个位置请求 Collection 6.8.3 Gossiper: 维护和同步节点状态和路由信息。 服务启动后首先更新 localEndPoint,seed,localState 等信息,启动 GossipTimerTask 开始定 期进行 Gossip 通讯 使用 GossipDigest(EndPointState 的摘要,包含 EndPoint 的版本状态信息)列表生成 GossipDigestSynMessage 发送 一旦收到此消息,整理出需要 push 的 EndPointState 列表(我是新的)和需要 pool 的 GossipDigest 列表(你是新的),生成 GossipDigestAckMessage 回应 一旦收到此消息,根据 EndPointState 列表更新本地错误检测和状态维护,根据 GossipDigest 列表整理出对应的 EndPointState 列表生成 GossipDigestAck2Message 回应 一旦收到此消息,根据 EndPointState 列表更新本地错误检测和状态维护 6.9 7、Service 6.9.1 StorageProxy——存储服务 mutate 输入:List 输出:void 工作: 按 table 和 key 做 getNaturalEndpoints 返回满足的 InetAddress 列表 龙兴平 (MSN: lxp8@sina.com) 第 64 页 共 83 页 2010-4-27 进而 getHintedEndpointMap 返回 Map,该映射为每一 个地址选择了一个故障备份地址[如果 Endpoint 是 isAlive,则备份为自身;若不是 isAlive, 则在临近位置找一个尚未使用的地址作备份] 然后对 HintedEndpointMap 中的每一个地址处理:如果地址为本地,直接执行; 如果地址为外地,直接发送;如果要发到备份地址,标记 Hint 标记为原始地址,发到备份 地址[即点 A 故障,选取点 B 作备份,把要写入的数据发给点 B,但是告诉点 B 这是点 A 的,点 B 后期写回给点 A] [无任何一致性保证] mutateBlocking 输入:List, ConsistencyLevel 输出:void 工作:同 mutate,唯一的差别的请求发出后还等待回应 [同时写出 N 份,必须在超时前收回 W 份响应认为成功,否则报错] weakReadRemote 输入:List 输出:List 工作: 按 key 去 findSuitableEndPoint (先找本地,再找相同 DataCenter,最后依次找, 找到后判断是否 isAlive ) 将 Message 做 sendRR 到 SuitableEndPoint,得到 List 使用 IAsyncResult(AsyncResult)真正去 get 数据,若超时则重试(重试 Tod o) 对数据反序列化得到 ReadResponse 根据一致性检查判断是否需要修复副本( [写请求,回掉中修改状态和数据,然后再显式 get 去拿状态和数据做事] strongRead 输入:List 输出:List 工作: 按 key 去 findSuitableEndPoint 按 key 去找到所有其他 Live 副本集合 getLiveNaturalEndpoints 将 Message 做 sendRR,对 SuitableEndPoint 发 ReadMessage,对其他发 DigestOnly 的 Message,得到 List 使用 QuorumResponseHandler 真正去 get 回应数据,并使用 IResponseResolver (ReadResponseResolver)判断数据和 Digest 是否匹配,否则 throws DigestMismatchException 重试一次 如果不是 isDigestQuery,记录 ColumnFamily 到 rowList、EndPoint 到 endPoints,对于新得到的 ColumnFamily,[使用 rowList 中其他结果进行合并得到 resolved 结果,再使用 resolved结果找出 rowlist 中不同的条目生成写 diff 包提交给 ReadRepairManager 做回写] 如果是 isDigestQuery,如果 rowList 中任意结果的 digest(MD5)与 ReadResponse 不一致,throws DigestMismatchException [不是份所有 R 份都是读结果;只有部分读结果,其余读摘要信息] [不是读请求都读回来才回应;读>R 且 set Keyspace1.Standard1['jsmith']['first'] = 'John' Value inserted. cassandra> set Keyspace1.Standard1['jsmith']['last'] = 'Smith' Value inserted. cassandra> set Keyspace1.Standard1['jsmith']['age'] = '42' Value inserted. 这个时候,Cassandra 中就已经有 3 条数据了。 其中插入数据的各个字段含义如下: 接下来,我们执行查询操作: cassandra> get Keyspace1.Standard1['jsmith'] (column=age, value=42; timestamp=1249930062801) (column=first, value=John; timestamp=1249930053103) (column=last, value=Smith; timestamp=1249930058345) Returned 3 rows. 这样,我们就可以将之前插入的数据查询出来了。 6.10.6 排序 有一点需要明确,我们使用 Cassandra 的时候,数据在写入的时候就已经排好顺序了。 龙兴平 (MSN: lxp8@sina.com) 第 70 页 共 83 页 2010-4-27 在某一个 Key 内的所有 Column 都是按照它的 Name 来排序的。我们可以在 storage-conf.xml 文件中 指定排序的类型。 目前 Cassandra 提供的排序类型有:BytesType, UTF8Type,LexicalUUIDType, TimeUUIDType, AsciiType,和 LongType。 现在假设你的原始数据如下: {name: 123, value: "hello there"}, {name: 832416, value: "kjjkbcjkcbbd"}, {name: 3, value: "101010101010"}, {name: 976, value: "kjjkbcjkcbbd"} 当我们 storage-conf.xml 文件中指定排序的类型为 LongType 时: 排序后的数据就是这样的: {name: 3, value: "101010101010"}, {name: 123, value: "hello there"}, {name: 976, value: "kjjkbcjkcbbd"}, {name: 832416, value: "kjjkbcjkcbbd"} 如果我们指定排序的类型为 UTF8Type 排序后的数据就是这样的: {name: 123, value: "hello there"}, {name: 3, value: "101010101010"}, {name: 832416, value: "kjjkbcjkcbbd"}, {name: 976, value: "kjjkbcjkcbbd"} 大家可以看到,指定的排序类型不一样,排序的结果也是完全不同的。 对于 SuperColumn,我们有一个额外的排序维度,所以我们可以指定 CompareSubcolumnsWith 来进 行另一个维度的排序类型。 假设我们的原始数据如下: { // first SuperColumn from a Row name: "workAddress", // and the columns within it value: { street: {name: "street", value: "1234 x street"}, city: {name: "city", value: "san francisco"}, zip: {name: "zip", value: "94107"} } 龙兴平 (MSN: lxp8@sina.com) 第 71 页 共 83 页 2010-4-27 }, { // another SuperColumn from same Row name: "homeAddress", // and the columns within it value: { street: {name: "street", value: "1234 x street"}, city: {name: "city", value: "san francisco"}, zip: {name: "zip", value: "94107"} } } 然后我们定义 CompareSubcolumnsWith 和 CompareWith 的排序类型都是 UTF8Type,那么排序后 的结果为: { // this one's first b/c when treated as UTF8 strings { // another SuperColumn from same Row // This Row comes first b/c "homeAddress" is before "workAddress" name: "homeAddress", // the columns within this SC are also sorted by their names too value: { // see, these are sorted by Column name too city: {name: "city", value: "san francisco"}, street: {name: "street", value: "1234 x street"}, zip: {name: "zip", value: "94107"} } }, name: "workAddress", value: { // the columns within this SC are also sorted by their names too city: {name: "city", value: "san francisco"}, street: {name: "street", value: "1234 x street"}, zip: {name: "zip", value: "94107"} } } 再额外提一句,Cassandra 的排序功能是允许我们自己实现的,只要你继承 org.apache.cassandra.db.marshal.IType 就可以了。 6.11 Cassandra 存储机制 Cassandra 是结合了 Google Bigtable 的数据模型和 Amazon Dynamo 高可用框架的一个产品。 Cassandra 的存储机制,也是借鉴了 Bigtable 的设计,采用 Memtable 和 SSTable 的方式。和关系数 据库一样,Cassandra 在写数据之前,也需要先记录日志,称之为 commitlog,然后数据才会写入到 Column Family 对应的 Memtable 中,并且 Memtable 中的内容是按照 key 排序好的。Memtable 是 一种内存结构,满足一定条件后批量刷新到磁盘上,存储为 SSTable。这种机制,相当于缓存写回机制 龙兴平 (MSN: lxp8@sina.com) 第 72 页 共 83 页 2010-4-27 (Write-back Cache),优势在于将随机 IO 写变成顺序 IO 写,降低大量的写操作对于存储系统的压力。 SSTable 一旦完成写入,就不可变更,只能读取。下一次 Memtable 需要刷新到一个新的 SSTable 文件 中。所以对于 Cassandra 来说,可以认为只有顺序写,没有随机写操作。 因为 SSTable 数据不可更新,可能导致同一个 Column Family 的数据存储在多个 SSTable 中,这时查 询数据时,需要去合并读取 Column Family 所有的 SSTable 和 Memtable,这样到一个 Column Family 的数量很大的时候,可能导致查询效率严重下降。因此需要有一种机制能快速定位查询的 Key 落在哪些 SSTable 中,而不需要去读取合并所有的 SSTable。Cassandra 采用的是 Bloom Filter 算法,通过多 个 hash 函数将 key 映射到一个位图中,来快速判断这个 key 属于哪个 SSTable。关于 Bloom Filter, 有兴趣的可以去看看参考文章 4,5 和 6。 为了避免大量 SSTable 带来的性能影响,Cassandra 也提供一种定期将多个 SSTable 合并成一个新的 SSTable 的机制,因为每个 SSTable 中的 key 都是已经排序好的,因此只需要做一次合并排序就可以完 成该任务,代价还是可以接受的。所以在 Cassandra 的数据存储目录中,可以看到三种类型的文件,格 式类似于: Column Family Name-序号-Data.db Column Family Name-序号-Filter.db Column Family Name-序号-index.db 其中 Data.db 文件是 SSTable 数据文件,SSTable 是 Sorted Strings Table 的缩写,按照 key 排序后 存储 key/value 键值字符串。index.db 是索引文件,保存的是每个 key 在数据文件中的偏移位置,而 Filter.db 则是 Bloom Filter 算法生产的映射文件。 参考文章: [1].http://wiki.apache.org/cassandra/ArchitectureOverview [2].http://wiki.apache.org/cassandra/MemtableSSTable [3].http://wiki.apache.org/cassandra/ArchitectureSSTable [4].http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx [5].http://www.hellodba.net/2009/04/bloom_filter.html [6].http://www.googlechinablog.com/2007/07/bloom-filter.html [7].http://labs.google.com/papers/bigtable.html 6.12 Cassandra 相关理论 6.12.1 Bloom Filter 概念和原理 Bloom Filter 是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集 合,并能判断一个元素是否属于这个集合。Bloom Filter 的这种高效是有一定代价的:在判 龙兴平 (MSN: lxp8@sina.com) 第 73 页 共 83 页 2010-4-27 断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合 (false positive)。因此,Bloom Filter 不适合那些“零错误”的应用场合。而在能容忍低错 误率的应用场合下,Bloom Filter 通过极少的错误换取了存储空间的极大节省。 集合表示和元素查询 下面我们具体来看 Bloom Filter 是如何用位数组表示集合的。初始状态时,Bloom Filter 是一个包含 m 位的位数组,每一位都置为 0。 为了表达 S={x1, x2,…,xn}这样一个 n 个元素的集合,Bloom Filter 使用 k 个相互独立的哈希 函数(Hash Function),它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一 个元素 x,第 i 个哈希函数映射的位置 hi(x)就会被置为 1(1≤i≤k)。注意,如果一个位置 多次被置为 1,那么只有第一次会起作用,后面几次将没有任何效果。在下图中,k=3,且 有两个哈希函数选中同一个位置(从左边数第五位)。 在判断 y 是否属于这个集合时,我们对 y 应用 k 次哈希函数,如果所有 hi(y)的位置都 是 1(1≤i≤k),那么我们就认为 y 是集合中的元素,否则就认为 y 不是集合中的元素。下 图中 y1 就不是集合中的元素。y2 或者属于这个集合,或者刚好是一个 false positive。 错误率估计 前面我们已经提到了,Bloom Filter 在判断一个元素是否属于它表示的集合时会有一定 的错误率(false positive rate),下面我们就来估计错误率的大小。在估计之前为了简化模型, 我们假设 kn




需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载





下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!