Redis 連鎖更新

前面說(shuō)過(guò)， 每個(gè)節(jié)點(diǎn)的 previous_entry_length 屬性都記錄了前一個(gè)節(jié)點(diǎn)的長(zhǎng)度：

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

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

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

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

因?yàn)?nbsp;e1 的 previous_entry_length 屬性僅長(zhǎng) 1 字節(jié)， 它沒(méi)辦法保存新節(jié)點(diǎn) new 的長(zhǎng)度， 所以程序?qū)?duì)壓縮列表執(zhí)行空間重分配操作， 并將e1 節(jié)點(diǎn)的 previous_entry_length 屬性從原來(lái)的 1 字節(jié)長(zhǎng)擴(kuò)展為 5 字節(jié)長(zhǎng)。

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

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

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

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

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

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

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

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

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

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