如何实现缓存系统的更新机制

标签: NoSQL Redis 缓存系统设计 | 发表时间:2014-10-19 23:25 | 作者:Jay13
出处:http://www.cricode.com

问题是这样的:假设要你设计一个缓存系统,你如何实现缓存的更新机制!

例如某网站具有高并发访问量,为提高性能,其中的一些网页页面都是存放在缓存中的,当需要更新缓存中的页面时,缓存系统如何完成缓存的更新?

给出解决方案之前,先看看内存数据库Redis中字典的设计。

Redis 中的字典结构表示如下:

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时,值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

我们暂时不管其dict结构体中其他的成员,只关注其中的哈希表成员:

dictht ht[2];

Redis的字典底层是用hash表来实现的, 一个哈希表里面可以有多个哈希表节点, 而每个哈希表节点就保存了字典中的一个键值对,但是,但是有趣的是这里使用了两个hash表。

为什么使用两个hash表呢?

因为在真实使用场景下,我们需要扩展或者收缩hash表的规模。出于节约内存的考虑,我们不可能一次性分配一个巨大巨大的hash表,因此,只在初始时分配一个合适大小的hash表,在使用过程中,当发现碰撞率过高时,我们就需要扩大hash表的规模。同样是基于节约内存的考虑,当hash表的填充率很低时,我们可以适当的收缩hash表的规模。

使用两个hash表是为了方便进行hash表的扩展和收缩。扩展或收缩哈希表时我们需要将  ht[0] 里面的所有键值对 rehash 到  ht[1] 里面。而且这个将ht[0]里面的键值对rehash到ht[1]不是一次性、集中式地完成的, 而是分多次、渐进式地完成的。

这样做的原因在于, 如果  ht[0] 里只保存着四个键值对, 那么服务器可以在瞬间就将这些键值对全部 rehash 到  ht[1] ; 但是, 如果哈希表里保存的键值对数量不是四个, 而是四百万、四千万甚至四亿个键值对, 那么要一次性将这些键值对全部 rehash 到  ht[1] 的话, 庞大的计算量可能会导致服务器在一段时间内停止服务。

因此, 为了避免 rehash 对服务器性能造成影响, 服务器不是一次性将  ht[0] 里面的所有键值对全部 rehash 到  ht[1] , 而是分多次、渐进式地将  ht[0] 里面的键值对慢慢地 rehash 到  ht[1] 。

以下是哈希表渐进式 rehash 的详细步骤:

  1. 为  ht[1] 分配空间, 让字典同时持有  ht[0] 和  ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量  rehashidx , 并将它的值设置为  0 , 表示 rehash 工作正式开始。
  3. 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将  ht[0] 哈希表在  rehashidx 索引上的所有键值对 rehash 到  ht[1] , 当 rehash 工作完成之后, 程序将  rehashidx 属性的值增一。
  4. 随着字典操作的不断执行, 最终在某个时间点上,  ht[0] 的所有键值对都会被 rehash 至  ht[1] , 这时程序将  rehashidx 属性的值设为  -1 , 表示 rehash 操作已完成。

渐进式 rehash 的好处在于它采取分而治之的方式, 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上, 从而避免了集中式 rehash 而带来的庞大计算量。

【PS:如果上面的描述不够清楚,可以移步这里: 渐进式rehash

====================================================

OK,看完的Redis的字典设计及其rehash机制,相信其能给我们带来灵感。现在我们再来说说 缓存系统的更新机制设计问题。

如下是一个可行的解决方案(假设我们的更新机制是每5分钟更新一次缓存):

1)设计两个缓存池,记为A、B,而A和B的内容都是从后端服务器数据库中获取到的数据。正常情况下,客户端的请求都是从缓存池A中获取缓存内容,同时,设置一个全局的变量ref用于记录当前正在访问缓存A的客户端数量,来一个客户端请求将ref值加1,响应完一个客户端请求后ref减一。

2)当缓存更新时间到时,如果ref不为0,则我们不能直接更新缓存,因为这时有客户端正在从缓存池A取数据。这里,我们可以借鉴Redis的rehash思想,更新时间到,我们将客户端的访问都引导到B缓存池,此时的缓存池A不再接受新的客户端数据请求,A的ref变量只减不增,当ref变量减少到0时,我们便可以更新A缓存池中的内容了。

【PS:初始nosql等相关知识,如有错误,欢迎指正!】

参考链接:

http://redisbook.com/en/latest/preview/dict/datastruct.html

相关 [缓存 系统 更新] 推荐:

如何实现缓存系统的更新机制

- - 快课网
问题是这样的:假设要你设计一个缓存系统,你如何实现缓存的更新机制. 例如某网站具有高并发访问量,为提高性能,其中的一些网页页面都是存放在缓存中的,当需要更新缓存中的页面时,缓存系统如何完成缓存的更新. 在 给出解决方案之前,先看看内存数据库Redis中字典的设计. Redis 中的字典结构表示如下:.

缓存更新的套路

- - 酷 壳 – CoolShell.cn
看到好些人在写更新缓存数据代码时, 先删除缓存,然后再更新数据库,而后续的操作会把数据再装载的缓存中. 试想,两个并发操作,一个是更新操作,另一个是查询操作,更新操作删除缓存后,查询操作没有命中缓存,先把老数据读出来后放到缓存中,然后更新操作更新了数据库. 于是,在缓存中的数据还是老的数据,导致缓存中的数据是脏的,而且还一直这样脏下去了.

缓存级别与缓存更新问题

- - Float_Luuu的博客
缓存失效问题被认为是计算机科学中最难的两件事之一,这篇文章来自翻译,内容主要包括缓存级别与缓存更新常见的几种模式. 缓存常用来加快页面的加载速度,减少服务器或数据库服务的负载. 缓存应用的常见模式如上图所示:. 检索缓存,尝试查找之前相同请求的执行结果,如果找到了则返回,省去了重新执行的步骤;. 如果缓存未命中,则重新执行计算逻辑并将结果保存至缓存;.

五款优秀的Linux缓存系统

- 勇丞 - FeedzShare
来自: Solidot - FeedzShare  . 发布时间:2011年04月27日,  已有 4 人推荐. Naomi James 写道 "1897年,意大利经济学家帕累托(Vilfredo Pareto)发现,国家80%的财富是掌握在20%的人口手中. 这一现象被称为帕累托法则或80-20法则.

分布式缓存系统 Xixibase

- Le - 开源中国社区最新软件
Xixibase是一个高性能,跨平台的分布式缓存系统. Xixibase server 采用 C++ 实现,底层网络库采用的是Boost Asio. Xixibase 主要特点: 1. 实现'Local Cache'功能, 当客户端打开'Local Cache'选项, 客户端可以将数据同时存储在Server 端和本地,并且保证本地数据和Server 端的数据的一致性.

多节点CDN缓存加速系统wdcdn1.5版本发布

- Eric - wdlinux致力于Linux服务器架构,配置,性能优化,自动化.Linux技术群:14797584
Wdcdn是基于lamp+squid开发的一套CDN架构管理系统,包括squid系统及web管理系统两部分.. 可帮助中小站长或中小企业快速构建自己的CDN网络及服务器群,提供更好的服务,更快速的网站,我们也致力打造这样一个完善完美的CDN缓存加速系统. 分单节点,多节点(集中管理版本)两个版本. 1 单节点版本 (看这里http://www.wdlinux.cn/wdcdn) 就是用一台或两台机,单独配置squid和wdcdn管理后台,此方式适用于中小站长或企业,构建一两个节点的CDN网络,最简单的就比如一个电信,一个网通,然后加上智能DNS解释就搞掂,但多于两个节点在管理上就不方便,没有统一操作后台和数据同步等.

如何使用bloomfilter构建大型Java缓存系统

- - ImportNew
在如今的软件当中,缓存是解决很多问题的一个关键概念. 你的应用可能会进行CPU密集型运算. 你当然不想让这些运算一边又一边的重复执行,相反,你可以只执行一次, 把这个结果放在内存中作为缓存. 有时系统的瓶颈在I/O操作上,比如你不想重复的查询数据库,你想把结果缓存起来,只在数据发生变化时才去数据查询来更新缓存.

聊聊高并发系统之HTTP缓存(转)

- - 企业架构 - ITeye博客
原文网址:http://jinnianshilongnian.iteye.com/blog/2319573. 最近遇到很多人来咨询我关于浏览器缓存的一些问题,而这些问题都是类似的,因此总结本文来解答以后遇到类似问题的朋友. 因本文主要以浏览器缓存场景介绍,所以非浏览器场景下的一些用法本文不会介绍,而且本文以chrome为测试浏览器.

J.Wong:MX、M9都有Android 4.0系统更新

- Adam - cnBeta.COM
近期不少煤油纷纷在论坛上发帖询问,魅族梦想机MX何时能用上Android 4.0系统. 对于如此敏感的话题,J.Wong现身给予回应称,会尽快为MX和M9带来Ice Cream Sandwich系统的更新. 当一位煤油发帖询问MX上市会不会跳票时,J.Wong意外现身并跟帖回复称,MX将会保持原计划在12月份正式上市.

自助建站系统 Tap 更新,更加社会化

- 狒狒 - 我爱水煮鱼
我前面介绍的免费自助建站平台:Tap进行了重大的更新,支持包含新浪、人人、开心网第三方账号登录Tap,并且支持同步平台内容到第三方,整个平台更加社会化. Tap是一个新型的免费自助建站服务平台,它可以创建并管理包括网站在内的各种网络应用. 易用、专业、高效的Tap能让您轻松摆脱建站过程中技术对创造力的制约.