2.1 如何分片減速N次？

您可以像這樣分片並減慢 N 次：

  • 按順序發送 docs00...docs15 請求，而不是並行發送。
  • 在簡單查詢中，不通過 key進行選擇，WHERE something=234。

在這種情況下，序列化部分（serial）佔用的不是 1% 也不是 5%，而是現代數據庫中的 20% 左右。如果您使用極其高效的二進制協議訪問數據庫或將其作為動態庫鏈接到 Python 腳本中，您還可以獲得 50% 的序列化部分。

一個簡單請求的其餘處理時間將被解析請求、準備計劃等不可並行化的操作佔用。即不讀記錄變慢。

如果我們將數據分成 16 個表並按順序運行，例如 PHP 編程語言中的習慣（它不太擅長啟動異步進程），那麼我們將減速 16 倍。而且，也許甚至更多，因為還將添加網絡往返。

突然間，分片時編程語言的選擇變得很重要。

請記住編程語言的選擇，因為如果您按順序向數據庫（或搜索服務器）發送查詢，那麼加速從何而來？相反，會出現放緩。

2.2 關於半自動

在某些地方，信息技術的複雜性激發了 chthonic 恐怖。例如，開箱即用的 MySQL 肯定沒有實現對某些版本的分片，但是，戰鬥中使用的數據庫的大小增長到不合適的值。

面對個別DBA的苦難人性已經被折磨了很多年，白手起家寫了幾個不好的sharding解決方案。之後，編寫了一種或多或少體面的分片解決方案，稱為 ProxySQL（MariaDB/Spider、PG/pg_shard/Citus，...）。這是這個斑點的一個眾所周知的例子。

ProxySQL 作為一個整體，當然是一個成熟的企業級開源解決方案，用於路由等。但是要解決的任務之一是數據庫的分片，它本身不能以人類的方式分片。你看，沒有“shards = 16”開關，你要么必須重寫應用程序中的每個請求，並且有很多地方，要么在應用程序和數據庫之間放置一些中間層，看起來：“嗯... 從文檔中選擇 *？是的，它必須分成 16 個小的 SELECT * FROM server1.document1, SELECT * FROM server2.document2 - 使用這樣的登錄名/密碼到此服務器，再到另一個。如果一個人沒有回答，那麼……”，等等。這恰恰可以通過中間斑點來完成。它們略低於所有數據庫。對於 PostgreSQL，據我了解，

配置每個特定的補丁是一個單獨的大主題，無法放在一份報告中，因此我們將只討論基本概念。讓我們更好地談談嗡嗡聲的理論。

2.3 絕對完美的自動化？

在這個字母F()中分片的情況下變高的整個理論，基本原理總是大致相同：shard_id = F(object)。

分片 - 它是關於什麼的？我們有 20 億條記錄（或 64 條）。我們想把它們分成幾塊。出現了一個意想不到的問題——如何？我應該根據什麼原則將我的 20 億條記錄（或 64 條）分散到我可用的 16 台服務器上？

我們潛在的數學家應該建議，最終總會有一些神奇的功能，對於每個文檔（對象、行等），將決定將它放在哪一塊。

Java webinar

深入數學，這個函數總是不僅取決於對象本身（行本身），還取決於外部設置，例如分片總數。對於每個對象必須告訴將其放置在何處的函數，返回的值不能超過系統中的服務器數。並且功能略有不同：

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

但是，我們不會深入研究這些個別函數的荒野，我們只會討論 F() 是什麼神奇函數。

2.4 什麼是 F()？

他們可以想出很多不同的很多不同的實現機制。示例摘要：

  • F = rand() % nums_shards 數量
  • F = somehash(object.id) % num_shards
  • F = 對象.日期 % num_shards
  • F = object.user_id % num_shards
  • ...
  • F = shard_table [ somehash() |... object.date |... ]

一個有趣的事實——你可以自然地隨機分散所有數據——我們將下一條記錄扔到任意服務器、任意核心、任意表中。這不會有太多的快樂，但它會起作用。

有一些更智能的方法可以通過可重現甚至一致的哈希函數進行分片，或者通過某些屬性進行分片。讓我們來看看每種方法。

F = 蘭德（）

四處散佈不是很正確的方法。一個問題：我們將 20 億條記錄隨機分散在一千台服務器上，而且我們不知道記錄在哪裡。我們需要拉出 user_1，但我們不知道他在哪裡。我們訪問一千台服務器並對所有內容進行分類——不知何故這是低效的。

F = somehash()

讓我們用大人的方式來打散用戶：從user_id計算出可重現的hash函數，除以服務器的個數取餘，馬上聯繫到想要的服務器。

我們為什麼要這樣做呢？然後，我們有一個高負載，沒有其他東西適合一台服務器。如果合適，生活就會如此簡單。

太好了，情況已經好轉了，為了獲得一條記錄，我們提前去一個已知的服務器。但是，如果我們有一個鍵範圍，那麼在這個整個範圍內，我們需要遍歷鍵的所有值，並且在極限情況下，要么轉到與範圍內的鍵一樣多的分片，要么甚至到每個服務器。當然，情況有所改善，但並非針對所有請求。一些查詢已受到影響。

自然分片（F = object.date % num_shards）

有時，也就是通常，95% 的流量和 95% 的負載是具有某種自然分片的請求。例如，95% 的條件社交分析查詢僅影響最近 1 天、3 天、7 天的數據，其餘 5% 涉及最近幾年。但是 95% 的請求因此自然地按日期分片，系統用戶的興趣集中在最近幾天。

在這種情況下，您可以按日期劃分數據，例如按一天劃分，然後根據對某一天的報告或對象的請求的響應從這一天到這個分片。

生活正在改善——我們現在不僅知道特定物體的位置，而且我們還知道範圍。如果我們被要求的不是日期範圍，而是其他列的範圍，那麼，當然，我們將不得不遍歷所有分片。但是按照遊戲規則，我們只有5%的這樣的請求。

看起來我們已經想出了一個理想的解決一切的辦法，但是有兩個問題：

  • 當 95% 的請求僅涉及上週時，此解決方案是為特定案例量身定制的。
  • 由於 95% 的請求涉及上週，因此它們將全部落在為上週提供服務的一個分片上。這個碎片會融化，而其他所有碎片在此期間都將閒置。同時，你不能扔掉它們；檔案數據也必須存儲起來。

並不是說這是一個糟糕的分片方案——我們切斷了熱數據，但是，需要對最熱的分片做一些事情。

這個問題是通過滑稽動作、跳躍和藥膏來解決的，也就是說，增加燃燒當天的副本數量，然後在這一天成為過去並進入檔案時逐漸減少副本數量。沒有理想的解決方案稱為“您只需要以錯誤的方式使用神奇的哈希函數將數據分佈在集群上”。

2.5 支付的價格

形式上，我們知道現在我們知道“一切”。的確，我們不知道一種巨大的頭痛和兩種較小的頭痛。

1. 單純痛：嚴重塗抹

這是教科書中的一個例子，戰鬥中幾乎不會出現，而是突然出現。

  • 以帶日期為例，僅以不帶日期為例！
  • 無意的不均勻（可感知）分佈。

他們選擇了分片機制，和/或數據發生了變化，當然PM沒有傳達需求（我們代碼沒有錯誤，PM總是不報告需求），以及分發變得異常不均勻。也就是說，他們錯過了標準。

要捕捉，您需要查看碎片的大小。當我們的一個分片過熱或變得比其他分片大 100 倍時，我們肯定會看到問題。您可以簡單地通過更換密鑰或分片功能來修復它。

這是一個簡單的問題，說實話，我不認為至少一百個人中會有至少一個人會在生活中遇到這個問題，但突然間它至少會幫助某人。

2.“無敵”之痛：聚合、加入

如何進行選擇，將一個表中的十億條記錄加入另一個表中的十億條記錄？

  • 如何“快速”計算... aaa 和 bbb 之間的 randcol 在哪裡？
  • 如何“聰明地”做... users_32shards JOIN posts_1024 分片？

簡答：不行，受罪！

如果您將 10 億條記錄分配給第一個表中的一千台服務器以便它們更快地工作，並且在第二個表中也這樣做，那麼自然地一千到一千台服務器應該成對地相互通信。一百萬個連接將無法正常工作。如果我們向不適合分片的數據庫（搜索、存儲、文檔存儲或分佈式文件系統）發出請求，這些請求將大幅減慢。

很重要的一點是，有些請求總是會抹黑不成功，會變慢。盡量減少他們的百分比很重要。因此，無需對 10 億乘 10 億的記錄進行巨大的連接。如果可以將一個小表複製到所有節點，相對於您加入一個巨大的共享表，您應該這樣做。例如，如果連接實際上在某種程度上是本地的，則可以將用戶和他的帖子並排放置，以相同的方式對它們進行分片，並在同一台機器上進行所有連接——你需要這樣做.

這是為期三天的單獨課程，所以讓我們繼續討論最後的地獄般的痛苦和處理它的不同算法。

2.6. 複雜/長期痛苦：重新分片

做好準備：如果您是人生中第一次對數據進行分片，那麼平均而言您還會分片五次。

不管你配置多少個集群，你仍然需要重新分片。

如果你非常聰明和幸運，那麼至少過度分片一次。但是一旦你確定了，因為在你認為 10 個單位對用戶來說足夠的那一刻，那個時候有人寫了一個 30 個的請求，併計劃請求 100 個單位的未知資源。碎片永遠不夠。對於第一個分片方案，在任何情況下，您都會錯過 - 您總是必須增加要添加的服務器數量，或者做其他事情 - 通常，以某種方式重新打包數據。

如果我們有 2 的冪次方就好了：有 16 個服務器分片，現在是 32 個。如果是 17 就更有趣了，現在是 23——兩個非常質數。數據庫是怎麼做到的，也許它們內部有某種魔力？

正確答案是：不，裡面沒有魔法，他們裡面有地獄。

接下來，我們會考慮什麼可以“用手”來完成，或許我們會理解為“作為一台自動機器”。

在額頭#1。搬遷一切

對於所有對象，我們考慮 NewF(object)，轉移到一個新的分片。

NewF()=OldF() 匹配的機會很低。

讓我們涵蓋幾乎所有內容。

哦。

我希望沒有將所有 20 億條記錄從舊分片轉移到新分片這樣的地獄。幼稚的做法是可以理解的：有 17 台機器，6 台機器加入集群，整理出 20 億條記錄，他們從 17 台機器轉移到 23 台機器。每 10 年一次，您甚至可以做到。但總的來說，這是一個糟糕的舉動。

在額頭#2。搬遷一半

下一個幼稚的改進——讓我們放棄這樣一個愚蠢的方案——將禁止 17 輛汽車重新分片為 23 輛，我們將始終將 16 輛汽車重新分片為 32 輛汽車！然後，根據理論，我們將不得不移動恰好一半的數據，實際上我們也可以這樣做。

對於所有對象，我們考慮 NewF(object)，轉移到一個新的分片。

嚴格來說是 2^N，現在嚴格來說是 2^(N+1) 個碎片。

匹配NewF()=OldF()的概率是0.5。

讓我們傳輸大約 50% 的數據。

最優，但僅適用於 2 的冪。

原則上，一切都很好，除了在汽車數量方面綁定到 2 的冪。奇怪的是，這種天真的方法可以奏效。

請注意，在這種情況下，按 2 的冪對集群進行額外拆分也是最佳選擇。在任何情況下，將 16 台機器添加到 16 台機器的集群中，我們都必須移動一半的數據 - 恰好一半並移動。

好吧，但人類真的沒有發明任何其他東西嗎？這個問題來自好奇心。

更有趣#3。一致性哈希

當然這裡需要一張關於consistent hashing的圓圈圖。

如果你google一下“consistent hashing”，那肯定會出來一個圓圈，所有的結果都是圓圈填充的。

想法：讓我們在圓圈上畫出分片標識符（散列），並在頂部標記散列的服務器標識符。當您需要添加服務器時，我們在圓圈上放置一個新點，然後將靠近它的點（並且只有靠近它的點）重新定位。

添加分片時：我們不是查看所有內容，而是查看 2 個“鄰居”，平均移動 1/n。

刪除分片時：我們只查看被刪除的分片，我們只移動它。有點最優。

在添加分片時在最小化流量方面非常有效，在正常數據平衡方面絕對令人厭惡。因為當我們散列所有這些分配給大量機器的對象時，我們做的相對不均勻：圓周圍的點間隔不均勻，每個特定節點的負載可能與其他節點非常不同。

這個問題被虛擬節點的最後一行解決了。圓上的每個節點，每個服務器都由一個以上的點表示。通過添加服務器、分片等，我們正在添加幾個點。每次我們刪除一些東西時，我們相應地刪除了幾個點並移動了一小部分數據。

我用圓圈談論這個空間，因為，例如，這樣的方案在 Cassandra 內部。也就是說，當她開始在節點之間追記錄時，知道圈子在看著你，很可能不贊成。

然而，與第一種方法相比，生活有所改善 - 在添加/刪除分片時，我們已經查看了不是所有記錄，而是僅查看了一部分，並且僅移動了一部分。

注意，問題是：是否可以進一步改進？並且還提高加載分片的均勻性？他們說這是可能的！

更有趣#4。會合/HRW

下一個簡單的想法（材料是教育性的，所以沒有什麼複雜的）：shard_id = arg max hash(object_id, shard_id)。

為什麼它被稱為 Rendezvous hashing 我不知道，但我知道它為什麼被稱為 Highest Random Weight。很容易想像它是這樣的：

例如，我們有 16 個分片。對於每個需要放在某處的對象（字符串），我們根據分片編號中的對象計算 16 個哈希值。誰擁有最高的哈希值，誰就獲勝。

這就是所謂的 HRW 哈希，又名 Rendezvous 哈希。像棍子一樣笨，計算分片數量的方案首先比圓圈更容易觀察，另一方面給出了均勻的負載。

唯一不利的是，添加新分片對我們來說變得更糟了。存在這樣的風險，即在添加新分片時，我們仍有一些哈希值會發生變化，因此可能有必要審查所有內容。碎片移除技術沒有太大變化。

另一個問題是它的計算量很大，有大量的分片。

更有趣#5。更多技巧

有趣的是，研究並沒有停滯不前，谷歌每年都會發布一些新的太空技術：

  • 跳轉哈希 - 谷歌 '2014。
  • 多探頭—Google '2015。
  • 磁懸浮谷歌 '2016。

如果你對這個主題感興趣，你可以閱讀許多論文。我提出這個數據是為了明確問題沒有解決，沒有可以在所有數據庫中實施的超級解決方案。直到現在，人們都在為論文辯護。

結論

有一個重要的基本技術叫做分片，以 Gallius Julius Caesar 的名字命名：“分而治之，統治並分而治之！”。如果數據放不下一台服務器，就需要拆分成20台服務器。

了解了所有這些之後，人們應該會覺得最好不要分片。如果你決定最好不要分片，這是正確的感覺。如果您可以以 100 美元的價格向服務器添加內存並且不分片任何東西，那麼您應該這樣做。分片時，會出現一個複雜的分佈式系統，數據來回傳遞，數據堆積在不知何處。能避免就一定要避免。

最好不要手工完成，“基礎”（搜索，DFS，...）可以自行分片更好。無論如何，遲早會出現高負載，並且必須以某種方式拆分數據。這不是事實，即使基地可以自己做，你也不會遇到任何問題。記住算法原教旨主義——你需要了解裡面的一切是如何運作的。

第一次設置分片時，仔細選擇 F()，考慮請求、網絡等。但是準備好，您可能必須選擇 2 次，並且至少需要重做一次。