樹狀結構大數據類型的高效支持

陳世敏

中國科學院計算技術研究所，北京 100190

摘要：傳統的關系數據模型難以滿足大數據應用日益豐富的數據表達和處理的需求，因此實踐中涌現了多種非傳統的大數據類型。其中，以JSON為代表的樹狀結構大數據類型被廣泛應用，具有重要的理論意義和實用價值。系統介紹了樹狀結構大數據類型，并探討如何高效支持樹狀結構大數據的分析運算。

關鍵詞：樹狀結構大數據；JSON；赤兔

論文引用格式：

陳世敏. 樹狀結構大數據類型的高效支持[J]. 大數據, 2018, 4(4): 35-43.

CHEN S?M. Efficient support of tree-structured data types[J]. Big Data Research, 2018, 4(4): 35-43.

1 引言

大數據產業是全球高科技競爭的前沿領域。大數據技術的推廣應用對國家經濟、政治、法治、科技、文化、教育、民生、社會、生態文明、國家安全等方面，都會產生深遠的影響。傳統的關系數據模型從20世紀70年代出現至今，在商用數據處理方面得到了廣泛的應用。但是，關系模型的簡單、扁平的二維表結構無法滿足各行各業（如社交網絡、物聯網、醫療生物、金融等）日益豐富的大數據表達和處理的需求。于是，實踐中涌現了多種非傳統的大數據類型，出現了一批支持非傳統數據類型的大數據系統，被統稱為NoSQL數據庫系統。其中，應用最廣泛的是鍵值對（keyvalue）數據類型、圖（graph）數據類型和以JSON（JavaScript object notation）等為代表的樹狀結構數據類型（tree-structured data type）。

樹狀結構數據類型可直觀地表達高級程序設計語言中類（class）、結構（struct）等豐富的結構，能夠簡潔地支持嵌套、多值和缺值，已被廣泛應用于社交網絡數據服務、Web服務、數據交換格式、分布式系統協議、物聯網等，是一種重要的大數據類型。實踐中常見的樹狀結構數據類型有JSON、Protocol Buffers等。JSON是JavaScript語言標準的一個子集，常常作為數據輸出和數據交換的類型。Protocol Buffers是Google公司推出的一種數據類型，是實現分布式系統內部通信協議的數據格式，也是Google公司的Dremel和BigQuery等大數據系統的數據類型。

本文將對以JSON為代表的樹狀結構大數據類型進行深入介紹，首先舉例說明樹狀結構大數據的含義，然后從多個角度說明樹狀結構大數據的價值和意義，最后結合筆者近期的研究工作，說明樹狀結構大數據類型的處理和支持。

2 樹狀結構大數據類型

樹狀結構大數據類型包括多種新型數據類型，例如JSON、Protocol Buffers、Apache Avro等。這些數據類型的具體表現形式不同，但是它們都可以表達嵌套、多值、缺值等豐富復雜的記錄結構，具有相似的結構特點，可以互相轉化。它們的記錄結構都可以采用語法樹來表達，因此將它們統稱為樹狀結構大數據類型。

以JSON為例，一個JSON類型的數據記錄如下：

{“geo”:{“coordinates”:[-7.1,13.4]},

“retweet_count”:0,

“user”:{“status”:28156,

“favorite”:0,

“followers”:5740,

“id”:32

}

}

JSON用花括號、方括號、引號、冒號、逗號等標點符號來表達記錄的結構。具體而言，花括號表示一個對象，對象的多個屬性以逗號隔開。方括號表示一個數組，數組的多個元素以逗號隔開。一個屬性由屬性名和屬性值組成，兩者由冒號隔開，屬性名以引號標注，屬性值可以是原子的字符串、數值、布爾值等類型，也可以是嵌套的對象或數組。在這個例子中，記錄是一個對象，由3個頂層屬性geo、retweet_count和user組成。geo屬性的屬性值是一個嵌套對象，內部只有一個coordinates屬性，其屬性值是一個數組，數組的每個元素是一個數值；retweet_count屬性的屬性值是一個數值；user屬性的屬性值是一個嵌套對象，包括status、favorite、followers和id 4個屬性，而這4個屬性的屬性值都是數值。

將上述記錄的內部結構表達為一棵樹，如圖1所示。

圖1 對應于JSON記錄實例的語法樹

樹根代表整個記錄。樹中的一個節點對應記錄中的一個屬性，葉子節點對應屬性值為原子類型的屬性，而非葉子節點則對應屬性值是嵌套值的屬性。灰色的節點代表多值，即數組的情況。在這個例子中，最高層的3個屬性geo、retweet_count和user對應根的3個孩子節點。其中，retweet_count的屬性值是原子的數值類型，因此retweet_count節點沒有孩子節點，是一個葉子節點。user的屬性值是一個嵌套對象，由status、favorite、followers和id 4個屬性組成，因此user節點有4個孩子節點。而這4個屬性的屬性值都是原子類型，因此它們都是葉子節點。geo屬性的屬性值是一個嵌套對象，包括一個coordinates屬性，因此geo節點有一個coordinates孩子節點。coordinates屬性的屬性值是一個數組，而數組的每個元素是原子類型，用灰色的coordinates節點表達數組，該節點沒有孩子，是葉子節點。

JSON、Protocol Buffers、Apache Avro等多種樹狀結構數據類型都可以把記錄結構表達為語法樹的形式。可以通過如下遞歸定義更確切地表達樹狀數據類型T_tree：

T_tree= T_object

T_object= {key1:T_value1,…,keyn:T_valuen}

T_array=[T_value,…,T_value]

T_primitive= string | number | boolean| null

T_value= T_primitive| T_object| T_array

一個樹狀數據記錄可以遞歸地表達為一棵樹，T_tree是樹根，樹根必須是T_object，每個T_object由屬性名key和屬性值value組成。除了T_object，還定義了數組T_array和原子類型T_primitive。而value類型則可以遞歸地定義為原子類型、對象類型、數組類型。樹狀結構數據類型可以表達多層復雜的嵌套，每層嵌套表現為樹的一個內部節點，而樹的葉子節點是原子類型。

3 實用價值

與關系數據模型相比，樹狀結構大數據類型的每個記錄具有更加靈活豐富的結構，因此在實踐中得到了廣泛的應用。例如，社交網絡數據服務Twitter等輸出的數據類型就是JSON，Web 2.0 RESTful架構中推薦的數據交換格式是JSON，許多提供公共數據下載的網站可以使用JSON下載數據，Apache Hadoop、HBase等開源大數據系統中分布式通信協議采用了Protocol Buffers來實現。此外，許多物聯網單片機芯片（如Arduino、DragonBoard、BeagleBone等）支持JSON格式的數據輸出。大量的原始數據是樹狀結構數據類型。

樹狀結構大數據類型的3個主要特點使其具有廣泛的實用價值，具體如下。

（1）豐富的結構

樹狀結構大數據類型支持嵌套、多值、缺值等豐富的結構，可以非常方便地表達程序設計語言中“對象”等復雜類型的數據，例如C語言中的struct、C++/Java等語言中的class、Python語言中的dictionary等類型。因此，可以采用樹狀結構大數據類型自然地對應用程序的內存數據結構進行序列化，便于寫入外存和進行網絡通信，并保持原始內存數據結構的特征。與之相比，關系數據模型采用簡單、扁平的記錄結構，記錄的每個屬性都是原子類型，因此對于應用程序數據結構中的嵌套、多值等情況來說，必須采用特殊的編碼，將數據轉換為關系數據模型允許的記錄格式，才可以完成序列化。可見，樹狀結構大數據類型豐富的結構可以更好地支持大數據時代多種多樣的應用。

（2）靈活的類型

JSON類型不需要事先定義記錄的類型就可以直接使用。關系數據庫中先要采用create table建立數據表，才可以加載或插入數據記錄。而在JSON中，數據記錄的結構是在每條記錄中定義的。如第2節中的例子，JSON采用標點符號定義每條記錄的具體結構。因此，JSON允許靈活地增、刪、改記錄結構，允許將多種結構的記錄放入相同的數據集，這可以簡化很多大數據應用領域的數據存儲和管理。例如，在數據采集中，經常遇到同種數據可能有很多小的類別的情況，雖然所有數據都有一些公共屬性，但是不同類別還包括許多各自特殊的屬性。在這種情況下，如果采用關系模型，就需要為每個小類別采用create table建立一個新表，數據存儲和后續的數據處理就需要面對大量的關系表，使整個過程十分繁雜。而采用JSON樹狀結構數據類型，就可以把所有小類別的數據記錄都存儲在一個數據集中，每個記錄允許不同的屬性（實際上是允許許多缺值的屬性）在一個數據集中對所有數據進行統一的管理，大大簡化了數據管理、編程處理的成本。

（3）低廉的成本

XML也可以表達豐富的嵌套、多值結構。實際上，數據庫領域一直希望推動XML成為應用數據存儲和交換的標準。但是，XML的表達引入了很高的成本，包括DTD類型的定義和解析、XML標簽占用的空間等。與之相比，JSON等樹狀結構數據類型更加簡潔輕量。以JSON為例，記錄結構采用簡單的標點符號來表達，便于人的理解和程序的解析，而且這種表達方式引入的空間開銷很小。因此，在實踐中JSON等樹狀結構數據類型已經逐漸取代了XML，成為事實上數據存儲和交換的標準。

4 理論意義

樹狀結構大數據類型不僅具有很強的實用價值，而且具有重要的理論意義，主要表現為以下兩個方面。

（1）關系數據模型的第4次變革

在關系模型出現之后，數據庫研究領域已經認識到了關系模型表達能力的局限性，曾經3次試圖擴展關系數據模型，以支持更加豐富復雜的結構：20世紀80年代后期到20世紀90年代初期的面向對象的數據庫（object oriented database）、20世紀90年代中后期的關系對象式數據庫（object relational database）和21世紀初的XML。這些嘗試取得了一定的學術成果和產業應用，例如關系對象式數據庫被PostgreSQL等系統支持，XML形成了國際標準，但是它們都未竟全功，沒有得到廣泛的接受和使用。樹狀結構大數據類型實際上可以看作關系數據模型的第4次變革。目前，JSON等類型已經被產業界廣泛接受。產業界的推動與學術界的多次嘗試和經驗積累，可能引發質變，使這次新的嘗試有很大的成功概率，產生能夠代替關系數據模型的新數據模型。

（2）一種通用的大數據模型

樹狀數據結構類型可以表達豐富的結構，包括嵌套、多值、缺值等結構。相對于單個鍵值對、單個圖的頂點、單條圖的邊、單個圖的屬性、單條關系型記錄等，單條樹狀結構的數據記錄的結構可以更加豐富復雜。因此，實際上很容易把鍵值對、圖的頂點、邊、屬性和關系型記錄寫成樹狀數據結構類型的數據，而且可能有多種不同的寫法，從而可能以樹狀結構大數據類型為基礎，實現對其他流行的大數據類型的支持。因此，樹狀結構大數據類型是一種通用的大數據模型。

樹狀結構大數據類型具有很強的表達能力，其難點在于如何高效地支持樹狀大數據類型的存儲和運算，以支持其豐富、靈活的結構。

5 現有的樹狀結構數據處理系統

現有的樹狀結構數據處理系統主要有以下3種。

（1）擴展關系型數據庫系統

主流的關系數據庫系統Oracle、Microsoft SQL Server、IBM DB2和開源數據庫系統PostgreSQL等都擴展了對JSON的支持。基本思路是將整個JSON記錄以文本或者二進制格式存放在關系表的單個屬性中，提供內置函數，支持JSON的解析和訪問，從而可以在SQL語句中動態地解析JSON記錄，提取JSON屬性值，并用于SQL查詢[4]，這也是SQL/JSON工作組的基本解決方案。但是，這種解決方案對數據分析的支持較差。數據分析操作通常只關心JSON記錄的少量屬性，存儲和讀取整條JSON記錄會導致大量不必要的I/O訪問。而且，每次執行SQL查詢語句，都要動態地解析JSON記錄，引入很大的性能開銷。

（2）行式樹狀結構數據處理系統

以MongoDB為代表的文檔存儲（document store）系統支持JSON的行式存儲和處理。MongoDB是通過C/C++實現的，采用二進制的BSON格式存儲JSON記錄。對于JSON的屬性名，BSON仍然存儲其字符串；而對于JSON的原子屬性值， BSON采用二進制存儲。MongoDB提供一組JavaScript編程界面，可以執行與SQL查詢功能相當的操作。和擴展關系型數據庫系統相似，由于采用行式存儲，數據分析操作會導致大量的I/O開銷。此外，在訪問JSON嵌套結構時，MongoDB需要在每個嵌套層次進行字符串比較，搜索對應的屬性名，性能代價較大。

（3）列式樹狀結構數據處理系統

Google Dremel提出了Protocol Buffers數據的列式存儲編碼方式。Apache Parquet是Dremel的開源實現，支持Parquet格式的文件存取和訪問。與Apache Hive結合，就可以將數據存放在Parquet列式文件中，并利用Hive實現基于MapReduce的SQL查詢，對大規模的樹狀數據進行分析。由于采用了列式存儲， Parquet可以有效地避免讀取不相關屬性的I/O操作。但其基于MapReduce和Java的實現影響了查詢的效率。

上述3種系統都采用完全通用的設計，為了支持樹狀結構數據類型可能出現的豐富、復雜的嵌套和多值結構，引入了復雜的算法。例如，為了把多個分別存儲的數據列組裝還原成原始記錄，Dremel的組裝算法要建立一個有限狀態自動機，根據自動機和列式文件中的特殊編碼完成組裝。除了上述討論每種系統各自的性能問題外，這種完全通用的解決方案本身也存在相對高昂的代價。

6 樹狀大數據的高效支持：赤兔

筆者設計實現了一個樹狀結構數據管理系統——赤兔（system for tree structured data,Steed）。Steed是采用C/C++語言實現的，支持通用的樹狀結構數據存儲和類似SQL的查詢處理，包括選擇、投影、連接、分組、聚集、排序等多種運算。Steed同時支持行式和列式的樹狀結構數據存儲，以適應不同類型應用的需要。系統能夠自動提取JSON的語法樹，從而有效地壓縮了對屬性名的存儲。圖2展示了Steed的系統結構，主要包括數據解析模塊、數據存儲模塊和查詢執行模塊。數據解析模塊讀取并解析文本的JSON或Protocol Buffers數據，將其轉化為行式或者列式的二進制格式，存儲在數據存儲模塊中。數據存儲模塊存儲行式或列式二進制數據，支持兩種格式數據的相互轉換。查詢執行模塊支持類SQL的查詢，支持行式和列式數據的查詢處理。整個查詢執行采用傳統關系型數據庫中查詢樹的方式實現。

圖2Steed系統結構

（1）簡單路徑及其優化

通過對現實的樹狀結構數據進行分析，提出了一種頻繁子模式——簡單路徑（simple path）。在樹狀結構數據的語法樹中，存在許多從樹根到葉子的路徑。如果在根到葉子的路徑上存在很多的多值（數組）節點，那么其存儲和處理就要考慮很多可能出現的情況，相對復雜。相反，當路徑中不存在多值節點或僅存在一個多值節點時，就有可能進行簡化的處理。這種一條包含最多一個多值節點的從樹根到葉子的路徑就是簡單路徑。筆者分析了現實的樹狀結構數據的結構，發現簡單路徑大量存在。例如，Twitter數據的語法樹中包含203個葉子節點，其中195個葉子節點對應的路徑是簡單的，即96%的路徑是簡單路徑。此外，還分析了Yahoo、IMDB、Sina Weibo等多種表述性狀態傳遞（representational state transfer， REST）服務數據，發現超過99%的路徑是簡單的。其中，Sina Weibo提供104種不同的調用服務，這些服務數據對應的語法樹中67%的路徑不包含多值節點，32%的路徑包含一個多值節點，只有1%的路徑是包含兩個到多個多值節點的復雜路徑。筆者分析了Apache Hadoop中所有449種非空的基于Protocol Buffers的通信協議，發現97%的路徑是簡單路徑。在其他多類現實數據集中，都觀察到相似的現象：絕大多數路徑是簡單路徑。針對簡單路徑， Steed優化了列式存儲、列式組裝和內存行式格式。

（2）MongoDB+Steed

MongoDB是對JSON文件進行存儲和處理的大數據系統。MongoDB是采用C/C++語言實現的，包括Mongod和Mongos兩個主要部分。其中，Mongod負責單機的數據管理和運算，而Mongos在Mongod的基礎上實現了分布式處理，提供了數據劃分、備份、分布式執行等功能。目前， MongoDB以行式BSON記錄作為數據的存儲格式，對大規模數據分析的運算可能引起大量額外的I/O操作。而Steed支持JSON的二進制列式存儲，可以很好地支持大規模的數據分析運算。因此，將Steed作為MongoDB的存儲引擎，就有可能使MongoDB對JSON數據進行列式I/O操作，從而大大提升大數據分析的效率。此外，目前Steed的實現是一個單機的數據庫系統，而MongoDB在分布式處理方面有較強的能力，因此將Steed作為MongoDB的存儲引擎，就可以自然地利用MongoDB的分布式處理能力，形成一個能夠支持多機分布式存儲和運算的樹狀結構大數據系統。MongoDB已經在實踐中得到了廣泛應用，在最流行的數據庫引擎排名中名列第5位。若MongoDB+Steed仍然采用MongoDB的前端界面和編程語言，就有可能更容易地被廣大MongoDB用戶接受，因此筆者將MongoDB的后端WiredTiger存儲引擎替換為Steed，使用列式存儲讀取數據，并轉化為BSON，使用MongoDB現有的內存處理。在具體實現中，需要把上層查詢運算的相關信息發送到下層的Steed存儲引擎。只有這樣，Steed才可能得知有哪些屬性列參與了當前的查詢運算，從而可以采用列式的訪問讀取這些列的相關信息，而不是訪問全部的列，達到減少I/O開銷、提升效率的目的。

（3）性能比較

Steed和現有的樹狀結構數據處理系統PostgresQL、MongoDB、Hive+Parquet的性能對比如圖3所示。Steed Row和Steed Column分別采用行式和列式數據存儲。實驗是在單臺聯想ThinkCentre M8500t工作站上運行的，工作站配有一個3.4 GHz 4核的Intel Core i7-4770處理器、16 GB內存和一個7 200 r/min的SATA硬盤。在Twitter數據上運行多種查詢操作，圖3中從左到右依次是選擇一個屬性（select）、使用1~3個條件過濾數據集（1filter、2filters、3filters）、分組統計（group）、在分組統計的結果上進一步過濾（having）、排序（order）、連接（join）。總體而言，Steed Column性能在所有系統中最優，比Hive+Parquet提高4.1~17.8倍，比MongoDB提高55.9~105.2倍，比PostgreSQL提高33.8~1 294倍。MongoDB+Steed采用了列式存儲，比采用行式存儲的原始MongoDB性能提升16~51倍。把BSON格式改變為Steed的內存結構，節省了對字符串屬性名的比較，采用了更高效的查詢處理實現，Steed Column比MongoDB+Steed性能提升1.8~5.5倍。

圖3Steed和現有樹狀結構數據處理系統的性能對比

7 結束語

傳統的關系數據模型難以滿足大數據應用日益豐富的大數據表達和處理需求，因此實踐中涌現了多種非傳統的大數據類型。其中，以JSON為代表的樹狀結構大數據類型是一種重要的大數據類型。本文從數據模型、實用價值和理論意義等方面介紹了樹狀結構大數據類型，探討了樹狀結構大數據類型的高效處理，設計實現了一個樹狀結構數據管理系統——Steed系統，支持通用的樹狀結構數據存儲和類似SQL的查詢處理。通過分析現實數據，提出一種頻繁子模式——簡單路徑，簡單路徑在實際數據中大量存在。針對簡單路徑，Steed優化了外存存儲、列組裝算法和內存行式結構。與現有系統PostgreSQL、MongoDB、Hive+Parquet相比，Steed對數據分析類的操作普遍有10~1 000倍的性能提升。

《大數據》期刊

《大數據（Big?Data?Research，BDR）》雙月刊是由中華人民共和國工業和信息化部主管，人民郵電出版社主辦，中國計算機學會大數據專家委員會學術指導，北京信通傳媒有限責任公司出版的科技期刊。

關注《大數據》期刊微信公眾號，獲取更多內容

總結

以上是生活随笔為你收集整理的树状结构大数据类型的高效支持的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。