1.前言

為了適應大數據應用場景的要求,Hadoop以及NoSQL等與傳統企業平臺完全不同的新興架構迅速地崛起.而下層技術基礎的革命必將影響上層建筑：數據模型和算法.簡單地將傳統基于第四范式結構化關系型數據庫的模型拷貝到新的引擎上,無異于削足適履,不僅增加了大數據應用開發的難度和復雜度,又無法發釋放新框架的潛能.

該如何構建基于NoSQL的數據模型?現在能供參考的公開知識積累要么是空虛簡單的一句“去規范化“或粗暴的寬表化(將query和應用需要訪問的所有字段“排排坐“,放在一個有很多列的結構化表中),要么是針對具體工具或具體場景的實現細節,(如《HBase權威指南》中對于如何設計HBase主鍵的探討).沒有一個像編程的設計模式一樣的,在模型架構層面可以遵循的方法論.

在比較不同的NoSQL數據庫時,通常使用功能以外其他各種指標,如可擴展性、性能和一致性.由于這些指標通常是使用NoSQL的初衷,所以無論從理論的角度還是實踐的角度被深入地研究了,而像CAP定理這樣的分布式系統基礎結論也同樣適用于NoSQL系統.另一方面,在NoSQL的數據模型領域,卻還沒有很好地研究過,也缺乏關系數據庫中那種系統性的理論.

我在這篇文章中從數據建模的角度對NoSQL家族系統做了比較簡單的比較,并簡要介紹幾種常見建模技術.

2.NoSQL數據模型視圖

要探索數據建模技術,必須先從系統性的NoSQL數據模型視圖著手,這多多少少能幫助我們揭示其發展趨勢以及相互之間的關系.下圖描繪了主要NoSQL家族系統的虛擬“進化”過程,即鍵值存儲,BigTable類型的數據庫,文檔數據庫,全文搜索引擎,數據庫和圖形數據庫：

首先,我們應該注意到,一般意義上講,SQL和關系型模型都是在很久以前就被設計出來,目的是為最終用戶交互之用.這種面向用戶的性質有極深的影響：

最終用戶往往對匯總報表信息感興趣而不是單獨的數據項,因而SQL這方面做了大量的工作.

不能指望作為自然人的用戶能顯式地控制并發性、完整性、一致性或者數據類型有效性.這就是為什么SQL竭力關注于事務保證、schema和參照完整性.

另一方面,軟件應用程序往往對在數據庫內部做聚合沒有太大的興趣,而且至少在許多情況下,程序能夠自己控制完整性和有效性.除此之外,剔除這些功能對于性能和可擴展性存儲的影響極其重要.

新數據模型的演變開始了：

鍵-值存儲是一個非常簡單,但非常強大的模型.下面所描述的許多技術都完全適用于這個模型.

鍵值模型最致命的缺點之一就是不適合按范圍處理主鍵的場景.有序的鍵-值模型突破了這一限制,并顯著提高了聚合能力.

有序的鍵-值模型非常強大,但它不提供任何針對值(value)的建模框架.在一般情況下,值的建模可以由應用程序完成,但BigTable風格的數據庫想得更加周到,它可以將值按照映射的映射的映射(map-of-maps-of-maps)進行建模,說得明確點,分別是列簇(column family)、列(column)和時間戳化的版本.

文檔數據庫對BigTable模式提出兩個明顯的改善.第一,值可以被聲明為任意復雜的schema,而不僅僅是一個映射的映射(map-of-maps).第二,至少有一些產品實現了被數據庫管理的索引.就這個意義上來講,全文搜索引擎也可以同樣被認為提供了靈活的schema和自動化的索引.他們之間主要區別在于,文檔數據庫是根據字段名對索引進行編組,而搜索引擎是使用字段值對索引編組.值得注意的是像Oracle Coherence這樣的鍵-值存儲系統增加了索引和內嵌入口處理器的功能,正逐步向文件數據庫演進.

最后,圖形數據模型可以被視為有序的鍵-值模型朝另外一個方向的進化.圖形數據庫允許對業務實體進行非常透明的建模(這個東西取決于那個東西),而分層建模技術在這方面用的是另外的數據模型,但也可與之媲美.圖形數據庫和文件數據庫息息相關,因為許多實現允許建模的值是映射或者文檔.

3.NoSQL數據建模的一般注意事項

與關系型建模不同,NoSQL數據建模往往是從特定查詢的應用開始：

關系型建模是典型地被手上可用數據的結構所驅動.設計主要圍繞著的是“我有什么樣的答案?”

NoSQL數據建模通常由特定應用的訪問模式所驅動,比如需要支持的查詢類型.設計主要圍繞著的是“我有什么問題?”

NoSQL數據建模往往比關系數據庫建模需要更加深入地了解數據結構和算法.在這篇文章中,我介紹了幾個著名的數據結構,他們雖然非NoSQL所特有,但對于實際的NoSQL建模非常有用.

數據復制和去規范化是一等公民.

關系數據庫在對分層或圖形數據進行建模和處理時不是很方便.圖形數據庫顯然是這個領域的完美解決方案,但實際上大多數的NoSQL也都非常善于解決這樣的問題.這就是為什么這篇文章為分層數據建模單獨寫了一個章節.

雖然數據建模技術基本上和具體實現無關,但我還是列出了在寫這篇文章時我能想到的產品：

鍵值存儲：Oracle Coherence,Redis,Kyoto Cabinet

BigTable風格的數據庫： Apache HBase,Apache Cassandra

文檔數據庫： MongoDB,CouchDB

全文搜索引擎： Apache Lucene,Apache Solr

圖形數據庫：Neo4j,FlockDB

4.概念技術

本節專門介紹NoSQL數據建模的基本原則.

1、 去規范化(Denormalization)

可以將去規范化定義為把相同的數據復制到多個文檔或數據表中,這樣可以簡化/優化查詢處理,或者讓用戶數據能匹配一個特定的數據模型.在本文的大多數技術用到了這樣或那樣的去規范化.

一般來說,去規范化用于以下的折衷：

查詢的數據量或每次查詢IO**與總數據量的折衷.去規范化可以將一個查詢所需的所有數據組合起來存放到同一個地方.這通常意味著對相同數據的不同的查詢會訪問不同的數據組合.因此,數據需要被復制多份,也就意味著增加了總數據量.

處理復雜性與總數據量的折衷.建模時的規范化和相應查詢的連接(join)明顯增加了查詢處理器的復雜度,在分布式系統中尤為明顯.去規范化允許將數據按照查詢友好的方式存儲,從而簡化查詢的處理.

適用性：鍵值存儲,文檔數據庫, BigTable風格的數據庫

2、 聚合(Aggregates)

所有主流NoSQL都提供了這樣或那樣的松散schema(soft schema)支持：

鍵值存儲和圖形數據庫通常不對值進行約束,所以值可能是任意格式.另外,也可以通過使用組合鍵將一個業務實體表示為多條記錄.例如,可以將一個用戶帳戶建模為UserID_name,UserID_email,UserID_messages等組合鍵表示的一個實體集合.如果用戶沒有電子郵件或消息,然后相應的實體不會被記錄.

BigTable模式也支持松散schema,因為一個列簇是可變的列集合,一個單元格又能存儲不定數目的數據版本.

文檔數據庫天生就沒schema,雖然某些文檔數據庫允許在數據輸入時使用用戶定義的schema進行驗證.

松散schema允許使用復雜的內部結構(嵌套實體)構造實體的類,也允許改變特定實體的結構.這個更能帶來了兩個重要的便利：

通過嵌套的實體,最小化了一對多的關系,也因此減少了連接(join).

異構業務實體的模型可以使用一個文檔集合或者一個數據表.松散schema掩藏了這種建模和業務實體之間“技術”上的差異.

我們用下面的圖來說明這些便利.該圖描繪了對電子商務領域中一個產品實體進行的建模.首先我們可以認為所有的產品都有一個ID、價格(Price)和描述(Description).進一步來看,我們發現不同類型的產品有不同的屬性,如圖書包含作者信息,而牛仔褲有長度屬性.這些屬性中間的某些屬性天生就有一對多或這多對多的特性,比如音樂唱片中的曲目.

更進一步來看,可能有些實體不可能使用固定的類型進行建模.例如,不同品牌的牛仔褲的屬性是不固定的,而每個制造商出產的牛仔褲的屬性也是不一致的.在規范化的關系型數據模型中雖然這些問題都可以解決,但方法很猥瑣.松散schema軟架構允許只使用一個聚合(Aggregation)(產品)就能對所有類型的產品及其屬性進行建模：

內嵌的去規范化會在性能和一致性上對更新操作造成很大的影響,所以要特別注意更新過程.

適用性：鍵值存儲,文檔數據庫, BigTable的風格數據庫

3、 應用端連接(Application Side Joins)

很少有NoSQL解決方案支持連接.NoSQL“問題導向”性質的后果就是,通常在設計時處理join,而關系型模型是在執行查詢時處理join.查詢時處理join幾乎肯定會帶來性能上的損失,但在許多情況下,可使用去規范化和聚合,即嵌入嵌套實體來避免join.當然,join在許多情況下是不可避免的,而且應該由應用程序處理.主要的用例：

多對多關系往往是通過鏈接(link)建模的,這需要join.

聚合操作往往不適合內部實體會被頻繁修改的場景.通常更好的辦法是將發生的事情作為一條新的記錄保留,并在查詢的時候將所有記錄做join,而不是去更改值.例如,對于一個信息系統而言,可以用嵌套包含了Message實體的User實體來建模.但是,如果會經常地添加消息,更好的辦法可能是把Message提取出來作為獨立實體,并在查詢時再將其與User進行連接：

適用性：鍵值存儲,文檔數據庫, BigTable風格數據庫,圖形數據庫

5.一般建模技術

在本節中,我們將討論適用于各種NoSQL實現的一般建模技術.

1、 原子聚合(Atomic Aggregates)

許多NoSQL解決方案提供了有限的事務支持,雖然有些NoSQL不支持.在某些情況下,人們還可以使用分布式鎖或應用程序管理的MVCC機制實現事務行為,但常見的是使用聚合技術來對數據建模,以保證一些ACID特性.

強大的事務處理機制對于關系型數據庫而言是不可或缺的,其中原因之一就是規范化的數據通常需要在多個地方進行更新.另一方面,聚合允許一個單個業務實體存儲為一個文件,行或鍵值對,從而可以對其進行原子性的更新：

當然,做為一種數據建模技術,原子聚合并不是一個完善的事務型解決方案,但如果存儲能提供原子性、鎖或者TAS(test-and-set,測試并設置)指令上的一些擔保,那原子聚合就是可行的.

(譯者注：即將需要事務性操作的業務數據聚合放在一起,存儲在一個NoQSQL提供或者應用能提供原子性操作的數據結構中.使用HBase時,將某個用戶某個業務的所有數據,如上圖,用一行存儲就是這種模式的應用.)

適用性：鍵值存儲,文檔數據庫, BigTable風格數據庫

2、 可枚舉主鍵(Enumerable Keys)

也許無序鍵-值數據模型最大的好處就是可以通過將主鍵哈希的辦法把實體數據分別存儲在多個服務器上.排序使事情變得更加復雜,但是即使存儲不提供這樣的功能,有時應用程序也能利用到有序主鍵的優勢.讓我們將對電子郵件建模作為一個例子：

某些NoSQL存儲提供原子計數器,能生成一個順序化的ID.在這種情況下,可以使用userID_messageID作為一個復合鍵來存儲消息.如果最新的消息ID是已知的,那就可以遍歷以前的消息.另外,對于任何一個給定的消息ID,也可以向前或向后進行遍歷.

也可以將消息分桶(bucket),例如,每天的數據放到一個桶里.這樣就允許從任何指定日期或當前日期開始,向前或向后遍歷一個郵箱.

適用性：鍵值存儲

(譯者注：能利用主鍵的一些自然或業務維度的特征,將隨機讀寫轉換為順序讀寫能提高遍歷性能,同時能方便應用邏輯編寫.但需要注意對分布式部署時并發寫的影響以及對于業務的過度耦合.對于無序主鍵和有序主鍵的討論可以參見《HBase權威指南》中Schema設計章節.)

3、 降維(Dimensionality Reduction)

降維這種技術允許將一個多維數據模型映射到一個鍵-值模型或其他非多維模型.

傳統的地理信息系統使用四叉樹(Quadtree)或R樹(R-tree)的某種變形來做索引.這些結構需要就地完成更新操作,因此在數據量很大時,維護開銷相當的大.另一種方法是對這個二維結構進行遍歷,并將其扁平化為一個普通的條目列表.使用這種技術的一個眾所周知的例子是Geohash. Geohash使用類似Z形狀的路線來掃描整個二維空間,每次移動根據行進方向被編碼為0或1.交錯位的經度和緯度上的變更移動以及移動.編碼過程在下圖中進行了說明,其中黑色和紅色位分別代表經度和緯度：

如圖所示,Geohash的一個重要特性是能夠通過這種逐位編碼的近似程度來估計區域之間的距離.Geohash編碼允許使用簡單普通的數據模型來存儲地理信息,比如用有序鍵值保存空間上的聯系.[6.1]講述了BigTable中的降維技術.更多有關Geohash及其相關技術的信息可以在[6.2]和[6.3]中找到.

適用性：鍵值存儲,文檔數據庫, BigTable風格的數據庫

(譯者注：通過交織編碼方式來能將原本需要多維度標示的數據,如cube,存儲到一維的鍵值存儲系統中,這是一種非常重要的建模模式：提供了不同縮放等級下在多維空間中鄰接的數據仍然順序存儲,遍歷高效;同時不同主鍵從前向后的相似度和空間距離的遠近相一致,能通過鍵值的簡單順序比較判斷其位置“相似度”.

它的應用遠遠不只地理信息的表示,有多個維度屬性不同粒度的數據表示都能用到這個技術,比如線下銷售交易數據通常都有時間和分支結構信息,用戶查詢銷售數據時通常先查詢一個大的區域,而且使用的時間段跨度也比較大,需要查詢更具體的信息時同時縮小地區和時間來逐步定位細節,這時分支機構和時間就好比是經度維度的兩個軸,通過交織時間和分支結構編碼的方式建立主鍵,能很好的滿足這種場景.而單純的使用時間或分支機構做主鍵或索引卻都不能適應上述場景.)

4、 索引表(Index Table)

索引表是一個非常簡單的技術,它在內部不支持索引的存儲上提供索引的支持.這類存儲中最重要的一類就是BigTable風格的數據庫.索引表的想法是按照訪問模式所需要的鍵來創建和維護一個特殊的表.例如,有一個主表,存儲了可以通過用戶ID直接訪問的用戶帳戶.查詢指定城市的所有用戶可以通過一個額外的用城市做主鍵的表來支持：

索引表可以在每一個主表記錄更新時更新或者使用批模式更新.無論哪種方式,它會導致額外的性能損失,并帶來數據一致性上的問題.

可以認為索引表是一種對關系數據庫實例化視圖的模擬.

適用性： BigTable風格的數據庫

5、 組合主鍵索引(Composite Key Index)

復合主鍵是一個非常通用的技術,但尤其在主鍵有序存儲時極其有用.復合主鍵結合二次排序就能建立起一種多維索引,這和前面所述的降維技術在原理上是類似的.例如,假設我們有一組記錄,每個記錄是一個用戶統計數據.如果我們要按用戶來自的地區來聚合這些統計資料,我們可以使用這樣的主鍵格式(State:City:UserId).如果主鍵的存儲支持通過部分匹配來選取范圍(如BigTable風格的數據庫),那就可以在特定的州(State)或者城市(City)的記錄上做遍歷：

適用性： BigTable風格的數據庫

(譯者注：在使用HBase這類BigTable風格的數據庫時,如果主鍵只使用一個字段/域的信息簡直是暴殄天物.使用多字段組合主鍵不僅能解決主鍵值不能重復的問題,還能提高對于數據子集二次查找時的性能.)

6、 組合主鍵的聚合

復合主鍵不僅可用于作索引,還可以為不同類型分組.讓我們來看一個例子.有一個巨大的日志數組,記錄了互聯網用戶和他們訪問不同的網站(點擊流)的信息.我們的目標是對于每個唯一用戶計算出每個站點的點擊數量.這類似于下面的SQL查詢：

我們可以使用將用戶名當前綴的組合主鍵來對這種情況進行建模：

我們的想法是將一個用戶的所有記錄放置在一起,這樣就可能將其全部加載到內存中(一個用戶不會產生太多的事件),并使用哈希表或其他方法消除掉重復的網站.另一種技術是將用戶做為主鍵,每次事件到達時將網站添加到這條數據的后部.然而,在大多數實現中,修改數據一般比插入數據的效率低.

適用性：有序鍵值存儲,BigTable風格的數據庫

7、 倒排搜索-直接聚合

這種技術更像是數據處理模式,而不是數據建模.然而,數據模型也受這種模式使用的影響.這種技術的主要思想是使用索引來找到滿足條件的數據,但聚合操作還是使用原來的方式或者全表掃描.讓我們來考慮一個例子.有一堆的日志數據記錄了互聯網用戶和他們訪問不同的網站(點擊流,click stream)的信息.假設每條記錄都包括用戶ID、用戶所屬類別(男性、女性、博主(Blogger)等)、用戶來自的城市以及訪問的網址.我們的目標是找出滿足條件(網址、城市等)的觀眾,并將這堆觀眾(如符合標準的用戶集合)中出現的不同用戶按類別歸類.

很明顯,滿足條件的用戶可以通過像{類別->[用戶ID]}或{網站->[用戶ID]}這樣的倒排索引表非常高效地查找到.使用這樣的倒排索引,可以得到所要的用戶ID的交集或者并集(如果用戶ID被存儲為排有序的列表或位圖,這就可以非常高效地實現),從而獲得目標用戶.但如果目標用戶是使用類似這樣的聚集查詢描述的：

那如果類別的數量很大,就不能用倒排索引做有效的處理.要解決這個問題,可以用{用戶名->[分類集合]}的形式創建直接索引(Direct Index),然后遍歷它來建立最終報表.此架構示意如下圖：

最后需要提示的是,我們需要知道如果隨機地訪問目標用戶中每一個用戶ID所對應記錄,這樣做的效率可能很低.可以通過利用批量查詢處理解決這個問題.這意味著,一些數量的用戶集可以被預先計算(針對不同的報表條件),然后可以通過對直接索引表或倒排索引表進行一次全表掃描從而計算出這批目標用戶的所有報告.

適用性：鍵值存儲,BigTable風格的數據庫,文檔數據庫

分層建模技術(Hierarchy Modeling Techniques)

(譯者注：如果需要通過屬性或者類別來快速查找對應的實體,這樣的索引比不可少.現在很火的用大數據分析用戶畫像不就需要像{用戶標簽->用戶群}這樣的結構么.)

8、 樹聚合(Tree Aggregation)

可以將一條單獨的記錄或者文件的模型建成樹,甚至是任意的圖(通過去規范化).

在樹會被一次性訪問的場景中(例如,博客的整個評論樹會被讀取,并顯示在一篇文章的頁面中),這個技術很高效.

搜索和訪問任意條目可能有問題.

在大多數NoSQL的實現中,更新操作的效率低下(同相互獨立的節點相比).

適用性：鍵值存儲,文檔數據庫

(譯者注：這是文檔型NoSQL的天下,對于無需跨樹join的場景,不僅讀寫效率高,而且能很好的支持局部性的事務應用.)

9、 鄰接列表(Adjacency Lists)

鄰接列表是一個簡單的圖型建模方法——每個節點作為一個單獨記錄建模,其中有包含直接祖先的數組或包含后代的數組.它允許通過其父母或子女的標識符來搜索一個節點,當然也可以通過查詢一次前進一步的方式來遍歷一個圖.無論對于深度優先或廣度優先遍歷而言,要在整個子樹中找到一個給定的節點,這種方法的效率通常不高.

適用性：鍵值存儲,文檔數據庫

10、 物化路徑

物化路徑是一種有助于避免在樹型結構上做遞歸遍歷的技術.也可以認為這是一種去規范化的技術.其設計思想是用一個節點所有的父節點或者子女節點來標識該節點,這樣就有可以不用遍歷而得到一個節點的所有祖先節點或者衍生節點：

因為這個技術可以將層次結構轉換成扁平化的文檔,所以它對于全文搜索引擎特別地有用.從上圖中可以看出,在男鞋(Men’s Shoes)類別下所有的產品或者子類別可以簡單的通過查詢一個類別名稱而得到.這個查詢很短.

物化路徑的存儲方式可以是一個ID的集合,或者一個是包含級聯ID的字符串.后一種方式允許使用正則表達式,來查找那些指定部分的路徑符合某種條件的節點.此種方法如在下圖(路徑也包括了節點自身)所示：

適用性：鍵值存儲,文檔數據庫,搜索引擎

11、 嵌套集合(Nested Sets)

在對類似樹型結構進行建模時,嵌套集合是個標準的做法.它在關系數據庫中廣泛被使用,然而它也完全適用于鍵值存儲和文檔數據庫.其設計思想是在用數組來存儲樹的葉子節點(譯者：每個葉子節點對應數組中的一個位置下標),并將每個非葉結點映射為一個葉子節點的范圍,這個范圍就是開始葉子節點和結束葉子節點在數組中的位置下標.如下圖所示：

這個結構對于不變數據來講非常有效,因為它占用的內存小,并且可以在不遍歷樹的情況下得到一個給定節點的所有葉子節點.然而,因為增加一個葉子節點會帶來位置下標的大量更新,所以插入和更新的操作代價是相當的高.

適用性：鍵值存儲,文檔數據庫

(譯者注：適用于字典表、按日期排序的歷史日志數據表等.)

12、 扁平化嵌套文件：字段名稱編號

搜索引擎通常工作在扁平化的文檔之上,即每個文檔由兩個扁平列表組成,這兩個列表分別記錄了字段的名稱和它對應的值.數據建模的目標是將業務實體映射為簡單無結構的文檔,但如果實體內部的結構很復雜,這就難辦了.一個典型的困難就是層次結構模型,比如要將內部嵌套了文檔的文檔映射為簡單無結構的文檔.讓我們來考慮下面的例子：

每一個業務實體是一份某種形式的簡歷,其中包含了這個人的名字,和枚舉了他或她所具有的技能以及相應技能水平的列表.為這樣的實體建模的一個很顯然的方式就是是建立的簡單無結構文檔,里面包含Skill和Level字段的列表.這種模式允許通過技能或水平來搜索某個人,但將這兩個字段聯合起來搜索卻容易導致虛假匹配,正如上圖所述.(譯者：簡單的AND操作不能感知技能以及其水平的對應關系.)

在[4.6]中提出了一種解決這個問題的方法.這項技術的主要思想是將每一項技能以及相應的水平聯合起來組成一個配對(pair),并使用下標標識成為Skill_i和Level_i.在搜索時需要同時查詢所有這些對值(查詢中OR條件語句的個數是和一個人所能具有的技能的最大值相同)：

這種方法實際上沒有可擴展性,因為隨著嵌套結構的數目的增長會迅速增加查詢的復雜度.

適用性：搜索引擎

(譯者注：如果你對于使用索引來加速查詢無計可施,尤其對用戶將來如何查詢數據一無所知,無法在設計模型時進行優化時,這就是最后的稻草：使用全文搜索工具.它至少能在可接受的時間內能查出點東西來^o^.)

13、 扁平化嵌套文件：近似查詢

在[4.6]中還描述了另一種可以解決嵌套文件問題的技術.它的想法是使用近似的查詢,將文檔中單詞之間的距離限制在可以接受的距離范圍以內.在下面的圖中,所有的技能和水平都被索引到了一個叫SkillAndLevel的域.使用“Excellent”和“Poetry”進行查詢表示的話,就會查找到這兩個單詞鄰接的條目：

[4.3]講述了在Solr之上使用這種技術的一個成功案例.

適用性：搜索引擎

(譯者注：同上,但查詢召回率高,會出現假匹配,有臟數據.)

14、 批量圖處理

在瀏覽一個指定節點的相鄰節點或瀏覽兩個或幾個節點之間的關系時,像Neo4j這樣的圖形數據庫的性能出奇的好.然而,通用圖形數據庫對大圖做全局性處理不是很高效,因為擴展性不好.分布式圖形處理可以使用MapReduce或者消息傳遞(Message Passing)模式來實現.我以前的一篇文章就介紹了一種這樣的模式.這種方法使用了鍵值存儲、文檔數據庫和BigTable風格的數據庫,能處理大型的圖形.

作者：CatherinePlans