鄒 韜,錢榮濤,毛嘉莉

（華東師范大學(xué) 數(shù)據(jù)科學(xué)與工程學(xué)院,上海 200062）

0 引 言

隨著大數(shù)據(jù)時代的發(fā)展,鋼鐵物流也迎來了數(shù)字化轉(zhuǎn)型,越來越多的網(wǎng)絡(luò)貨運(yùn)平臺應(yīng)運(yùn)而生,由此產(chǎn)生了大規(guī)模的多源物流數(shù)據(jù).這些數(shù)據(jù)作為網(wǎng)絡(luò)貨運(yùn)平臺的基礎(chǔ),為司機(jī)畫像、車貨匹配、車輛調(diào)度以及運(yùn)輸監(jiān)控等關(guān)鍵任務(wù)提供支撐,因此,研究面向物流數(shù)據(jù)的索引與查詢是極為重要的.

然而,使用傳統(tǒng)的關(guān)系型數(shù)據(jù)庫對物流數(shù)據(jù)進(jìn)行管理面臨一系列挑戰(zhàn).首先,貨運(yùn)數(shù)據(jù)類型繁多且來源復(fù)雜.以山東省某鋼鐵集團(tuán)下屬的物流企業(yè)—京創(chuàng)智匯物流科技有限公司 (以下簡稱京創(chuàng))為例,在其研發(fā)的網(wǎng)絡(luò)貨運(yùn)平臺上每天產(chǎn)生的數(shù)據(jù)類型包括購買和銷售場景中的訂單數(shù)據(jù),倉儲場景中的庫存數(shù)據(jù),運(yùn)輸場景中的運(yùn)單數(shù)據(jù)和軌跡數(shù)據(jù)等.然而,京創(chuàng)在使用關(guān)系型數(shù)據(jù)庫管理這些數(shù)據(jù)時,對不同場景中的數(shù)據(jù)存儲在不同表中管理,僅在每列數(shù)據(jù)上構(gòu)建索引,并不能直接滿足物流數(shù)據(jù)復(fù)雜查詢的需求.這體現(xiàn)在: ①對于不同表中數(shù)據(jù)的連接查詢是最常用的查詢類型之一,京創(chuàng)通過多表連接構(gòu)建寬表的方式來完成連接查詢,這導(dǎo)致了大量的冗余查詢與計(jì)算,從而影響查詢性能;② 面對以軌跡數(shù)據(jù)為代表的時空數(shù)據(jù)的快速更新與動態(tài)增長,傳統(tǒng)關(guān)系型數(shù)據(jù)庫由于存儲容量和平臺可擴(kuò)展性的影響,無法很好應(yīng)對海量時空數(shù)據(jù)的存儲與查詢.例如,隨著單表中軌跡數(shù)據(jù)的增長,僅通過B 樹索引會存在大量冗余計(jì)算,使得時空查詢性能隨著數(shù)據(jù)的增多而降低.而選擇各類R 樹進(jìn)行索引則存在頻繁插入導(dǎo)致R 樹分裂,更新索引開銷過大的問題.綜上所述,面向鋼鐵物流數(shù)據(jù),進(jìn)行數(shù)據(jù)融合,并設(shè)計(jì)合理的存儲方式、高效的索引與查詢方案是亟待解決的實(shí)際問題.表1 給出該貨運(yùn)平臺貨運(yùn)物流數(shù)據(jù)量情況,可以發(fā)現(xiàn)軌跡數(shù)據(jù)總量最大、相應(yīng)的增長速度也最大.隨著業(yè)務(wù)的增多和對更高質(zhì)量 (采樣間隔更低) 軌跡的需求,軌跡數(shù)據(jù)的增長速度會大大提高.而京創(chuàng)現(xiàn)行的管理方式無法很好管理這些仍在快速增長的軌跡數(shù)據(jù)。

表1 貨運(yùn)物流數(shù)據(jù)量Tab.1 Volume of freight logistic data

為了解決鋼鐵物流數(shù)據(jù)存儲查詢時面臨的上述挑戰(zhàn),本文將實(shí)時數(shù)據(jù)和歷史數(shù)據(jù)分級存儲,并構(gòu)建相應(yīng)的索引,以期提高物流數(shù)據(jù)的存儲和查詢效率.具體步驟為: 首先,使用Spark 對于多源的物流數(shù)據(jù)進(jìn)行融合;然后,對于海量的歷史物流數(shù)據(jù)與貨運(yùn)平臺實(shí)時采集到的多源數(shù)據(jù)采用分級管理,將實(shí)時采集得到的物流數(shù)據(jù)存儲在內(nèi)存數(shù)據(jù)庫Redis (Remote Dictionary Server) 上,以保證其高效的訪問性能,并將歷史數(shù)據(jù)存儲在基于磁盤的HBase (Hadoop Database) 數(shù)據(jù)庫中;最后,在此基礎(chǔ)上,利用開源索引工具GeoMesa 構(gòu)建時空索引與屬性索引以支持歷史數(shù)據(jù)的高效查詢,同時,在 Redis 上為實(shí)時數(shù)據(jù)構(gòu)建相應(yīng)的索引,并按照設(shè)定的時間周期對數(shù)據(jù)進(jìn)行切片導(dǎo)出,將導(dǎo)出的歷史數(shù)據(jù)保存到HBase 中.

本文的主要結(jié)果如下:

(1) 針對鋼鐵貨運(yùn)平臺所產(chǎn)生的海量多源數(shù)據(jù),利用分布式云存儲和NoSQL 技術(shù),設(shè)計(jì)分級存儲策略,將貨運(yùn)平臺所產(chǎn)生的歷史數(shù)據(jù)與實(shí)時數(shù)據(jù)分開存儲,確保實(shí)時數(shù)據(jù)的高效訪問.

(2) 為滿足物流調(diào)度決策必需的基于跨源數(shù)據(jù)的高頻次關(guān)聯(lián)查詢、分析需求,利用Spark 對車輛所產(chǎn)生的軌跡數(shù)據(jù)、運(yùn)單數(shù)據(jù)、車輛信息數(shù)據(jù)等跨源數(shù)據(jù)進(jìn)行融合,生成具有多屬性的運(yùn)單軌跡數(shù)據(jù).

(3) 為歷史數(shù)據(jù)和實(shí)時數(shù)據(jù)構(gòu)建時空索引和屬性索引,以提升屬性查詢、時空范圍查詢和運(yùn)單軌跡時空范圍查詢的效率.

(4) 在物流企業(yè)提供的真實(shí)數(shù)據(jù)集上進(jìn)行了大量對比實(shí)驗(yàn),驗(yàn)證了本文所提出的存儲方式和構(gòu)建的索引相較于傳統(tǒng)方法有顯著的性能提升.

1 相關(guān)工作

時空數(shù)據(jù)作為物流數(shù)據(jù)中最重要的組成部分,是物流數(shù)據(jù)管理中最為關(guān)鍵的一環(huán),許多物流數(shù)據(jù)管理平臺都為物流中的時空數(shù)據(jù)設(shè)計(jì)特有的管理策略,如京東的城市時空數(shù)據(jù)引擎 (Jd Urban Spatio-temporal Data Engine),菜鳥的STAMP (Spatial-Temporal Analysis and Management Platform)平臺等.因此,對于物流數(shù)據(jù)的管理,要先考慮對于時空數(shù)據(jù)的存儲和索引.現(xiàn)有對于時空數(shù)據(jù)索引和查詢的研究可以分為兩類: 單機(jī)系統(tǒng)和分布式系統(tǒng).

在單機(jī)系統(tǒng)中,許多索引是在R-Tree 基礎(chǔ)上進(jìn)行擴(kuò)展,主要分為兩類.第一類是增加時間維度,構(gòu)建3D R-Tree,例如,STR-Tree (Sort-Tile-Recursive-Tree),TB-Tree (Trajectory-Bundle-Tree),以減少查詢對磁盤的訪問.第二類則是先對時間段進(jìn)行分區(qū),然后在每個時間分區(qū)內(nèi)再構(gòu)建R-Tree 索引.例如,Historical R-Tree,Multi-version 3D R-Trees.然而隨著時空數(shù)據(jù)規(guī)模的不斷增大,各種基于R-Tree結(jié)構(gòu)的索引查詢性能受到單機(jī)計(jì)算資源的限制,導(dǎo)致難以高效查詢出一定時空條件下的時空對象.

在分布式系統(tǒng)中,很多研究[1-8]在這些系統(tǒng)之上構(gòu)建時空索引擴(kuò)展模塊,以支持對時空數(shù)據(jù)的高效查詢.Simba[1]基于Spark SQL 框架進(jìn)行擴(kuò)展,結(jié)合RDD (Resilient Distributed Datasets)結(jié)構(gòu)構(gòu)建了兩層索引機(jī)制: ①為所有分區(qū)構(gòu)建一個全局索引;② 在各個數(shù)據(jù)分區(qū)內(nèi)部構(gòu)建本地索引,以支持范圍查詢和kNN (k-Nearest Neighbor)查詢在內(nèi)的多種查詢.DITA (Distributed In-Memory Trajectory Analytics)[2]利用起止點(diǎn)信息進(jìn)行分區(qū)和構(gòu)建全局索引,根據(jù)軌跡中的關(guān)鍵點(diǎn)構(gòu)建本地索引,以支持高效的相似查詢,并設(shè)計(jì)了負(fù)載均衡策略.Ratel[3]構(gòu)建了兩層索引: ①在全局根據(jù)軌跡的起止點(diǎn)建立R 樹索引;② 在本地為軌跡中間的節(jié)點(diǎn)構(gòu)建網(wǎng)格索引,以支持軌跡的相似查詢和起止點(diǎn)范圍查詢.Dragoon[4]設(shè)計(jì)了一個可變RDD 模型,以混合方式對于歷史軌跡和實(shí)時軌跡流進(jìn)行管理,并設(shè)計(jì)不同的分區(qū)策略以支持ID (IDentity)查詢、范圍查詢和kNN 查詢.這些系統(tǒng)是基于Spark 的數(shù)據(jù)管理系統(tǒng),在處理數(shù)據(jù)時需要將所有數(shù)據(jù)加載到內(nèi)存中,這就要求有大量內(nèi)存的高性能集群,對于平臺而言代價過于高昂.還有許多研究[5-8]基于Hbase 構(gòu)建時空數(shù)據(jù)管理系統(tǒng),如multi-dimensional-HBase[5]在HBase 的基礎(chǔ)上擴(kuò)展了對空間查詢的支持.通過構(gòu)建KD (K-Dimensional)樹和四叉樹索引支持空間范圍查詢和kNN 查詢,GeoMesaa[6]利用GeoHash 將多維空間信息轉(zhuǎn)換為一維字符串,與時間信息交叉編碼生成時空索引,并通過ECQL (Extended Common Query Language)過濾器查詢數(shù)據(jù),以支持時空范圍查詢.ST-Hash[7]在GeoHash 的基礎(chǔ)上提出ST-Hash 編碼方式,在編碼過程中除了空間維度外,還包括時間維度,以支持時空點(diǎn)查詢和時空范圍查詢.JUST[8]在GeoMesa 的基礎(chǔ)上構(gòu)建時空數(shù)據(jù)引擎,增加Z2T、XZ2T 索引和查詢算法以支持更高效的ID 查詢和時空范圍查詢.STEHIX[9]利用Hilbert 填充曲線對空間進(jìn)行劃分和編碼,并對Region 中的數(shù)據(jù)構(gòu)建粒度更細(xì)的空間索引和時間索引.當(dāng)進(jìn)行時空查詢時,首先,利用空間信息定位到具體的Region;然后,分別利用空間索引和時間索引檢索結(jié)果;最后,取二者查詢數(shù)量較小的作為索引結(jié)果返回.

在物流場景中除了時空數(shù)據(jù)外,還有非時空數(shù)據(jù),這類數(shù)據(jù)對于物流場景的應(yīng)用同樣關(guān)鍵,因此,同樣需要對它們構(gòu)建索引,以支持對它們的查詢. GR2-Tree[10]由3D R-Tree 和包含R-Tree 節(jié)點(diǎn)屬性的結(jié)構(gòu)體組成,可以實(shí)現(xiàn)對多屬性的軌跡的查詢,但隨著軌跡點(diǎn)的插入,會引起R-Tree 節(jié)點(diǎn)的分裂,相應(yīng)的屬性結(jié)構(gòu)體也需要更新,維護(hù)索引的開銷較大.JUST 以屬性為主鍵構(gòu)建屬性索引,每構(gòu)建一個屬性索引,就需要復(fù)制一份數(shù)據(jù),隨著屬性類別的增加,索引也相應(yīng)急劇增加,導(dǎo)致大量數(shù)據(jù)冗余.Feng 等[11]通過圖模型對實(shí)體節(jié)點(diǎn)構(gòu)建全局索引,并在內(nèi)存中以對象形式存儲節(jié)點(diǎn)和相關(guān)聯(lián)的屬性數(shù)據(jù),但是由于索引結(jié)構(gòu)依賴于不同數(shù)據(jù)庫系統(tǒng),全局索引與局部索引關(guān)聯(lián)性較弱,存在索引不一致、維護(hù)代價高等問題.

2 整體框架與實(shí)現(xiàn)

2.1 數(shù)據(jù)介紹和整體框架

本文所使用的數(shù)據(jù)主要來自于貨車的軌跡數(shù)據(jù)表、運(yùn)單數(shù)據(jù)表與運(yùn)單司機(jī)表,其中后兩個表中的字段較多,僅列出其中重要的字段.軌跡數(shù)據(jù)表由12 個字段組成包括: 車牌號,采樣時間,經(jīng)度,緯度,速度,方向,地址,省份,市,縣,查詢時間和插入時間,軌跡數(shù)據(jù)包括39 142 000 個GPS (Global Positioning System)軌跡點(diǎn),共526 359 條軌跡.而運(yùn)單表則有130 個字段組成,是一張寬表,主要包括3 部分的信息: 運(yùn)單相關(guān)信息,如運(yùn)單號、運(yùn)單狀態(tài)、發(fā)貨與收貨公司標(biāo)識符、返單時間、返單地址等;貨物相關(guān)信息,如貨物類型、重量等;運(yùn)載相關(guān)信息,如起止點(diǎn)標(biāo)識符、運(yùn)送貨車的車牌號等.運(yùn)單數(shù)據(jù)表包括2 157 000 條運(yùn)單數(shù)據(jù),表中的許多數(shù)據(jù)都是缺失的,是典型的稀疏數(shù)據(jù).運(yùn)單司機(jī)表包括18 個字段,運(yùn)單司機(jī)表是以運(yùn)單為單位呈現(xiàn)司機(jī)的信息,包括運(yùn)單號、公司標(biāo)識符、司機(jī)姓名、電話、車牌號等字段,運(yùn)單司機(jī)表包括2 251 814 條數(shù)據(jù).

京創(chuàng)所使用的關(guān)系型數(shù)據(jù)庫存儲運(yùn)單表與運(yùn)單司機(jī)表這樣的稀疏數(shù)據(jù)存在的問題有: 數(shù)據(jù)冗余,浪費(fèi)大量存儲空間,并且查詢性能較差.當(dāng)按行存儲時,即使該位為空,也需要占用空間.當(dāng)查詢時,并不需要讀出所有表中的所有屬性,但是關(guān)系數(shù)據(jù)庫會對記錄按順序逐條訪問,這導(dǎo)致了較長的查詢延遲.

針對以上問題,選取HBase 來存儲數(shù)據(jù).一方面,HBase 作為面向列存儲的分布式數(shù)據(jù)庫,適合用來存儲海量的軌跡數(shù)據(jù)和稀疏的運(yùn)單數(shù)據(jù),因?yàn)槭敲嫦蛄写鎯?空列并不占用空間,可以有效節(jié)省存儲空間,在查詢時僅遍歷需要的列,也可以大大節(jié)省查詢時間.另一方面,因?yàn)?參考京東與阿里在存儲海量物流數(shù)據(jù)時,也是在HBase 上進(jìn)行擴(kuò)展的,相關(guān)資料比較多,所以,本文選取HBase 來存儲海量的歷史物流數(shù)據(jù).京創(chuàng)希望冷熱數(shù)據(jù)能夠分開存儲,以滿足場景中對于實(shí)時數(shù)據(jù)的查詢要求.Redis 作為一個高性能的內(nèi)存數(shù)據(jù)庫,是用來緩存熱點(diǎn)數(shù)據(jù)的最佳選擇之一,本文使用Redis 緩存實(shí)時數(shù)據(jù).

論文整體框架如圖1 所示,首先,對多源物流數(shù)據(jù)進(jìn)行分類,分為時空數(shù)據(jù)和非時空數(shù)據(jù),并按照場景中數(shù)據(jù)之間的關(guān)聯(lián),將二者融合關(guān)聯(lián)起來.然后,將歷史數(shù)據(jù)存儲在HBase 里并構(gòu)建屬性索引、Z2 索引、XZ2 索引,將實(shí)時數(shù)據(jù)存儲在Redis 里并構(gòu)建屬性索引和時空網(wǎng)格索引.最后,分別在HBase 與 Redis 上實(shí)現(xiàn)屬性查詢、時空范圍查詢和運(yùn)單軌跡的時空范圍查詢.

圖1 整體框架Fig.1 Overall architecture

2.2 數(shù)據(jù)融合

在鋼鐵貨運(yùn)的運(yùn)力預(yù)測、運(yùn)力調(diào)度與車貨匹配等應(yīng)用中,所需的數(shù)據(jù)除了車輛的軌跡數(shù)據(jù)外,還包括該車輛的信息、運(yùn)送的貨物類型等數(shù)據(jù),因此,查詢就涉及對運(yùn)單、車輛以及軌跡等跨源數(shù)據(jù)的關(guān)聯(lián).如果不預(yù)先對數(shù)據(jù)進(jìn)行融合,在完成相關(guān)查詢與分析時,需要通過連接多表查詢獲得結(jié)果,這樣會耗費(fèi)大量的時間.鑒于此,本文以貨車的軌跡數(shù)據(jù)為中心,將其與不同來源的物流數(shù)據(jù)進(jìn)行融合,并將融合后的中間結(jié)果保存在HDFS (Hadoop Distributed File System)文件中,這樣既可以將其作為物流數(shù)據(jù)挖掘的輸入數(shù)據(jù),又便于后續(xù)數(shù)據(jù)的寫入和索引構(gòu)建.

數(shù)據(jù)融合旨在將預(yù)處理過后的軌跡數(shù)據(jù)與網(wǎng)絡(luò)貨運(yùn)平臺的物流運(yùn)營數(shù)據(jù)按照應(yīng)用需求進(jìn)行融合,產(chǎn)生多屬性的運(yùn)單軌跡.運(yùn)單軌跡是由帶有時間戳的位置序列和表征車輛、貨物信息的屬性組成.以軌跡數(shù)據(jù)和運(yùn)單數(shù)據(jù)融合,生成帶有運(yùn)單號和貨物類型的運(yùn)單軌跡為例.具體步驟為: ①讀取軌跡數(shù)據(jù),將相同車牌的軌跡點(diǎn)放在一個列表里,并按照采樣時間對其進(jìn)行排序.如果兩個鄰接的軌跡點(diǎn)采樣時間間隔超過設(shè)定閾值 (如1 h),將軌跡進(jìn)行分段.② 根據(jù)車牌號將運(yùn)單號和軌跡段進(jìn)行匹配,將同一輛貨車的軌跡按運(yùn)單號進(jìn)行拆分,根據(jù)軌跡段中第一個軌跡點(diǎn)的采樣時間將其與裝載時間最近的運(yùn)單進(jìn)行匹配.③獲得的運(yùn)單軌跡形式為“車牌號+運(yùn)單號+貨物類型+軌跡點(diǎn)列表”,采用這種存儲方式可以有效減小軌跡數(shù)據(jù)存儲所占的空間,其中每一行是一條與運(yùn)單匹配的軌跡,具體示例如圖2 所示.

圖2 數(shù)據(jù)融合舉例Fig.2 Example of data fusion

2.3 數(shù)據(jù)的存儲和索引

對于運(yùn)單軌跡數(shù)據(jù)的存儲和索引,主要分為兩部分: 一部分是對于歷史數(shù)據(jù)的處理,另一部分是對于實(shí)時數(shù)據(jù)的處理.

2.3.1 歷史數(shù)據(jù)的存儲和索引

對于歷史數(shù)據(jù),考慮到其巨大的數(shù)據(jù)量以及需要進(jìn)行頻繁的插入,選取分布式NoSQL 數(shù)據(jù)庫HBase 來進(jìn)行存儲,因?yàn)镠Base 擴(kuò)展簡單、讀寫速度大且存儲成本低.HBase 中的數(shù)據(jù)以鍵值 (keyvalue) 的形式進(jìn)行存儲,其中key 由行鍵、列族、列和時間戳組成,當(dāng)想要獲得相應(yīng)數(shù)據(jù)時,需要通過key 獲得相應(yīng)的value.

對于索引,則使用GeoMesa 來進(jìn)行構(gòu)建.GeoMesa 共支持6 種索引,分別是ID 索引、屬性索引、Z2 索引、Z3 索引、XZ2 索引和XZ3 索引.其中,ID 索引和屬性索引屬于普通屬性索引,主要用于查詢非時空屬性.Z2、Z3、XZ2、XZ3 屬于時空索引,用于查詢時空屬性,其中,Z2 和Z3 索引用于索引點(diǎn)類型的數(shù)據(jù),Z2 索引針對包含經(jīng)緯度的二維點(diǎn)類型數(shù)據(jù),Z3 索引針對包含經(jīng)緯度和時間的三維點(diǎn)類型數(shù)據(jù).XZ2 和XZ3 索引則是在Z2、Z3 索引基礎(chǔ)上進(jìn)行擴(kuò)展,用于索引線或者面等類型的數(shù)據(jù).

GeoMesa 中時空索引的原理是,利用GeoHash 編碼系統(tǒng)將二維的地理位置編碼為由字母和數(shù)字組成的一維字符串,然后用這個一維的字符串對時空數(shù)據(jù)進(jìn)行索引.GeoHash 屬于二維Z 階填充曲線的實(shí)際應(yīng)用,編碼過程如下: ①轉(zhuǎn)換經(jīng)緯度,將地球緯度區(qū)間[–90°,90°]和經(jīng)度區(qū)間[–180°,180°]不斷進(jìn)行左右劃分,如果給定坐標(biāo)屬于二分的右區(qū)間范圍,則標(biāo)記一個1,否則標(biāo)記一個0,針對不同的編碼層級,分別得到經(jīng)度和緯度的二進(jìn)制編碼;② 將經(jīng)度依次放在偶數(shù)位上,將緯度依次放在奇數(shù)位上組成一維的二進(jìn)制編碼;③利用Base32 編碼技術(shù)將二進(jìn)制編碼轉(zhuǎn)換為由數(shù)字和字母組成的字符串.對于三維數(shù)據(jù),則是在GeoHash 的基礎(chǔ)上針對時間緯度進(jìn)行擴(kuò)展,生成時空索引.

存儲數(shù)據(jù)的存儲類型選擇經(jīng)緯度組成的坐標(biāo)點(diǎn)類型,將ID 設(shè)置為車牌號加采樣時間組成的字符串,對貨物類型和運(yùn)單號這兩個屬性構(gòu)建屬性索引,用于支持對這兩者的屬性查詢,并構(gòu)建Z2 索引和Z3 索引,用于支持對點(diǎn)數(shù)據(jù)的時空查詢.

基于GeoMesa 的Java 接口開發(fā)了將貨運(yùn)物流數(shù)據(jù)導(dǎo)入HBase 數(shù)據(jù)庫的程序,程序的主要步驟為: ①根據(jù)HBase 的配置信息,構(gòu)建連接,創(chuàng)建存儲對象;② 根據(jù)貨車軌跡數(shù)據(jù)的屬性創(chuàng)建相應(yīng)的屬性名和類型,并創(chuàng)建相應(yīng)的表結(jié)構(gòu);③根據(jù)實(shí)際需求設(shè)置索引的屬性;④ 將數(shù)據(jù)轉(zhuǎn)換成已定義的結(jié)構(gòu)類型,然后寫入數(shù)據(jù)庫.

2.3.2 實(shí)時數(shù)據(jù)的存儲和索引

在貨運(yùn)物流場景中,實(shí)時數(shù)據(jù)作為最近產(chǎn)生的數(shù)據(jù),具有極高的時效價值,經(jīng)常被運(yùn)用到各種實(shí)時場景分析中,屬于熱點(diǎn)數(shù)據(jù).Redis 是一個開源的內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)存儲系統(tǒng),在內(nèi)存中存取數(shù)據(jù)比磁盤讀取效率高,并且支持多種類型的數(shù)據(jù)結(jié)構(gòu),更符合實(shí)時數(shù)據(jù)的存儲和查詢要求.并且Redis 可以設(shè)置key 的過期時間,便于淘汰隨時間推移的過時數(shù)據(jù).對于實(shí)時產(chǎn)生的流數(shù)據(jù),將其存儲在Redis 中,并構(gòu)建相應(yīng)的網(wǎng)格索引和屬性索引,以支持各種實(shí)時查詢.

實(shí)時的運(yùn)單軌跡數(shù)據(jù)由車牌號、經(jīng)緯度、采樣時間和其他屬性如貨物類型、訂單號等組成.在Redis 中,采用集合來存儲運(yùn)單軌跡,集合的key 為車牌號加時間段,value 為該時間段內(nèi)這輛貨車的所有運(yùn)單軌跡點(diǎn),具體處理步驟為: ①時間段劃分與歸并.這里設(shè)置時間段長度為1 h,在實(shí)際使用中可以根據(jù)場景對數(shù)據(jù)時間范圍的不同要求,更改時間段的長短.將1 h 內(nèi)接收到的數(shù)據(jù)歸入同一個時間段,使同一輛貨車在同一時段內(nèi)具有相同的key.例如,對于時刻2021-05-19 7:35:58,按照1 h 間隔,將其歸入2021-05-19 7:00:00,轉(zhuǎn)換成時間戳為1621378800,將歸并后的時間戳作為key 的組成部分.② key 的組成.用時間段轉(zhuǎn)成的時間戳以及車牌號組合成key,例如,歸并后時間戳為1621378800,車牌號為蘇H5435Z,則key 為蘇H5435ZT1621378800,增加的T 表示時間段前綴.③value 的組成.用Redis 中特有的數(shù)據(jù)結(jié)構(gòu),即有序集合,來存儲運(yùn)單軌跡數(shù)據(jù),集合中存入的是每條運(yùn)單軌跡數(shù)據(jù)的時間戳、經(jīng)緯度坐標(biāo)及其他屬性,如貨物類型、運(yùn)單號等.在有序集合中用軌跡點(diǎn)采樣時間的時間戳作為分?jǐn)?shù)值 (Redis 中用于對數(shù)據(jù)進(jìn)行排序),value 為經(jīng)緯度、時間、貨物類型、運(yùn)單號等信息拼接而成的字符串.

為了提高運(yùn)單軌跡的查詢效率,需要構(gòu)建索引,因此,設(shè)計(jì)了網(wǎng)格索引和屬性索引,以支持運(yùn)單軌跡的查詢.

關(guān)于實(shí)時數(shù)據(jù)的時空索引構(gòu)建,本文采用網(wǎng)格索引,主要是因?yàn)閿?shù)據(jù)需要實(shí)時更新,所以要求索引能夠在數(shù)據(jù)增刪時進(jìn)行更新.網(wǎng)格索引在每次更新時只需要修改某一網(wǎng)格范圍內(nèi)的軌跡點(diǎn)數(shù)據(jù),開銷較小.Redis 作為key-value 的數(shù)據(jù)庫,通過網(wǎng)格編碼將二維經(jīng)緯度數(shù)據(jù)映射為一維數(shù)據(jù),再加上歸并的時間段,實(shí)現(xiàn)起來較為簡單,無須額外的存儲結(jié)構(gòu).索引的具體構(gòu)建步驟為: ①網(wǎng)格劃分.貨運(yùn)物流軌跡數(shù)據(jù)分布在我國的各個省份,需要查詢的數(shù)據(jù)范圍覆蓋我國大部分省份.本文把經(jīng)度范圍設(shè)置為73°E～ 135°E,緯度范圍為3°N～ 53°N.這里綜合考慮設(shè)置網(wǎng)格索引粒度為0.1°,采用經(jīng)度、緯度對網(wǎng)格編碼,以每個網(wǎng)格中最小經(jīng)緯度坐標(biāo)編碼,橫坐標(biāo)表示東經(jīng) (用E 表示),縱坐標(biāo)表示北緯 (用N 表示) .例如,坐標(biāo) (119.329 711°,35.174 452°) 所在網(wǎng)格的網(wǎng)格號表示為E119.3N35.1.② key 的組成.索引key 值中的時間段也按照1h 間隔劃分,則key 由網(wǎng)格編號加時間段轉(zhuǎn)換后的時間戳.例如,對于2021-05-19 7:35:58,經(jīng)緯度坐標(biāo)為 (119.329 711°,35.174 452°) 的軌跡點(diǎn),將其歸入2021-05-19 7:00:00,轉(zhuǎn)換成時間戳為1621378800,所在網(wǎng)格號為E119.3N35.1,所以key 為E119.3N15.1 T1621378800.③value 的組成.value 是一個有序集合,集合內(nèi)存入的是所對應(yīng)網(wǎng)格在該時間段內(nèi)所有軌跡點(diǎn)的車牌號,每個車牌號所對應(yīng)的分?jǐn)?shù)值為每條軌跡數(shù)據(jù)的采樣時間.例如,車牌號為蘇H5435Z 的軌跡點(diǎn)所對應(yīng)的分?jǐn)?shù)值為2021-05-19 7:35:58,轉(zhuǎn)換成的時間戳1621380958,value 為蘇H5435Z.

屬性索引同樣需要考慮索引更新問題,所以對于屬性索引也加上其所屬的時間段,便于當(dāng)其所對應(yīng)軌跡點(diǎn)過期時,同時刪除所對應(yīng)的屬性索引.具體步驟為: ①時間段劃分與歸并.與存儲模塊中一樣,將1 h 內(nèi)的接收到的數(shù)據(jù)歸入同一個時間段,使同一屬性在同一時段內(nèi)具有相同的key.② key 的組成.屬性索引的key 主要由屬性值和時間段轉(zhuǎn)成的時間戳組成,例如,對貨物類型構(gòu)建屬性索引,假設(shè)貨物類型為熱軋卷板,歸并后時間戳為1621378800,則key 為熱軋卷板T1621378800.③value 的組成.本文使用無序集合來存儲屬性索引的value,集合中存入的是該時間段屬性為key 中所對應(yīng)屬性值的車牌號.例如,key 為熱軋卷板T1621378800,所對應(yīng)的value 為2021-05-19 7:00:00—8:00:00 內(nèi)所有運(yùn)送貨物類型為熱軋卷板的車牌號集合.

2.4 數(shù)據(jù)的查詢

2.4.1 查詢需求分析和定義

在貨運(yùn)物流信息平臺的實(shí)際應(yīng)用中,經(jīng)常需要通過查詢得到所需的數(shù)據(jù)結(jié)果以進(jìn)行分析.在鋼鐵貨運(yùn)場景中,常用的查詢包含屬性查詢、時空范圍查詢和運(yùn)單軌跡時空范圍查詢.例如,當(dāng)查詢某輛貨車執(zhí)行某個運(yùn)單的軌跡時,需要實(shí)現(xiàn)屬性查詢;當(dāng)查詢指定時段 (如15:00:00—17:00:00) 返回鋼廠的貨車信息時,需使用時空范圍查詢;當(dāng)查詢特定范圍內(nèi)運(yùn)力數(shù)時,涉及時空范圍與貨物類型,需要執(zhí)行運(yùn)單軌跡的時空范圍查詢.

定義1(軌跡點(diǎn)p) 軌跡點(diǎn)是通過定位設(shè)備采集到的貨車的位置信息,表示為p=(pid,plat,plon,pt),其中pid表示軌跡點(diǎn)編號,plat表示緯度,plon表示經(jīng)度,pt表示采集時間.

定義2(軌跡T) 軌跡T可以表示為一個由軌跡點(diǎn){p0,p1,···,pn}構(gòu)成的序列,描述貨車在一定時間范圍內(nèi)的位置變化.

定義3(運(yùn)單軌跡O) 運(yùn)單軌跡由貨車執(zhí)行運(yùn)輸任務(wù)時被分派的運(yùn)單屬性以及貨車軌跡組成,可以表示為O=(Oatt,Ot) ,其中Oatt=(Owb,Oti,Ogt)表示運(yùn)單屬性集合,Owb表示運(yùn)單編號,Oti表示車牌號,Ogt表示運(yùn)送貨物類型,Ot表示貨車軌跡.

定義4(運(yùn)單軌跡數(shù)據(jù)集So) 運(yùn)單軌跡數(shù)據(jù)集So={O1,O2,···,O|So|}是一定時空范圍內(nèi)運(yùn)單軌跡的集合,其中|So|表示集合的元素個數(shù).

定義5(屬性查詢) 給定運(yùn)單軌跡數(shù)據(jù)集So和軌跡屬性值Qa,返回軌跡集合Sa,其中Sa由所有滿足查詢軌跡屬性值Qa的軌跡組成.

定義6(時空范圍查詢) 給定運(yùn)單軌跡數(shù)據(jù)集So和時空范圍Qr,返回軌跡集合Sr,其中Sr由所有存在軌跡點(diǎn)在查詢范圍Qr內(nèi)的軌跡組成.

定義7(運(yùn)單軌跡的時空范圍查詢) 給定運(yùn)單軌跡數(shù)據(jù)集So、軌跡屬性值Qa和時空范圍Qr,返回軌跡集合Qar,其中Qar包含所有存在軌跡點(diǎn)在查詢范圍內(nèi)且屬性滿足Qa的軌跡組成.

因?yàn)閷?shí)時數(shù)據(jù)和歷史數(shù)據(jù)分別存儲在Redis 和HBase 里,并構(gòu)建了相應(yīng)的索引,所以將從歷史數(shù)據(jù)和實(shí)時數(shù)據(jù)這兩個方面介紹.

2.4.2 歷史數(shù)據(jù)的查詢

歷史數(shù)據(jù)存儲在HBase 里,并通過GeoMesa 構(gòu)建了屬性索引、Z2 索引、Z3 索引等.對于歷史數(shù)據(jù)的查詢也是通過GeoMesa 這個中間件來實(shí)現(xiàn)的.GeoMesa 提供了一套統(tǒng)一的GeoTools Query 查詢接口,這個接口采用基于CQL (Common Query Language)的條件查詢,支持各種空間關(guān)系謂詞和時間關(guān)系謂詞.

使用GeoTools 進(jìn)行查詢的基本流程如下.

(1)根據(jù)查詢條件編寫ECQL 下面給出每種類型查詢的例子.

①屬性查詢.定義查詢的CQL 為String attribute=“truck_no=蘇H5435Z”,如果需要查詢滿足多個屬性要求,可以用關(guān)鍵字“AND”將多個條件連接起來,在查詢語句中關(guān)鍵字為大寫.

② 時空范圍查詢.定義查詢語句“String range=“BBOX(geom,119.37,35.17,119.38,35.30)AND dtg DURING 2021-05-21T00:00:00.000Z/2021-05-22T00:00:00.000Z””,其中關(guān)鍵字“BBOX”用于限制空間范圍,“DURING”用于限制時間范圍,“AND”用于連接不同的查詢條件.

③運(yùn)單軌跡的時空范圍查詢.對于歷史數(shù)據(jù)的運(yùn)單軌跡時空范圍查詢,給出查詢的時空范圍和相應(yīng)的屬性值限制,使用關(guān)鍵字“AND”進(jìn)行連接.例如,定義CQL 語句 String capacity=“goodDes=‘熱軋卷板’ AND BBOX(geom,119.37,35.17,119.38,35.30) AND dtg DURING 2021-05-21T00:00:00.000Z/2021-05-22T00:00:00.000Z”.

(2)獲取待查詢表的表名與表結(jié)構(gòu).

(3)用CQL 創(chuàng)建Filter 類型的對象.

(4)創(chuàng)建查詢對象,將(2)與(3)中獲取的表結(jié)構(gòu)、表名和Filter 對象作為查詢對象.

(5)構(gòu)建GeoMesa 連接,創(chuàng)建存儲對象.

(6)使用存儲對象獲取數(shù)據(jù)讀取器,將查詢對象傳給數(shù)據(jù)讀取器執(zhí)行查詢,查詢結(jié)果通過讀取器獲取.

GeoMesa 在執(zhí)行查詢計(jì)劃時,重寫CQL 以進(jìn)行快速評估并優(yōu)化,再根據(jù)可用索引對過濾條件進(jìn)行拆分,由索引選擇決定主過濾器和輔助過濾器.例如,對于運(yùn)單軌跡的時空范圍查詢,GeoMesa 分解出兩種索引方案.

(1) Z3 索引+屬性Filter 索引.

Z3 索引 (主過濾器): BBOX(geom,119.37,35.17,119.38,35.30) AND dtg DURING 2021-05-21T00:00:00.000Z/2021-05-22T00:00:00.000Z.

屬性Filter 索引 (輔助過濾器): goodDes=‘熱軋卷板’.

(2) Z2 索引+時間和屬性Fliter 索引.

Z2 索引 (主過濾器): BBOX(geom,119.37,35.17,119.38,35.30).

時間和屬性Flite 索引 (輔助過濾器): dtg DURING 2021-05-21T00:00:00.000Z/2021-05-22T00:00:00.000Z AND goodDes=‘熱軋卷板’.

GeoMesa 會對以上兩種索引組合進(jìn)行比較,并選擇更優(yōu)的組合.

2.4.3 實(shí)時數(shù)據(jù)的查詢

實(shí)時數(shù)據(jù)存儲在Redis 里,對于實(shí)時數(shù)據(jù)的查詢主要通過構(gòu)建相應(yīng)索引表,加速查詢的過程.

(1) 屬性查詢.當(dāng)對軌跡數(shù)據(jù)進(jìn)行存儲時,key 用的是貨車車牌號,對于車牌號的屬性查詢,可以使用Redis 中有序集合的Zrange 命令獲得指定車牌號的軌跡.對于其他屬性的屬性查詢,則需要先通過該屬性的索引,以得到滿足該屬性條件的車牌號,再根據(jù)車牌號查詢得到軌跡數(shù)據(jù).當(dāng)查詢滿足多個屬性要求的軌跡時,首先,需要根據(jù)屬性索引得到滿足每個屬性的車牌號;然后,對這些車牌號的集合求并集;最后,根據(jù)并集中的車牌號查詢其軌跡數(shù)據(jù).

(2) 時空范圍查詢.對于時空范圍查詢,首先,需要根據(jù)給定的時間范圍,計(jì)算得到與其相交時間段的候選時間戳;其次,根據(jù)給定查詢的空間范圍,獲得與其相交的候選的網(wǎng)格集合,最終的查詢結(jié)果在候選的網(wǎng)格集合中;再次,將候選時間戳和候選網(wǎng)格集合兩兩組合得到候選時空網(wǎng)格集合,取出候選時空網(wǎng)格中的軌跡點(diǎn);最后,篩選出滿足時空范圍條件的軌跡點(diǎn)集合,并返回結(jié)果.

(3) 運(yùn)單軌跡的時空范圍查詢.首先,計(jì)算與查詢的時空范圍相交的網(wǎng)格和時段,將網(wǎng)格與時段逐一組合成候選 key 集合,并篩選出候選 key 集合中滿足時空范圍要求的車牌號集合;然后,計(jì)算符合屬性要求的車牌號集合;最后,對這兩個車牌號集合求交集,根據(jù)交集中的車牌號查詢最終結(jié)果并返回.具體流程如圖3 所示.

圖3 運(yùn)單軌跡時空范圍查詢流程Fig.3 Process of spatio-temporal range query on attribute trajectory

3 實(shí) 驗(yàn)

本文在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),對查詢的性能進(jìn)行評估.本文所使用的數(shù)據(jù)集來自山東省某鋼鐵物流企業(yè)運(yùn)營的網(wǎng)絡(luò)貨運(yùn)平臺的真實(shí)數(shù)據(jù)集,包含從2021 年05 月01 日至2022 年02 月28 日共10 個月的運(yùn)單及其軌跡數(shù)據(jù).其中,軌跡數(shù)據(jù)包含39 142 000 個GPS 軌跡點(diǎn),共526 359 條軌跡;運(yùn)單數(shù)據(jù)有2 157 000 條.實(shí)驗(yàn)所使用的集群共有3 個節(jié)點(diǎn),每個節(jié)點(diǎn)配備Centos7.4、4 核中央處理器、16 G 內(nèi)存、200 G 磁盤,選擇PostgreSQL 數(shù)據(jù)庫作為對比數(shù)據(jù)庫,版本是13.3.PostgreSQL 是一個對象關(guān)系型數(shù)據(jù)庫,通過安裝PostGIS 插件擴(kuò)展了PostgreSQL 對空間數(shù)據(jù)的支持.將軌跡數(shù)據(jù)和運(yùn)單屬性存入PostgreSQL 中,并對其中的經(jīng)度、緯度、時間戳構(gòu)建索引,實(shí)驗(yàn)中對比了PostgreSQL 與本文所提出方案的存儲性能和查詢性能.

3.1 存儲性能

存儲性能的評價指標(biāo)主要分為兩部分: 一部分是存儲軌跡數(shù)據(jù)和運(yùn)單數(shù)據(jù)所需的磁盤空間;另一部分是將數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫所需時間.

圖4 展示的是數(shù)據(jù)融合前后數(shù)據(jù)存儲磁盤所需要的空間大小,將全部軌跡數(shù)據(jù)分為5 等份,分別測試占全部數(shù)據(jù)20%、40%、60%、80%與100%數(shù)據(jù)量的存儲空間.在融合前,原始數(shù)據(jù)一條記錄存儲一個軌跡點(diǎn),融合后一條記錄存儲一條軌跡.從圖4 中可以看出,隨著數(shù)據(jù)規(guī)模的增大,數(shù)據(jù)融合前后占用磁盤空間大小差異更加明顯,和融合前相比,融合后的數(shù)據(jù)存儲所占用的空間更小.說明經(jīng)過數(shù)據(jù)融合可以顯著減小軌跡的存儲空間.

圖4 存儲空間Fig.4 Data size

將本文所提出的物流數(shù)據(jù)管理系統(tǒng)與PostgreSQL 的數(shù)據(jù)存儲時間進(jìn)行對比,結(jié)果如圖5 所示,可以看出,本文所提出的數(shù)據(jù)管理系統(tǒng)存儲數(shù)據(jù)耗時更短,在批量插入數(shù)據(jù)時更有優(yōu)勢.究其原因,是本文使用的HBase 數(shù)據(jù)庫底層是基于分布式文件系統(tǒng)HDFS,能夠?qū)崿F(xiàn)對海量數(shù)據(jù)存儲的秒級響應(yīng),在軌跡這類超大規(guī)模的數(shù)據(jù)處理中非常高效.PostgreSQL 這一傳統(tǒng)的關(guān)系型數(shù)據(jù)庫,本身不支持并行插入數(shù)據(jù),而且PostgreSQL 內(nèi)部所使用的是R-Tree 索引,隨著數(shù)據(jù)的不斷插入,R-Tree 索引頻繁更新,導(dǎo)致存儲性能不高.本文所提出的系統(tǒng)使用網(wǎng)格索引并且按照鍵值對的形式存儲管理數(shù)據(jù),所以存儲效率較高,適合物流管理領(lǐng)域?qū)Υ罅寇壽E等數(shù)據(jù)進(jìn)行存儲.

圖5 寫入耗時Fig.5 Writing time

3.2 查詢性能

(1) 屬性查詢.使用貨車的車牌號和運(yùn)送的貨物類型作為查詢條件,測試屬性查詢的性能,結(jié)果如圖6 所示.可以看出,在數(shù)據(jù)量較少時,PostgreSQL 查詢耗時更短,因?yàn)?本文所提出的方案使用GeoMesa 進(jìn)行查詢,在執(zhí)行查詢計(jì)劃時,都需要解析 CQL,并計(jì)算不同索引的查詢性能,無論數(shù)據(jù)規(guī)模的大小,這一過程都需要耗費(fèi)一定的時間,所以,在數(shù)據(jù)較少時優(yōu)勢并不明顯.但是隨著數(shù)據(jù)量的增加,PostgreSQL 的查詢耗時急劇增長,而本文所提出的系統(tǒng)中使用HBase 的查詢耗時增長則比較平緩,當(dāng)數(shù)據(jù)量達(dá)到千萬級別時,本文所提出的方案遠(yuǎn)優(yōu)于對比方案.反映了本文所提出的物流數(shù)據(jù)管理系統(tǒng)查詢性能的高效率.

圖6 屬性查詢性能Fig.6 Performance of attribute query

(2) 時空范圍查詢.在全部數(shù)據(jù)上分別測試了不同時間范圍和不同空間范圍下的查詢耗時.在空間范圍查詢實(shí)驗(yàn)中,分別選取5 km × 5 km、10 km × 10 km、15 km × 15 km、20 km × 20 km、25 km × 25 km 共5 個不同矩形空間范圍作為查詢條件,同時保持其在相同的時間范圍,在本文所提出的系統(tǒng)和PostgreSQL 上分別進(jìn)行實(shí)驗(yàn).在時間范圍查詢實(shí)驗(yàn)中,分別選取1 h、1 d、7 d、30 d 共4 種不同的時間范圍,并控制空間范圍相同進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖7 所示.

圖7 時空范圍查詢性能Fig.7 Performance of spatio-temporal range query

從圖7(a)中可以發(fā)現(xiàn),無論是本文所提出的系統(tǒng),還是PostgreSQL,整體上,查詢耗時和查詢的空間范圍關(guān)系不大,因?yàn)?在真實(shí)的物流場景中,數(shù)據(jù)分布是不均勻的,增大時空范圍不能保證查詢到更多的結(jié)果,所以,查詢時間受空間范圍的影響較小.另外,可以看出,本文所提出的系統(tǒng)的查詢耗時遠(yuǎn)短于PostgreSQL 的查詢耗時,后者的查詢耗時大概是前者的6 倍.圖7(b)的時間范圍查詢實(shí)驗(yàn)結(jié)果與圖7(a)類似,與PostgreSQL 相比,本文所提出的系統(tǒng)的查詢性能更優(yōu).

(3) 運(yùn)單軌跡的時空范圍查詢.分別進(jìn)行時間范圍查詢和空間范圍查詢的實(shí)驗(yàn),對于同樣的屬性條件,選取不同空間范圍測試查詢耗時,實(shí)驗(yàn)結(jié)果如圖8 所示.從圖8(a)中可以發(fā)現(xiàn),隨著空間范圍的增大,PostgreSQL 查詢耗時逐步增長,而本文所提出系統(tǒng)的查詢耗時沒有明顯變化,這是因?yàn)?本文所提出的系統(tǒng)底層使用HBase 進(jìn)行存儲,HBase 的擴(kuò)展性非常高,所以,即使查詢數(shù)量增加,查詢所需要的時間幾乎不變.從圖8(b)中可以看出,對于運(yùn)單軌跡的時空范圍查詢,時間范圍的改變對于查詢性能影響較小,但因?yàn)楸疚乃岢龅南到y(tǒng)底層HBase 的高擴(kuò)展性,本文所提出的系統(tǒng)的查詢耗時也短于PostgreSQL 的查詢耗時.

圖8 運(yùn)單軌跡時空范圍查詢耗時Fig.8 Performance of spatio-temporal range query on attribute trajectory

從以上3 種查詢實(shí)驗(yàn)的結(jié)果可以看出,本文所提出的物流數(shù)據(jù)管理系統(tǒng)對于屬性查詢、時空范圍查詢和運(yùn)單軌跡的時空范圍查詢這3 類查詢較為高效.特別是當(dāng)數(shù)據(jù)量非常大時,查詢性能明顯優(yōu)于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫,更適合鋼鐵物流數(shù)據(jù)管理的場景.

4 結(jié) 語

為實(shí)現(xiàn)對鋼鐵網(wǎng)絡(luò)貨運(yùn)平臺產(chǎn)生的海量、多源的物流數(shù)據(jù)的存儲和查詢,本文基于HBase 和Redis 將海量歷史數(shù)據(jù)和實(shí)時數(shù)據(jù)分級存儲管理,并在此基礎(chǔ)上構(gòu)建 Z2、Z3 與網(wǎng)格索引等時空索引與屬性索引來提升查詢效率.通過在真實(shí)物流數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),驗(yàn)證了本文所提出的索引能有效提高查詢效率.在未來研究中,考慮針對場景中常用到的其他查詢,如相似查詢和kNN 查詢,并設(shè)計(jì)相應(yīng)的索引和查詢優(yōu)化策略.