Redis 連鎖更新

前面說過， 每個節(jié)點(diǎn)的 previous_entry_length 屬性都記錄了前一個節(jié)點(diǎn)的長度：

• 如果前一節(jié)點(diǎn)的長度小于 254 字節(jié)， 那么 previous_entry_length 屬性需要用 1 字節(jié)長的空間來保存這個長度值。
• 如果前一節(jié)點(diǎn)的長度大于等于 254 字節(jié)， 那么 previous_entry_length 屬性需要用 5 字節(jié)長的空間來保存這個長度值。

現(xiàn)在， 考慮這樣一種情況： 在一個壓縮列表中， 有多個連續(xù)的、長度介于 250 字節(jié)到 253 字節(jié)之間的節(jié)點(diǎn) e1 至 eN ， 如圖 7-11 所示。

因為 e1 至 eN 的所有節(jié)點(diǎn)的長度都小于 254 字節(jié)， 所以記錄這些節(jié)點(diǎn)的長度只需要 1 字節(jié)長的 previous_entry_length 屬性， 換句話說，e1 至 eN 的所有節(jié)點(diǎn)的 previous_entry_length 屬性都是 1 字節(jié)長的。

這時， 如果我們將一個長度大于等于 254 字節(jié)的新節(jié)點(diǎn) new 設(shè)置為壓縮列表的表頭節(jié)點(diǎn)， 那么 new 將成為 e1 的前置節(jié)點(diǎn)， 如圖 7-12 所示。

因為 e1 的 previous_entry_length 屬性僅長 1 字節(jié)， 它沒辦法保存新節(jié)點(diǎn) new 的長度， 所以程序?qū)嚎s列表執(zhí)行空間重分配操作， 并將e1 節(jié)點(diǎn)的 previous_entry_length 屬性從原來的 1 字節(jié)長擴(kuò)展為 5 字節(jié)長。

現(xiàn)在， 麻煩的事情來了 —— e1 原本的長度介于 250 字節(jié)至 253 字節(jié)之間， 在為 previous_entry_length 屬性新增四個字節(jié)的空間之后， e1的長度就變成了介于 254 字節(jié)至 257 字節(jié)之間， 而這種長度使用 1 字節(jié)長的 previous_entry_length 屬性是沒辦法保存的。

因此， 為了讓 e2 的 previous_entry_length 屬性可以記錄下 e1 的長度， 程序需要再次對壓縮列表執(zhí)行空間重分配操作， 并將 e2 節(jié)點(diǎn)的previous_entry_length 屬性從原來的 1 字節(jié)長擴(kuò)展為 5 字節(jié)長。

正如擴(kuò)展 e1 引發(fā)了對 e2 的擴(kuò)展一樣， 擴(kuò)展 e2 也會引發(fā)對 e3 的擴(kuò)展， 而擴(kuò)展 e3 又會引發(fā)對 e4 的擴(kuò)展……為了讓每個節(jié)點(diǎn)的previous_entry_length 屬性都符合壓縮列表對節(jié)點(diǎn)的要求， 程序需要不斷地對壓縮列表執(zhí)行空間重分配操作， 直到 eN 為止。

Redis 將這種在特殊情況下產(chǎn)生的連續(xù)多次空間擴(kuò)展操作稱之為“連鎖更新”（cascade update）， 圖 7-13 展示了這一過程。

除了添加新節(jié)點(diǎn)可能會引發(fā)連鎖更新之外， 刪除節(jié)點(diǎn)也可能會引發(fā)連鎖更新。

考慮圖 7-14 所示的壓縮列表， 如果 e1 至 eN 都是大小介于 250 字節(jié)至 253 字節(jié)的節(jié)點(diǎn)， big 節(jié)點(diǎn)的長度大于等于 254 字節(jié)（需要 5 字節(jié)的 previous_entry_length 來保存）， 而 small 節(jié)點(diǎn)的長度小于 254 字節(jié)（只需要 1 字節(jié)的 previous_entry_length 來保存）， 那么當(dāng)我們將 small 節(jié)點(diǎn)從壓縮列表中刪除之后， 為了讓 e1 的 previous_entry_length 屬性可以記錄 big 節(jié)點(diǎn)的長度， 程序?qū)U(kuò)展 e1 的空間， 并由此引發(fā)之后的連鎖更新。

因為連鎖更新在最壞情況下需要對壓縮列表執(zhí)行 N 次空間重分配操作， 而每次空間重分配的最壞復(fù)雜度為 O(N) ， 所以連鎖更新的最壞復(fù)雜度為 O(N^2) 。

要注意的是， 盡管連鎖更新的復(fù)雜度較高， 但它真正造成性能問題的幾率是很低的：

• 首先， 壓縮列表里要恰好有多個連續(xù)的、長度介于 250 字節(jié)至 253 字節(jié)之間的節(jié)點(diǎn)， 連鎖更新才有可能被引發(fā)， 在實(shí)際中， 這種情況并不多見；
• 其次， 即使出現(xiàn)連鎖更新， 但只要被更新的節(jié)點(diǎn)數(shù)量不多， 就不會對性能造成任何影響： 比如說， 對三五個節(jié)點(diǎn)進(jìn)行連鎖更新是絕對不會影響性能的；

因為以上原因， ziplistPush 等命令的平均復(fù)雜度僅為  ， 在實(shí)際中， 我們可以放心地使用這些函數(shù)， 而不必?fù)?dān)心連鎖更新會影響壓縮列表的性能。