591
任意列搜索之 列存儲優化
標簽
PostgreSQL , 列存儲 , shard , 切片 , 大塊 , 小塊 , sort , 塊級索引 , bitmap scan , 索引延遲 , 歸整
背景
數據分析係統，決策係統的數據量通常非常龐大，屬性（列）非常多，可能涉及到任意列的組合條件查詢，篩選結果、聚合結果、多維分析等。
這種場景如何優化能滿足實時的響應需求呢？
PostgreSQL中有一些技術，可以滿足此類場景。
1. 內置bitmapAnd bitmapOr，使用任意字段的索引搜索時，可以快速跳過不滿足條件的塊，快速的得到組合結果。
實測10億數據，31個字段任意搜索，約幾百毫秒的響應時間。
案例如下：
《多字段，任意組合條件查詢(無需建模) - 毫秒級實時圈人 最佳實踐》
還有這種方法，要求每個字段都建立索引，對數據寫入會有性能影響（特別是與堆存儲線性相關性很差的字段，索引分裂會比較嚴重，導致IO巨大）。
對於數據量非常龐大的場景，建議對表進行分區，可以建立多級分區。
例如UID為一級HASH分區，時間戳為二級範圍分區。這樣可以控製每個表的大小，通過時間分區我們可以將曆史數據靜態化，不影響新錄入數據的索引。從而提升整體性能。
2. PostgreSQL支持多種索引接口，針對不同的數據類型，數據的存儲風格。在前麵的案例中也有介紹。
因此並不是btree一路用到底，對於不同的類型有不同的搜索需求，比如範圍類型，數組類型，全文檢索類型，通常會根據包含、相交來進行查詢。而對於空間數據，通常會根據相交，距離等進行查詢。對於一維類型通常會根據=，或者範圍進行查詢。
這些數據類型都能找到合適的索引來加速掃描，結合bitmapAnd, bitmapOr，實現實時的任意字段搜索。
3. bitmap 索引(greenplum)
對於選擇性較差的列，例如1億記錄，隻有1000個唯一值，這種情況下，使用bitmap index就可以達到非常好的效果。
案例如下
《Greenplum 最佳實踐 - 什麼時候選擇bitmap索引》
《PostgreSQL (varbit, roaring bitmap) VS pilosa(bitmap庫)》
4. 列存儲, cstore(orc)格式
https://github.com/citusdata/cstore_fdw
如果單機已經做了很多優化，例如使用分區表，但是由於實時寫入的數據量依舊很龐大，數據錄入由於索引過多遇到瓶頸了，還有什麼優化手段呢？
一、海量數據 - 實時任意字段查詢，實時寫入 矛盾優化
要做到實時的海量寫入，又要實時的查詢，確實是一個比較矛盾的問題。
因為要實時寫入，就要盡量少的索引，而要實時查詢，就要索引的支持。
那麼到底怎麼解決這個矛盾問題呢？
1、索引延遲合並
在PostgreSQL中有一個GIN索引，這個索引是針對多值類型的索引，例如數組。
當用戶在寫入一條記錄時，（一個數組往往涉及多個元素），索引的條目可能會設置到多個，因此每寫一條記錄，IO是巨大的，因此GIN有一個加速數據寫入、更新、刪除的特性，fastupdate。
這個特性也比較好理解，實際上就是延遲合並，比如累計1000條記錄後，合並一次到索引的條目中。從而大幅提升寫入性能。
那麼我們也可以使用類似的技術來優化以上場景，隻是需要對所有的索引接口都做類似的fastupdate功能。
2、lambda批量操作
我們可以將數據分為兩個部分，一個部分是實時寫入部分，另一部分是數據的合並部分。
數據實時的寫入部分（不需要索引），實時寫入後，再批量對其建立索引。
也就是先寫入，到達分區邊界後，寫入新的分區，而前一個分區則開始建立索引。PG支持對一張表並行的創建多個索引。
例如
每個小時一個分區。
12:00-13:00，數據寫入12:00到13:00的分區，在12:00時，可以對11:00-12:00的分區建立索引。
因此實時的數據都是寫入沒有索引的表，寫入吞吐可以做到500萬行/s左右。
批量創建索引的速度是非常快的，通常可以跟上節奏。
另外有兩個類似的場景，有興趣的話也可以參考一下，與本例的用法不一樣。
《塊級(ctid)掃描在IoT(物聯網)極限寫和消費讀並存場景的應用》
3、分布式
當單機的容量、寫入性能、查詢性能可能成為瓶頸時，可以創建多個實例。
多個實例有許多方法可以融合起來。
例如
3.1 postgres_fdw + inherit
https://www.postgresql.org/docs/9.6/static/tutorial-inheritance.html
https://www.postgresql.org/docs/10/static/postgres-fdw.html
《PostgreSQL 9.6 單元化,sharding (based on postgres_fdw) - 內核層支持前傳》
《PostgreSQL 9.6 sharding + 單元化 (based on postgres_fdw) 最佳實踐 - 通用水平分庫場景設計與實踐》
3.2 postgres_fdw + pg_pathman
https://github.com/postgrespro/pg_pathman
https://www.postgresql.org/docs/10/static/postgres-fdw.html
《PostgreSQL 9.5+ 高效分區表實現 - pg_pathman》
《PostgreSQL 9.6 sharding based on FDW & pg_pathman》
3.3 plproxy
https://github.com/plproxy/plproxy
《PostgreSQL 最佳實踐 - 水平分庫(基於plproxy)》
《阿裏雲ApsaraDB RDS for PostgreSQL 最佳實踐 - 2 教你RDS PG的水平分庫》
《阿裏雲ApsaraDB RDS for PostgreSQL 最佳實踐 - 3 水平分庫 vs 單機 性能》
《阿裏雲ApsaraDB RDS for PostgreSQL 最佳實踐 - 4 水平分庫 之 節點擴展》
3.4 citusdata extension
https://github.com/citusdata/citus
4、幹掉索引，列存儲優化
列存儲除了可以降低單列統計，少量列統計的IO掃描成本，同時還可以提高壓縮比。
列存儲的方法是本文的重點，實際上可以不需要索引，使用列存，對列存的存儲進行優化和規則，使得訪問數據就如有索引一樣高效。
列存的優化手段是編排，可以參考如下文章。
《從一維編排到多維編排，從平麵存儲到3D存儲 - 數據存儲優化之路》
二、列存儲編排優化
單列編排比較好實現，多列編排則需要建立列和列之間的映射關係。例如使用一個中間VALUE（PK）進行關聯，這樣會增加一個成本。
例如
PK（沒有的話使用隱含PK）
pk_val1
pk_val2
pk_val3
column a
a_val1, pk?
a_val2, pk?
a_val3, pk?
column b
b_val1, pk?
b_val2, pk?
b_val3, pk?
column c
c_val1, pk?
c_val2, pk?
c_val3, pk?
bitmapAnd, bitmapOr結合
where column a ?
and column b ?
or column c ?
bitmap掃描方法如下，隻是替換成PK。
Heap, one square = one page:
+---------------------------------------------+
|c____u_____X___u___X_________u___cXcc______u_|
+---------------------------------------------+
Rows marked c match customers pkey condition.
Rows marked u match username condition.
Rows marked X match both conditions.
Bitmap scan from customers_pkey:
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
+---------------------------------------------+
One bit per heap page, in the same order as the heap
Bits 1 when condition matches, 0 if not
Bitmap scan from ix_cust_username:
+---------------------------------------------+
|000001000001000100010000000001000010000000010| bitmap 2
+---------------------------------------------+
Once the bitmaps are created a bitwise AND is performed on them:
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
|000001000001000100010000000001000010000000010| bitmap 2
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
|000000000001000000010000000000000010000000000| Combined bitmap
+-----------+-------+--------------+----------+
| | |
v v v
Used to scan the heap only for matching pages:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
The bitmap heap scan then seeks to the start of each page and reads the page:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
seek------->^seek-->^seek--------->^
| | |
------------------------
only these pages read
and each read page is then re-checked against the condition since there can be >1 row per page and not all necessarily match the condition.
編排的工作量和索引類似，也會涉及到塊的調整，因此也會導致寫延時，為了降低寫延遲，同樣需要類似的優化，延遲編排、分片等。
延遲編排
為了達到最大的寫入吞吐，寫入時數據為無序狀態。
分片優化
對寫入的數據，按每列的存儲分片進行整理，例如每個存儲分片32MB。
整理的目標是使得這32MB的分片的字段按順序存儲（對於不同的類型，整理規則可調整，例如按順序，按GEOHASH值順序，按聚集等）。
整理好之後，生成每個分片內的元信息，例如每8K一個單位，保存這個單位的數據邊界（最大最小值），數據的平均值，COUNT，方差等。
在搜索數據時，由於每個分片存儲了每8K的邊界信息，所以根據列條件，可以快速的過濾不滿足條件的8K單位（不需要掃描它們）。從而達到和索引一樣的效果。
（分片元信息類似BRIN索引：《PostgreSQL 聚集存儲 與 BRIN索引 - 高並發行為、軌跡類大吞吐數據查詢場景解說》 ）。
分片合並歸整
直到前麵的優化手段，隻是做到了分片內的數據歸整，分片和分片直接，是有可能存在數據的交集的。
例如：
第一個分片包含cola : 1-1000的數據，第二個分片可能包含cola : 2-2000的數據，這兩個分片是有交集的，如果搜索的數據是落在交集中的 ，那麼這兩個分片都需要掃描。
分片合並歸整的目的就是要盡量的減少分片之間的數據邊界模煳問題，讓分片的邊界更加的清晰。
例如對於分區表，有32GB數據，每個分片32MB，那麼當數據寫完後，可以對整個分區做歸整，使得每個分片的邊界清晰。
這個操作類似於PostgreSQL的cluster功能。
三、行列混合編排
列存儲非常適合對列進行統計分析，返回少量聚合結果的業務場景。
但是列存儲也可能帶來另一個負麵影響，例如用戶可能要返回多列，或者整行數據。由於列存儲每列的存儲都是獨立的，當需要返回一整行記錄時，需要掃描更多的數據塊。當返回的記錄數多時，可能會放大這個負麵影響。
行列混合存儲就出現了，行列混合存儲的思想類似與shard的思想。（在分布式數據庫中，建表時，將表按規則切分成若幹的shard，然後再將shard存儲到不同的數據節點(shard數往往大於節點數)，當擴容時，move shard即可，而不需要改變數據在shard層麵的分布規則。 例如某個分布式數據庫由4個數據節點組成，建表時，可以分成4096個shard，那麼在擴容時，移動shard就可以完成擴容。而不需要改變數據的路由規則，它們隻需要按原來的方法路由到對應的shard即可。）
在行列混合存儲的應用中，也有類似shard的思想，例如將記錄數切片，每一批數據的列存儲放到一個單獨的數據文件中。
這麼做的好處是，當用戶需要訪問這批數據時，訪問的是連續的數據塊，而不是離散的數據庫，從而提升返回大量數據的性能。（當然，這裏指的是返回相鄰的大量數據）。
小結
大量數據實時讀寫，實時任意列搜索的場景，優化的手段非常多。
本文詳解介紹了列存儲的優化方法。
包括分片延遲編排，分片歸整，行列混合等。
分片延遲編排，在保證數據高速寫入的前提下，可以實現數據在分片內的順序，8K單位的元數據。減少數據搜索時的掃描成本。
分片歸整，指更大範圍的分片編排，進一步提升整體的邊界清晰度，從而再一次減少數據搜索時的掃描成本。
行列混合存儲，當需要返回大量的連續整行記錄時，可以大幅降低掃描的數據塊的離散度。
最後更新：2017-06-15 15:31:58