Управление дисковой памятью системы хранения данных LHCb а основе прогноза популярности данных (1187433), страница 2
Текст из файла (страница 2)
Îñü Y âûðàæàåò ÷èñëî îáðàùåíèéê ôàéëó çà êàæäûé ïðîìåæóòîê âðåìåíè. Ïðåäñòàâëåííàÿ èñòîðèÿ îáðàùåíèé èñïîëüçóåòñÿ äëÿ ïîñòðîåíèÿ öåïè Ìàðêîâà, ÷òîáû ïðåäñêàçàòü ÷àñòîòó îáðàùåíèé âáóäóùåì. Êàê ïîêàçàíî íà ðèñóíêå 1, òîëüêî âûäåëåííàÿ îêíîì èñòîðèÿ îáðàùåíèé3Ðèñ. 1: Èñòîðèÿ îáðàùåíèé ê ôàéëó.èñïîëüçóåòñÿ äëÿ îáó÷åíèÿ ìîäåëè. Ïåðåìåùàÿ îêíî ñî âðåìåíåì ìîæíî ðåàëèçîâàòüîíëàéí ïðîãíîç ÷àñòîòû îáðàùåíèé ê ôàéëó.2) Ïðåäñêàçàòåëüíàÿ ìîäåëü: Èñïîëüçóÿ èñòîðèþ îáðàùåíèé äëÿ êàæäîãî ôàéëà,ñòðîèòñÿ ìîäåëü öåïè Ìàðêîâà, ÷òîáû ïðåäñêàçàòü ÷àñòîòó îáðàùåíèé â áóäóùåìäëÿ êàæäîãî îáúåêòà.
Äëÿ íà÷àëà, íåîáõîäèìî îïðåäåëèòü ÷èñëî ñîñòîÿíèé öåïèÌàðêîâà, è êàêîé èíòåðâàë ÷àñòîòû îáðàùåíèé äîëæåí ñîîòâåòñòâîâàòü êàæäîìóñîñòîÿíèþ. Íàïðèìåð, êàê ïîêàçàííî íà ðèñóíêå 1, åñëè ìàêñèìàëüíîå ÷èñëî îáðàùåíèé â òå÷åíèå îäíîãî ïðîìåæóòêà âðåìåíè ðàâíî 50, òî 50 ìîæíî ðàçäåëèòü íàäâà ïðîìåæóòêà è ïîñòðîèòü öåïü Ìàðêîâà, êîòîðàÿ áóäåò èìåòü òðè ñîñòîÿíèÿ: 0,(0, 25] and (25, 50] ñîîòâåòñòâåííî.
Åñëè â òå÷åíèå îäíîãî ïðîìåæóòêà âðåìåíè íå áóäåò íè îäíîãî îáðàùåíèÿ ê ôàéëó, òîãäà öåïü Ìàðêîâà áóäåò íàõîäèòüñÿ â ñîñòîÿíèè0. Åñëè ÷èñëî îáðàùåíèé áóäåò áîëüøå 0, íî ìåíüøå 25, òî òîãäà öåïü Ìàðêîâà áóäåòâ ñîñòîÿíèè 1, è òàê äàëåå. Äèàãðàììà ïåðåõîäîâ äëÿ öåïè Ìàðêîâà èçîáðàæåíà íàðèñóíêå 2.Çàòåì, èñòîðèÿ îáðàùåíèé ïðåîáðàçóåòñÿ â ïîñëåäîâàòåëüíîñòü ñîñòîÿíèé öåïèÌàðêîâà èñïîëüçóÿ îïðåäåëåííûå èíòåðâàëû çíà÷åíèé ÷èñëà îáðàùåíèé äëÿ êàæäîãî ñîñòîÿíèÿ.
Íàïðèìåð, ïîñëåäîâàòåëüíîñòü ñîñòîÿíèé äëÿ èñòîðèè îáðàùåíèé,ïîêàçàííîé íà ðèñóíêå 2 1, 1, 1, 1, 1, 0, 0... Íà îñíîâàíèè òàêîé ïîñëåäîâàòåëüíîñòèñîñòîÿíèé ìîæíî îïðåäåëèòü âåðîÿòíîñòè ïåðåõîäîâ ìåæäó êàæäûìè äâóìÿ ñîñòîÿíèÿìè öåïè Ìàðêîâà è ïîñòðîèòü ìàòðèöó ïåðåõîäà êàê ïîêàçàíî íèæå:p00 p01 p02T = p10 p11 p12 p20 p21 p22(1) ñîîòâåòñòâèè ñî ñâîéñòâàìè öåïåé Ìàðêîâà ïîëó÷àåì:limn→∞Tnπ 0 π1 π2= π 0 π1 π2 π 0 π1 π2(2)ãäå π =[π0 , π1 , π2 ] íàçûâàåòñÿ ñòàöèîíàðíûì ðàñïðåäåëåíèåì öåïè Ìàðêîâà.
Òàêæå, π ìîæíî íàéòè ñ ïîìîùüþ ëåâîãî ñîáñòâåííîãî âåêòîðà E ñ åäèíè÷íîé íîðìîé4Ðèñ. 2: Äèàãðàììà ïåðåõîäîâ äëÿ öåïè Ìàðêîâà.äëÿ ìàòðèöû ïåðåõîäàT:Eπ=Pi ei(3)ãäå ei - i-ûé ýëåìåíò ñîáñòâåííîãî âåêòîðà E. Òàê êàê ñòàöèîíàðíîå ðàñïðåäåëåíèå π îòðàæàåò âåðîÿòíîñòü òîãî, ÷òî êàæäîå ñîñòîÿíèå öåïè Ìàðêîâà áóäåò àêòèâíîâ áóäóùåì, ýòî ñâîéñòâî ìîæåò áûòü èñïîëüçîâàííî, ÷òîáû ïðåäñêàçàòü ÷èñëî îáðàùåíèé ê êàæäîìó ôàéëó.Èñïîëüçóÿ ïðåäñêàçàííûå ÷àñòîòû îáðàùåíèé ìîæíî ðàíæèðîâàòü ôàéëû òàê,÷òîáû ðàíã ïîêàçûâàë êàêèå îáúåêòû äîëæíû õðàíèòüñÿ èëè äîëæíû áûòü óäàëåíû ñ SSD äèñêîâ. Îäíàêî, äîëæíî áûòü ó÷òåíî òî, ÷òî äàæå åñëè ñòàöèîíàðíîåðàñïðåäåëåíèå ïîêàæåò, ÷òî ñîñòîÿíèå 1 áóäåò àêòèâíûì ñ áîëüøåé âåðîÿòíîñòüþ,÷åì ñîñòîÿíèå 2, ñîñòîÿíèå 2 âûðàæàåò áîëüøåå ÷èñëî îáðàùåíèé ê ôàéëó.
Ïîýòîìó,èñïîëüçóåòñÿ âçâåøåííàÿ ñóììà ñòàöèîíàðíîãî ðàñïðåäåëåíèÿ, ÷òîáû ðàíæèðîâàòüôàéëû ïî èõ çíà÷èìîñòè. Âåñà âûáèðàþòñÿ ïðîïîðöèîíàëüíûìè èíòåðâàëàì ÷èñëà îáðàùåíèé äëÿ êàæäîãî ñîñòîÿíèÿ öåïè Ìàðêîâà. Íàïðèìåð, åñëè ñòàöèîíàðíîåðàñïðåäåëåíèå π =[0.31, 0.56, 0.13], è âçÿòû âåñà [0, 10, 20] äëÿ òðåõ ñîñòîÿíèé öåïè, òîðàíã äëÿ ôàéëà âû÷èñëÿåòñÿ êàê rankobj = 0.31 × 0 + 0.56 × 10 + 0.13 × 20 = 8.2.
Òîãäà ðàíã îáúåêòà ìîæíî èñïîëüçîâàòü äëÿ îïðåäåëåíèÿ îïòèìàëüíîãî ðàñïðåäåëåíèÿäàííûõ â ñèñòåìå õðàíåíèÿ äàííûõ.2.1.4Ðàñïðåäåëåíèå äàííûõÒàê êàê ôàéëû ðàíæèðîâàííû ïî çíà÷èìîñòè, ñëåäóþùèé øàã - íàéòè òàêîå ðàñïðåäåëåíèå äàííûõ, êîòîðîå ìèíèìèçèðóåò âðåìÿ çàäåðæêè îáðàùåíèÿ ê äàííûì èáóäåò óäîâëåòâîðÿòü òðåáîâàíèÿì ïîëüçîâàòåëåé ê ñèñòåìå. Àâòîðû ðàáîòû ïîëàãàþò, ÷òî òðåáîâàíèÿ ïîëüçîâàòåëåé ìîæíî âûðàçèòü ÷åðåç óðàâíåíèÿ è íåðàâåíñòâà.Íàïðèìåð, èñïîëüçóÿ îáîçíà÷åíèÿ èç òàáëèöû 1, òðåáîâàíèå, ÷òîáû ìèíèìàëüíîå÷èñëî êîïèé äëÿ i-ãî ôàéëà ðàâíÿëîñü 3 ìîæíî çàïèñàòü êàê cpi > 3.5Òàáëèöà 1: Îáîçíà÷åíèå ñèìâîëîâ.NMcsidsifibijatieijcpiÎáùåå ÷èñëî äèñêîâÎáùåå ÷èñëî ôàéëîâÅìêîñòü i-ãî äèñêàÐàçìåð i-ãî îáúåêòà äàííûõÏðåäñêàçàííàÿ ÷àñòîòà îáðàùåíèé äëÿ i-ãî ôàéëàÏðîïóñêíàÿ ñïîñîáíîñòü ñîåäèíåíèÿ ìåæäó i-ûì è j -ûì äèñêàìèÏðîïóñêíàÿ ñïîñîáíîñòü i-ãî äèñêàÕðàíèòñÿ ëè i-ûé ôàéë íà j -îì äèñêå (0 èëè 1)Ìèíèìàëüíîå ÷èñëî êîïèé äëÿ ôàéëà iÇàäà÷ó ïîèñêà îïòèìàëüíîãî ðàñïðåäåëåíèÿ äàííûõ àâòîðû çàïèñûâàþò â âèäåçàäà÷è îïòèìèçàöèè:Ïîèñê ìàêñèìóìà âûðàæåíèÿ:Xfi × max[j ∈ N, atj × eij ](4)i∈Mñ îãðàíè÷åíèÿìè:Xeij = cpi , i ∈ M,(5)dsi ≤ csj , j ∈ N,(6)j∈NXi:eij =1 ýòîì ïðèìåðå âûðàæåíèå 4 âûðàæàåò æåëàíèå àâòîðîâ ðàñïðåäåëèòü ôàéëûìåæäó äèñêàìè òàê, ÷òîáû ìàêñèìèçèðîâàòü âçâåøåííóþ ñóììó ïðîïóñêíûõ ñïîñîáíîñòåé äèñêîâ, ãäå âåñà - ÷àñòîòà îáðàùåíèé.Ïåðâîå îãðàíè÷åíèå, âûðàæåíèå 5, îòîáðàæàåò òî, ÷òî ÷èñëî êîïèé ôàéëîâ çàäàåòñÿ ïîëüçîâàòåëåì.
Âòîðîå îãðàíè÷åíèå - íè îäèí äèñê íå ìîæåò ñîäåðæàòü áîëüøåäàííûõ, ÷åì åãî åìêîñòü.Òàêèì æå îáðàçîì ìîæíî âûðàçèòü áîëåå ñëîæíûå òðåáîâàíèÿ ïîëüçîâàòåëåé.2.1.5ÐåçóëüòàòûÀíàëèçèðóÿ èñòîðèþ îáðàùåíèé ê ðàçëè÷íûì ôàéëàì, àâòîðû âûÿñíèëè, ÷òî âñåîáúåêòû ìîæíî ðàçäåëèòü íà äâå êàòåãîðèè ïî èñòîðèè îáðàùåíèé ê íèì. Ê ïåðâîéêàòåãîðèè îòíîñÿòñÿ ôàéëû ñ ïîñòîÿííîé ÷àñòîòîé îáðàùåíèé ê íèì. Ôàéëû èç ýòîéêàòåãîðèè ÷àñòî èñïîëüçóþòñÿ íà ïðîòÿæåíèè âñåãî ñðîêà ñóùåñòâîâàíèÿ ôàéëà áåçñóùåñòâåííîé ðàçíèöû ìåæäó ìèíèìàëüíûì è ìàêñèìàëüíûì ÷èñëîì îáðàùåíèé êíèì. Íà ðèñóíêå 3 èçîáðàæåí ïðèìåð ôàéëà èç 1 êàòåãîðèè. Àëãîðèòìû ìàøèííîãîîáó÷åíèÿ, â ÷àñòíîñòè öåïè Ìàðêîâà, ïîçâîëÿþò äîñòè÷ü âûñîêîé òî÷íîñòè äëÿ òàêèõ îáúåêòîâ. Êî âòîðîé êàòåãîðèè îòíîñÿòñÿ ôàéëû, êîòîðûé èñïîëüçóþòñÿ î÷åíüðåäêî.
Îäíàêî, ÷èñëî îáðàùåíèé çà îäèí ïðîìåæóòîê âðåìåíè äëÿ òàêèõ ôàëîâ ìîæåò ïðèíèìàòü áîëüøèå çíà÷åíèÿ. Ïðèìåð ôàéëà èç âòîðîé êàòåãîðèè èçîáðàæåí íàðèñóíêå 4. Êàê ñîîáùàþò àâòîðû ðàáîòû, äëÿ òàêèõ ôàéëîâ î÷åíü òðóäíî ñäåëàòüäîñòàòî÷íî òî÷íûé ïðîãíîç ÷èñëà îáðàùåíèé, èñïîëüçóÿ ëþáîé àëãîðèòì ìàøèííîãîîáó÷åíèÿ, âêëþ÷àÿ öåïè Ìàðêîâà.Àâòîðû ñðàâíèâàþò ñðåäíþþ ïðîïóñêíóþ ñïîñîáíîñòü íà ÷òåíèå ôàéëîâ, êîòîðûå ìîæíî äîñòè÷ü ïðèìåíÿÿ èõ ïðåäñêàçàòåëüíóþ ìîäåëü íà îñíîâå öåïåé Ìàðêîâà6Ðèñ. 3: Èñòîðèÿ îáðàùåíèé 1ãî òèïà.è ïðèìåíÿÿ ìîäåëü ñëó÷àéíîãî âûáîðà.
Ìîäåëü ñëó÷àéíîãî âûáîðà çàêëþ÷àåòñÿ âòîì, ÷òî ñëó÷àéíî âûáèðàþòñÿ îáúåêòû äàííûõ (ôàéëîâ), êîòîðûå áóäóò õðàíèòüñÿíà SSD äèñêàõ. Òàê êàê ÷èñëî SSD äèñêîâ îãðàíè÷åíî, àâòîðû ðàññ÷èòûâàþò ñðåäíþþ ïðîïóñêíóþ ñïîñîáíîñòü íà ÷òåíèå äëÿ ñèñòåì ñ äîëåé SSD äèñêîâ îò 2,5% äî50%. Áîëåå òîãî, àâòîðû ïîëàãàþò, ÷òî ïðîïóñêíàÿ ñïîñîáíîñòü SSD äèñêîâ íà ÷òåíèåðàâíà 550 ÌÁ/ñ è äëÿ HDD äèñêîâ - 120 ÌÁ/ñ. Ðèñóíîê 5 ïîêàçûâàåò, ÷òî ïðåäñòàâëåííûé àâòîðàìè ðàáîòû ìåòîä äåìîíñòðèðóåò ñâîþ ýôôåêòèâíîñòü ïî ñðàâíåíèþ ñìîäåëüþ ñëó÷àéíîãî âûáîðà.2.2Ñèñòåìà ïåðåðàñïðåäåëåíèÿ äàííûõ äëÿ ðàñïðåäåëåííîéñèñòåìû õðàíåíèÿ äàííûõ ATLAS ðàáîòå A Popularity-Based Prediction and Data Redistribution Tool for ATLAS DistributedData Management[4,5] àâòîðû ïðåäñòàâëÿþò ñèñòåìó äëÿ ïðåäñêàçàíèÿ ïîïóëÿðíîñòèäàííûõ â ñèñòåìàõ ñ áîëüøèì îáúåìîì äàííûõ, òàêèõ êàê ñèñòåìà ðàñïðåäåëåííîãîõðàíåíèÿ äàííûõ ATLAS.
Èñïîëüçóÿ ïîëó÷åííûé ïðîãíîç ïîïóëÿðíîñòè, âîçìîæíîïåðåðàñïðåäåëèòü äàííûå â ñèñòåìå äëÿ óìåíüøåíèÿ âðåìåíè çàäåðæêè äëÿ çàäà÷,êîòîðûå èñïîëüçóþò ýòè äàííûå. Ïðîãíîç ïîïóëÿðíîñòè ïðîèçâîäèòñÿ ïî èñòîðèèîáðàùåíèé ê äàííûì ñ ïðèìåíåíèåì èñêóññòâåííûõ íåéðîííûõ ñåòåé[1,2].2.2.1ÂâåäåíèåATLAS - îäèí èç ÷åòûðåõ îñíîâíûõ ýêñïåðèìåíòîâ Áîëüøîãî Àäðîííîãî Êîëëàéäåðà.  ðàñïðåäåëåííîé ñèñòåìå õðàíåíèÿ äàííûõ ATLAS õðàíÿòñÿ îãðîìíûå îáúåìûäàííûõ ñ äåòåêòîðà è äàííûõ ìîäåëèðîâàíèÿ ôèçè÷åñêèõ ïðîöåññîâ. Íà ìîìåíò íàïèñàíèÿ ðàáîòû ñèñòåìà ñîäåðæàëà áîëåå 150 ÏÁ ýêñïåðèìåíòàëüíûõ äàííûõ, êîòîðûå ðàñïðåäåëåíû íà áîëåå ÷åì 150 ñàéòàõ ïî âñåìó ìèðó. ñâîåé ðàáîòå àâòîðû ïðåäñòàâëÿþò íîâûé ñïîñîá àâòîìàòè÷åñêè è äèíàìè÷åñêè óäàëÿòü è äîáàâëÿòü íîâûé êîïèè äàííûõ â ñèñòåìå â ñîîòâåòñòâèè ñ áóäóùåéïîïóëÿðíîñòüþ äàííûõ. Äàííûé ñïîñîá ðåàëèçîâàí â òðåõ ÷àñòÿõ.
 ïåðâîé ÷àñòèàíàëèçèðóåòñÿ èñòîðèÿ îáðàùåíèé ê äàííûì, ÷òîáû ñäåëàòü ïðåäñêàçàòü ÷èñëî âîç7Ðèñ. 4: Èñòîðèÿ îáðàùåíèé 2ãî òèïà.ìîæíûõ îáðàùåíèé â áëèæàéøåì áóäóùåì. Çàòåì, èñïîëüçóÿ ïîëó÷åííûé ïðîãíîç,äàííûå â ñèñòåìå ïåðåðàñïðåäåëÿþòñÿ ïóòåì äîáàâëåíèÿ èëè óäàëåíèÿ êîïèé ôàéëîâ. Êàê óòâåðæäàþò àâòîðû, î÷åíü òðóäíî îïðåäåëèòü ïðåèìóùåñòâà òàêèõ ìåòîäîâíà æèâûõ ñèñòåìàõ, ãäå øàáëîí íàãðóçêè íà ñèñòåìó íèêîãäà íå ïîâòîðÿåòñÿ. Ïîýòîìó, òðåòüÿ ÷àòü èõ ðàáîòû ïîñâÿùåíà ìîäåëèðîâàíèþ ñèñòåìû ðàñïðåäåëåííîãîõðàíåíèÿ äàííûõ ñ ïîâòîðÿþùèìñÿ øàáëîíîì íàãðóçêè äëÿ îïðåäåëåíèÿ êà÷åòñâàèõ ìåòîäà.Äî ïðèìåíåíèÿ ïðåäëîæåííîãî àâòîðàìè ìåòîäà, ðàñïðåäåëåíèå äàííûõ â ñèñòåìåíîñèëî ñòàòè÷åñêèé õàðàêòåð, ÷òî ïðèâîäèëî â áîëüøîìó ÷èñëó íåâîñòðåáîâàííûõêîïèé ôàéëîâ â ñèñòåìå.
Èäåÿ ïðåäëîæåííîãî ìåòîäà â òîì, ÷òîáû àâòîìàòè÷åñêèîïðåäåëÿòü íåâîñòðåáîâàííûå ôàéëû è äèíàìè÷åñêè îñâîáîæäàòü ìåñòî äëÿ áîëååïîïóëÿðíûõ ôàéëîâ. Äåëàåòñÿ îáùåå ïðåäïîëîæåíèå, ÷òî ïîëüçà îò áîëüøåãî ÷èñëàêîïèé ôàëîâ çàêëþ÷àåòñÿ â òîì, ÷òî: 1) óìåíüøàåòñÿ âðåìÿ îæèäàíèÿ ïîëüçîâàòåëåé,ïåðåä òåì êàê èç çàäà÷è ïîëó÷àò äàííûå äëÿ äàëüíåéøåé ðàáîòû, 2) ðåñóðñû ñèñòåìûèñïîëüçóþòñÿ áîëåå ýôôåêòèâíî.2.2.2Ïðîãíîç ïîïóëÿðíîñòè×òîáû ïðîâîäèòü ðàñïðåäåëåíèå äàííûõ â ñèñòåìå ëó÷øå, íåîáõîäèìû çíàíèÿ î áóäóùåì ÷èñëå îáðàùåíèé ê äàííûì. Ò.å. íåîáõîäèìî ñäåëàòü ïðîãíîç ÷èñëà îáðàùåíèéâ áóäóùåì. Ïðåäïîëàãàåòñÿ, ÷òî èñòîðèþ ïîâåäåíèÿ ïîëüçîâàòåëåé ìîæíî èñïîëüçîâàòü äëÿ ïðîãíîçà ïîïóëÿðíîñòè äàííûõ â áóäóùåì. Ñóùåñòâóåò ìíîæåñòâî ñïîñîáîâñäåëàòü íåîáõîäèìû ïðîãíîç.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
