3.2.1　缓存和散列

缓存（Cache）可以被看作计算机系统的伟大发明之一，它的应用在该领域中是普遍存在的。小到计算机的中央处理器（CPU）、主板、显卡等硬件，大到大规模的互联网站点，都在广泛使用缓存并从中受益。举例来说，自己组装过个人计算机硬件的朋友可能会更关心中央处理器、主板的缓存有多大；如果是电子游戏的粉丝，还会关注显卡的缓存有多大。这些硬件所采用的缓存是比普通的内存更快的介质，可以显著提升计算机的运行速度。不过，考虑到个人计算机的成本和设计框架，这里的高速缓存容量不可能很大，若干兆字节（MB）是比较常见的设置。而在网站的架构设计中，一般不会像个人计算机样采用高速的缓存介质，普通的服务器内存就已足矣，但是容量可以更大，至少是数个吉字节（GB）。此处将这个概念抽象出来，将缓存定义为数据交换的缓冲区，它的读取速度远远高于普通存储介质，作用是帮助系统更快地运行。当某个应用需要读取数据时，会优先从缓存中查找所需要的内容，如果找到了则直接获取，这个效率比读取普通存储的效率更高。如果缓存中没有发现所需要的内容，再到普通存储中寻找。

在了解缓存的概念之后，我们看看缓存的几个要素。

• 硬件性能：缓存的普遍规律是以高速读取介质来充当相对低速的介质的缓冲。由于缓存的应用场景非常广泛，因此没有绝对的条件来定义何种性能可以达到缓存的资格。例如，在个人计算机系统中，内嵌于主板中的一级（L1 Cache）和二级（L2 Cache）高速缓存，可以存放内存条中常用的数据，以便提升内存读取速度，这时它就充当了内存的缓存角色。同样，相对于硬盘而言，内存条又可以充当硬盘的缓存，存放硬盘读取中常用的数据，用于提升硬盘读取的速度。
• 命中率：缓存之所以能提升访问速度，主要是因为能直接从高速介质中读取，这种情况称为“命中”（hit）。但是，高速介质的成本是非常昂贵的，而且一般也不支持持久化存储，因此放入数据的容量必须受到限制，只能是全局信息的一部分。那么，一定是有部分数据无法在缓存中读取，而必须要到原始的存储中查找，这种情况称之为“错过”（missed）。可以通过公式（3-1）来简单地定义命中率。

其中|V|是整体的数据访问次数，而|H|是能够在缓存中查找到数据的次数。如果命中率高，系统能够频繁地获取已经在缓存中驻留的数据，速度就会明显提升。如果获取的命中率非常低，系统仍然需要到低速介质上进行读取，那就不可能带来性能的提升。那么接下来的问题就是，如何在缓存容量有限的情况下，尽可能地提升命中率呢？人们开始研究缓存的淘汰算法，通过某种机制将缓存中可能无用的数据剔除，然后向剔除后空余的空间中补充将来可能会访问的数据。最基本的策略包括最少使用（Least Frequently Used，LFU）和最久未用（Least Recently Used，LRU）。LFU会记录每个缓存对象被使用的频率，并将使用次数最少的对象剔除。而LRU会记录每个缓存对象最近使用的时间，并将剔除使用时间点最久远的对象。

• 更新周期：缓存之所以处理效率惊人，除了硬件性能上的先天优势外，还需要保证较高的命中率。但是，被访问的数据不会一成不变，对于变化速度很快的数据，我们需要将变动主动更新到缓存中，或者让原有内容失效，否则用户将读取到过时的内容。在无法及时更新数据的情况下，高命中率反而变成了坏事，轻则影响用户交互的体验，重则会导致应用逻辑的错误。
• 应用场景：由于缓存应用很广泛，要一一细分不太容易，因此只能从大体上简单地将它们分为系统级和应用级。系统级缓存是指操作系统提供的缓存，主要是利用主板缓存、显卡缓存和内存等提升操作系统的运行速度，对于普通使用者或开发者而言基本上都是透明的。而应用级缓存则和开发者的架构设计有关，例如一个在线用户量很大的网站，随着数据量的增大、访问的集中，就会出现后台持久化存储负担加重、数据库响应恶化、网站显示延迟等重大影响。而缓存就成为解决或优化这些性能问题的关键。本章后面提到的非持久化缓存，都是与应用级缓存相关的话题。

图3-9体现了缓存设计的因素和大致的工作流程。

图3-9　缓存的工作流程

了解这些要素之后，我们不禁要问，在实际运用中是如何实现缓存的机制的呢？这里就需要提到散列（Hash）和散列表（Hash Table）的概念了。曾经有人提出，假如在计算机编程语言的世界里，只能存在一种数据结构，那么你会选择什么？大部分“程序猿”和“攻城师”都会选择散列表。虽然只是说笑之词，不过也足以说明散列结构在计算机领域举足轻重。在前面介绍持久化存储时，无论是HBase还是MongoDB都要用到散列的设计理念。不过，对于非持久化的缓存而言，其设计和研发很多都是围绕散列展开的，这个概念显得更重要了。

散列（或散列函数）通过一定的算法将原始的数据转换为一个唯一（或者尽可能唯一）的数值，这个数值可以称为散列值。散列表，也称为散列映射，写入的时候以数据的散列值作为键（Key），以待写入的数据作为值（Value），进行Key-Value配对的存储。这样可以带来一个非常明显的好处，对于给定的数据，我们可以通过散列值计算快速定位，以加快查找的速度。无论散列表中有多少数据，插入和删除操作只需要耗费接近常量的时间，即O（1）的时间复杂度，这正好满足了缓存高速运作的需求。图3-10展示了散列表工作的基本流程。

图3-10　散列表的结构和工作流程

这里的散列函数非常简单，是将数据的所有位数相加。例如，328的散列值就是3+2+8=13。从图3-10中可以看出，散列值不一定是唯一的，不同的数据经过散列函数后，可能会得出一样的散列值，称为“散列冲突”。对于冲突的数据对象，会通过列表存储所有对应的数据，查询的时候需要进行多一些遍历操作。好的散列函数会尽量避免这种冲突。即使存在冲突，通过散列寻址还是可以大幅提升查询效率的。

“哦，这下我明白了缓存的意思，也知道如何通过散列来实现最基础的缓存机制了。那么是不是可以运用这层缓存来减轻数据库的负载呢？”

“思路很对，尤其是对你们这种电商的业务模式，对于缓存的需要更为迫切。当商品数量和用户访问流量达到一定的规模之后，如果每次都要去数据库获取实时的库存、价格、订单等信息，性能会很容易下降，系统甚至会有崩溃的风险。这个时候完全可以采用缓存来解决，将商品的ID作为键，而相关的库存、价格等作为值，这样最常用的商品信息都可以直接放入内存，读写速度将大大提升。”

“那么，有哪些非持久化存储系统可以支持缓存呢？”

“嗯，下面我们分别介绍应用级的几种缓存系统，包括Memcached、Berkeley DB和Redis。不过，需要注意的是，系统属于持久化还是非持久化，有时划分得并没有那么绝对。目前很多系统在设计的时候都会支持多种功能。例如，我们也可以使用MongoDB做缓存，而下面即将介绍的缓存方案Redis和Berkeley DB也是支持持久化存储的。这里的划分主要是按照这些系统目前在业界最常见的应用方式进行的。”