基于數(shù)據(jù)隱私的工作流數(shù)據(jù)布局

葛金磊，董春龍，靳偉，陳鳳妹，黃濤

（硅湖職業(yè)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，蘇州 215300）

1 背景

隨著數(shù)據(jù)采集技術(shù)的進(jìn)步和服務(wù)需求的提高[1]，各類行業(yè)數(shù)據(jù)的數(shù)量和類型持續(xù)增長，已逐漸具備了“大數(shù)據(jù)”的特征，如：交通、醫(yī)療、氣象等行業(yè)[2-3]。而基于這些海量的行業(yè)數(shù)據(jù)基礎(chǔ)和不斷提高的行業(yè)服務(wù)需求，各類應(yīng)用程序的計(jì)算復(fù)雜度也在不斷增加[4-5]。因此，各行業(yè)部門整合已有的各類“計(jì)算”和“存儲(chǔ)”資源建立“集群”，再將大量的氣象應(yīng)用和海量數(shù)據(jù)遷移到集群中[6]，一方面，為了提高所有應(yīng)用的平均數(shù)據(jù)響應(yīng)時(shí)間，各行業(yè)部門對(duì)海量歷史數(shù)據(jù)的特征進(jìn)行分析，再合理分布到各存儲(chǔ)節(jié)點(diǎn)[7]，另一方面，借助“云計(jì)算”強(qiáng)大的計(jì)算性能，來減少各類應(yīng)用的執(zhí)行時(shí)間[8]。然而，集群中各節(jié)點(diǎn)之間的數(shù)據(jù)傳輸也產(chǎn)生了額外的傳輸時(shí)間。此外，隨著各類行業(yè)數(shù)據(jù)保密性要求的提高，部分?jǐn)?shù)據(jù)之間存在一定的隱私?jīng)_突，應(yīng)當(dāng)盡量避免放在相同或者鄰近的存儲(chǔ)節(jié)點(diǎn)上，以保證隱私數(shù)據(jù)的安全性[8-9]。

因此，基于行業(yè)歷史數(shù)據(jù)的整體布局和隱私數(shù)據(jù)的安全性要求，如何對(duì)各類應(yīng)用工作流和實(shí)時(shí)輸入數(shù)據(jù)進(jìn)行協(xié)同布局優(yōu)化已逐漸成為一個(gè)新的挑戰(zhàn)。針對(duì)各行業(yè)普遍采用的Fat-tree 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，本文提出了一種工作流和數(shù)據(jù)的協(xié)同布局優(yōu)化方法，以共同優(yōu)化數(shù)據(jù)訪問時(shí)間和隱私數(shù)據(jù)沖突程度。

2 問題分析

2.1 Fat-tree網(wǎng)絡(luò)分析

由于傳統(tǒng)樹狀結(jié)構(gòu)網(wǎng)絡(luò)的帶寬是逐層收斂的，因此，很可能導(dǎo)致網(wǎng)絡(luò)擁塞。因此，基于傳統(tǒng)樹形網(wǎng)絡(luò)結(jié)構(gòu)，提出了“Fat-tree”拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)。Fat-tree 網(wǎng)絡(luò)結(jié)構(gòu)從上到下分為三層：核心層、匯聚層和邊緣層，匯聚層交換機(jī)和邊緣層交換機(jī)形成一個(gè)Pod。Fat-tree 拓?fù)渚W(wǎng)絡(luò)的帶寬不收斂，可以提供高吞吐量的傳輸服務(wù)，確保網(wǎng)絡(luò)暢通無阻。另外，任意兩個(gè)節(jié)點(diǎn)之間有多條并行路徑，因此網(wǎng)絡(luò)的容錯(cuò)性較好。

在行業(yè)實(shí)際應(yīng)用中，基于“虛擬化”技術(shù)和Fat-tree網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，將各個(gè)子部門的“計(jì)算”資源和“存儲(chǔ)”資源集中構(gòu)建成一個(gè)公共云數(shù)據(jù)中心。因此，每個(gè)部門中的交換機(jī)構(gòu)成一個(gè)Pod，或者幾個(gè)相鄰部門的所有交換機(jī)共同構(gòu)成一個(gè)Pod，并且每個(gè)Pod 連接到它所屬子部門的服務(wù)器，每一個(gè)計(jì)算服務(wù)器或存儲(chǔ)服務(wù)器都作為集群中的一個(gè)計(jì)算節(jié)點(diǎn)或存儲(chǔ)節(jié)點(diǎn)。

2.2 工作流分析

在行業(yè)應(yīng)用云處理模式下，為了系統(tǒng)性地減少所有應(yīng)用的平均數(shù)據(jù)獲取時(shí)間，各行業(yè)部門對(duì)云數(shù)據(jù)中心中的海量歷史數(shù)據(jù)進(jìn)行特性分析，并合理分布到各存儲(chǔ)節(jié)點(diǎn)中，作為各應(yīng)用的重要數(shù)據(jù)源。同時(shí)，基于工作流技術(shù)，每一個(gè)應(yīng)用程序可以被建模為一個(gè)工作流，應(yīng)用中的每一步操作都可以建模為工作流中一系列有先后序列的子任務(wù)集合。其中，每一個(gè)子任務(wù)的執(zhí)行都需要有各自依賴的數(shù)據(jù)源，包括：歷史數(shù)據(jù)、用戶輸入數(shù)據(jù)等，并且各數(shù)據(jù)之間存在一定的數(shù)據(jù)隱私?jīng)_突。

因此，基于云數(shù)據(jù)中心中的歷史數(shù)據(jù)和各數(shù)據(jù)之間的隱私?jīng)_突關(guān)系，完成工作流和輸入數(shù)據(jù)的協(xié)同放置，以減少數(shù)據(jù)平均訪問時(shí)間和隱私數(shù)據(jù)沖突程度。

3 問題建模

在本節(jié)中，我們主要對(duì)工作流和數(shù)據(jù)的協(xié)同布局模型進(jìn)行分析與建模。

假設(shè)一個(gè)工作流包括M 個(gè)子任務(wù)，那么這個(gè)工作流可以被表示為一個(gè)具有先后序列的任務(wù)集合T={t0,t1,...,tm-1,...,tM-1}，其中，tm-1代表第m 個(gè)子任務(wù)。該工作流的數(shù)據(jù)源主要包括P 個(gè)輸入數(shù)據(jù)和Q 個(gè)歷史數(shù)據(jù)，可以分別表示為I = {i0, i1, ..., ip-1, ..., iP-1}和H = {h0,h1,...,hq-1,...,hQ-1}，其中，如果存在K 對(duì)隱私?jīng)_突數(shù)據(jù)，那么這些隱私?jīng)_突數(shù)據(jù)之間的沖突關(guān)系可以表示為γ= {γ0, γ1, ..., γk-1, ..., γK-1}，其中γk-1= {dx, dy}，(dx, dy∈{I,H})表示第k 對(duì)沖突數(shù)據(jù)。而M 個(gè)子任務(wù)和各數(shù)據(jù)之間的依賴關(guān)系可以表示為β={β0,β1,...,βm-1,...,βM-1}，其中βm-1={dx|dx∈{I,H}}表示任務(wù)tm-1所依賴的數(shù)據(jù)源。

3.1 數(shù)據(jù)訪問時(shí)間模型

在Fat-tree 網(wǎng)絡(luò)拓?fù)渲校僭O(shè)任務(wù)tm及其所需數(shù)據(jù)dn分別布局在計(jì)算節(jié)點(diǎn)Nodei和存儲(chǔ)節(jié)點(diǎn)Nodej中，而且服務(wù)器與邊緣層間帶寬、邊緣層與匯聚層間帶寬以及匯聚層與核心層間帶寬分別表示為Bse、Bea和Bac，那么任務(wù)tm對(duì)數(shù)據(jù)的訪問時(shí)間可以如下計(jì)算：

●如果Nodei和Nodej是同一節(jié)點(diǎn)，則；

●如果Nodei和Nodej屬于同一Pod 下的相同交換機(jī)，則=2*dn/Bse；

●如果Nodei和Nodej屬于同一Pod 下的不同交換機(jī)，則=2*(dn/Bse+dn/Bea)；

●如果Nodei和Nodej屬于不同的Pod，則=2*(dn/Bse+dn/Bea+dn/Bac)；

因此，任務(wù)tm對(duì)于其所需數(shù)據(jù)集βm的總數(shù)據(jù)訪問時(shí)間可以計(jì)算為：

然后，M 個(gè)任務(wù)的平均數(shù)據(jù)訪問時(shí)間TAvg可以計(jì)算為：

3.2 數(shù)據(jù)隱私?jīng)_突模型

由于部分歷史數(shù)據(jù)和輸入數(shù)據(jù)之間存在隱私?jīng)_突，這些數(shù)據(jù)的網(wǎng)絡(luò)存儲(chǔ)距離越近，則隱私被侵犯的可能性就越大。因此，為了確保這些隱私數(shù)據(jù)的安全性，優(yōu)先將相互沖突的數(shù)據(jù)布局在不同的Pod 下，然后，再依次考慮布局在同一Pod 的不同交換機(jī)和相同交換機(jī)下，并應(yīng)當(dāng)盡量避免布局在同一存儲(chǔ)節(jié)點(diǎn)中。

因此，假設(shè)經(jīng)過協(xié)同布局后，布局在同一存儲(chǔ)節(jié)點(diǎn)的沖突數(shù)據(jù)有NSN對(duì)，布局在相同交換機(jī)下不同存儲(chǔ)節(jié)點(diǎn)的沖突數(shù)據(jù)有NSS對(duì)，布局在同一Pod 不同交換機(jī)下的沖突數(shù)據(jù)有NSP對(duì)。并為這三種布局沖突情況分別設(shè)置相對(duì)應(yīng)的沖突權(quán)重 w0，w1和 w2，其中，w0+ w1+w2=1，而沖突權(quán)重w 越大，則代表該情況下的沖突數(shù)據(jù)放置得越近，隱私?jīng)_突程度也越大。因此，所有隱私數(shù)據(jù)的沖突度C 可以表示如下：

而在本次實(shí)驗(yàn)中，權(quán)重 w0，w1和 w2分別設(shè)置為0.55、0.3 和 0.15。

3.3 優(yōu)化目標(biāo)與約束條件

經(jīng)過對(duì)“數(shù)據(jù)訪問時(shí)間模型”和“數(shù)據(jù)隱私?jīng)_突模型”的分析和建模，這個(gè)基于數(shù)據(jù)隱私?jīng)_突的工作流和數(shù)據(jù)協(xié)同布局問題已經(jīng)被建模為一個(gè)多目標(biāo)優(yōu)化問題，其中，最小化“平均數(shù)據(jù)訪問時(shí)間”和“隱私數(shù)據(jù)沖突度”就設(shè)定為該優(yōu)化問題的兩個(gè)優(yōu)化目標(biāo)。因此，該優(yōu)化模型可以表示為：

另外，該優(yōu)化問題還需要滿足一定的約束條件，即任意一個(gè)節(jié)點(diǎn)的已用資源不能超過該節(jié)點(diǎn)的最大資源量，因此約束條件可以表示為：

4 問題優(yōu)化

在上一節(jié)，這個(gè)基于數(shù)據(jù)隱私?jīng)_突的工作流和數(shù)據(jù)協(xié)同布局問題已經(jīng)被建模為一個(gè)帶約束的多目標(biāo)優(yōu)化問題，而非支配排序差分進(jìn)化（Non-dominated Sorted Differential Evolution，NSDE）算法作為一個(gè)高效的多目標(biāo)優(yōu)化算法。在本節(jié)中，我們主要采用NSDE 算法來求解該多目標(biāo)優(yōu)化問題。首先，我們需要對(duì)問題進(jìn)行編碼，并生成初始種群作為第一代的父代種群。然后，基于父代種群，循環(huán)執(zhí)行變異，交叉和選擇操作，其中在選擇階段，采用快速的非支配排序和擁擠距離計(jì)算來選擇較好的個(gè)體保留給下一代。最后，將最佳個(gè)體作為問題的最終解。

4.1 編碼

在編碼階段，我們用實(shí)數(shù)表示每一個(gè)任務(wù)和輸入數(shù)據(jù)的布局策略，即相應(yīng)任務(wù)或數(shù)據(jù)的放置位置。因此，所有任務(wù)和輸入數(shù)據(jù)的布局策略可以編碼為一個(gè)集合 X={XT，XI}，其中表示 M個(gè)任務(wù)的布局策略表示P 個(gè)輸入數(shù)據(jù)的放置策略。此外，所有歷史數(shù)據(jù)的放置位置XH是固定的。

4.2 基于NSDE算法優(yōu)化協(xié)同布局問題

NSDE 算法是基于種群進(jìn)化的多目標(biāo)優(yōu)化算法。因此，我們首先需要初始化種群，生成第一代父代種群。

（1）初始化：假設(shè)種群的大小為NP，那么該初始種群可以表示為 X = {X0,X1,…,Xi,…,XNP-1}，其中 Xi= {x0,x1,…,xj,…,xM-1,xM,…,xM+P-1}是第 i 個(gè)個(gè)體，代表 M 個(gè)任務(wù)和P 個(gè)輸入數(shù)據(jù)的第i 種布局策略。xj作為個(gè)體Xi中的一個(gè)基因，代表某一個(gè)對(duì)應(yīng)的任務(wù)或者輸入數(shù)據(jù)的布局策略，其中，初始種群中所有的基因都是在一定范圍內(nèi)隨機(jī)生成。

（2）進(jìn)化：初始種群作為第一代父代種群，NSDE 基于父代種群開始執(zhí)行變異，交叉和選擇操作。首先，在變異階段，根據(jù)變異因子F，通過隨機(jī)選擇的兩個(gè)個(gè)體的差異向量與第三個(gè)體相結(jié)合來生成變異個(gè)體Hi，直至生成種群大小也為NP 的變異種群H={H0，H1，…，Hi，…，HNP-1}。其次，在交叉階段，根據(jù)交叉因子 CR，分別從變異個(gè)體Hi和父代個(gè)體Xi中選擇相應(yīng)基因組成交叉?zhèn)€體Ri，直至生成種群大小也為NP 的交叉種群R={R0，R1，…，Ri，…，RNP-1}。而在選擇階段，將父代種群X 和交叉種群R 合并為一個(gè)種群大小為2NP 的種群 Y={Y0，Y1，…，Yi，…，Y2NP-1}，再基于該種群執(zhí)行“非支配排序”和“擁擠度距離比較”操作，將種群Y 分解成多個(gè)支配層。最后，優(yōu)先將較好支配層中的個(gè)體和同一支配層中擁擠距離較好的個(gè)體保留給下一代種群X中，直到種群X 的大小為NP。

（3）迭代：NSDE 算法對(duì)種群 X 循環(huán)執(zhí)行變異、交叉和選擇操作，直至滿足終止條件，如達(dá)到最大進(jìn)化代數(shù)或結(jié)果收斂，最終獲得最優(yōu)個(gè)體作為該多目標(biāo)優(yōu)化問題的解。

5 結(jié)語

針對(duì)云數(shù)據(jù)中心的工作流和數(shù)據(jù)協(xié)同布局問題，本文基于云數(shù)據(jù)中心的Fat-tree 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和歷史數(shù)據(jù)布局的現(xiàn)狀，提出了一種基于NSDE 的工作流和數(shù)據(jù)協(xié)同布局方法（CPDE），重點(diǎn)考慮工作流對(duì)各類數(shù)據(jù)的平均訪問時(shí)間以及隱私數(shù)據(jù)沖突等問題，并基于不同規(guī)模的數(shù)據(jù)集，和常用的基于“貪心算法”的協(xié)同布局方法（CPG）進(jìn)行實(shí)驗(yàn)比較。通過實(shí)驗(yàn)對(duì)比分析，論證了本文提出的CPDE 方法在“平均數(shù)據(jù)訪問時(shí)間”和“隱私?jīng)_突度”兩個(gè)指標(biāo)上都優(yōu)于CPG 方法，具有比CPG 方法更佳的綜合性能。

而在未來的研究中，我們還將進(jìn)一步研究工作流的執(zhí)行時(shí)間和云數(shù)據(jù)中心的能耗與負(fù)載均衡等因素。另外，結(jié)合邊緣計(jì)算的優(yōu)點(diǎn)，考慮云數(shù)據(jù)中心和邊緣計(jì)算的結(jié)合，在這樣的“混合云”環(huán)境下考慮工作流和數(shù)據(jù)的協(xié)同布局問題。