6.1 自动补全 6.1.1 自 动补全最近联系人 因为Redis的列表会以有序的方式来存储元素， 并且和Redis提供的其他结构相比， 列表占用的内存是最少的， 所以我们选择使用列表来存储用户的联系人信息 构建最近联系人自 动补全列表通常需要对Redis执行3个操作。 第一个操作 就是添加或者更新一个联系人， 让他成为最新的被联系用户， 这个操作包含以下3个步骤。 （ 1） 如果指定的联系人已经存在于最近联系人列表里面， 那么从列 表里面移除他。 （ 2） 将指定的联系人添加到最近联系人列表的最前面。 （ 3） 如果在添加操作完成之后， 最近联系人列表包含的联系人数量 超过了 100个， 那么对列表进行修剪， 只保留位于列表前面的100个联系人。以上描述的3个操作可以通过依次执行LREM命令、 LPUSH命令和LTRIM命令来实现， 并且为了确保操作不会带有任何竞争条件， 我们会像在第3章中介绍的那样， 使用由MULTI命令和EXEC命令构成的事务包裹起LREM、 LPUSH和LTRIM这3个命令 第二个操作 就是在用户不想再看见某个联系人的时候， 将指定的联系人从联系人列表里面移除掉，这个操作可以通过以下这个LREM调用来完成： 最后一个操作 就是获取自 动补全列表并查找匹配的用户。 因为实际的自 动补全处理是在Python里面完成的， 所以操作需要首先获取整个列表结构， 然后再在Python里面处理它， 正如代码清单6-2所示
因为我们已经预先考虑到了 “从列表里面移除一个元素所需的时间与列表长度成正比”这个问题， 并明确地限制最近联系人列表最多只能存储100个联系人， 所以本节给出的自 动补全实现可以运行得非常好， 并且速度也足够快， 但它并不适合用来处理非常大的列表。 如果你需要一个能够存储更多元素的最常使用列表（ most-recently-used list） 或者最少使用列表（ least-recently-used list） ， 那么可以考虑使用带有时间戳的有序集合来代替本节介绍的最近联系人列表。 6.1.2 通讯录自动补全 对于比较短的列表来说， 这种做法还算可行， 但对于非常长的列表来说， 仅仅为了找到几个元素而获取成千上万个元素， 是一种非常浪费资源的做法。 因此， 为了对包含非常多元素的列表进行自 动补全， 我们必须直接在Redis内部完成查找匹配元素的工作。 为了在客户端进行自 动补全的时候， 尽量减少服务器需要传输给客户端的数据量， 我们将使用有序集合来直接在Redis内部完成自 动补全的前缀计算工作。 在大多数情况下， 我们使用有序集合是为了快速地判断某个元素是否存在于有序集合里面、 查看某个成员在有序集合中的位置或索引 ， 以及从有序集合的某个地方快速地按范围取出多个元素。 而这一次， 我们将把有序集合里面的所有分值都设置为0——这种做法使得我们可以使用有序集合的另一个特性： 当所有成员的分值都相同时， 有序集合将根据成员的名字来进行排序； 而当所有成员的分值都是0的时候， 成员将按照字符串的二进制顺序进行排序 为了执行自 动补全操作， 程序会以小写字母的方式插入联系人的名字， 并且为了方便起见， 程序规定用户的名字只能包含英文字母， 这样的话就不需要考虑如何处理数字或者符号了。 （1） 那么我们该如何实现这个自 动补全功能呢？ 首先， 如果我们将用户的名字看作是类似abc， abca， abcd， …， abd这样的有序字符串序列， 那么查找带有abc前缀的单词实际上就是查找介于abbz. . . 之后和abd之前的字符串。 如果我们知道第一个排在abbz之前的元素的排名以及第一个排在abd之后的元素的排名， 那么就可以用一个ZRANGE调用来取得所有介于abbz. . . 和abd之间的元素， 而问题就在于我们并不知道那两个元素的具体排名。 为了解决这个问题， 我们需要向有序集合分别插入两个元素， 一个元素排在abbz. . . 的后面， 而另一个元素则排在abd的前面， 接着根据这两个元素的排名来调用ZRANGE命令， 最后移除被插入的两个元素。 因为在ASCII编码里面， 排在z后面的第一个字符就是左花括号{， 所以我们只要将{拼接到abc前缀的末尾， 就可以得出元素abc{， 这个元素既位于abd之前， 又位于所有带有abc前缀的合法名字之后。 同样的， 只要将{追加到abb的末尾， 就可以得出元素abb{， 这个元素位于所有带有abc前缀的合法名字之前， 可以在按范围查找所有带有abc前缀的名字时， 将其用作起始元素。 另一方面， 因为在ASCII编码里面，第一个排在a前面的字符就是反引 号`， 所以如果我们要查找的是带有aba前缀的名字， 而不是带有abc前缀的名字， 那么可以使用ab` 作为范围查找的起始元素， 并将aba{用作范围查找的结束元素。综上所述， 通过将给定前缀的最后一个字符替换为第一个排在该字符前面的字符， 可以得到前缀的前驱（ predecessor） ， 而通过给前缀的末尾拼接上左花括号， 可以得到前缀的后继（ successor） 。 为了防止多个前缀搜索同时进行时出现任何问题， 程序还会给前缀拼接一个左花括号， 以便在有需要的时候， 根据这个左花括号来过滤掉被插入有序集合里面的起始元素和结束元素。 （2） 字符集与国际化 对于只使用a～z字符的语言来说， 这个在ASCII编码里面查找前一个字符和后一个字符的方法可以运作得非常好， 但如果你要处理的字符并不仅仅限于a～z范围， 那么你还需要解决其他几个问题。 首先， 你需要想办法把所有字符都转换为字节， 常见的做法是使用UTF-8、 UTF-16或者UTF-32字符编码（ UTF-16和UTF-32有大端版本和小端版本可用， 但只有大端版本可以在我们所处的情况下运作） 。 其次， 你需要找出自 己想要支持的字符范围， 并确保你的字符编码在你所选范围的前面和后面都至少留有一个字符。 最后， 你需要使用位于范围前面和后面的字符来分别代替前面例子中的反引 号` 和左花括号{。 好在我们的算法只关心编码而不是字符在底层的排列顺序， 所以无论你使用的是UTF-8， 还是大端或者小端的UTF-16、 UTF-32， 你都可以使用空字节（ null） 来代替反引 号， 并使用你的编码和语言支持的最大值来代替左花括号。 （某些语言的绑定数量是比较有限的， 它们在UTF-16上面最大只能支持Unicode码点U+ffff， 在UTF-32上面最大只能支持Unicode码点U+2ffff。 ） 在确认了需要查找的范围之后， 程序会将起始元素和结束元素插入有序集合里面， 然后查看两个被插入元素的排名， 并从它们之间取出一些元素， 最后再从有序集合里面移除这两个元素（为了避免滋扰用户，程序最多只会取出10个元素） 。 为了防止自 动补全程序在多个公会成员同时向同一个公会成员发送消息的时候， 将多个相同的起始元素和结束元素重复地添加到有序集合里面， 或者错误地从有序集合里面移除了由其他自 动补全程序添加的起始元素和结束元素， 自 动补全程序会将一个随机生成的128位全局唯一标识符（ UUID） 添加到起始元素和结束元素的后面。 另外自 动补全程序还会在插入起始元素和结束元素之后， 通过使用WATCH、 MULTI和EXEC来确保有序集合不会在进行范围查找和范围取值期间发生变化。 通过向有序集合添加元素来创建查找范围， 并在取得范围内的元素之后移除之前添加的元素， 这是一种非常有用的技术。 虽然本章只将这种技术用在了实现自 动补全上面， 但是这种技术同样可以应用在任何已排序索引 （ sorted index） 上面。 第7章中将会介绍一种能够改善这类操作的技术， 这种技术能够应用于几种不同类型的范围查询， 并且不需要过添加元素来创建范围。 之所以把这个改善后的方法留到之后才介绍， 是因为它只能够应用于某些类型的数据， 而本章介绍的方法则可以对任意类型的数据进行范围查询。 我们需要谨慎地处理其他正在执行的自 动补全操作， 这也是程序里面用到了WATCH命令的原因。 但是随着负载的增加， 程序进行重试的次数可能会越来越多， 导致资源被白白浪费。 接下来的一节将介绍如何通过使用锁来减少对WATCH命令的使用， 甚至使用锁来代替WATCH命令， 从而达到避免重试、 提升性能并在某些情况下简化代码的效果。
6.2 分布式锁 Redis使用WATCH命令来代替对数据进行加锁， 因为WATCH只会在数据被其他客户端抢先修改了的情况下通知执行了这个命令的客户端， 而不会阻止其他客户端对数据进行修改， 所以这个命令被称为乐观锁 分布式锁也有类似的“首先获取锁， 然后执行操作， 最后释放锁”动作， 但这种锁既不是给同一个进程中的多个线程使用， 也不是给同一台机器上的多个进程使用， 而是由不同机器上的不同Redis客户端进行获取和释放的。 虽然Redis提供的SETNX命令确实具有基本的加锁功能， 但它的功能并不完整， 并且也不具备分布式锁常见的一些高级特性， 所以我们还是需要自 己动手来构建分布式锁 这一节将会说明“为什么使用WATCH命令来监视被频繁访问的键可能会引 起性能问题”， 还会展示构建一个锁的详细步骤， 并最终在某些情况下使用锁去代替WATCH命令。 6.2.1 锁的重要性 现在来回顾一下商品的购物过程。 当玩家在市场上购买商品的时候， 程序首先需要使用WATCH去监视市场以及买家的个人信息散列， 在得知买家现有的钱数以及商品的售价之后， 程序会验证买家是否有足够的钱来购买指定的商品： 如果买家有足够的钱， 那么程序会将买家支付的钱转移给卖家， 接着将商品添加到买家的包裹里面， 并从市场里面移除已被售出的商品； 相反地， 如果买家没有足够的钱来购买商品， 那么程序就会取消事务。 在执行购买操作的过程中， 如果有其他玩家对市场进行了改动， 或者因为记录买家个人信息的散列出现了变化而引 发了WATCH错误， 那么程序将重新执行购买操作。 为了展示锁对于性能扩展的必要性， 我们会模拟市场在3种不同负载情况下的性能表现， 这3种情况分别是1个玩家出售商品， 另1个玩家购买商品； 5个玩家出售商品， 另1个玩家购买商品； 以及5个玩家出售商品， 另外5个玩家购买商品。 表6-1展示了模拟的结果。
（3） 因为在程序持有锁期间， 其他客户端可能会擅自 对锁进行修改， 所以锁的释放操作需要和加锁操作一样小心谨慎地进行。 代码清单6-10中的release_lock()函数展示了锁释放操作的实现代码： 函数首先使用WATCH命令监视代表锁的键， 接着检查键目 前的值是否和加锁时设置的值相同， 并在确认值没有变化之后删除该键（这个检查还可以防止程序错误地释放同一个锁多次） 。
在使用锁代替WATCH重新实现商品购买操作之后， 我们可以再次进行之前的商品买卖模拟操作： 表6-2中的单数行展示了WATCH实现的模拟结果， 而表中的复数行则展示了在与前一行条件相同的情况下， 锁实现的模拟结果。
新的acquire_lock_with_timeout()函数给锁增加了超时限制特性， 这一特性确保了锁总会在有需要的时候被释放， 而不会被某个客户 端一直把持着。 更棒的是， 这个新的加锁函数可以和之前写好的锁释放函数一起使用， 我们不需要另外再写新的锁释放函数。
6.3 计数信号量 计数信号量是一种锁， 它可以让用户限制一项资源最多能够同时被多少个进程访问， 通常用于限定能够同时使用的资源数量。 你可以把我们在前一节创建的锁看作是只能被一个进程访问的信号量。
6.4 任务队列 在处理Web客户端发送的命令请求时， 某些操作的执行时间可能会比我们预期的更长一些。 通过将待执行任务的相关信息放入队列里面，并在之后对队列进行处理， 用户可以推迟执行那些需要一段时间才能完成的操作， 这种将工作交给任务处理器来执行的做法被称为任务队列（ task queue） 。 现在有很多专门的任务队列软件（如ActiveMQ、RabbitMQ、 Gearman、 Amazon SQS， 等等） ， 另外在缺少专门的任务队列可用的情况下， 也有一些临时性的方法可以创建任务队列。 比方说使用定期作业来扫描一个数据表， 查找那些在给定时间/日 期之前或者之后被修改过/被检查过的用户账号， 并根据扫描的结果执行某些操作， 这也是在创建任务队列。 这一节接下来将介绍两种不同类型的任务队列， 第一种队列会根据务被插入队列的顺序来尽快地执行任务， 而第二种队列则具有安排任务在未来某个特定时间执行的能力。 6.4.1 先进先出队列 我们要编写的队列将以“先到先服务”（ first-come， first-served） 的方式发送邮件， 并且无论发送是否成功， 程序都会把发送结果记录到日 志里面。 本书在第3章和第5章中曾经介绍过， Redis的列表结构允许用户通过RPUSH和LPUSH以及RPOP和LPOP， 从列表的两端推入和弹出元素。这次的邮件队列将使用RPUSH命令来将待发送的邮件推入列表的右端，并且因为工作进程除了发送邮件之外不需要执行其他工作， 所以它将使用阻塞版本的弹出命令BLPOP从队列中弹出待发送的邮件， 而命令的最大阻塞时限为30秒（从右边推入元素并从左边弹出元素的做法， 符合我们从左向右进行阅读的习惯） 。 6.4.2 延迟任务 有几种不同的方法可以为队列中的任务添加延迟性质， 以下是其中3种最直截了当的方法。 1.在任务信息中包含任务的执行时间， 如果工作进程发现任务的执行时间尚未来临， 那么它将在短暂等待之后， 把任务重新推入队列里面。 2.工作进程使用一个本地的等待列表来记录所有需要在未来执行的任务， 并在每次进行while循环的时候， 检查等待列表并执行那些已 经到期的任务。 3.把所有需要在未来执行的任务都添加到有序集合里面， 并将任务的执行时间设置为分值， 另外再使用一个进程来查找有序集合里面是否存在可以立即被执行的任务， 如果有的话， 就从有序集合里面移除那个任务， 并将它添加到适当的任务队列里面。 因为无论是进行短暂的等待， 还是将任务重新推入队列里面， 都会浪费工作进程的时间， 所以我们不会采用第一种方法。 此外， 因为工作进程可能会因为崩溃而丢失本地记录的所有待执行任务， 所以我们也不会采用第二种方法。 最后， 因为使用有序集合的第三种方法最简单和直接， 所以我们将采取这一方法， 并使用6.2节中介绍的锁来保证任务从有序集合移动到任务队列时的安全性。
6.5 消息拉取 两个或多个客户端在互相发送和接收消息的时候， 通常会使用以下两种方法来传递消息。 第一种方法被称为消息推送（ push messaging） ， 也就是由发送者来确保所有接收者已经成功接收到了消息。 Redis内置了用于进行消息推送的PUBLISH命令和SUBSCRIBE命令，本书在第3章中已经介绍过这两个命令的用法和缺陷③。 第二种方法被称为消息拉取（ pull messaging） ， 这种方法要求接收者自 己去获取存储在某种邮箱（ mailbox） 里面的消息。 尽管消息推送非常有用， 但是当客户端因为某些原因而没办法一直保持在线的时候， 采用这一消息传递方法的程序就会出现各种各样的问题。 为了解决这个问题， 我们将编写两个不同的消息拉取方法， 并使用它们来代替PUBLISH命令和SUBSCRIBE命令。 6.5.1 单接收者消息的发送与订阅替代品 6.5.2 多接收者消息的发送与订阅替代品
6.6 使用 Redis进行文件分发 在构建分布式软件和分布式系统的时候， 我们常常需要在多台机器上复制、 分发或者处理数据文件， 而现有的工具可以以几种不同的方式来完成这些工作： （1）如果服务器需要持续地分发文件， 那么常见的做法是使用NFS或者Samba来载入一个路径（ path） 或者驱动器； （2）对于内容会逐渐发生变化的文件来说， 常见的做法是使用一款名为Rsync的软件来尽量减少两个系统之间需要传输的数据量； （3）在需要将多个文件副本分发到多台机器上面的时候， 可以使用BitTorrent协议来将文件部分地（ partial） 分发到多台机器上面， 然后通过让各台机器互相分享自 己所拥有的数据来降低服务器的负载。 遗憾的是， 以上提到的所有方法都有显著的安装成本以及相对的价值。 （1）虽然NFS和Samba都很好用， 但是由于这两种技术都对操作系统进行了整合， 所以它们在网络连接不完美的时候都会出现明显的问题（有时候甚至在网络连接无恙的情况下， 也是如此） 。 （2） Rsync旨在解决网络不稳定带来的问题， 让单个文件或者多个文件可以部分地进行传送和续传（ resume） ， 但Rsync在开始传输文件之前必须先下载整个文件， 并且负责获取文件的软件也必须与Rsync进行对接， 这一点是否可行也是一个需要考虑的地方。 （3）尽管BitTorrent是一个了不起的技术， 但它也只适用于服务器在发送文件方面遇到了限制或者网络未被充分使用的情况 下， 并且这种技术也需要软件与BitTorrent客户端进行对接， 而我们需要获取文件的系统上可能并没有合适的BitTorrent客户端可用。 除了上面提到的问题之外， 上述3种方法还需要设置并维护账号、 权限以及服务器。 因为我们已经有了一个安装完毕、 正在运行并且随时可用的Redis， 所以我们还是使用Redis来进行文件分发比较好， 这也可以避免使用其他软件时碰到的一些问题： Redis的客户端会妥善地处理连接故障， 通过客户端也可以直接获取数据， 并且针对数据的处理操作可以立即执行而不必等待整个文件出现。 6.6.1 根据地理位置聚合用户数据 6.6.2 发送日 志文件 6.6.3 接收日 志文件 6.6.4 处理日 志文件
6.7 小结 在这一章， 我们学习了 6个主要的主题， 但如果仔细地观察这些主题的话， 就会发现我们实际上解决了 9个问题。 本章尽可能地采用前面章节介绍过的想法和工具来构建更有用的工具， 以此来强调“解决某个问题时用到的技术， 同样可以用来解决其他问题”这个道理。 本章试图向读者传达的第一个概念是： 尽管WATCH是一个内置、 方便且有用的命令， 但是使用6.2节中介绍的分布式锁可以让针对Redis的并发编程变得简单得多。 通过锁住粒度更细的部件而不是整个数据库键， 可以大大减少冲突出现的几率， 而锁住各个相关的操作也有助于降低操作的复杂度。 在这一章中， 我们就看到了如何使用锁去简化4.6节介绍过的商品买卖市场以及6.4.2节介绍过的延迟任务队列， 并对它们的性能进行提升。 本章试图向读者传达的第二个概念， 读者应该铭记于心， 并将其付诸于实践的就是： 只要多花点心思， 就可以使用Redis构建出可重用的组件。 比如在这一章中， 我们就看到了如何在计数器信号量、 延迟队列和具有多个接收者的消息传递系统中重用分布式锁， 以及如何在使用Redis进行文件分发的时候， 重用具有多个接收者的消息传递系统。 在接下来的一章中， 我们将使用Redis来构建更高级的工具， 并编写文档索引 、 基于分值进行索引 和排序的搜索引 擎等能够支援整个应用序的代码， 还会实现一个广告追踪系统和一个职位搜索系统。 本书在后章节中也会继续使用这些组件， 因此请读者留心观察， 并记住使用Redis来构建可重用的组件并不是一件难事。 ② 本书作者对几个带有超时限制特性的Redis锁实现进行了测试，发现即使只使用5个客户端来获取和释放同一个锁， 也有至少一半的锁实现在10秒内就出现了多个客户端都获得了锁的问题。 ③ 简单来说， PUBLISH和SUBSCRIBE的缺陷在于客户端必须一直在线才能接收到消息， 断线可能会导致客户端丢失信息； 除此之外， 旧版Redis可能会因为订阅者处理消息的速度不够快而变得不稳定甚至崩溃， 又或者被管理员杀死。 ④ MapReduce（又称Map/Reduce） 是Google推广的一种分布式计算方式， 它可以高效并且简单地解决某些问题。