第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(在用户登录后)去获取。有一种很不实效的解决方法,其将用户对象分别放置到两个字符串值里去:

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

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

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

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

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

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

  1. get users:9001

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

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

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

引用和索引(References and Indexes)

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

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

  1. sadd friends:leto ghanima paul chani jessica

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

  1. sadd friends_of:chani leto paul

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

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

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

数据交互和流水线(Round Trips and Pipelining)

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

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

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

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

  1. sadd friends:vladimir piter
  2. sadd friends:paul jessica leto "leto II" chani

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

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

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

  1. redis.pipelined do
  2. 9001.times do
  3. redis.incr('powerlevel')
  4. end
  5. end

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

事务(Transactions)

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

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

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

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

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

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

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

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

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

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

  1. multi
  2. hincrby groups:1percent balance -9000000000
  3. hincrby groups:99percent balance 9000000000
  4. exec

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

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

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

这些不是Redis的事务功能的工作。但是,如果我们增加一个watchpowerlevel,我们可以这样做:

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

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

关键字反模式(Keys Anti-Pattern)

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

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

  1. keys bug:1233:*

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

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

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

小结

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