一種支持海量數(shù)據(jù)以圖搜圖的通用技術(shù)架構(gòu)

姜光杰

(青島海信網(wǎng)絡(luò)科技股份有限公司,山東青島 266071)

以圖搜圖就是通過搜索圖像的矢量特征,通過輸入目標(biāo)圖片及圖片中目標(biāo)的屬性描述,搜索出與其相似的一組圖片,為用戶提供相關(guān)圖形圖像資料檢索服務(wù)的專業(yè)搜索引擎系統(tǒng)。以圖搜圖主要包括了兩個主要部分,一部分是AI圖片特征提取,另一部分是圖搜引擎[1]。后者主要實現(xiàn)了特征向量的存儲以及比對搜索等功能。近幾年的技術(shù)在目標(biāo)檢索方面,尤其是如何在海量底庫的情況下實現(xiàn)高效快速的檢索,依舊是個難題。

圖1 featuredb 結(jié)構(gòu)圖Fig.1 Structure of featuredb

本文提出了一種分布式特征存儲檢索庫featuredb,采用了基于LSM-Tree的結(jié)構(gòu),支持海量特征向量數(shù)據(jù)實時寫入,并在此基礎(chǔ)上構(gòu)建了高效的特征索引。經(jīng)過實際驗證5億圖搜庫1.2秒返回結(jié)果。下面從三個方面來介紹以圖搜圖通用架構(gòu)。

1 向量特征存儲及特征索引構(gòu)建策略

Featuredb由三部分組成:meta主索引文件、chunk塊索引文件(*.bm文件)、chunk存儲塊(C-*.0文件和C-*.1文件)。如圖1所示,由于是順序?qū)懭?一個特征chunk存儲單元用完后,再順序?qū)懭胂乱粋€chunk存儲單元。因此整個架構(gòu)是彈性伸縮的。

一個目標(biāo)特征向量有一個唯一的索引號UID,UID的設(shè)計對應(yīng)了兩級索引,UID可以用公式表示為:

UID=cidx*65536+inner_idx

cidx表示chunk塊索引,inner_idx表示chunk塊內(nèi)索引。

其中:cidx的范圍[0,32767],inner_idx的范圍[0,65535].

UID的范圍[0,32767*65535=2,147,385,345],因此本特征索引設(shè)計規(guī)模支持單機存儲特征向量可達2 1 億規(guī)模。如果已知一個特征索引號UID,則cidx=UID/65536即UID高16位,inner_idx=UID% 65536,即UID低16位。

1.1 Meta主索引文件

主索引文件meta,采用bit-map映射,總長度為0x1018字節(jié),其中文件頭占0x18字節(jié),文件體占0x1000字節(jié),每個bit對應(yīng)一個chunk塊,bit值為0,表示其對應(yīng)的chunk塊不存在,bit值為1,表示對應(yīng)的chunk塊存在。整個meta文件可以用一個結(jié)構(gòu)體core_meta_t描述出來。一個meta文件最多可以管理32768個chunk塊。cidx就是該bit位在文件體中的偏移位置。

下面給出C++描述的meta文件結(jié)構(gòu)如下:

struct bit_map_hdr

{

uint32_t scan_index_word;

uint32_t used_bits;

};

typedef struct{

int64_t _version_flag;

uint32_t next_alloc_chunk_id;

uint32_t _reserved;

bit_map_hdr _free_chk_hdr;

int64_t _freechkbs_data[512];

}core_meta_t;

_version_flag:占用8字節(jié),固定內(nèi)容:0x12366,主要用于校驗庫文件。

next_alloc_chunk_id:占用4個字節(jié),表示下一個申請的chunk塊號。通常用于遍歷chunk塊。例如:當(dāng)前已經(jīng)使用了10個chunk塊,則next_alloc_chunk_id=11.

_reserved:目前未使用,暫時保留。占用4個字節(jié)。

_f re e_ch k_hd r:占用8 個字節(jié)。它是一個結(jié)構(gòu)體bit_map_hdr,前面4個字節(jié)scan_index_word,是_freechkbs_data數(shù)組的索引,表示當(dāng)前已經(jīng)使用的chunk塊簇的位置。used_bits:占用后面的4個字節(jié)。表示當(dāng)前已經(jīng)分配的chunk塊數(shù)量。

_freechkbs_data:表示chunk塊簇數(shù)組,數(shù)組總共包含了512個chunk塊簇。其中,每個chunk塊簇占用8個字節(jié),包含64個bit,管理著64個chunk塊,即每個chunk塊占用1個bit位置。

1.2 ★.bm:二級索引文件,即chunk塊內(nèi)部索引

每個chunk塊都有一個.bm索引文件,文件名是以cidx為名字,例如1.bm.

*.bm文件總長度為0x2010字節(jié),其中文件頭占0x10字節(jié),文件體占0x2000字節(jié)。采用bit-map映射,文件體每個bit表示一個特征向量的狀態(tài),用一個c++結(jié)構(gòu)體完整表示為:

struct bit_map_hdr

{

uint32_t scan_index_word;

uint32_t used_bits;

};

typedef struct{

int64_t _ver_flag;

bit_map_hdr _record_bmhdr;

int64_t _recbm_data[1024];

}chk_meta_t;

_ver_flag:占用8個字節(jié),固定內(nèi)容0x3001。用于校驗chunk文件真?zhèn)巍?/p>

_record_bmhdr:它對應(yīng)一個結(jié)構(gòu)體bit_map_hdr,結(jié)構(gòu)內(nèi)開頭4個字節(jié)是scan_index_word,表示_recbm_data數(shù)組的索引,表示已經(jīng)使用到的特征簇的位置。后面的4 個字節(jié)是used_bits,用于表示本chunk塊中已經(jīng)存儲的特征向量數(shù)。

_recbm_data:特征簇數(shù)組,每個特征簇占用8個字節(jié),總共1024個特征簇。

一個特征簇管理著6 4 個特征向量,即8 個字節(jié)的特征簇,總共包含64bit,每個bit對應(yīng)一個特征向量。比特值為1,表示該位置存儲了特征向量,比特值為0,表示該位置沒有存儲特征向量。1個bm 文件可以管理65535個特征向量。

1.3 特征存儲文件C-★.0, C-★.1

每個chunk塊都有一個C-*.0和C-*.1特征存儲文件,文件名是以cidx為名字。

本文設(shè)計的深度學(xué)習(xí)特征模型,特征提取后包括兩種特征,長特征是256個float,占用1024字節(jié)。短特征是256個bit,占用32個字節(jié)。由于這部分不在本文論述范圍,讀者可以根據(jù)自身應(yīng)用場景需要,選擇決定自己特征模型輸出的長短特征向量。

C-*.0文件:短特征文件,步長為32字節(jié),文件名是以UID的高16位cidx為文件名。例如:0號chunk塊的短特征,存儲于C-0.0文件,1號chunk塊的短特征,存儲于C-1.0文件,由于特征的長度固定,通過特征向量的UID,可以很方便的存取特征向量。

每個文件存儲65536個特征,每個特征長度32字節(jié),因此C-0.0文件長度為0x 200000字節(jié)。0.2M大小。

C-*.1文件:長特征文件,步長為1024字節(jié),文件名是以UID的高16位cidx為文件名。例如:0號chunk塊的長特征,存儲于C-0.1文件,1號chunk塊的長特征,存儲于C-1.1文件。由于每個文件存儲65536個特征向量,因此,C-0.1文件長度為0x400*65536=0x4000000字節(jié)。4M大小。

由于本文特征向量索引UID的設(shè)計非常靈活,使得根據(jù)UID讀取特征向量可以在o(1)時間內(nèi)完成。根據(jù)UID取高16位,就是對應(yīng)的chunk索引文件及chunk特征文件的名字,特征在chunk塊中的偏移值就是UID的低16位。

特征入庫時,步驟如下:

(1)在meta文件找到文件體內(nèi)最后出現(xiàn)的bit值為1的塊,找出塊對應(yīng)的b m 文件,在b m 文件文件體內(nèi)從后往前找最后出現(xiàn)的bit值為0的位置,如果已經(jīng)滿了,就在meta文件中選擇bit值為0的塊,創(chuàng)建一個新的chunk塊,返回bm文件最先bit為0的位置,這個就是新申請的UID。

(2)UID申請到,將兩級索引文件對應(yīng)的bit位設(shè)置為1。

(3)將短特征向量寫入到C-cidx.0內(nèi)存文件中偏移32*UID低16位位置。

(4)將長特征向量寫入到C-cidx.1內(nèi)存文件中偏移1024*UID低16位位置。

由于所有的chunk特征向量文件都通過內(nèi)存映像到內(nèi)存中,因此可以實時序列化到文件中。

2 向量特征檢索策略

本文自主設(shè)計了基于openMP的多線程任務(wù)調(diào)度及并行處理模式,如圖2所示,步驟如下:

圖2 特征檢索Fig.2 Feature retrieval

圖3 帶屬性的以圖搜圖檢索Fig.3 Graph search with attributes

(1)遍歷featuredb庫,分組并行處理將每個chunk塊存儲的圖片短特征與目標(biāo)圖片短特征進行漢明距離比對,根據(jù)相似度,篩選出最相似的前2000個結(jié)果集。

(2)在第一次初篩的基礎(chǔ)上,分組并行處理將初篩結(jié)果集分布在每個chunk塊中存儲的圖片長特征與目標(biāo)圖片進行余弦夾角的計算,篩選出最相似的400張圖片作為結(jié)果集返回給用戶。

3 帶目標(biāo)屬性值過濾的以圖搜圖策略

為了支持帶目標(biāo)屬性值的以圖搜圖,本文設(shè)計了采用clickhouse列式數(shù)據(jù)庫存儲目標(biāo)的結(jié)構(gòu)化屬性值,用UID作為key值字段,Clickhouse支持sql語句,可以根據(jù)目標(biāo)屬性值完成快速屬性過濾,返回對應(yīng)的UID列集合。同時為了以圖搜圖輸出結(jié)果中包含目標(biāo)的結(jié)構(gòu)化屬性值,特別的設(shè)計了使用內(nèi)存數(shù)據(jù)庫rocksdb用于在featherdb檢索返回的結(jié)果集中,補齊結(jié)果集中目標(biāo)的結(jié)構(gòu)化屬性值[2]。

Rocksdb是一個高性能的key-value數(shù)據(jù)庫,主要用于存儲建庫時表字段列表,用于用戶需求字段篩選,以UID為key值,存儲了特征向量對應(yīng)的所有屬性值,中間用逗號隔開。

以圖搜圖分為兩種場景,一種是帶目標(biāo)屬性值的圖搜,一種是純以圖搜圖。

帶屬性圖搜步驟如圖3 所示。步驟如下:

(1)Clickhouse主要用于屬性值的過濾。根據(jù)want Param和whereStm以及dbname,完成屬性值記錄檢索,返回UID列的結(jié)果集。

(2)Featuredb:根據(jù)clickhouse返回的UID列的結(jié)果集以及目標(biāo)圖片的長短特征,進行特征檢索,完成特征比對score打分,同時根據(jù)返回記錄數(shù)n的要求,根據(jù)score值排序,返回相似度最高的前n項。

(3)Rocksdb:獲取featuredb返回的n條結(jié)果集,根據(jù)UID,取出存儲的屬性記錄,同時根據(jù)wantParam和rocksdb存儲的fieldlist,將客戶感興趣的字段值填充的返回結(jié)果集。

純以圖搜圖則只需要執(zhí)行前面的向量特征檢索策略再加上步驟3即可。

4 總結(jié)

整套圖搜架構(gòu),無論是列式存儲還是kv存儲,對庫的選型方面,適應(yīng)了海量數(shù)據(jù)存儲及高可靠性、高并發(fā)的需求。同時滿足了彈性可擴展,以及高性能索引和高性能存儲。主要特點如下:

(1)featuredb架構(gòu)靈活,UID線型索引方案,任意access時間復(fù)雜度為O(1)。

(2)基于位圖(bit-map)與分塊(chunk)的索引組織與劃分方案。極低的內(nèi)存占用,高效磁盤同步機制,接近常數(shù)量級時間復(fù)雜度。

(3)采用了基于mmap的“磁盤-內(nèi)存”數(shù)據(jù)映射方案,解決特征數(shù)據(jù)快速讀寫訪問問題,實現(xiàn)極高效的內(nèi)存-磁盤IO機制。