“用空间换时间”的算法 带你走进缓存世界

我们常常考究一个算法的时间复杂度或空间复杂度，如果我们有绝对足够的时间或空间，那么算法就不需要了，可惜这种条件是不存在的，只是在某些情况下相对来说我们不用去考虑其中一个。今天我们讨论的“缓存”，自然就是“用空间换时间”的算法。缓存就是把一些数据暂时存放于某些地方，可能是内存，也有可能硬盘。总之，目的就是为了避免某些耗时的操作。我们常见的耗时的操作，比如数据库的查询、一些数据的计算结果，或者是为了减轻服务器的压力。其实减轻压力也是因查询或计算，虽然短耗时，但操作很频繁，累加起来也很长，造成严重排队等情况，服务器抗不住。

概念性的东西暂就不说了，说多了都是故事。现在我们来谈谈各种缓存。

初学.NET的朋友开始就会接触到DataSet类，云里雾里的看着DataSet的例子程序，也不管是咋回事，用就是了。其实DataSet就是缓存，当我们去读取一段数据集合的时候，如果每读取一条数据就处理一条的话，那么我们的程序和数据库会一直连接着。假如处理一条数据的耗时可以忽略不计，或者只有你一个人使用这个数据库的话，那么数据库一直连着也无所谓，我们写代码完全可以不用DataSet类。但是事实上不耗时不可能的，如果耗时严重的话，就会一直占用这数据库连接，直到我们处理完毕。如果这种查询过多，连接数就会占用过多，而且数据库在某些操作时会锁住表，这就会造成其他的请求等待，会出现查询超时，程序异常等现象。所以，我们必须先把数据拿出来，再对这些数据进行相关的处理，尽早的关闭数据库连接，好让数据库处理其他的请求。 所以，适时地选用DataSet或DataReader是比较重要的(说明：DataReader就是hold住连接的读取方式)。

你可能会迷惑，不知不觉中使用了缓存(DataSet)，这都是.net帮你完成的事。可是，你可能还是不太清楚该如何使用缓存，或者说何时使用缓存。不用着急，我们一一来看。

上面说过，我们缓存的数据无非就是一些数据库的查询、计算结果和频繁查询。那么，我们在实际开发中会碰到哪些这种数据呢？ 其实仔细想想这是非常常见的，比如用户登录后的个人资料，当他每次点击连接后造成页面刷新，我们总不能都要去重新查询数据库吧？我们常常用Session来存储这个人的信息，当他退出系统后我们把Session清理掉，所以Session也是缓存，只不过他也是.NET给我们提供好的类，sorry，我又举了一个你不想看到的例子，哈哈。其实Session是私有化的数据，Session的数据访问必须通过SessionID(详情我就不多言了，大家google下)，还不足以说明缓存的意义。如果把这个问题延伸下去，假如我们开发的是一个多用户的Blog系统， 每当我们访问其中一个博客时都要去查询这个博主的资料，假如A和B同时访问一个博客时，最理想的状态就是只查询一次，而不是两个人都去访问数据库!是不是呢？其实。。。是也不是!(故事里的事，说是就是，不是也是;说不是就不是，是也不是。 ：)。之所以说不是，是因为假如我们的博客网站每天就几个人访问，而且一直发展不起来，我们就没必要用缓存，因为使用缓存带来了更多的开发复杂度，因为每当我们去更新博主的资料的时候不单单要更新数据库的信息，我们还要去处理缓存。但是如果我们的博客访问量非常大，就像博客园似的，如果再不缓存，那数据库服务器早就Gameover了：)，那么现在就来看怎么用缓存的吧。

.Net Framework提供了现成的缓存类供我们使用，常见的是 System.Web.HttpRuntime.Cache。每当我们去执行 BlogDataProvier.GetBlogInfo()方法时(假定这个方法是我们获取博主信息的方法，顾名思义嘛)，需要在查询之前先从缓存获取数据，假如数据不存在的话，再去数据库获取，并且把得到的结果存入缓存，并且返回该结果既可。下面我把这个方法的伪代码写出来，好让从来没用过缓存的朋友大致了解一下。　

public class SqlDataProvider  


{  



public static object GetBlogInfo(string username)  



{  



//这里是从数据库获取BlogInfo  




return null;  



}  


}  



public class BlogDataProvider  



{  



public static object GetBlogInfo(string username)  



{  



var cacheKey = "Blog_" + username;  



var blog = CacheHelper.Get(cacheKey);  



if (blog == null)  



{  


blog = SqlDataProvider.GetBlogInfo(username);  


CacheHelper.Set(cacheKey, blog);  


}  



return blog;  



}  


}  



public class CacheHelper  



{  



public static object Get(string key)  



{  



return System.Web.HttpRuntime.Cache.Get(key);  



}   



public static void Set(string key, object value)  



{  


System.Web.HttpRuntime.Cache.Insert(key, value);  


}  


}  


 

缓存，两个字道出了其实际意义，一个是“存”，我们刚刚存了;另一个是“缓”，暂缓，缓存一般只是用来暂时存储，其命运都会被删除或替换掉，所以缓存有个时效问题。如果你说你的数据永远都不会过期，那么说真的，我建议你直接写在代码里就可以了。

上面的例子让我们了解到了HttpCache类。看来我们可以用它来解决绝大部分的缓存问题，主要是公共数据的缓存(所谓公共数据就是你我都可以访问的同一数据)。希望新手朋友捧着MSDN仔细学习该类的用法，真的很重要哦，不是吗？

开始我们说了“拿空间换时间”，目前只提到了缓存一些频繁查询的情况，牺牲空间缓存时间的明显些的例子有吗？没问题，你看好咯!

说之前先插一句，我们公司现在在招人，其中一道笔试题是介绍一下List和Dictionary的区别和用途。很遗憾，面试了很多人，只有一个同学回答的到位，其他的说什么的都有。你想好怎么回答了吗？：)如果你看了下面发现和你现在想的一致而且你还需要找一份有挑战的工作的话，给我消息哦。

其实用List，Dictionary泛型就是用来迷魂人的，哈哈，就会有些同学往泛型上面扯，结果上当咯，我完全可以用ArrayList和Hashtable来问。

List是什么数据结构？数组!而且是动态的数组，之所以动态就是可以视情况动态申请空间。Dictionary是什么结构？有的同学回答是字典。字典是什么数据结构？ 散列表!散列，一听这名字就知道是散开分布的数据表。怎么个“散”法？ 自然是按照Key来散，每个Key对应一个Value，所以我们常叫做“键值对”，Key和Value是成对的。我们把Dictionary看作是一个数组，那么每个Key的hash值(什么是hash值？在.net里任何类型都有GetHashCode方法，返回int值，有木有)，便是数组的下标，而该数组的元素值就是Value!所以我们在获取Dictionary的某个Key的Value时，速度是非常快的，可以直接通过已知的下标拿到值，这个时间复杂度是O(1)。快不快啊？好快好快。但是，你有木有想到，所有的Key的hash值是按顺序来的吗？显然不是，鬼知道你用的什么key，所以，Dictionary的这个数组很长很长，浪费了很多空位置，所以，那就是 空间 换 时间。当然GetHashCode的算法不同，Key对应的值的分布也有区别，有的比较紧密有的比较松散，常见的算法比如一致性hash算法。

dictionary的实际内存分布

如上图所示，dict的分布是不紧凑的，牺牲了很多空间，但可以最快速的找到数据，所以dict或hash或map等，不管什么叫什么类，总之都是hashtable，它们的用途主要就是查询。所以，如果我们把博客按用户名作key缓存起来的话，用户访问博客时都是使用的username，所以我们甚至不需要blogId，就可以拿到博主的信息，根本没走数据库。

而list这种排列紧凑的数据集合一般用于批处理。当然还有兼顾空间和速度的数据结构，那就是树结构，在查找时不需要所有数据都进行遍历，时间复杂度一般是O(logn)，而且空间是紧凑的，采用的是链表结构，而不是紧凑的数组。所以在时间和空间上都不比前两者，但用途却十分广大，我们所用的数据库的索引基本上都是用的树。这样既保证了占用空间小，查询的速度也不慢。

上面这一段我们介绍了hash表的基本原理，现在我们明白了缓存的优势，在实际的项目使用中，我们除了使用系统提供的Cache类以外，完全可以自己尝试写缓存类，为什么不呢？呵呵。我们把一个变量斯static，然后再public，就等于是全局变量了，我们可以到处访问到他，而且我们还要用dict，因为他足够快!还不快动手去写一个，回来再接着看!

刚才提到了“缓”字，缓也有不同的策略，比如最常见的按时间缓存，在单位时间内该数据有效，每当访问时都要判断缓存的数据是否过期，再决定Get还是Remove。除了时间策略，还有使用热度策略，由于内存有限，所以我们的缓存也不是无限申请的，是时候限制长度了。限制了长度就意味着有人能进来就得有人要出去。这就是Remove策略。我们可以对所有的缓存打上标记，来标记他的热度，每次添加缓存的时候把热度最低的缓存剔除掉(假如已经达到限制的话)。每次获取缓存的时候给该缓存热度+1。这是多人性化的设计，不是吗？ 我上篇博文中已经贴出了这类的代码。有兴趣的朋友给你们个传送门。

我们继续用博客园作例子，我们知道博客园的访问量已经很大了(具体多大，俺不知道，反正以前发表评论经常超时，官方团队解决后还发表博文说咋解决的，结果评论里一大票同学都说怎么不用缓存阿：)。

当网站访问量达到一定程度后，一台机器很难处理太多的httprequest，这个时候我们必须使用多台机器。假如你的程序没同时跑在多台机器上的话，你对缓存的理解恐怕不会很深，因为谁都要会这种经历：哎呀 sessio不能分布式阿？ 哎呀妈呀，我的缓存不能在两台机器上阿，这可咋整？!

其实这也不能怪你，要怪就怪微软吧。因为IIS，我们的web程序驻留在一个进程里，每个httprequest会有一个线程来处理，所以你甚至都没用过多线程。害人啊，哈哈。但随着项目经验的增加，特别是大项目的历练后，也没什么了。之所以说是微软的错，是因为人家php阿，ruby阿，人家的服务端(apache，nginx等)都是多进程的。每个httprequest一个进程，总共开几十个进程，处理并发。多进程就意味着数据共享问题，就像我们多台机器的情况一样。 这时候需要借助一个共享缓存进程来供其他的web服务进程来访问获取缓存。 这就是下面要说的 分布式缓存。

如果说两三年前你不知memcached为何物，或许情有可原，那时候还流行自己写windows service。但现在满世界的NoSQL，MongoDB，Memcached，Redis，你再不知道的话，真该说多看看博客吧;看看新技术，你已经落后一个时代了。

上面提到的这个名词都是玩缓存的主。NoSQL是个新技术，NoSQL DB现在很多种，MongoDB就是一种，MongoDB是介于传统关系型数据库和内存数据库的杂交数据库，现在也算是很热门的数据库。MemCached是著名的分布式缓存服务，而Redis(Remoting Dictionary Service)，你懂了吧？!我们的缓存服务器可以用memcached或redis，Memcached是纯内存的，重启进程会丢失所有缓存，而redis可以把数据写到硬盘里，各有各的优点吧。Redis更适合存经过计算过的数据。而且Redis支持丰富的数据类型(list\set\hash\string)，这要比memcached更灵活些。 他们都有.net的Driver，还有相关的Example和UnitTest，可以官网下载看看。