配景

在物聯(lián)網(wǎng)、監(jiān)控、傳感器、金融等應(yīng)用領(lǐng)域,數(shù)據(jù)在時(shí)間維度上流式的產(chǎn)生,并且數(shù)據(jù)量非常龐大.

例如我們經(jīng)常看到的性能監(jiān)控視圖,便是很多點(diǎn)在時(shí)間維度上描繪的曲線.

又好比金融行業(yè)的走勢(shì)數(shù)據(jù)等等.

我們想象一下,如果每個(gè)傳感器或指標(biāo)每100毫秒產(chǎn)生1個(gè)點(diǎn),一天便是864000個(gè)點(diǎn).

而傳感器或指標(biāo)是非常多的,例如有100萬(wàn)個(gè)傳感器或指標(biāo),一天的量就接近一億的量.

假設(shè)我們要描繪一個(gè)時(shí)間段的圖形,這么多的點(diǎn),渲染估計(jì)都要很久.

那么有沒(méi)有好的壓縮算法,即能保證失真度,又能很好的對(duì)數(shù)據(jù)進(jìn)行壓縮呢?

旋轉(zhuǎn)門(mén)壓縮算法原理

旋轉(zhuǎn)門(mén)壓縮算法(SDT)是一種直線趨勢(shì)化壓縮算法,其本色是通過(guò)一條由起點(diǎn)和終點(diǎn)確定的直線代替一系列連續(xù)數(shù)據(jù)點(diǎn).

該算法必要記錄每段時(shí)間間隔長(zhǎng)度、起點(diǎn)數(shù)據(jù)和終點(diǎn)數(shù)據(jù), 前一段的終點(diǎn)數(shù)據(jù)即為下一段的起點(diǎn)數(shù)據(jù).

其基來(lái)源根基理較為簡(jiǎn)單, 參見(jiàn)圖.

第一個(gè)數(shù)據(jù)點(diǎn)a上下各有一點(diǎn),它們與a點(diǎn)之間的距離為E(即門(mén)的寬度), 這兩個(gè)點(diǎn)作為“門(mén)”的兩個(gè)支點(diǎn).

當(dāng)只有第一個(gè)數(shù)據(jù)點(diǎn)時(shí),兩扇門(mén)都是關(guān)閉的;隨著點(diǎn)數(shù)越來(lái)越多,門(mén)將逐步打開(kāi);注意到每扇門(mén)的寬度是可以伸縮的,在一段時(shí)間間隔里面,門(mén)一旦打開(kāi)就不克不及閉;

只要兩扇門(mén)未達(dá)到平行,或者說(shuō)兩個(gè)內(nèi)角之和小于180°(本文的算法將利用這一點(diǎn)進(jìn)行判斷),這種“轉(zhuǎn)門(mén)”操作即可繼續(xù)進(jìn)行.

圖中第一個(gè)時(shí)間段是從a到e, 成果是用a點(diǎn)到e點(diǎn)之間的直線代替數(shù)據(jù)點(diǎn)(a,b,c,d,e); 起到了可控失真(E)的壓縮作用.

第二個(gè)時(shí)間間隔從e點(diǎn)開(kāi)始,開(kāi)始時(shí)兩扇門(mén)關(guān)閉,然后逐步打開(kāi),后續(xù)操作與前一段類(lèi)似.

在PostgreSQL中實(shí)現(xiàn)旋轉(zhuǎn)門(mén)壓縮算法

通過(guò)旋轉(zhuǎn)門(mén)算法的原理,可以了解到,有幾個(gè)需要的輸入項(xiàng).

• 有x坐標(biāo)和y坐標(biāo)的點(diǎn)(如果是時(shí)間軸上的點(diǎn),可以通過(guò)epoch轉(zhuǎn)換成這種形式)

• E,即門(mén)的寬度,起到了控制壓縮失真度的作用

例子

創(chuàng)立測(cè)試表

create table tbl(id int, -- ID,可有可無(wú)val numeric, -- 值(如傳感器或金融行業(yè)的點(diǎn)值)t timestamp -- 取值時(shí)間戳);

插入10萬(wàn)條測(cè)試數(shù)據(jù)

insert into tbl select generate_series(1,100000), round((random()*100)::numeric, 2), clock_timestamp()+(generate_series(1,100000) || ' second')::interval ; test=> select * from tbl limit 10;

id | val | t

----+-------+----------------------------

1 | 31.79 | 2016-08-12 23:22:27.530318

2 | 18.23 | 2016-08-12 23:22:28.530443

3 | 5.14 | 2016-08-12 23:22:29.530453

4 | 90.25 | 2016-08-12 23:22:30.530459

5 | 8.17 | 2016-08-12 23:22:31.530465

6 | 97.43 | 2016-08-12 23:22:32.53047

7 | 17.41 | 2016-08-12 23:22:33.530476

8 | 0.23 | 2016-08-12 23:22:34.530481

9 | 84.67 | 2016-08-12 23:22:35.530487

10 | 16.37 | 2016-08-12 23:22:36.530493

(10 rows)

時(shí)間如何轉(zhuǎn)換成X軸的數(shù)值,假設(shè)每1秒為X坐標(biāo)的1個(gè)單位

test=> select (extract(epoch from t)-extract(epoch from first_value(t) over())) / 1 as x, -- 除以1秒為1個(gè)單位

val, t from tbl limit 100;

x | val | t

------------------+-------+----------------------------

0 | 31.79 | 2016-08-12 23:22:27.530318 1.00012493133545 | 18.23 | 2016-08-12 23:22:28.530443 2.00013494491577 | 5.14 | 2016-08-12 23:22:29.530453 3.00014090538025 | 90.25 | 2016-08-12 23:22:30.530459 4.00014686584473 | 8.17 | 2016-08-12 23:22:31.530465 5.00015187263489 | 97.43 | 2016-08-12 23:22:32.53047 6.00015807151794 | 17.41 | 2016-08-12 23:22:33.530476 7.00016307830811 | 0.23 | 2016-08-12 23:22:34.530481 8.00016903877258 | 84.67 | 2016-08-12 23:22:35.530487

編寫(xiě)實(shí)現(xiàn)螺旋門(mén)算法的函數(shù)

create or replace function f (

i_radius numeric, -- 壓縮半徑

i_time timestamp, -- 開(kāi)始時(shí)間

i_interval_s numeric, -- 時(shí)間轉(zhuǎn)換間隔 (秒,例如每5秒在坐標(biāo)上表現(xiàn)1個(gè)單位間隔,則這里使用5)

query text, -- 需要進(jìn)行旋轉(zhuǎn)門(mén)壓縮的數(shù)據(jù), 例子 'select t, val from tbl where t>=%L order by t limit 100' , select 子句必需固定, 必需按t排序

OUT o_val numeric, -- 值,縱坐標(biāo) y (跳躍點(diǎn)y)

OUT o_time timestamp, -- 時(shí)間,橫坐標(biāo) x (跳躍點(diǎn)x)

OUT o_x numeric -- 跳躍點(diǎn)x, 通過(guò) o_time 轉(zhuǎn)換)

returns setof record as $$

declare

v_time timestamp; -- 時(shí)間變量

v_x numeric; -- v_time 轉(zhuǎn)換為v_x

v_val numeric; -- y坐標(biāo)

v1_time timestamp; -- 前一點(diǎn) 時(shí)間變量

v1_x numeric; -- 前一點(diǎn) v_time 轉(zhuǎn)換為v_x

v1_val numeric; -- 前一點(diǎn) y坐標(biāo)

v_start_time numeric; -- 記錄第一條的時(shí)間坐標(biāo), 用于計(jì)算x偏移量

v_rownum int8 := 0; -- 用于標(biāo)志是否第一行

v_max_angle1 numeric; -- 最大上門(mén)夾角角度

v_max_angle2 numeric; -- 最大下門(mén)夾角角度

v_angle1 numeric; -- 上門(mén)夾角角度

v_angle2 numeric; -- 下門(mén)夾角角度begin

for v_time , v_val in execute format(query, i_time)

LOOP

-- 第一行,第一個(gè)點(diǎn),是實(shí)際要記錄的點(diǎn)位

v_rownum := v_rownum + 1; if v_rownum=1 then

v_start_time := extract(epoch from v_time);

v_x := 0;

o_val := v_val;

o_time := v_time;

o_x := v_x;

-- raise notice 'rownum=1 %, %', o_val,o_time;

return next; -- 返回第一個(gè)點(diǎn)

else

v_x := (extract(epoch from v_time) - v_start_time) / i_interval_s; -- 生成X坐標(biāo)

SELECT 180-ST_Azimuth(

ST_MakePoint(o_x, o_val+i_radius), -- 門(mén)上點(diǎn)

ST_MakePoint(v_x, v_val) -- next point

)/(2*pi())*360 as degAz, -- 上夾角

ST_Azimuth(

ST_MakePoint(o_x, o_val-i_radius), -- 門(mén)下點(diǎn)

ST_MakePoint(v_x, v_val) -- next point

)/(2*pi())*360 As degAzrev -- 下夾角

INTO v_angle1, v_angle2;

select GREATEST(v_angle1, v_max_angle1), GREATEST(v_angle2, v_max_angle2) into v_max_angle1, v_max_angle2; if (v_max_angle1 + v_max_angle2) >= 180 then -- 找到四邊形外的點(diǎn)位,輸出上一個(gè)點(diǎn),并從上一個(gè)點(diǎn)開(kāi)始重新計(jì)算四邊形

-- raise notice 'max1 %, max2 %', v_max_angle1 , v_max_angle2;

-- 復(fù)原

v_angle1 := 0;

v_max_angle1 := 0;

v_angle2 := 0;

v_max_angle2 := 0; -- 門(mén)已完全打開(kāi),輸出前一個(gè)點(diǎn)的值

o_val := v1_val;

o_time := v1_time;

v1_x := (extract(epoch from v1_time) - v_start_time) / i_interval_s; -- 生成前一個(gè)點(diǎn)的X坐標(biāo)

o_x := v1_x;

-- 用新的門(mén),與當(dāng)前點(diǎn)計(jì)算新的夾角

SELECT 180-ST_Azimuth(

ST_MakePoint(o_x, o_val+i_radius), -- 門(mén)上點(diǎn)

ST_MakePoint(v_x, v_val) -- next point

)/(2*pi())*360 as degAz, -- 上夾角

ST_Azimuth(

ST_MakePoint(o_x, o_val-i_radius), -- 門(mén)下點(diǎn)

ST_MakePoint(v_x, v_val) -- next point

)/(2*pi())*360 As degAzrev -- 下夾角

INTO v_angle1, v_angle2; select GREATEST(v_angle1, v_max_angle1), GREATEST(v_angle2, v_max_angle2) into v_max_angle1, v_max_angle2;

-- raise notice 'new max %, new max %', v_max_angle1 , v_max_angle2;

-- raise notice 'rownum<>1 %, %', o_val, o_time;

return next; end if;

-- 記錄當(dāng)前值,保留作為下一個(gè)點(diǎn)的前點(diǎn)

v1_val := v_val;

v1_time := v_time;

end if;

END LOOP;

end;

$$ language plpgsql strict;

壓縮測(cè)試

門(mén)寬為15,起始時(shí)間為'2016-08-12 23:22:27.530318',每1秒表現(xiàn)1個(gè)X坐標(biāo)單位.

test=>

select * from f (

15, -- 門(mén)寬度=15

'2016-08-12 23:22:27.530318', -- 開(kāi)始時(shí)間

1, -- 時(shí)間坐標(biāo)換算間隔,1秒

'select t, val from tbl where t>=%L order by t limit 100' -- query

);

o_val | o_time | o_x

-------+----------------------------+------------------

18.23 | 2016-08-12 23:22:28.530443 | 0

5.14 | 2016-08-12 23:22:29.530453 | 1.00001287460327

90.25 | 2016-08-12 23:22:30.530459 | 2.00001883506775

......

87.90 | 2016-08-12 23:24:01.53098 | 93.0005400180817

29.94 | 2016-08-12 23:24:02.530985 | 94.0005450248718

63.53 | 2016-08-12 23:24:03.53099 | 95.0005497932434

12.25 | 2016-08-12 23:24:04.530996 | 96.0005559921265

83.21 | 2016-08-12 23:24:05.531001 | 97.0005609989166

(71 rows)

可以看到100個(gè)點(diǎn),壓縮成了71個(gè)點(diǎn).

對(duì)比一下本來(lái)的100個(gè)點(diǎn)的值

test=> select val, t, (extract(epoch from t)-extract(epoch from first_value(t) over()))/1 as x from tbl where t>'2016-08-12 23:22:27.530318' order by t limit 100;

val | t | x

-------+----------------------------+------------------

18.23 | 2016-08-12 23:22:28.530443 | 0

5.14 | 2016-08-12 23:22:29.530453 | 1.00001001358032

90.25 | 2016-08-12 23:22:30.530459 | 2.0000159740448

......

83.21 | 2016-08-12 23:24:05.531001 | 97.0005581378937

87.97 | 2016-08-12 23:24:06.531006 | 98.0005631446838

58.97 | 2016-08-12 23:24:07.531012 | 99.0005691051483

(100 rows)

使用excel繪圖,進(jìn)行壓縮前后的對(duì)比

上面是壓縮后的數(shù)據(jù)繪圖,下面是壓縮前的數(shù)據(jù)繪圖

紅色標(biāo)記的位置,便是通過(guò)旋轉(zhuǎn)門(mén)算法壓縮掉的數(shù)據(jù).

失真度是可控的.

流式壓縮的實(shí)現(xiàn)

本文略,其實(shí)也很簡(jiǎn)單,這個(gè)函數(shù)改一下,創(chuàng)立一個(gè)以數(shù)組為輸入?yún)?shù)的函數(shù).

以lambda的方式,實(shí)時(shí)的從流式輸入的管道取數(shù),并執(zhí)行即可.

也可以寫(xiě)成聚合函數(shù),在基于PostgreSQL 的流式數(shù)據(jù)庫(kù)pipelineDB中調(diào)用,實(shí)現(xiàn)流式計(jì)算.

http://www.pipelinedb.com/

小結(jié)

通過(guò)旋轉(zhuǎn)門(mén)算法,對(duì)IT監(jiān)控、金融、電力、水利等監(jiān)控、物聯(lián)網(wǎng)、等流式數(shù)據(jù)進(jìn)行實(shí)時(shí)的壓縮.

數(shù)據(jù)不必要從數(shù)據(jù)庫(kù)LOAD出來(lái)即可在庫(kù)內(nèi)完成運(yùn)算和壓縮.

用戶(hù)也可以根據(jù)實(shí)際的需求,進(jìn)行流式的數(shù)據(jù)壓縮,同樣數(shù)據(jù)也不必要從數(shù)據(jù)庫(kù)LOAD出來(lái),在數(shù)據(jù)庫(kù)端即可完成.

PostgreSQL的功能一如既往的強(qiáng)大,好用,快用起來(lái)吧.

參考

1. http://baike.baidu.com/view/3478397.htm

2. http://postgis.net/docs/manual-2.2/ST_Azimuth.html

3. https://www.postgresql.org/docs/devel/static/functions-conditional.html

4. http://gis.stackexchange.com/questions/25126/how-to-calculate-the-angle-at-which-two-lines-intersect-in-postgis

5. http://gis.stackexchange.com/questions/668/how-can-i-calculate-the-bearing-between-two-points-in-postgis

6. http://www.pipelinedb.com/

更多深度技術(shù)內(nèi)容,請(qǐng)存眷云棲社區(qū)微信公眾號(hào)：yunqiinsight.