Управление дисковой памятью системы хранения данных LHCb а основе прогноза популярности данных (1187433), страница 4
Текст из файла (страница 4)
Êëàññèôèêàòîð - ýòî àëãîðèòì ìàøèííîãî îáó÷åíèÿ ñ ó÷èòåëåì[1]è ñîñòîèò èç íåñêîëüêèõ øàãîâ. Ñëåäóþùèå ïîäñåêöèè îïèñûâàþò êàæäûé øàã îïðåäåëåíèÿ ïîïóëÿðíîñòè äàííûõ.5.2.1Ðàçìåòêà ôàéëîâÒàê êàê êëàññèôèêàòîð - ýòî àëãîðèòì ìàøèííîãî îáó÷åíèÿ ñ ó÷èòåëåì, òî êàæäûéôàéë äîëæåí áûòü ðàçìå÷åí íà ïîïóëÿðíûé è íåïîïóëÿðíûé. Âðåìåííûå ðÿäû èñòîðèè îáðàùåíèé ê ôàéëàì ñèëüíî ðàçðåæåíû, ïîýòîìó ïîñëåäíèå 26 íåäåëü èñòîðèèîáðàùåíèé èñïîëüçóþòñÿ äëÿ ðàçìåòêè äàííûõ.
Åñëè ôàéë íå èñïîëüçóåòñÿ â ïîñëåäíèå 26 íåäåëü, ìû ïîìå÷àåì åãî êàê íåïîïóëÿðíûé è äàåì ìåòêó 1.  ïðîòèâíîì14ñëó÷àå, ìû ïîìå÷àåì ôàéë êàê ïîïóëÿðíûé è äàåì åìó ìåòêó 0. Ýòè ìåòêè îïðåäåëÿþò êëàññ ôàéëà (0 äëÿ ïîïóëÿðíûõ, 1 äëÿ íåïîïóëÿðíûõ). Íà ðèñóíêàõ 10 è 11ïðåäñòàâëåíû ôàéëû èç êàæäîãî êëàññà.Ðèñ. 10: Âðåìåííîé ðÿä ñ ìåòêîé 0.Ðèñ. 11: Âðåìåííîé ðÿä ñ ìåòêîé 1.5.2.2Ïðåäîáðàáîòêà äàííûõÌåòàäàííûå ôàéëîâ èñïîëüçóþòñÿ êàê âõîäíûå ïðèçíàêè äëÿ êëàññèôèêàòîðà. Áûëèâû÷èñëåíû íîâûå ïðèçíàêè, êîòîðûå èñïîëüçîâàëèñü âìåñòå ñ ñóùåñòâóþùèìè. Ýòèíîâûå ïðèçíàêè îïèñûâàþò ôîðìó âðåìåííîãî ðÿäà äëÿ èñòîðèè îáðàùåíèé ê ôàéëó.Òàê êàê ïîñëåäíèå 26 íåäåëü èñòîðèè îáðàùåíèé èñïîëüçóþòñÿ äëÿ ðàçìåòêè ôàéëîâ,òî äëÿ âû÷èñëåíèÿ íîâûõ ïðèçíàêîâ èñïîëüçóþòñÿ òîëüêî ïåðâûå 78 íåäåëü.
Èìåíàíîâûõ ïðèçíàêîâ: nb_peaks, last_zeros, inter_max, inter_mean, inter_std, inter_rel,mass_center, mass_center_sqrt, mass_moment and r_moment.15Nb_peaks - ÷èñëî íåäåëü, â òå÷åíèå êîòîðûõ ê ôàéëó îáðàùàëèñü. Last_zeros- ÷èñëî íåäåëü ñ òåõ ïîð, êàê ê ôàéëó â ïîñëåäíèé ðàç îáðàùàëèñü. Inter_max,inter_mean, inter_std âûðàæàþò ìàêñèìàëüíîå çíà÷åíèå, ñðåäíåå çíà÷åíèå è ñòàíäàðòíîå îòêëîíåíèå ÷èñëà íåäåëü ìåæäó ïîñëåäîâàòåëüíûìè íåäåëÿìè ñ íåíóëåâûì÷èñëîì îáðàùåíèé. Inter_rel - îòíîøåíèå inter_std ê inter_mean. Mass_center âûðàæàåò öåíòð ìàññ âðåìåííîãî ðÿäà ôàéëà, â êîòîðîì ìàññà - ýòî ÷èñëî îáðàùåíèé ê ôàéëó çà êàæäóþ íåäåëþ, à êîîðäèíàòà - íîìåð íåäåëè. Mass_center_sqrt,mass_moment è r_moment àíàëîãè÷íû mass_center, íî ìàññà è êîîðäèíàòà áåðóòñÿñ ðàçíûìè ñòåïåíÿìè.Ýòè íîâûå ïðèçíàêè ñóùåñòâåííî óâåëè÷èâàþò êà÷åñòâî êëàññèôèêàöèè.5.2.3Îáó÷åíèå êëàññèôèêàòîðàÍîâûå ïðèçíàêè, ìåòàäàííûå ôàéëîâ è èõ ìåòêè èñïîëüçóþòñÿ äëÿ îáó÷åíèÿ êëàññèôèêàòîðà.
 êà÷åñòâå êëàññèôèêàòîðà èñïîëüçóåòñÿ ãðàäèåíòíûé áóñòèíã[1] çà åãîâûñîêîå êà÷åñòâî êëàññèôèêàöèè, áûñòðóþ ðàáîòó è îòñóòñòâèå ïåðåîáó÷åíèÿ. Äëÿîáó÷åíèÿ êëàññèôèêàòîðà èñïîëüçîâàëñÿ ìåòîä ïåðåêðåñòíîé ïðîâåðêè ñ 10 ÷àñòÿìè(k-fold cross-validation)[1]. Âñå ôàéëû áûëè ðàçáèòû íà 10 ÷àñòåé. Êëàññèôèêàòîðîáó÷àëñÿ íà 9 ÷àñòÿõ äàííûõ, à çàòåì èñïîëüçîâàëñÿ äëÿ ïðåäñêàçàíèÿ âåðîÿòíîñòèïîëó÷èòü ìåòêó 1 äëÿ 10-îé ÷àñòè äàííûõ. Íà ðèñóíêå 12 èçîáðàæåíî ðàñïðåäåëåíèåâåðîÿòíîñòè äëÿ êàæäîãî èç êëàññîâ.Ðèñ.
12: Ðàñïðåäåëåíèå âåðîÿòíîñòè ïîëó÷èòü ìåòêó 1 äëÿ êàæäîãî êëàññà ôàéëîâ.5.2.4Îïðåäåëåíèå ïîïóëÿðíîñòè äàííûõÎïèñàííàÿ âûøå âåðîÿòíîñòü ïðåîáðàçóåòñÿ â ïîïóëÿðíîñòü òàê, ÷òîáû ïîïóëÿðíîñòü äëÿ êëàññà ñ ìåòêîé 1 áûëà ðàâíîìåðíî ðàñïðåäåëåíà. ×åì áëèæå ïîïóëÿðíîñòü ê 1, òåì âûøå âåðîÿòíîñòü òîãî, ÷òî ôàéë íå áóäåò èñïîëüçîâàí â áóäóùåì.Ò.å.
âû÷èñëåííàÿ ïîïóëÿðíîñòü îïðåäåëÿåò àíòèïîïóëÿðíîñòü ôàéëà. Òàêîé ñòðàííûé âûáîð ñâÿçàí ñ òåì, ÷òîáû ïåðâûå íà óäàëåíèå ôàéëû èìåëè áîëüøóþ âåëè÷èíóìåòðèêè. Ðèñóíîê 13 äåìîíñòðèðóåò ðàñïðåäåëåíèå ïîïóëÿðíîñòè äëÿ êàæäîãî êëàññà ôàéëîâ.16Ðèñ. 13: Ðàñïðåäåëåíèå ïîïóëÿðíîñòè äëÿ êàæäîãî êëàññà ôàéëîâ.5.3Ìîäóëü Data Intensity PredictorÊàê áûëî íàïèñàíî âûøå, ïîïóëÿðíîñòü äàííûõ âûðàæàåò âåðîÿòíîñòü òîãî, ÷òîôàéë áóäåò áåñïîëåçíûì â áóäóùåì. Âòîðîé âàæíîé õàðàêòåðèñòèêîé ÿâëÿåòñÿ èíòåíñèâíîñòü îáðàùåíèÿ ê ôàéëó. Ñóùåñòâóåò ìíîæåñòâî àëãîðèòìîâ àíàëèçà âðåìåííûõ ðÿäîâ[2] äëÿ ïðåäñêàçàíèÿ áóäóùèõ çíà÷åíèé âðåìåííûõ ðÿäîâ.
Òàê êàêáîëüøàÿ ÷àñòü âðåìåííûõ ðÿäîâ â äàííîé ðàáîòå ñèëüíî ðàçðÿæåíà, ñëîæíûå ïàðàìåòðè÷åñêèå ìåòîäû, òàêèå êàê ïîëèíîìèàëüíàÿ ðåãðåññèÿ[1], àâòîðåãðåññèÿ[1,2],ARMA[2], ARIMA[2], èñêóññòâåííûå íåéðîííûå ñåòè[1] è äðóãèå íå ïîäõîäÿò äëÿ ýòîéçàäà÷è.  ýòîé ñåêöèè îïèñûâàåòñÿ ïðèìåíåíèå äâóõ íåïàðàìåòðè÷åñêèõ ìîäåëåé[1]äëÿ ïðîãíîçà èíòåíñèâíîñòåé îáðàùåíèé ê ôàéëàì. Ýòèìè ìåòîäàìè ÿâëÿþòñÿ ìåòîäÿäåðíîãî ñãëàæèâàíèÿ Íàäàðàÿ-Âàòñîíà[1] è ìåòîä ñêîëüçÿùåãî ñðåäíåãî[1,2].5.3.1Ìåòîä ÿäåðíîãî ñãëàæèâàíèÿ Íàäàðàÿ-ÂàòñîíàÏóñòü òî÷êè (x1 , y1 ), (x2 , y2 ), ..., (xl , yl ) ïðåäñòàâëÿþò âðåìåííîé ðÿä è X l = {x1 , x2 , ..., xl }.Òîãäà, ôîðìóëà ÿäåðíîãî ñãëàæèâàíèÿ Íàäàðàÿ-Âàòñîíà [1]:Pllŷh (x; X ) =ãäåρ(x,xi )i=1 yi K( h ),Plρ(x,xi )K()i=1h(7)ŷh (x; X l ) - çíà÷åíèå âðåìåííîãî ðÿäà â òî÷êå x ïîñëå ÿäåðíîãî ñãëàæèâàíèÿíà çíà÷åíèÿõ X l ,2i)i)K( ρ(x,x) = exp(− (x−x) - RFB ÿäðî ñãëàæèâàíèÿ,h2h2h - øèðèíà îêíà ñãëàæèâàíèÿ.Äëÿ âûáîðà îïòèìàëüíîãî îêíà ñãëàæèâàíèÿ áûë âûáðàí ìåòîä Leave-One-Out [1]:lLOO(h, X ) =lX(ŷh (xi ; X l \ {xi }) − yi )2 7→ minhi=1(8)Ôîðìóëà ÿäåðíîãî ñãëàæèâàíèÿ Íàäàðàÿ-Âàòñîíà [1] ñ LOO [1] îïòèìèçàöèåé øèðèíû îêíà ñãëàæèâàíèÿ ïðèìåíÿåòñÿ íà âðåìåííûõ ðÿäàõ èñòîðèè îáðàùåíèé ê ôàé17ëàì.
Ìàêñèìàëüíàÿ øèðèíà îêíà ñãëàæèâàíèÿ áûëà âçÿòà â 30 íåäåëü. Íà ðèñóíêå14 èçîáðàæåí ïðèìåð âðåìåííîãî ðÿäà ïîñëå ïðîöåäóðû ÿäåðíîãî ñãëàæèâàíèÿ.5.3.2Ìåòîä ñêîëüçÿùåãî ñðåäíåãîÍà ñëåäóþùåì øàãå âû÷èñëÿåòñÿ ñêîëüçÿùåå ñðåäíåå[1,2] äëÿ äîïîëíèòåëüíîãî ñãëàæèâàíèÿ âðåìåííûõ ðÿäîâ. Ïóñòü òî÷êè (x1 , y1 ), (x2 , y2 ), ..., (xl , yl ) ïðåäñòàâëÿþò âðåìåííîé ðÿä ïîñëå ÿäåðíîãî ñãëàæèâàíèÿ. Òîãäà, ñêîëüçÿùåå ñðåäíåå âû÷èñëÿåòñÿñëåäóþùèì îáðàçîì:Pŷk =ki=k−wyiw(9)ãäå w - øèðèíà ñêîëüçÿùåãî îêíà.Øèðèíà ñêîëüçÿùåãî îêíà âûáðàíà òàê, ÷òîáû 90% âñåõ âðåìåííûõ ðÿäîâ ñ îäèíàêîâûìè çíà÷åíèÿìè nb_peaks èìåëè çíà÷åíèÿ inter_max ìåíüøå ëèáî ðàâíûìèøèðèíå îêíà.Ñêîëüçÿùåå ñðåäíåå â ìîìåíò xi ïðåäñòàâëÿåò çíà÷åíèå èíòåíñèâíîñòè îáðàùåíèÿê ôàéëó â ýòîò ìîìåíò. Ñàìûé ïðîñòîé ñïîñîá ïðåäñêàçàòü áóäóùåå çíà÷åíèå âðåìåííîãî ðÿäà - ýòî âçÿòü â êà÷åñòâå áóäóùåãî çíà÷åíèÿ ðÿäà çíà÷åíèå â ïîñëåäíåéòî÷êå íàáëþäåíèÿ (ñòàòè÷åñêàÿ ìîäåëü ïðîãíîçà â ðàáîòå [4]).
Ïðèìåð ñêîëüçÿùåãîñðåäíåãî è ïðåäñêàçàííîãî çíà÷åíèÿ èíòåíñèâíîñòè îáðàùåíèé ê ôàéëó ïðåäñòàâëåííà ðèñóíêå 14.Ðèñ. 14: Ïðèìåð âðåìåííîãî ðÿäà ïîñëå ïðèìåíåíèÿ ôîðìóëû ÿäåðíîãî ñãëàæèâàíèÿÍàäàðàÿ-Âàòñîíà è âû÷èñëåíèÿ ñêîëüçÿùåãî ñðåäíåãî.5.4Ìîäóëü Data Placement Optimizer ýòîé ñåêöèè îïèñûâàåòñÿ ñïîñîá îïðåäåëåíèÿ òîãî, êàêèå ôàéëû äîëæíû õðàíèòüñÿ íà æåñòêèõ äèñêàõ è ñêîëüêî êîïèé îíè äîëæíû èìåòü, èñïîëüçóÿ ïîïóëÿðíîñòüè ïðåäñêàçàííîå çíà÷åíèå èíòåíñèâíîñòè îáðàùåíèé ê ôàéëàì.
Ïî ïðè÷èíå òîãî,÷òî äèñêîâîå ïðîñòðàíñòâî áîëåå äîðîãîå, ÷åì ïðîñòðàíñòâî ìàãíèòíûõ ëåíò, ìû õîòèì çàíèìàòü êàê ìîæíî ìåíüøå äèñêîâîãî ïðîñòðàíñòâà. Ñ äðóãîé ñòîðîíû, êðàéíåíåæåëàòåëüíî óäàëèòü ñ æåñòêîãî äèñêà ôàéëû, êîòîðûå áóäóò âîñòðåáîâàíû â áóäóùåì. Áîëåå òîãî, ìû õîòèì õðàíèòü íàèáîëåå âîñòðåáîâàííûå ôàéëû ñ áîëüøèì÷èñëîì êîïèé, ÷òîáû óìåíüøèòü ñðåäíåå âðåìÿ äîñòóïà ê äàííûì.18Îïèñàííûå âûøå òðåáîâàíèÿ îòîáðàæåíû â ñëåäóþùåé ôóíêöèè ïîòåðü:L = CdisknXinSi (Rpi + αnXXIi)δi + CtapeSi (1 − δi ) + CmissSi mi ,Rpiii(10)Cdisk - öåíà 1 Ãá æåñòêîãî äèñêà,Ctape - öåíà 1 Ãá ìàãíèòíûõ ëåíò,Cmiss - öåíà âîññòàíîâëåíèÿ 1 Ãá äàííûõ ñ ìàãíèòíûõ ëåíò íà äèñê,α - øòðàô çà ìàëîå ÷èñëî êîïèé,Si - ðàçìåð îäíîé êîïèè i ôàéëà,Rpi - ÷èñëî êîïèé i ôàéëà,Ii - ïðåäñêàçàííàÿ èíòåíñèâíîñòü îáðàùåíèÿ ê i ôàéëó;δi - ðàâíî 1 åñëè i ôàéë íà äèñêå, 0 - èíà÷å;mi - ðàâíî 1 åñëè i ôàéë áûë âîññòàíîâëåí ñ ìàãíèòíûõ ëåíò íà äèñê.Ïåðâîå ñëàãàåìîå â ôóíêöèè ïîòåðü âûðàæàåò öåíó õðàíåíèÿ ôàéëîâ íà æåñòêèõäèñêàõ.
Âòîðîå ñëàãàåìîå - öåíà õðàíåíèÿ ôàéëîâ íà ìàãíèòíûõ ëåíòàõ. Ïîñëåäíååñëàãàåìîå ðàâíî öåíå îøèáîê, êîãäà ôàéë áûë óäàëåí ñ æåñòêîãî äèñêà, íî çàòåìáûë èñïîëüçîâàí.Âûðàæåíèå â ñêîáêàõ â ïåðâîì ñëàãàåìîì ôóíêöèè ïîòåðü èñïîëüçóåòñÿ, ÷òîáûîïðåäåëèòü îïòèìàëüíîå ÷èñëî êîïèé ôàéëîâ íà äèñêàõ, èñïîëüçóÿ ïðåäñêàçàííûåçíà÷åíèÿ èíòåíñèâíîñòåé îáðàùåíèé ê âðåìåííûì ðÿäàì. Îïòèìàëüíîå ÷èñëî êîïèéôàéëà ñ ïðåäñêàçàííîé èíòåíñèâíîñòüþ îáðàùåíèé Ii è äëÿ çíà÷åíèÿ α îïðåäåëÿåòñÿâûðàæåíèåì:p(11)Rpi_optimal = αIi ,Íà ðèñóíêå 15 ïðåäñòàâëåíà çàâèñèìîñòü îïòèìàëüíîãî ÷èñëà êîïèé äëÿ ôàéëà îòåãî çíà÷åíèÿ ïðåäñêàçàííîé èíòåíñèâíîñòè îáðàùåíèé è äëÿ ðàçëè÷íûõ çíà÷åíèéàëüôà. Íàïðèìåð, ïðåäïîëîæèì, ÷òî ïðåäñêàçàííàÿèíòåíñèâíîñòü I = 10 îáðàùåíèé√√â íåäåëþ è α = 0.5.
Òîãäà Rpoptimal = αI = 0.5 ∗ 10 = 2.24 ≈ 2 êîïèé.Ðèñ. 15: Çàâèñèìîñòü îïòèìàëüíîãî ÷èñëà êîïèé ôàéëà (Rp) îò ïðåäñêàçàííîãî çíà÷åíèÿ èíòåíñèâíîñòè îáðàùåíèÿ ê ôàéëó (I ) è α.19Çíà÷åíèå δi â ôóíêöèè ïîòåðü çàâèñèò îò ïîðîãîâîãî çíà÷åíèÿ ïîïóëÿðíîñòè ôàéëà. Ôàéë ñî çíà÷åíèåì ïîïóëÿðíîñòè ðàâíûì èëè áîëüøèì, ÷åì ïîðîãîâîå çíà÷åíèåóäàëÿþòñÿ ñ æåñòêîãî äèñêà (δi = 0). Çíà÷åíèå mi - ýòî ïðîèçâåäåíèå 1 − δi è ìåòêèêëàññà ith ôàéëà.Îïòèìèçàöèÿ ôóíêöèè ïîòåðü ñîñòîèò â òîì, ÷òîáû íàéòè òàêèå çíà÷åíèÿ ïîðîãîâîãî çíà÷åíèÿ ïîïóëÿðíîñòè äàííûõ è îïòèìàëüíûå çíà÷åíèÿ êîïèé ôàéëîâ, êîòîðûåäîñòàâëÿþò ôóíêöèè ïîòåðü ìèíèìóì.6Ñðàâíåíèå àëãîðèòìîâ6.1LRU àëãîðèòì ýòîé ðàáîòå ìû ïðèâîäèì ñðàâíåíèå íàøåé ðåêîìåíäàòåëüíîé ñèñòåìû è LastRecently Used (LRU) àëãîðèòìà.
LRU àëãîðèòì ñìîòðèò íà ïîñëåäíèå íàáëþäåíèÿ âèñòîðèè îáðàùåíèé ê ôàéëó è ïðèíèìàåò ðåøåíèå î òîì, êàêèå ôàéëû äîëæíû áûòüóäàëåíû ñ äèñêà.  äàííîé ðàáîòå âðåìåííûå ðÿäû ïåðâûõ 78 íåäåëü èñòîðèè îáðàùåíèé ê ôàéëàì èñïîëüçîâàëèñü êàê âõîäíûå äàííûå äëÿ àëãîðèòìà. Ïîñëåäíèå 26íåäåëü èñòîðèè èñïîëüçîâàëèñü äëÿ èçìåðåíèÿ êà÷åñòâà àëãîðèòìà. Òîãäà, åñëè ôàéëíå èñïîëüçîâàëñÿ â òå÷åíèå ïîñëåäíèõ N íåäåëü (ñ (78 − N )-îé ïî 78-óþ), òî ýòîòôàéë óäàëÿþò ñ äèñêà. ×èñëî êîïèé íå ìåíÿåòñÿ, ïî ñðàâíåíèþ ñ ïåðâîíà÷àëüíûì÷èñëîì êîïèé.6.2Âðåìÿ äîñòóïà ê äàííûìÂðåìÿ äîñòóïà ê äàííûì îöåíèâàåì âðåìåíåì çàãðóçêè âñåõ ôàéëîâ âñåìè ïîëüçîâàòåëÿìè:T =nXi=1Ii∗ Si tdisk α(Rpi )δi+nX(Ktape + Si ttape )mi +i=1nXIi∗ Si tdisk mi(12)i=1ãäå α(Rpi ) = 0.05 + Rp1 itdisk - ñðåäíåå âðåìÿ çàãðóçêè 1 Ãá äàííûõ ñ äèñêà,ttape - ñðåäíåå âðåìÿ çàãðóçêè 1 Ãá äàííûõ ñ ìàãíèòíûõ ëåíò íà äèñê,Ktape - êîíñòàíòíîå âðåìÿ, íåîáõîäèìîå äëÿ âîññòàíîâëåíèÿ ôàéëà ñ ìàãíèòíîéëåíòû íà äèñê,Ii∗ - ñðåäíåå ÷èñëî îáðàùåíèé (çàãðóçîê) ê ôàéëó çà íåäåëþ,Si - ðàçìåð îäíîé êîïèè i ôàéëà,Rpi - ÷èñëî êîïèé i ôàéëà,δi - ðàíî 1, åñëè i ôàéë íà äèñêå, èíà÷å - 0,mi (îøèáêè êëàññèôèêàöèè) - ðàâíî 1, åñëè i ôàéë áûë âîññòàíîâëåí ñ ëåíòûíà äèñê.Ïåðâîå ñëàãàåìîå âûðàæåíèÿ äëÿ âðåìåíè çàãðóçêè - âðåìÿ çàãðóçêè âñåõ ôàéëîâñ æåñòêèõ äèñêîâ âñåìè ïîëüçîâàòåëÿìè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
