第3章 - 使用数据结构

在上一章里，我们谈论了Redis的5种数据结构，对于一些可能的用途也给出了用例。现在是时候来看看一些更高级，但依然很常见的主题和设计模式。

大O表示法（Big O Notation）

在本书中，我们之前就已经看到过大O表示法，包括O(1)和O(N)的表示。大O表示法的惯常用途是，描述一些用于处理一定数量元素的行为的综合表现。在Redis里，对于一个要处理一定数量元素的命令，大O表示法让我们能了解该命令的大概运行速度。

在Redis的文档里，每一个命令的时间复杂度都用大O表示法进行了描述，还能知道各命令的具体性能会受什么因素影响。让我们来看看一些用例。

常数时间复杂度O(1)被认为是最快速的，无论我们是在处理5个元素还是5百万个元素，最终都能得到相同的性能。对于sismember命令，其作用是告诉我们一个值是否属于一个集合，时间复杂度为O(1)。sismember命令很强大，很大部分的原因是其高效的性能特征。许多Redis命令都具有O(1)的时间复杂度。

对数时间复杂度O(log(N))被认为是第二快速的，其通过使需扫描的区间不断皱缩来快速完成处理。使用这种“分而治之”的方式，大量的元素能在几个迭代过程里被快速分解完整。zadd命令的时间复杂度就是O(log(N))，其中N是在分类集合中的元素数量。

再下来就是线性时间复杂度O(N)，在一个表格的非索引列里进行查找就需要O(N)次操作。ltrim命令具有O(N)的时间复杂度，但是，在ltrim命令里，N不是列表所拥有的元素数量，而是被删除的元素数量。从一个具有百万元素的列表里用ltrim命令删除1个元素，要比从一个具有一千个元素的列表里用ltrim命令删除10个元素来的快速（实际上，两者很可能会是一样快，因为两个时间都非常的小）。

根据给定的最小和最大的值的标记，zremrangebyscore命令会在一个分类集合里进行删除元素操作，其时间复杂度是O(log(N)+M)。这看起来似乎有点儿杂乱，通过阅读文档可以知道，这里的N指的是在分类集合里的总元素数量，而M则是被删除的元素数量。可以看出，对于性能而言，被删除的元素数量很可能会比分类集合里的总元素数量更为重要。

（译注：zremrangebyscore命令的具体构成是ZREMRANGEBYSCORE Key max mix。）

对于sort命令，其时间复杂度为O(N+M*log(M))，我们将会在下一章谈论更多的相关细节。从sort命令的性能特征来看，可以说这是Redis里最复杂的一个命令。

还存在其他的时间复杂度描述，包括O(N^2)和O(C^N)。随着N的增大，其性能将急速下降。在Redis里，没有任何一个命令具有这些类型的时间复杂度。

值得指出的一点是，在Redis里，当我们发现一些操作具有O(N)的时间复杂度时，我们可能可以找到更为好的方法去处理。

（译注：对于Big O Notation，相信大家都非常的熟悉，虽然原文仅仅是对该表示法进行简单的介绍，但限于个人的算法知识和文笔水平实在有限，此小节的翻译让我头痛颇久，最终成果也确实难以让人满意，望见谅。）

仿多关键字查询（Pseudo Multi Key Queries）

时常，你会想通过不同的关键字去查询相同的值。例如，你会想通过电子邮件（当用户开始登录时）去获取用户的具体信息，或者通过用户id（在用户登录后）去获取。有一种很不实效的解决方法，其将用户对象分别放置到两个字符串值里去：

set users:leto@dune.gov "{id: 9001, email: 'leto@dune.gov', ...}"
set users:9001 "{id: 9001, email: 'leto@dune.gov', ...}"

这种方法很糟糕，如此不但会产生两倍数量的内存，而且这将会成为数据管理的恶梦。

如果Redis允许你将一个关键字链接到另一个的话，可能情况会好很多，可惜Redis并没有提供这样的功能（而且很可能永远都不会提供）。Redis发展到现在，其开发的首要目的是要保持代码和API的整洁简单，关键字链接功能的内部实现并不符合这个前提（对于关键字，我们还有很多相关方法没有谈论到）。其实，Redis已经提供了解决的方法：散列。

使用散列数据结构，我们可以摆脱重复的缠绕：

set users:9001 "{id: 9001, email: leto@dune.gov, ...}"
hset users:lookup:email leto@dune.gov 9001

我们所做的是，使用域来作为一个二级索引，然后去引用单个用户对象。要通过id来获取用户信息，我们可以使用一个普通的get命令：

get users:9001

而如果想通过电子邮箱来获取用户信息，我们可以使用hget命令再配合使用get命令（Ruby代码）：

id = redis.hget('users:lookup:email', 'leto@dune.gov')
user = redis.get("users:#{id}")

你很可能将会经常使用这类用法。在我看来，这就是散列真正耀眼的地方。在你了解这类用法之前，这可能不是一个明显的用例。

引用和索引（References and Indexes）

我们已经看过几个关于值引用的用例，包括介绍列表数据结构时的用例，以及在上面使用散列数据结构来使查询更灵活一些。进行归纳后会发现，对于那些值与值间的索引和引用，我们都必须手动的去管理。诚实来讲，这确实会让人有点沮丧，尤其是当你想到那些引用相关的操作，如管理、更新和删除等，都必须手动的进行时。在Redis里，这个问题还没有很好的解决方法。

我们已经看到，集合数据结构很常被用来实现这类索引：

sadd friends:leto ghanima paul chani jessica

这个集合里的每一个成员都是一个Redis字符串数据结构的引用，而每一个引用的值则包含着用户对象的具体信息。那么如果chani改变了她的名字，或者删除了她的帐号，应该如何处理？从整个朋友圈的关系结构来看可能会更好理解，我们知道，chani也有她的朋友：

sadd friends_of:chani leto paul

如果你有什么待处理情况像上面那样，那在维护成本之外，还会有对于额外索引值的处理和存储空间的成本。这可能会令你感到有点退缩。在下一小节里，我们将会谈论减少使用额外数据交互的性能成本的一些方法（在第1章我们粗略地讨论了下）。

如果你确实在担忧着这些情况，其实，关系型数据库也有同样的开销。索引需要一定的存储空间，必须通过扫描或查找，然后才能找到相应的记录。其开销也是存在的，当然他们对此做了很多的优化工作，使之变得更为有效。

再次说明，需要在Redis里手动地管理引用确实是颇为棘手。但是，对于你关心的那些问题，包括性能或存储空间等，应该在经过测试后，才会有真正的理解。我想你会发现这不会是一个大问题。

数据交互和流水线（Round Trips and Pipelining）

我们已经提到过，与服务器频繁交互是Redis的一种常见模式。这类情况可能很常出现，为了使我们能获益更多，值得仔细去看看我们能利用哪些特性。

许多命令能接受一个或更多的参数，也有一种关联命令（sister-command）可以接受多个参数。例如早前我们看到过mget命令，接受多个关键字，然后返回值：

keys = redis.lrange('newusers', 0, 10)
redis.mget(*keys.map {|u| "users:#{u}"})

或者是sadd命令，能添加一个或多个成员到集合里：

sadd friends:vladimir piter
sadd friends:paul jessica leto "leto II" chani

Redis还支持流水线功能。通常情况下，当一个客户端发送请求到Redis后，在发送下一个请求之前必须等待Redis的答复。使用流水线功能，你可以发送多个请求，而不需要等待Redis响应。这不但减少了网络开销，还能获得性能上的显著提高。

值得一提的是，Redis会使用存储器去排列命令，因此批量执行命令是一个好主意。至于具体要多大的批量，将取决于你要使用什么命令（更明确来说，该参数有多大）。另一方面来看，如果你要执行的命令需要差不多50个字符的关键字，你大概可以对此进行数千或数万的批量操作。

对于不同的Redis载体，在流水线里运行命令的方式会有所差异。在Ruby里，你传递一个代码块到pipelined方法：

redis.pipelined do
  9001.times do
    redis.incr('powerlevel')
  end
end

正如你可能猜想到的，流水线功能可以实际地加速一连串命令的处理。

事务（Transactions）

每一个Redis命令都具有原子性，包括那些一次处理多项事情的命令。此外，对于使用多个命令，Redis支持事务功能。

你可能不知道，但Redis实际上是单线程运行的，这就是为什么每一个Redis命令都能够保证具有原子性。当一个命令在执行时，没有其他命令会运行（我们会在往后的章节里简略谈论一下Scaling）。在你考虑到一些命令去做多项事情时，这会特别的有用。例如：

incr命令实际上就是一个get命令然后紧随一个set命令。

getset命令设置一个新的值然后返回原始值。

setnx命令首先测试关键字是否存在，只有当关键字不存在时才设置值

虽然这些都很有用，但在实际开发时，往往会需要运行具有原子性的一组命令。若要这样做，首先要执行multi命令，紧随其后的是所有你想要执行的命令（作为事务的一部分），最后执行exec命令去实际执行命令，或者使用discard命令放弃执行命令。Redis的事务功能保证了什么？

• 事务中的命令将会按顺序地被执行

• 事务中的命令将会如单个原子操作般被执行（没有其它的客户端命令会在中途被执行）

• 事务中的命令要么全部被执行，要么不会执行

你可以（也应该）在命令行界面对事务功能进行一下测试。还有一点要注意到，没有什么理由不能结合流水线功能和事务功能。

multi
hincrby groups:1percent balance -9000000000
hincrby groups:99percent balance 9000000000
exec

最后，Redis能让你指定一个关键字（或多个关键字），当关键字有改变时，可以查看或者有条件地应用一个事务。这是用于当你需要获取值，且待运行的命令基于那些值时，所有都在一个事务里。对于上面展示的代码，我们不能去实现自己的incr命令，因为一旦exec命令被调用，他们会全部被执行在一块。我们不能这么做：

redis.multi()
current = redis.get('powerlevel')
redis.set('powerlevel', current + 1)
redis.exec()

（译注：虽然Redis是单线程运行的，但是我们可以同时运行多个Redis客户端进程，常见的并发问题还是会出现。像上面的代码，在get运行之后，set运行之前，powerlevel的值可能会被另一个Redis客户端给改变，从而造成错误。）

这些不是Redis的事务功能的工作。但是，如果我们增加一个watch到powerlevel，我们可以这样做：

redis.watch('powerlevel')
current = redis.get('powerlevel')
redis.multi()
redis.set('powerlevel', current + 1)
redis.exec()

在我们调用watch后，如果另一个客户端改变了powerlevel的值，我们的事务将会运行失败。如果没有客户端改变powerlevel的值，那么事务会继续工作。我们可以在一个循环里运行这些代码，直到其能正常工作。

关键字反模式（Keys Anti-Pattern）

在下一章中，我们将会谈论那些没有确切关联到数据结构的命令，其中的一些是管理或调试工具。然而有一个命令我想特别地在这里进行谈论：keys命令。这个命令需要一个模式，然后查找所有匹配的关键字。这个命令看起来很适合一些任务，但这不应该用在实际的产品代码里。为什么？因为这个命令通过线性扫描所有的关键字来进行匹配。或者，简单地说，这个命令太慢了。

人们会如此去使用这个命令？一般会用来构建一个本地的Bug追踪服务。每一个帐号都有一个id，你可能会通过一个看起来像bug:account_id:bug_id的关键字，把每一个Bug存储到一个字符串数据结构值中去。如果你在任何时候需要查询一个帐号的Bug（显示它们，或者当用户删除了帐号时删除掉这些Bugs），你可能会尝试去使用keys命令：

keys bug:1233:*

更好的解决方法应该使用一个散列数据结构，就像我们可以使用散列数据结构来提供一种方法去展示二级索引，因此我们可以使用域来组织数据：

hset bugs:1233 1 "{id:1, account: 1233, subject: '...'}"
hset bugs:1233 2 "{id:2, account: 1233, subject: '...'}"

从一个帐号里获取所有的Bug标识，可以简单地调用hkeys bugs:1233。去删除一个指定的Bug，可以调用hdel bugs:1233 2。如果要删除了一个帐号，可以通过del bugs:1233把关键字删除掉。

小结

结合这一章以及前一章，希望能让你得到一些洞察力，了解如何使用Redis去支持（Power）实际项目。还有其他的模式可以让你去构建各种类型的东西，但真正的关键是要理解基本的数据结构。你将能领悟到，这些数据结构是如何能够实现你最初视角之外的东西。