我們的用戶互相寫訊息而不會感到疲倦。
這是相當多的。 如果你打算讀取所有用戶的所有訊息，則需要超過 150 萬年。 前提是您是一位相當高級的讀者，並且在每個訊息上花費的時間不超過一秒鐘。
對於如此大量的數據，以最佳方式建立儲存和存取數據的邏輯至關重要。 否則，在某個不那麼美妙的時刻，一切可能很快就會出問題。
對我們來說，這一刻已經是一年半前的事了。 我們是如何走到這一步以及最終發生了什麼 - 我們按順序告訴您。
背景
在第一個實作中，VKontakte 訊息在 PHP 後端和 MySQL 的組合上運行。 對於小型學生網站來說，這是一個完全正常的解決方案。 然而，該網站的成長不受控制，並開始要求優化自身的資料結構。
2009 年底，編寫了第一個文字引擎儲存庫，並於 2010 年將訊息傳輸到其中。
在文字引擎中，訊息儲存在清單中 - 一種「郵箱」。 每個這樣的清單都由一個 uid 決定 - 擁有所有這些訊息的使用者。 訊息具有一組屬性：對話者識別碼、文字、附件等。 「盒子」內的訊息識別碼是 local_id，它永遠不會改變，並為新訊息按順序分配。 這些「盒子」是獨立的，引擎內部彼此不同步；它們之間的通訊發生在 PHP 層級。 可以從內部看一下text-engine的資料結構與能力 .
這對於兩個用戶之間的通訊來說已經足夠了。 你猜接下來發生了什麼事？
2011 年 XNUMX 月，VKontakte 引入了與多個參與者的對話—多重聊天。 為了與他們合作，我們提出了兩個新的集群——member-chats 和 chat-members。 第一個儲存有關用戶聊天的數據，第二個儲存有關用戶聊天的數據。 除了清單本身之外，這還包括邀請用戶以及他們添加到聊天中的時間等。
「PHP，讓我們向聊天室發送一條訊息，」用戶說。
「來吧，{用戶名}，」PHP 說。
該方案也有缺點。 同步仍然是 PHP 的責任。 大型聊天和同時向他們發送訊息的用戶是一個危險的故事。 由於文字引擎實例取決於 uid，因此聊天參與者可能會在不同時間收到相同的訊息。 如果進展停滯不前，人們可以忍受這一點。 但這不會發生。
2015年底，我們推出了社群消息，2016年初，我們推出了社群消息API。 隨著社群中大型聊天機器人的出現，人們可能會忘記均勻的負載分配。
一個好的機器人每天會產生數百萬條訊息 - 即使是最健談的用戶也無法誇耀這一點。 這意味著這類機器人賴以生存的某些文本引擎實例開始受到最大程度的影響。
2016 年的訊息引擎包括 100 個聊天成員和成員聊天實例，以及 8000 個文字引擎。 它們託管在 64 台伺服器上，每台伺服器都有 32 GB 記憶體。 作為第一個緊急措施，我們將記憶體再增加了 XNUMX GB。 我們估計了預測。 如果沒有重大變化，這大約還夠再用一年。 您需要取得硬體或優化資料庫本身。
由於架構的性質，只有倍增硬體才有意義。 也就是說，至少將汽車數量增加一倍——顯然，這是一條相當昂貴的道路。 我們會優化。
新概念
新方法的核心本質是聊天。 聊天有一個與其相關的訊息清單。 用戶有一個聊天列表。
至少需要兩個新資料庫：
- 聊天引擎。 這是聊天向量的儲存庫。 每個聊天都有一個與其相關的訊息向量。 每個訊息在聊天中都有一個文字和一個唯一的訊息識別碼 - chat_local_id。
- 用戶引擎。 這是用戶向量的儲存-用戶的連結。 每個使用者都有一個peer_id向量（對話者-其他使用者、多聊天或社群）和一個訊息向量。 每個peer_id都有一個與其相關的訊息向量。 每個訊息都有一個 chat_local_id 和該使用者的唯一訊息 ID - user_local_id。
新叢集使用 TCP 相互通訊 - 這可以確保請求的順序不會改變。 請求本身及其確認記錄在硬碟上 - 因此我們可以在引擎故障或重新啟動後隨時恢復佇列的狀態。 由於用戶引擎和聊天引擎各有 4 個分片，因此叢集之間的請求佇列將均勻分佈（但實際上根本沒有 - 而且運行速度非常快）。
在大多數情況下，我們資料庫中的磁碟操作是基於二進位更改日誌 (binlog)、靜態快照和記憶體中的部分映像的組合。 白天的變更會寫入二進位日誌，並定期建立目前狀態的快照。 快照是為我們的目的而優化的資料結構的集合。 它由一個標頭（圖像的元索引）和一組元檔案組成。 標頭永久儲存在 RAM 中，並指示從快照中尋找資料的位置。 每個圖元檔案都包含在接近的時間點可能需要的數據，例如與單一使用者相關的數據。 當您使用快照頭查詢資料庫時，將讀取所需的圖元文件，然後考慮建立快照後發生的二進位日誌中的變更。 您可以閱讀有關此方法優點的更多信息 .
同時，硬碟上的資料每天只更改一次 - 在莫斯科的深夜，此時負載最小。 由於這一點（知道磁碟上的結構全天保持不變），我們可以用固定大小的數組替換向量 - 因此，可以增加記憶體。
在新方案中發送訊息如下所示：
- PHP 後端聯絡用戶引擎並請求發送訊息。
- 使用者引擎將請求代理到所需的聊天引擎實例，該實例返回使用者引擎 chat_local_id - 此聊天中新訊息的唯一識別碼。 然後，chat_engine 將訊息廣播給聊天中的所有收件者。
- 使用者引擎從聊天引擎接收 chat_local_id 並將 user_local_id 傳回給 PHP - 該使用者的唯一訊息識別碼。 然後使用該標識符，例如透過 API 處理訊息。
但除了實際發送訊息之外，您還需要實現一些更重要的事情：
- 例如，子清單是您開啟對話清單時看到的最新訊息。 未讀訊息、帶有標籤的訊息（「重要」、「垃圾郵件」等）。
- 在聊天引擎中壓縮訊息
- 在用戶引擎中快取訊息
- 搜尋（透過所有對話方塊並在特定對話方塊中）。
- 即時更新（長輪詢）。
- 保存歷史記錄以在行動用戶端上實現快取。
所有子列表的結構都在快速變化。 為了與他們合作，我們使用 。 這種選擇的解釋是，我們有時會在樹的頂部儲存快照中的一整段訊息 - 例如，在每晚重新索引之後，樹由一個頂部組成，其中包含子清單的所有訊息。 Splay 樹可以輕鬆插入到此類頂點的中間，而無需考慮平衡。 另外，Splay不會儲存不必要的數據，這節省了我們的記憶體。
訊息涉及大量訊息，其中大部分是文本，能夠進行壓縮非常有用。 重要的是我們能夠準確地取消存檔，即使是一封單獨的郵件。 用於壓縮訊息 透過我們自己的啟發法 - 例如，我們知道在訊息中單字與「非單字」（空格、標點符號）交替出現 - 而且我們還記得使用俄語符號的一些特殊性。
由於用戶比聊天少得多，為了在聊天引擎中保存隨機存取磁碟請求，我們將訊息緩存在用戶引擎中。
訊息搜尋被實作為從使用者引擎到包含該使用者聊天的所有聊天引擎實例的對角線查詢。 結果在用戶引擎本身中組合。
好吧，所有細節都已考慮在內，剩下的就是切換到新方案 - 最好是在用戶沒有註意到的情況下。
資料遷移
因此，我們有一個按使用者儲存訊息的文字引擎，以及兩個叢集 chat-member 和 member-chats，它們儲存有關多聊天室及其中使用者的資料。 如何從這個轉移到新的使用者引擎和聊天引擎？
舊方案中的member-chats主要用於最佳化。 我們迅速地將必要的資料從它轉移到聊天成員，然後它就不再參與遷移過程。
聊天成員排隊。 它包括 100 個實例，而 chat-engine 有 4 個實例。 要傳輸數據，您需要使其合規 - 為此，聊天成員被分成相同的 4 個副本，然後在聊天引擎中啟用聊天成員 binlog 的讀取。
現在聊天引擎知道來自聊天成員的多聊天，但它還不知道與兩個對話者的對話。 此類對話位於與使用者相關的文字引擎中。 在這裡，我們「正面」獲取資料：每個聊天引擎實例詢問所有文字引擎實例是否有所需的對話。
太棒了 - 聊天引擎知道有哪些多聊天聊天，並且知道有哪些對話。
您需要合併多個聊天中的消息，以便最終在每個聊天中獲得一個訊息列表。 首先，聊天引擎從文字引擎檢索此聊天中的所有使用者訊息。 在某些情況下，它們的數量相當多（多達數億），但除了極少數例外，聊天完全適合 RAM。 我們有無序的訊息，每個訊息都有多個副本 - 畢竟，它們都是從與用戶相對應的不同文字引擎實例中提取的。 目標是對郵件進行排序並刪除佔用不必要空間的副本。
每個訊息都有一個時間戳，其中包含發送時間和文字。 我們使用時間進行排序 - 我們將指標放置在多聊天參與者最舊的訊息上，並比較目標副本文字中的雜湊值，從而增加時間戳記。 副本具有相同的雜湊值和時間戳記是合乎邏輯的，但實際上並非總是如此。 您還記得，舊方案中的同步是由 PHP 執行的 - 在極少數情況下，不同用戶發送相同訊息的時間會有所不同。 在這些情況下，我們允許自己編輯時間戳記——通常在一秒鐘內。 第二個問題是不同收件人的訊息順序不同。 在這種情況下，我們允許建立額外的副本，為不同的使用者提供不同的訂購選項。
此後，有關多聊天中的消息的數據將發送到用戶引擎。 導入訊息有一個令人不快的功能。 在正常操作中，到達引擎的訊息嚴格按照 user_local_id 升序排列。 從舊引擎導入到用戶引擎的消息失去了這個有用的屬性。 同時，為了測試的方便，您需要能夠快速存取它們，在其中找到內容並添加新內容。
我們使用特殊的資料結構來儲存導入的訊息。
它表示一個大小的向量 大家在哪裡 - 不同且依降序排列，具有特殊的元素順序。 在每個帶有索引的段落中 元素已排序。 在這樣的結構中搜尋元素需要時間 通過 二分搜尋。 增加的元素攤銷 .
因此，我們找到瞭如何將資料從舊引擎傳輸到新引擎的方法。 但這個過程需要幾天的時間——在這些天裡我們的用戶不太可能放棄互相寫信的習慣。 為了在這段時間不遺失訊息，我們切換到同時使用新舊叢集的工作方案。
資料被寫入聊天成員和使用者引擎（而不是文字引擎，例如根據舊方案的正常操作）。 用戶引擎將請求代理到聊天引擎 - 這裡的行為取決於該聊天是否已經被合併。 如果聊天尚未合併，則聊天引擎不會將訊息寫入自身，且其處理僅在文字引擎中進行。 如果聊天已合併到聊天引擎中，則會將 chat_local_id 返回使用者引擎並將訊息傳送給所有收件者。 用戶引擎將所有資料代理到文字引擎 - 這樣，如果發生問題，我們可以隨時回滾，將所有當前資料保留在舊引擎中。 text-engine 傳回 user_local_id，使用者引擎儲存該 ID 並將其返回後端。
因此，轉換過程如下所示：我們連接空的用戶引擎和聊天引擎群集。 chat-engine 讀取整個 chat-members binlog，然後依照上述方案啟動代理程式。 我們傳輸舊數據並獲得兩個同步集群（舊的和新的）。 剩下的就是將讀取從文字引擎切換到用戶引擎並禁用代理。
Результаты
由於採用了新方法，引擎的所有效能指標都得到了改進，資料一致性問題也得到了解決。 現在我們可以快速在訊息中實現新功能（並且已經開始這樣做 - 我們增加了聊天參與者的最大數量，實現了對轉發訊息的搜索，啟動了固定訊息並提高了每個用戶訊息總數的限制） 。
邏輯上的變化確實是巨大的。 我想指出的是，這並不總是意味著需要一個龐大的團隊和無數行程式碼進行多年的開發。 聊天引擎和使用者引擎以及所有附加故事（例如用於訊息壓縮的 Huffman、Splay 樹和匯入訊息的結構）不到 20 萬行程式碼。 它們是由 3 位開發人員在短短 10 個月內編寫的（但是，值得記住的是 - 世界冠軍 ).
此外，我們沒有將伺服器數量增加一倍，而是將其數量減少了一半——現在用戶引擎和聊天引擎運行在 500 台實體機器上，而新方案有很大的負載空間。 我們在設備上節省了大量資金 - 大約 5 萬美元 + 每年 750 萬美元的營運費用。
我們努力為最複雜和大規模的問題找到最佳解決方案。 我們有很多這樣的人 - 這就是我們在資料庫部門尋找有才華的開發人員的原因。 如果您熱愛並知道如何解決此類問題，並且對演算法和資料結構有豐富的了解，我們邀請您加入我們的團隊。 聯絡我們的 了解詳情。
即使這個故事與您無關，請注意，我們重視推薦。 告訴朋友 ，如果他成功完成試用期，您將獲得100萬盧布的獎金。
來源： www.habr.com