負(fù)載均衡

大約 8 分鐘

負(fù)載均衡

本文檔介紹 IoTDB 中的分區(qū)策略和負(fù)載均衡策略。根據(jù)時(shí)序數(shù)據(jù)的特性，IoTDB 按序列和時(shí)間維度對(duì)其進(jìn)行分區(qū)。結(jié)合序列分區(qū)與時(shí)間分區(qū)創(chuàng)建一個(gè)分區(qū)，作為劃分的基本單元。為了提高吞吐量并降低管理成本，這些分區(qū)被均勻分配到分片（Region）中，分片是復(fù)制的基本單元。分片的副本決定了數(shù)據(jù)的存儲(chǔ)位置，主副本負(fù)責(zé)主要負(fù)載的管理。在此過程中，副本放置算法決定哪些節(jié)點(diǎn)將持有分片副本，而主副本選擇算法則指定哪個(gè)副本將成為主副本。

分區(qū)策略和分區(qū)分配

IoTDB 為時(shí)間序列數(shù)據(jù)實(shí)現(xiàn)了量身定制的分區(qū)算法。在此基礎(chǔ)上，緩存于配置節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)上的分區(qū)信息不僅易于管理，而且能夠清晰區(qū)分冷熱數(shù)據(jù)。隨后，平衡的分區(qū)被均勻分配到集群的分片中，以實(shí)現(xiàn)存儲(chǔ)均衡。

分區(qū)策略

IoTDB 將生產(chǎn)環(huán)境中的每個(gè)傳感器映射為一個(gè)時(shí)間序列。然后，使用序列分區(qū)算法對(duì)時(shí)間序列進(jìn)行分區(qū)以管理其元數(shù)據(jù)，再結(jié)合時(shí)間分區(qū)算法來管理其數(shù)據(jù)。下圖展示了 IoTDB 如何對(duì)時(shí)序數(shù)據(jù)進(jìn)行分區(qū)。

分區(qū)算法

由于生產(chǎn)環(huán)境中通常部署大量設(shè)備和傳感器，IoTDB 使用序列分區(qū)算法以確保分區(qū)信息的大小可控。由于生成的時(shí)間序列與時(shí)間戳相關(guān)聯(lián)，IoTDB 使用時(shí)間分區(qū)算法來清晰區(qū)分冷熱分區(qū)。

序列分區(qū)算法

默認(rèn)情況下，IoTDB 將序列分區(qū)的數(shù)量限制為 1000，并將序列分區(qū)算法配置為哈希分區(qū)算法。這帶來以下收益：

由于序列分區(qū)的數(shù)量是固定常量，序列與序列分區(qū)之間的映射保持穩(wěn)定。因此，IoTDB 不需要頻繁進(jìn)行數(shù)據(jù)遷移。
序列分區(qū)的負(fù)載相對(duì)均衡，因?yàn)樾蛄蟹謪^(qū)的數(shù)量遠(yuǎn)小于生產(chǎn)環(huán)境中部署的傳感器數(shù)量。

更進(jìn)一步，如果能夠更準(zhǔn)確地估計(jì)生產(chǎn)環(huán)境中的實(shí)際負(fù)載情況，序列分區(qū)算法可以配置為自定義的哈希分區(qū)或列表分區(qū)，以在所有序列分區(qū)中實(shí)現(xiàn)更均勻的負(fù)載分布。

時(shí)間分區(qū)算法

時(shí)間分區(qū)算法通過下式將給定的時(shí)間戳轉(zhuǎn)換為相應(yīng)的時(shí)間分區(qū)

\left\lfloor\frac{\text{Timestamp}-\text{StartTimestamp}}{\text{TimePartitionInterval}}\right\rfloor\text{。}

在此式中， $\text{StartTimestamp}$ 和 $\text{TimePartitionInterval}$ 都是可配置參數(shù)，以適應(yīng)不同的生產(chǎn)環(huán)境。 $\text{StartTimestamp}$ 表示第一個(gè)時(shí)間分區(qū)的起始時(shí)間，而 $\text{TimePartitionInterval}$ 定義了每個(gè)時(shí)間分區(qū)的持續(xù)時(shí)間。默認(rèn)情況下， $\text{TimePartitionInterval}$ 設(shè)置為七天。

元數(shù)據(jù)分區(qū)

由于序列分區(qū)算法對(duì)時(shí)間序列進(jìn)行了均勻分區(qū)，每個(gè)序列分區(qū)對(duì)應(yīng)一個(gè)元數(shù)據(jù)分區(qū)。這些元數(shù)據(jù)分區(qū)隨后被均勻分配到元數(shù)據(jù)分片中，以實(shí)現(xiàn)元數(shù)據(jù)的均衡分布。

數(shù)據(jù)分區(qū)

結(jié)合序列分區(qū)與時(shí)間分區(qū)創(chuàng)建數(shù)據(jù)分區(qū)。由于序列分區(qū)算法對(duì)時(shí)間序列進(jìn)行了均勻分區(qū)，特定時(shí)間分區(qū)內(nèi)的數(shù)據(jù)分區(qū)負(fù)載保持均衡。這些數(shù)據(jù)分區(qū)隨后被均勻分配到數(shù)據(jù)分片中，以實(shí)現(xiàn)數(shù)據(jù)的均衡分布。

分區(qū)分配

IoTDB 使用分片來實(shí)現(xiàn)時(shí)間序列的彈性存儲(chǔ)，集群中分片的數(shù)量由所有數(shù)據(jù)節(jié)點(diǎn)的總資源決定。由于分片的數(shù)量是動(dòng)態(tài)的，IoTDB 可以輕松擴(kuò)展。元數(shù)據(jù)分片和數(shù)據(jù)分片都遵循相同的分區(qū)分配算法，即均勻劃分所有序列分區(qū)。下圖展示了分區(qū)分配過程，其中動(dòng)態(tài)擴(kuò)展的分片匹配不斷擴(kuò)展的時(shí)間序列和集群。

分片擴(kuò)容

分片的數(shù)量由下式給出

\text{RegionGroupNumber}=\left\lfloor\frac{\sum_{i=1}^{DataNodeNumber}\text{RegionNumber}_i}{\text{ReplicationFactor}}\right\rfloor\text{。}

在此式中， $\text{RegionNumber}_i$ 表示期望在第 $i$ 個(gè)數(shù)據(jù)節(jié)點(diǎn)上放置的副本數(shù)量，而 $\text{ReplicationFactor}$ 表示每個(gè)分片中的副本數(shù)量。 $\text{RegionNumber}_i$ 和 $\text{ReplicationFactor}$ 都是可配置的參數(shù)。 $\text{RegionNumber}_i$ 可以根據(jù)第 $i$ 個(gè)數(shù)據(jù)節(jié)點(diǎn)上的可用硬件資源（如 CPU 核心數(shù)量、內(nèi)存大小等）確定，以適應(yīng)不同的物理服務(wù)器。 $\text{ReplicationFactor}$ 可以調(diào)整以確保不同級(jí)別的容錯(cuò)能力。

分配策略

元數(shù)據(jù)分片和數(shù)據(jù)分片都遵循相同的分配策略，即均勻劃分所有序列分區(qū)。因此，每個(gè)元數(shù)據(jù)分片持有相同數(shù)量的元數(shù)據(jù)分區(qū)，以確保元數(shù)據(jù)存儲(chǔ)均衡。同樣，對(duì)于每個(gè)時(shí)間分區(qū)，每個(gè)數(shù)據(jù)分片獲取與其持有的序列分區(qū)對(duì)應(yīng)的數(shù)據(jù)分區(qū)。因此，時(shí)間分區(qū)內(nèi)的數(shù)據(jù)分區(qū)均勻分布在所有數(shù)據(jù)分片中，確保每個(gè)時(shí)間分區(qū)內(nèi)的數(shù)據(jù)存儲(chǔ)均衡。

值得注意的是，IoTDB 有效利用了時(shí)序數(shù)據(jù)的特性。當(dāng)配置了 TTL（生存時(shí)間）時(shí)，IoTDB 可實(shí)現(xiàn)無需遷移的時(shí)序數(shù)據(jù)彈性存儲(chǔ)，該功能在集群擴(kuò)展時(shí)最小化了對(duì)在線操作的影響。上圖展示了該功能的一個(gè)實(shí)例：新生成的數(shù)據(jù)分區(qū)被均勻分配到每個(gè)數(shù)據(jù)分片，過期數(shù)據(jù)會(huì)自動(dòng)歸檔。因此，集群的存儲(chǔ)最終將保持平衡。

均衡策略

為了提高集群的可用性和性能，IoTDB 采用了精心設(shè)計(jì)的存儲(chǔ)均衡和計(jì)算均衡算法。

存儲(chǔ)均衡

數(shù)據(jù)節(jié)點(diǎn)持有的副本數(shù)量反映了它的存儲(chǔ)負(fù)載。如果數(shù)據(jù)節(jié)點(diǎn)之間的副本數(shù)量差異較大，擁有更多副本的數(shù)據(jù)節(jié)點(diǎn)可能成為存儲(chǔ)瓶頸。盡管簡單的輪詢（Round Robin）放置算法可以通過確保每個(gè)數(shù)據(jù)節(jié)點(diǎn)持有等量副本來實(shí)現(xiàn)存儲(chǔ)均衡，但它會(huì)降低集群的容錯(cuò)能力，如下所示：

假設(shè)集群有 4 個(gè)數(shù)據(jù)節(jié)點(diǎn)，4 個(gè)分片，并且副本因子為 2。
將分片 $r_1$ 的 2 個(gè)副本放置在數(shù)據(jù)節(jié)點(diǎn) $n_1$ 和 $n_2$ 上。
將分片 $r_2$ 的 2 個(gè)副本放置在數(shù)據(jù)節(jié)點(diǎn) $n_3$ 和 $n_4$ 上。
將分片 $r_3$ 的 2 個(gè)副本放置在數(shù)據(jù)節(jié)點(diǎn) $n_1$ 和 $n_3$ 上。
將分片 $r_4$ 的 2 個(gè)副本放置在數(shù)據(jù)節(jié)點(diǎn) $n_2$ 和 $n_4$ 上。

在這種情況下，如果數(shù)據(jù)節(jié)點(diǎn) $n_2$ 發(fā)生故障，由它先前負(fù)責(zé)的負(fù)載將只能全部轉(zhuǎn)移到數(shù)據(jù)節(jié)點(diǎn) $n_1$ ，可能導(dǎo)致其過載。

為了解決這個(gè)問題，IoTDB 采用了一種副本放置算法，該算法不僅將副本均勻放置到所有數(shù)據(jù)節(jié)點(diǎn)上，還確保每個(gè) 數(shù)據(jù)節(jié)點(diǎn)在發(fā)生故障時(shí)，能夠?qū)⑵湄?fù)載轉(zhuǎn)移到足夠多的其他數(shù)據(jù)節(jié)點(diǎn)。因此，集群實(shí)現(xiàn)了存儲(chǔ)分布的均衡，并具備較高的容錯(cuò)能力，從而確保其可用性。

計(jì)算均衡

數(shù)據(jù)節(jié)點(diǎn)持有的主副本數(shù)量反映了它的計(jì)算負(fù)載。如果數(shù)據(jù)節(jié)點(diǎn)之間持有主副本數(shù)量差異較大，擁有更多主副本的數(shù)據(jù)節(jié)點(diǎn)可能成為計(jì)算瓶頸。如果主副本選擇過程使用直觀的貪心算法，當(dāng)副本以容錯(cuò)算法放置時(shí)，可能會(huì)導(dǎo)致主副本分布不均，如下所示：

假設(shè)集群有 4 個(gè)數(shù)據(jù)節(jié)點(diǎn)，4 個(gè)分片，并且副本因子為 2。
選擇分片 $r_5$ 在數(shù)據(jù)節(jié)點(diǎn) $n_5$ 上的副本作為主副本。
選擇分片 $r_6$ 在數(shù)據(jù)節(jié)點(diǎn) $n_7$ 上的副本作為主副本。
選擇分片 $r_7$ 在數(shù)據(jù)節(jié)點(diǎn) $n_7$ 上的副本作為主副本。
選擇分片 $r_8$ 在數(shù)據(jù)節(jié)點(diǎn) $n_8$ 上的副本作為主副本。

請(qǐng)注意，以上步驟嚴(yán)格遵循貪心算法。然而，到第 3 步時(shí)，無論在數(shù)據(jù)節(jié)點(diǎn) $n_5$ 或 $n_7$ 上選擇分片 $r_7$ 的主副本，都會(huì)導(dǎo)致主副本分布不均衡。根本原因在于每一步貪心選擇都缺乏全局視角，最終導(dǎo)致局部最優(yōu)解。

為了解決這個(gè)問題，IoTDB 采用了一種主副本選擇算法，能夠持續(xù)平衡集群中的主副本分布。因此，集群實(shí)現(xiàn)了計(jì)算負(fù)載的均衡分布，確保了其性能。