FlockDB存儲(chǔ)圖數(shù)據(jù)的數(shù)據(jù)庫(kù)

FlockDB是一個(gè)存儲(chǔ)圖數(shù)據(jù)的數(shù)據(jù)庫(kù)，但是它并沒(méi)有優(yōu)化遍歷圖的操作。它優(yōu)化的操作包括：超大規(guī)模鄰接矩陣查詢(xún)，快速讀寫(xiě)和可分頁(yè)查詢(xún)。

FlockDB將圖存儲(chǔ)為一個(gè)邊的集合，每條邊用兩個(gè)代表頂點(diǎn)的64位整數(shù)表示。對(duì)于一個(gè)社會(huì)化網(wǎng)絡(luò)圖，這些頂點(diǎn)ID即用戶(hù)ID，但是對(duì)于“收藏”推文這 樣的邊，其目標(biāo)頂點(diǎn)(destination id)則是一條推文的ID。每一條邊都被一個(gè)64位的位置信息標(biāo)識(shí)，用于排序。(Twitter在“關(guān)注”類(lèi)的邊上用了時(shí)間戳標(biāo)識(shí)，所以你的關(guān)注者列表時(shí) 按時(shí)間排序的，最新的在最前面。）

當(dāng)一條邊被“刪除”，這條記錄并沒(méi)有從MySQL中真正刪除，而是標(biāo)記為“刪除”狀態(tài)，這會(huì)影響到主鍵值(一個(gè)由源ID-source id，狀態(tài)-position，位置-position構(gòu)成的組合鍵)。類(lèi)似的，用戶(hù)賬戶(hù)被刪除時(shí)，他們所有的邊都會(huì)改為存檔(archive)狀態(tài)，允 許之后被恢復(fù)(但是根據(jù)服務(wù)協(xié)議，我們只會(huì)保留一段時(shí)間)。我們只保留了一個(gè)組合主鍵和一個(gè)輔助索引來(lái)完成所有的查詢(xún)。這種表結(jié)構(gòu)優(yōu)化使得MySQL大放 異彩，并提供給我們可預(yù)測(cè)的性能。

一條復(fù)雜的查詢(xún)例如“我關(guān)注的人里面哪些關(guān)注了奧巴馬總統(tǒng)”能分解成一些單用戶(hù)查詢(xún)(誰(shuí)在關(guān)注奧巴馬總統(tǒng))，并很快響應(yīng)。數(shù)據(jù)根據(jù)節(jié)點(diǎn)分塊，所以這些查詢(xún)能分別在各自的數(shù)據(jù)塊，通過(guò)一個(gè)索引過(guò)的范圍查詢(xún)得到結(jié)果。類(lèi)似的，遍歷一個(gè)長(zhǎng)結(jié)果集是用位置作為游標(biāo)，而不是用LIMIT/OFFSET，所有頁(yè)的數(shù)據(jù)均被索引，訪問(wèn)一樣快。

基于進(jìn)入系統(tǒng)的時(shí)間，寫(xiě)操作具有冪等性(不管操作多少次結(jié)果都不變的性質(zhì)，比如取絕對(duì)值的函數(shù)就具有冪等性)和交換性(操作順序不影響結(jié)果，比如加法就具 有交換性)。因?yàn)槟芙粨Q操作順序而不影響最終結(jié)果，所以我們才能在網(wǎng)絡(luò)或者硬件臨時(shí)故障的時(shí)候記錄下所有操作或者恢復(fù)幾分鐘甚至幾小時(shí)之前丟失的數(shù)據(jù)。這 種性質(zhì)在初次部署是尤其有用。

可交換的寫(xiě)操作簡(jiǎn)化了新數(shù)據(jù)塊的創(chuàng)建流程。一個(gè)新數(shù)據(jù)塊能在即時(shí)處理寫(xiě)請(qǐng)求的同時(shí)，在后臺(tái)慢慢從舊數(shù)據(jù)塊導(dǎo)入數(shù)據(jù)。導(dǎo)入完成時(shí)，該數(shù)據(jù)塊即處于“激活”狀態(tài)，并準(zhǔn)備處理讀操作。

應(yīng)用服務(wù)器(昵稱(chēng)flapps)用Scala編寫(xiě)，無(wú)狀態(tài)，可水平伸縮。flapps與數(shù)據(jù)庫(kù)獨(dú)立，隨著查詢(xún)負(fù)載增加，我們可以增加更多的flapps。Flapps暴露了很少的thrift API給客戶(hù)端，我們寫(xiě)的Ruby客戶(hù)端包含更豐富的接口。

我們使用Gizzard庫(kù)來(lái)處理數(shù)據(jù)分塊層。該層將一段源ID映射到物理數(shù)據(jù)庫(kù)，對(duì)于同一個(gè)物理地址的表，通過(guò)建立樹(shù)來(lái)處理。寫(xiě)操作在本地登記后即返回，這樣數(shù)據(jù)庫(kù)崩潰或者出現(xiàn)性能問(wèn)題能有效跟網(wǎng)站相應(yīng)時(shí)間解耦。

圖的每一條邊都被存儲(chǔ)了兩次：一次正向存儲(chǔ)(根據(jù)源ID做索引和分塊)，一次反向存儲(chǔ)(根據(jù)目的ID做索引和分塊)。這樣類(lèi)似于“誰(shuí)在關(guān)注我”這樣的查詢(xún)可以跟查詢(xún)“我在關(guān)注誰(shuí)”一樣高效，并且所有結(jié)果數(shù)據(jù)都分布在同一塊。

結(jié)果是我們擁有了一個(gè)可以按需擴(kuò)展的一般服務(wù)器集群。在這個(gè)冬天，我們不知不覺(jué)已經(jīng)增加了50%的數(shù)據(jù)庫(kù)容量?，F(xiàn)在我這個(gè)數(shù)據(jù)庫(kù)里存儲(chǔ)了130億條邊，峰值可承受負(fù)載達(dá)到每秒2萬(wàn)次寫(xiě)和10萬(wàn)次讀。

介紹內(nèi)容來(lái)自 http://article.yeeyan.org/view/yangxiao/136627