分庫分表的一般做法

一般會使用三種算法：

1. 哈希分庫分表：根據分庫分表鍵算出一個哈希值，根據這個哈希值選擇一個數據庫。最常見的就是數字類型的字段作為分庫分表鍵，然后取余。比如在訂單表里，可以按照買家的ID除以8的余數進行分表
2. 范圍分庫分表：將某個數據按照范圍大小進行分段。比如說根據ID，[0,1000)在一張表，[1000,2000)在另外一張表。最常見的應該是按照日期進行分庫分表，比如每個月一張表
3. 中間表：引入一個中間表來記錄數據所在的目標表。一般是記錄主鍵到目標表的映射關系。
   
   這三者并不互斥，也就是說可以考慮使用哈希分庫分表，同時引入一個中間表；也可以先進行范圍分庫分表，再引入一個中間表。

分庫分表中間件的形態

1. SDK形態：通過依賴的形式引入代碼里，比如Java的依賴ShardingSphere
2. Proxy形態：獨立部署的分庫分表中間件，對于所有的業務方來說，就像一個普通的數據庫，業務方的查詢發送過去后，就會執行分庫分表，發起實際的查詢，再把查詢結果返回給業務方。ShardingSphere也支持這種形態。
   
3. Sidecar形態：提供了一個分庫分表的Sidecar，但是現在并沒有非常成熟的產品

Sidecar是一種分庫分表中間件的形態。它是一個理論上的概念，指的是一個獨立的組件，為應用程序提供分庫分表的功能。在這種形態下，Sidecar作為應用程序的伴隨服務運行，類似于服務網格中的Sidecar容器，它與應用程序實例部署在一起，但作為獨立的進程運行。

其中，SDK形態的性能最好，但是和語言強耦合。
Proxy形態性能最差，因為所有的數據庫查詢都發送給它了，很容易成功性能瓶頸。尤其單機部署Proxy的話，還面臨著單節點故障的問題。優點是跟編程語言無關，部署一個Proxy之后可以給使用不同編程語言的業務使用。同時，業務方可以輕易地從單庫單表切換到分庫分表。

Sidecar 目前還沒有成熟的產品，但是從架構上來說它的性能應該介于 SDK 和 Proxy 之間，并且也沒有單體故障、集群管理等煩惱。

面試準備

還需要弄清楚幾個問題：

• 公司是如何解決分庫分表中的分頁問題的？
• 有沒有因為排序或分頁而引起的性能問題？最終怎么解決的

還可以去看看公司的監控數據，注意下分頁查詢的響應時間。并且在業務高峰期或是頻繁執行分頁的時候，看看內存和CPU的使用率。這些數據可以作為分頁查詢比較引起性能問題的證據。

面試策略上來說，最好把分頁查詢優化作為你性能優化的一個舉措，可以進一步和前面的查詢優化、數據庫參數優化相結合，這樣方案會更完善，能力會更全面。

如果面試官問到了數據庫性能優化和數據庫分頁查詢，你都可以嘗試把話題引導到分頁查詢上。

基本思路

可以嘗試介紹一下是如何優化數據庫性能的，比如SQL本身優化、數據庫優化，然后羅列出準備的SQL案例，說明你在SQL優化方面做過哪些事情，比如優化過分庫分表的查詢，其中最典型的就是優化分頁查詢。
假設之前是全局查詢，現在采用禁用跨頁查詢的方案來優化

最開始我在公司監控慢查詢的時候，發現有一個分頁查詢非常慢。這個分頁查詢是按照更新時間降序來排序的。后來我發現那個分頁查詢用的是全局查詢法，因為這個接口原本是提供給 Web 端用的，而 Web 端要支持跨頁查詢，所以只能使用全局查詢法。當查詢的頁數靠后的時候，響應時間就非常長。 后來我們公司搞出 App 之后，類似的場景直接復用了這個接口。但是事實上在 App 上是沒有跨頁需求的。所以我就直接寫了一個新接口，這個接口要求分頁的時候帶上上一頁的最后一條數據的更新時間。也就是我用這個更新時間構造了一個查詢條件，只查詢早于這個時間的數據。那么分頁查詢的時候 OFFSET 就永遠被我控制在 0 了，查詢的時間就非常穩定了。

最后你可以加一個總結。

分頁查詢在分庫分表里面是一個很難處理的問題，要么查詢可能有性能問題，比如說這里使用的全局查詢法，要么就是要求業務折中，比如說我優化后禁用了跨頁，以及要求數據平均分布的平均分頁法，當然還有各方面都不錯，但是實現比較復雜的二次查詢法、中間表法。

當面試官追問你其中細節的時候，你就可以這樣來引導。

全局查詢

理論上說，分頁查詢要在全局有序的情況下進行，但是在分庫分表以后，要做到全局有序就很難了。假如說我們的數據庫order_tab是以buyer_id % 2來進行分表的，如果你要執行一個語句

SELECT * FROM order_tab ORDER BY id LIMIT 4 OFFSET 2

實際執行查詢的時候，就要考慮各種數據的分布情況。

• 符合條件的數據全部在某個表里面。在這就是order_tab_0上有全部數據，或是order_tab_1上有全部數據。
  
• 偏移量中前面兩條全部在一張表，但是符合條件的數據在另外一張表
  
• 偏移量和數據在兩張表都有
  
  在分庫分表中，一個SELECT語句生成的目標語句是這樣的：

SELECT * FROM order_tab ORDER BY id LIMIT 6 OFFSET 0
SELECT * FROM order_tab ORDER BY id LIMIT 6 OFFSET 0

注意看LIMIT部分，被修改成了0,6。通俗的說，如果一個分頁語句是 LIMIT x OFFSET y 的形式，那么最終生成的目標語句就是 LIMIT x + y OFFSET 0。

LIMIT x OFFSET y => LIMIT x+y OFFSET 0

當分庫分表中間件拿到這兩個語句的查詢結果之后，就要在內存里進行排序，再找出全局的LIMIT 4 OFFSET 2
可以先回答這種全局排序的思路，關鍵詞就是 LIMIT x + y OFFSET 0

分庫分表中間件一般采用的就是全局排序法。假如說我們要查詢的是LIMIT X OFFSET y，那么分庫分表中間件會把查詢改寫為LIMIT x+y OFFSET 0，然后把查詢請求發送給所有的目標表。在拿到所有的返回值后，在內存中排序，然后根據排序結果找出全局符合條件的目標數據。

接下來可以先從性能問題上刷一個亮點，抓住受影響的三個方面：網絡、內存和CPU

這個解決方案的最大問題就是性能不好。
首先是網絡傳輸瓶頸，比如在LIMIT 10 OFFSET 1000這種場景下，如果沒有分庫分表，只需要傳輸10條數據；在分庫分表的情況下，如果命中了N個表，那么需要傳輸的是(1000+10)*N條數據。而實際上最終我們只會用其中的10條數據，存在巨大的浪費。
其次是內存瓶頸。收到那么多數據之后，中間件需要維持在內存中排序。
CPU也會成為瓶頸，因為排序本身是一個CPU密集的操作。所以在Proxy形態的分庫分表中間件里，分頁查詢一多，就容易把中間件的內存耗盡，引發OOM，又或是CPU 100%。
不過可以通過歸并排序來緩解這些問題。

關鍵在拿到數據之后，使用歸并排序的算法。

在分庫分表里，可以使用歸并排序算法來給返回的結果排序，也就是說在改寫為LIMIT x+y OFFSET 0之后，每個目標表返回的結果都是有序的，自然可以使用歸并排序。在歸并排序的過程中，我們可以逐條從返回結果中讀取，這意味著沒必要將所有的結果一次性放到內存中再排序。在分頁的場景下，取夠了數據可以直接返回，剩下的數據就可以丟棄了。

前面說了全局查詢這個方案的性能很差，那么有沒有其他方案呢？
的確有，比如平均分頁、禁用跨頁查詢、換用其他中間件等。不過任何方案都不是十全十美的，這些方案也存在一些難點，有的是需要業務折中，有的處理過程非常復雜。我們先來看第一個需要業務折中的平均分頁方案

優化方案1：平均分頁

看到分頁查詢的第一個念頭應該是：能不能在不同的表上平均分頁查詢數據，得到的結果合并在一起就是分頁的結果
例如，查詢中的語句是這樣的

SELECT * FROM order_tab ORDER BY id LIMIT 4 OFFSET 2

因為本身有兩張表，可以改成這樣

SELECT * FROM order_tab_0 ORDER BY id LIMIT 2 OFFSET 1
SELECT * FROM order_tab_1 ORDER BY id LIMIT 2 OFFSET 1

在每一張表都查詢從偏移量1開始的2條數據，那么合并在一起就可以認為從全局的偏移量2開始的4條數據。
圖里我們能夠看出來，按照道理全局的 LIMIT 4 OFFSET 2 拿到的應該是 3、4、5、6 四條數據。但是這里我們拿到的數據卻是 2、4、5、9。這也就是這個方案的缺陷：它存在精度問題。也就是說，它返回的數據并不一定是全局最精確的數據

那么這個方案是不是就不能用了呢？并不是的，在一些對順序、精度要求不嚴格的場景下，還是可以用的。例如瀏覽頁面，你只需要返回足夠多的數據行，但是這些數據具體來自哪些表，用戶并不關心。
關鍵詞就是平均分頁

在一些可以接受分頁結果不精確的場景下，可以考慮平均分頁的做法。舉個例子來說，如果查詢的是 LIMIT 4 OFFSET 2，并且命中了兩張目標表，那么就可以考慮在每個表上都查詢 LIMIT 2 OFFSET 1。這些結果合并在一起就是 LIMIT 4 OFFSET 2 的一個近似答案。這種做法對于數據分布均勻的分庫分表效果很好，偏差也不大。

這個方案還有一個進階版本，就是根據數據分布來決定如何取數據。

更加通用的做法是根據數據分布來決定分頁在不同的表上各自取多少條數據。比如說一張表上面有 70% 的數據，但是另一張表上只有 30% 的數據，那么在 LIMIT 10 OFFSET 100 的場景下，可以在 70% 的表里取 LIMIT 7 OFFSET 70，在 30% 的表里取 LIMIT 3 OFFSET 30。所以，也可以把前面平均分配的方案看作是各取 50% 的特例

那如何知道一張表上有70%的數據，另外一張表上有30%。
在開發的時候先用SQL在不同的表上執行一下，看看同樣的WHERE條件下各自返回了多少數據，就可以推斷出來了。
不過實際上，能夠接受不精確的業務場景還是比較少的。所以我們還有一種業務折中的解決方案，它精確并且高效，也就是禁用跨頁查詢方案。

優化方案2：禁用跨頁查詢

只允許用戶從第0頁開始，逐頁往后翻，不允許跨頁。
假如業務上分頁查詢是50條數據一頁，那么發起的查詢依次是：

SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 0
SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 50
SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 100
...

不斷增長的只有偏移量，如何控制住這個偏移量呢？
答案是根據ORDER BY的部分來增加一個查詢條件。上述例子里的order by是根據id升序排序的，只需要在where部分增加一個大于上次查詢的最大id的條件就可以了。max_id 是上一批次的最大id

SELECT * FROM order_tab WHERE `id` > max_id ORDER BY id LIMIT 50 OFFSET 0

即使order by里使用了多個列，規則也是一樣的

總體來看，回答要分成兩部分，第一部分介紹基本做法，關鍵詞是拿到上一批次的極值。

目前比較好的分頁做法是禁用跨頁查詢，然后在每一次查詢條件里加上上依次查詢的極值，也就是最大值或者最小值。比如說第一次查詢的時候ORDER BY ID LIMIT 10 OFFSET 0，那么下一頁就可以改為WHERE id > max_id ORDER BY ID LIMIT 10 OFFSET 0。在現在的手機 App 里這個策略是非常好用的，因為手機 App 都是下拉刷新，天然就不存在跨頁的問題。

第一部分提到了極值，面試官可能問你什么時候用最大值，什么時候用最小值，可以這樣說：

至于用最大值還是最小值，取決于order by。總的原則就是升序用最大值，降序用最小值。如果order by里面包含了多個列，那么針對每一個列是升序還是降序，來確定使用最大值還是最小值。

這種方案并沒有徹底解決分庫分表查詢中的分頁問題，但是控制了偏移量，極大的減少了網絡通信的消耗和磁盤掃描的消耗。

優化方案3：換用中間件

一種思路是使用NoSQL之類的來存儲數據，比如使用Elasticsearch、ClickHouse；另一種思路是使用分布式關系型數據庫，相當于把分頁的難題拋給了數據庫

優化方案4：二次查詢（亮點）

先嘗試獲取某個數據的全局偏移量，再根據這個偏移量來計算剩下數據的偏移量。這里用一個例子來闡述它的基本原理，再抽象出一般步驟。
假設我們的查詢是

SELECT * FROM order_tab ORDER BY id LIMIT 4 OFFSET 4

數據分布如圖所示：

全局的LIMIT 4 OFFSET 4 是 5、6、7、8 四條數據

步驟1：首次查詢

把SQL語句改寫成這樣：

SELECT * FROM order_tab_0 ORDER BY id LIMIT 4 OFFSET 2
SELECT * FROM order_tab_1 ORDER BY id LIMIT 4 OFFSET 2

我們只是把OFFSET平均分配了，但是LIMIT沒變
第一次查詢到的數據是這樣
order_tab_0 拿到了 4、6、10、12，而 order_tab_1 拿到了 7、8、9、11

步驟二：確認最小值

id最小的是4，來自order_tab_0

步驟三：二次查詢

這一次查詢需要利用上一步找出來的最小值以及各自分庫的最大值來構造BETWEEN查詢，改寫得到的SQL是：

SELECT * FROM order_tab_0 WHERE id BETWEEN 4 AND 12
SELECT * FROM order_tab_1 WHERE id BETWEEN 4 AND 11

結果：

• order_tab_0 返回 4、6、10、12。
• order_tab_1 返回 5、7、8、9、11，也就是多了 1 條數據，記住這一點。
  
  取過來的所有數據排序之后就是4、5、6、7、8、9、10、11、12

步驟四：計算最小值的全局偏移量

核心是：根據BETWEEN中多出來的數據量來推斷全局偏移量

現在我們知道4在order_tab_0中的偏移量是2，也就是說比4小的數據有2條。
在BETWEEN查詢里，order_tab_1返回的結果是5,7,8,9,11，其中7在第一次查詢里的偏移量是2，所以5的偏移量是1。也就是說，5的前面只有一條比4小的數據。
那么4在order_tab中的全局偏移量就是1+2=3，也就是4前面有三條數據。

加上4本身，剛好構成了OFFSET 4，因此從5開始取，往后取4條數據。

總結

簡化版本：

1. 首次查詢，拿到最小值
2. 二次查詢，確實最小值的全局偏移量
3. 在二次查詢的結果里根據最小值取到符合偏移量的數據

抽象版本：
假設分庫分表共有n個表，查詢是LIMIT X OFFSET Y，那么：

1. 首先發送查詢語句 LIMIT X OFFSET Y/N 到所有的表
2. 找到返回結果中的最小值（升序），記作min
3. 執行第二次查詢，關鍵是BETWEEN min AND max，其中max是第一次查詢的數據中每個表各自的最大值
4. 根據min、第一次查詢和第二次查詢的值來確定min的全局偏移量。總的來說，min在某個表里的偏移量這樣計算：如果第二次查詢比第一次查詢多了K條數據，偏移量就是Y/N-K。然后把所有表的偏移量加在一起，就是min的全局偏移量
5. 根據min的全局偏移量，在第二次查詢的結果里面向后補足到Y，得到第一條數據的位置，再取X條。

優化方案5：引入中間表（亮點）

引入中間表的意思是額外存儲一份數據，只用來排序。這個方案里面就是在中間表里加上排序相關的列。

排序是一個非常常見的需求，那么就可以考慮引入一個中間表來輔助排序。比如說用更新時間來排序的時候，在中間表里加上更新時間。查詢的時候先在中間表里查到目標數據，再去目標表里把全部數據都查詢出來。
有兩個明顯的缺陷：一是WHERE只能使用中間表上的列；二是維護中間表也會引起數據一致性問題。

那么如何解決數據一致性問題呢？

比較簡單的做法就是業務保持雙寫，也就是寫入目標表也寫入中間表。不過這里我更加建議使用 Canal 之類的框架來監聽 binlog，異步更新中間表。這樣做的好處是業務完全沒有感知，沒有什么改造成本。更新的時候可以考慮引入重試機制，進一步降低失敗的幾率。

面試官可能進一步問你，如果更新中間表經過重試之后也失敗了，怎么辦？
這時候并沒有更好的辦法，無非就是引入告警，然后人工介入處理。最后你可以再總結一下這個方案。

這個方案是一個依賴最終一致性的方案，在強調強一致性的場景下并不是很合適。