存儲圖數據的數據庫 FlockDB
FlockDB是一個存儲圖數據的數據庫，但是它并沒有優化遍歷圖的操作。它優化的操作包括：超大規模鄰接矩陣查詢，快速讀寫和可分頁查詢。
- a high rate of add/update/remove operations
- potientially complex set arithmetic queries
- paging through query result sets containing millions of entries
- ability to "archive" and later restore archived edges
- horizontal scaling including replication
- online data migration
FlockDB將圖存儲為一個邊的集合，每條邊用兩個代表頂點的64位整數表示。對于一個社會化網絡圖，這些頂點ID即用戶ID，但是對于“收藏” 推文這 樣的邊，其目標頂點(destination id)則是一條推文的ID。每一條邊都被一個64位的位置信息標識，用于排序。(推ter在“關注”類的邊上用了時間戳標識，所以你的關注者列表時 按時間排序的，最新的在最前面。）
當一條邊被“刪除”，這條記錄并沒有從MySQL中真正刪除，而是標記為“刪除”狀態，這會影響到主鍵值(一個由源ID-source id，狀態-position，位置-position構成的組合鍵)。類似的，用戶賬戶被刪除時，他們所有的邊都會改為存檔(archive)狀態，允 許之后被恢復(但是根據服務協議，我們只會保留一段時間)。我們只保留了一個組合主鍵和一個輔助索引來完成所有的查詢。這種表結構優化使得MySQL大放 異彩，并提供給我們可預測的性能。
一條復雜的查詢例如“我關注的人里面哪些關注了奧巴馬總統”能分解成一些單用戶查詢(誰在關注奧巴馬總統)，并很快響應。數據根據節點分塊，所以這些查詢能分別在各自的數據塊，通過一個索引過的范圍查詢得到結果。類似的，遍歷一個長結果集是用位置作為游標，而不是用LIMIT/OFFSET，所有頁的數據均被索引，訪問一樣快。
基于進入系統的時間，寫操作具有冪等性(不管操作多少次結果都不變的性質，比如取絕對值的函數就具有冪等性)和交換性(操作順序不影響結果，比如加法就具 有交換性)。因為能交換操作順序而不影響最終結果，所以我們才能在網絡或者硬件臨時故障的時候記錄下所有操作或者恢復幾分鐘甚至幾小時之前丟失的數據。這 種性質在初次部署是尤其有用。
可交換的寫操作簡化了新數據塊的創建流程。一個新數據塊能在即時處理寫請求的同時，在后臺慢慢從舊數據塊導入數據。導入完成時，該數據塊即處于“激活”狀態，并準備處理讀操作。
應用服務器(昵稱flapps)用Scala編寫，無狀態，可水平伸縮。flapps與數據庫獨立，隨著查詢負載增加，我們可以增加更多的flapps。Flapps暴露了很少的thrift API給客戶端，我們寫的Ruby客戶端包含更豐富的接口。
我們使用Gizzard庫來處理數據分塊層。該層將一段源ID映射到物理數據庫，對于同一個物理地址的表，通過建立樹來處理。寫操作在本地登記后即返回，這樣數據庫崩潰或者出現性能問題能有效跟網站相應時間解耦。
圖的每一條邊都被存儲了兩次：一次正向存儲(根據源ID做索引和分塊)，一次反向存儲(根據目的ID做索引和分塊)。這樣類似于“誰在關注我”這樣的查詢可以跟查詢“我在關注誰”一樣高效，并且所有結果數據都分布在同一塊。
結果是我們擁有了一個可以按需擴展的一般服務器集群。在這個冬天，我們不知不覺已經增加了50%的數據庫容量。現在我這個數據庫里存儲了130億條邊，峰值可承受負載達到每秒2萬次寫和10萬次讀。
介紹內容來自 http://article.yeeyan.org/view/yangxiao/136627