第三章 - 使用數(shù)據(jù)結(jié)構(gòu)

在上一章里，我們談?wù)摿薘edis的5種數(shù)據(jù)結(jié)構(gòu)，對于一些可能的用途也給出了用例?，F(xiàn)在是時候來看看一些更高級，但依然很常見的主題和設(shè)計模式。

大O表示法（Big O Notation）

在本書中，我們之前就已經(jīng)看到過大O表示法，包括O(1)和O(N)的表示。大O表示法的慣常用途是，描述一些用于處理一定數(shù)量元素的行為的綜合表現(xiàn)。在Redis里，對于一個要處理一定數(shù)量元素的命令，大O表示法讓我們能了解該命令的大概運(yùn)行速度。

在Redis的文檔里，每一個命令的時間復(fù)雜度都用大O表示法進(jìn)行了描述，還能知道各命令的具體性能會受什么因素影響。讓我們來看看一些用例。

常數(shù)時間復(fù)雜度O(1)被認(rèn)為是最快速的，無論我們是在處理5個元素還是5百萬個元素，最終都能得到相同的性能。對于sismember命令，其作用是告訴我們一個值是否屬于一個集合，時間復(fù)雜度為O(1)。sismember命令很強(qiáng)大，很大部分的原因是其高效的性能特征。許多Redis命令都具有O(1)的時間復(fù)雜度。

對數(shù)時間復(fù)雜度O(log(N))被認(rèn)為是第二快速的，其通過使需掃描的區(qū)間不斷皺縮來快速完成處理。使用這種“分而治之”的方式，大量的元素能在幾個迭代過程里被快速分解完整。zadd命令的時間復(fù)雜度就是O(log(N))，其中N是在分類集合中的元素數(shù)量。

再下來就是線性時間復(fù)雜度O(N)，在一個表格的非索引列里進(jìn)行查找就需要O(N)次操作。ltrim命令具有O(N)的時間復(fù)雜度，但是，在ltrim命令里，N不是列表所擁有的元素數(shù)量，而是被刪除的元素數(shù)量。從一個具有百萬元素的列表里用ltrim命令刪除1個元素，要比從一個具有一千個元素的列表里用ltrim命令刪除10個元素來的快速（實(shí)際上，兩者很可能會是一樣快，因?yàn)閮蓚€時間都非常的?。?/p>

根據(jù)給定的最小和最大的值的標(biāo)記，zremrangebyscore命令會在一個分類集合里進(jìn)行刪除元素操作，其時間復(fù)雜度是O(log(N)+M)。這看起來似乎有點(diǎn)兒雜亂，通過閱讀文檔可以知道，這里的N指的是在分類集合里的總元素數(shù)量，而M則是被刪除的元素數(shù)量。可以看出，對于性能而言，被刪除的元素數(shù)量很可能會比分類集合里的總元素數(shù)量更為重要。

（譯注：zremrangebyscore命令的具體構(gòu)成是ZREMRANGEBYSCORE Key max mix。）

對于sort命令，其時間復(fù)雜度為O(N+M*log(M))，我們將會在下一章談?wù)摳嗟南嚓P(guān)細(xì)節(jié)。從sort命令的性能特征來看，可以說這是Redis里最復(fù)雜的一個命令。

還存在其他的時間復(fù)雜度描述，包括O(N^2)和O(C^N)。隨著N的增大，其性能將急速下降。在Redis里，沒有任何一個命令具有這些類型的時間復(fù)雜度。

值得指出的一點(diǎn)是，在Redis里，當(dāng)我們發(fā)現(xiàn)一些操作具有O(N)的時間復(fù)雜度時，我們可能可以找到更為好的方法去處理。

（譯注：對于Big O Notation，相信大家都非常的熟悉，雖然原文僅僅是對該表示法進(jìn)行簡單的介紹，但限于個人的算法知識和文筆水平實(shí)在有限，此小節(jié)的翻譯讓我頭痛頗久，最終成果也確實(shí)難以讓人滿意，望見諒。）

仿多關(guān)鍵字查詢（Pseudo Multi Key Queries）

時常，你會想通過不同的關(guān)鍵字去查詢相同的值。例如，你會想通過電子郵件（當(dāng)用戶開始登錄時）去獲取用戶的具體信息，或者通過用戶id（在用戶登錄后）去獲取。有一種很不實(shí)效的解決方法，其將用戶對象分別放置到兩個字符串值里去：

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

這種方法很糟糕，如此不但會產(chǎn)生兩倍數(shù)量的內(nèi)存，而且這將會成為數(shù)據(jù)管理的惡夢。

如果Redis允許你將一個關(guān)鍵字鏈接到另一個的話，可能情況會好很多，可惜Redis并沒有提供這樣的功能（而且很可能永遠(yuǎn)都不會提供）。Redis發(fā)展到現(xiàn)在，其開發(fā)的首要目的是要保持代碼和API的整潔簡單，關(guān)鍵字鏈接功能的內(nèi)部實(shí)現(xiàn)并不符合這個前提（對于關(guān)鍵字，我們還有很多相關(guān)方法沒有談?wù)摰剑Ｆ鋵?shí)，Redis已經(jīng)提供了解決的方法：散列。

使用散列數(shù)據(jù)結(jié)構(gòu)，我們可以擺脫重復(fù)的纏繞：

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}")

你很可能將會經(jīng)常使用這類用法。在我看來，這就是散列真正耀眼的地方。在你了解這類用法之前，這可能不是一個明顯的用例。

引用和索引（References and Indexes）

我們已經(jīng)看過幾個關(guān)于值引用的用例，包括介紹列表數(shù)據(jù)結(jié)構(gòu)時的用例，以及在上面使用散列數(shù)據(jù)結(jié)構(gòu)來使查詢更靈活一些。進(jìn)行歸納后會發(fā)現(xiàn)，對于那些值與值間的索引和引用，我們都必須手動的去管理。誠實(shí)來講，這確實(shí)會讓人有點(diǎn)沮喪，尤其是當(dāng)你想到那些引用相關(guān)的操作，如管理、更新和刪除等，都必須手動的進(jìn)行時。在Redis里，這個問題還沒有很好的解決方法。

我們已經(jīng)看到，集合數(shù)據(jù)結(jié)構(gòu)很常被用來實(shí)現(xiàn)這類索引：

sadd friends:leto ghanima paul chani jessica

這個集合里的每一個成員都是一個Redis字符串?dāng)?shù)據(jù)結(jié)構(gòu)的引用，而每一個引用的值則包含著用戶對象的具體信息。那么如果chani改變了她的名字，或者刪除了她的帳號，應(yīng)該如何處理？從整個朋友圈的關(guān)系結(jié)構(gòu)來看可能會更好理解，我們知道，chani也有她的朋友：

sadd friends_of:chani leto paul

如果你有什么待處理情況像上面那樣，那在維護(hù)成本之外，還會有對于額外索引值的處理和存儲空間的成本。這可能會令你感到有點(diǎn)退縮。在下一小節(jié)里，我們將會談?wù)摐p少使用額外數(shù)據(jù)交互的性能成本的一些方法（在第1章我們粗略地討論了下）。

如果你確實(shí)在擔(dān)憂著這些情況，其實(shí)，關(guān)系型數(shù)據(jù)庫也有同樣的開銷。索引需要一定的存儲空間，必須通過掃描或查找，然后才能找到相應(yīng)的記錄。其開銷也是存在的，當(dāng)然他們對此做了很多的優(yōu)化工作，使之變得更為有效。

再次說明，需要在Redis里手動地管理引用確實(shí)是頗為棘手。但是，對于你關(guān)心的那些問題，包括性能或存儲空間等，應(yīng)該在經(jīng)過測試后，才會有真正的理解。我想你會發(fā)現(xiàn)這不會是一個大問題。

數(shù)據(jù)交互和流水線（Round Trips and Pipelining）

我們已經(jīng)提到過，與服務(wù)器頻繁交互是Redis的一種常見模式。這類情況可能很常出現(xiàn)，為了使我們能獲益更多，值得仔細(xì)去看看我們能利用哪些特性。

許多命令能接受一個或更多的參數(shù)，也有一種關(guān)聯(lián)命令（sister-command）可以接受多個參數(shù)。例如早前我們看到過mget命令，接受多個關(guān)鍵字，然后返回值：

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還支持流水線功能。通常情況下，當(dāng)一個客戶端發(fā)送請求到Redis后，在發(fā)送下一個請求之前必須等待Redis的答復(fù)。使用流水線功能，你可以發(fā)送多個請求，而不需要等待Redis響應(yīng)。這不但減少了網(wǎng)絡(luò)開銷，還能獲得性能上的顯著提高。

值得一提的是，Redis會使用存儲器去排列命令，因此批量執(zhí)行命令是一個好主意。至于具體要多大的批量，將取決于你要使用什么命令（更明確來說，該參數(shù)有多大）。另一方面來看，如果你要執(zhí)行的命令需要差不多50個字符的關(guān)鍵字，你大概可以對此進(jìn)行數(shù)千或數(shù)萬的批量操作。

對于不同的Redis載體，在流水線里運(yùn)行命令的方式會有所差異。在Ruby里，你傳遞一個代碼塊到pipelined方法：

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

正如你可能猜想到的，流水線功能可以實(shí)際地加速一連串命令的處理。

事務(wù)（Transactions）

每一個Redis命令都具有原子性，包括那些一次處理多項(xiàng)事情的命令。此外，對于使用多個命令，Redis支持事務(wù)功能。

你可能不知道，但Redis實(shí)際上是單線程運(yùn)行的，這就是為什么每一個Redis命令都能夠保證具有原子性。當(dāng)一個命令在執(zhí)行時，沒有其他命令會運(yùn)行（我們會在往后的章節(jié)里簡略談?wù)撘幌耂caling）。在你考慮到一些命令去做多項(xiàng)事情時，這會特別的有用。例如：

incr命令實(shí)際上就是一個get命令然后緊隨一個set命令。

getset命令設(shè)置一個新的值然后返回原始值。

setnx命令首先測試關(guān)鍵字是否存在，只有當(dāng)關(guān)鍵字不存在時才設(shè)置值

雖然這些都很有用，但在實(shí)際開發(fā)時，往往會需要運(yùn)行具有原子性的一組命令。若要這樣做，首先要執(zhí)行multi命令，緊隨其后的是所有你想要執(zhí)行的命令（作為事務(wù)的一部分），最后執(zhí)行exec命令去實(shí)際執(zhí)行命令，或者使用discard命令放棄執(zhí)行命令。Redis的事務(wù)功能保證了什么？

• 事務(wù)中的命令將會按順序地被執(zhí)行

• 事務(wù)中的命令將會如單個原子操作般被執(zhí)行（沒有其它的客戶端命令會在中途被執(zhí)行）

• 事務(wù)中的命令要么全部被執(zhí)行，要么不會執(zhí)行

你可以（也應(yīng)該）在命令行界面對事務(wù)功能進(jìn)行一下測試。還有一點(diǎn)要注意到，沒有什么理由不能結(jié)合流水線功能和事務(wù)功能。

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

最后，Redis能讓你指定一個關(guān)鍵字（或多個關(guān)鍵字），當(dāng)關(guān)鍵字有改變時，可以查看或者有條件地應(yīng)用一個事務(wù)。這是用于當(dāng)你需要獲取值，且待運(yùn)行的命令基于那些值時，所有都在一個事務(wù)里。對于上面展示的代碼，我們不能去實(shí)現(xiàn)自己的incr命令，因?yàn)橐坏?code>exec命令被調(diào)用，他們會全部被執(zhí)行在一塊。我們不能這么做：

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

（譯注：雖然Redis是單線程運(yùn)行的，但是我們可以同時運(yùn)行多個Redis客戶端進(jìn)程，常見的并發(fā)問題還是會出現(xiàn)。像上面的代碼，在get運(yùn)行之后，set運(yùn)行之前，powerlevel的值可能會被另一個Redis客戶端給改變，從而造成錯誤。）

這些不是Redis的事務(wù)功能的工作。但是，如果我們增加一個watch到powerlevel，我們可以這樣做：

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

在我們調(diào)用watch后，如果另一個客戶端改變了powerlevel的值，我們的事務(wù)將會運(yùn)行失敗。如果沒有客戶端改變powerlevel的值，那么事務(wù)會繼續(xù)工作。我們可以在一個循環(huán)里運(yùn)行這些代碼，直到其能正常工作。

關(guān)鍵字反模式（Keys Anti-Pattern）

在下一章中，我們將會談?wù)撃切]有確切關(guān)聯(lián)到數(shù)據(jù)結(jié)構(gòu)的命令，其中的一些是管理或調(diào)試工具。然而有一個命令我想特別地在這里進(jìn)行談?wù)摚?code>keys命令。這個命令需要一個模式，然后查找所有匹配的關(guān)鍵字。這個命令看起來很適合一些任務(wù)，但這不應(yīng)該用在實(shí)際的產(chǎn)品代碼里。為什么？因?yàn)檫@個命令通過線性掃描所有的關(guān)鍵字來進(jìn)行匹配?；蛘撸唵蔚卣f，這個命令太慢了。

人們會如此去使用這個命令？一般會用來構(gòu)建一個本地的Bug追蹤服務(wù)。每一個帳號都有一個id，你可能會通過一個看起來像bug:account_id:bug_id的關(guān)鍵字，把每一個Bug存儲到一個字符串?dāng)?shù)據(jù)結(jié)構(gòu)值中去。如果你在任何時候需要查詢一個帳號的Bug（顯示它們，或者當(dāng)用戶刪除了帳號時刪除掉這些Bugs），你可能會嘗試去使用keys命令：

keys bug:1233:*

更好的解決方法應(yīng)該使用一個散列數(shù)據(jù)結(jié)構(gòu)，就像我們可以使用散列數(shù)據(jù)結(jié)構(gòu)來提供一種方法去展示二級索引，因此我們可以使用域來組織數(shù)據(jù)：

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

從一個帳號里獲取所有的Bug標(biāo)識，可以簡單地調(diào)用hkeys bugs:1233。去刪除一個指定的Bug，可以調(diào)用hdel bugs:1233 2。如果要刪除了一個帳號，可以通過del bugs:1233把關(guān)鍵字刪除掉。

小結(jié)

結(jié)合這一章以及前一章，希望能讓你得到一些洞察力，了解如何使用Redis去支持（Power）實(shí)際項(xiàng)目。還有其他的模式可以讓你去構(gòu)建各種類型的東西，但真正的關(guān)鍵是要理解基本的數(shù)據(jù)結(jié)構(gòu)。你將能領(lǐng)悟到，這些數(shù)據(jù)結(jié)構(gòu)是如何能夠?qū)崿F(xiàn)你最初視角之外的東西。