Karibu miaka 9 iliyopita Cloudflare ilikuwa kampuni ndogo, na sikuifanyia kazi, nilikuwa mteja tu. Mwezi mmoja baada ya kuzindua Cloudflare, nilipokea arifa kwamba tovuti yangu DNS haionekani kufanya kazi. Cloudflare imefanya mabadiliko kwa , na kulikuwa na DNS iliyovunjika.
Mara moja nilimwandikia Matthew Prince na kichwa "DNS yangu iko wapi?" na akajibu jibu refu lililojaa maelezo ya kiufundi), ambayo nilijibu:
Kutoka kwa: John Graham-Cumming
Tarehe: Oktoba 7, 2010, 9:14
Mada: Re: DNS yangu iko wapi?
Kwa: Mathayo PrinceRipoti nzuri, asante. Nitapiga simu ikiwa kuna shida. Pengine inafaa kuandika chapisho kuhusu hili mara tu umekusanya taarifa zote za kiufundi. Nadhani watu watafurahia hadithi ya wazi na ya uaminifu. Hasa ikiwa utaambatisha grafu kwake ili kuonyesha jinsi trafiki imekua tangu kuzinduliwa.
Nina ufuatiliaji mzuri kwenye tovuti yangu, na ninapokea SMS kuhusu kila kushindwa. Ufuatiliaji unaonyesha kuwa kushindwa kulitokea kutoka 13:03:07 hadi 14:04:12. Uchunguzi unafanywa kila dakika tano.
Nina hakika utaijua. Una uhakika hauitaji mtu wako mwenyewe huko Uropa? 🙂
Naye akajibu:
Kutoka kwa Mathayo Prince
Tarehe: Oktoba 7, 2010, 9:57
Mada: Re: DNS yangu iko wapi?
Kwa: John Graham-CummingAsante. Tulimjibu kila aliyeandika. Niko njiani kuelekea ofisini sasa na tutaandika kitu kwenye blogu au tubandike chapisho rasmi kwenye ubao wetu wa matangazo. Nakubali kabisa, uaminifu ndio kila kitu.
Sasa Cloudflare ni kampuni kubwa sana, ninaifanyia kazi, na sasa sina budi kuandika kwa uwazi kuhusu makosa yetu, matokeo yake na matendo yetu.
Matukio ya Julai 2
Mnamo tarehe 2 Julai tulizindua sheria mpya katika Kanuni Zinazodhibitiwa za WAFs kutokana na hilo kwenye kila processor core usindikaji trafiki ya HTTP/HTTPS kwenye mtandao wa Cloudflare duniani kote. Tunaboresha mara kwa mara sheria zinazodhibitiwa za WAF ili kukabiliana na udhaifu na vitisho vipya. Mnamo Mei, kwa mfano, tuliharakisha ili kulinda dhidi ya hatari kubwa katika SharePoint. Jambo zima la WAF yetu ni uwezo wa kupeleka sheria haraka na kimataifa.
Kwa bahati mbaya, sasisho la Alhamisi iliyopita lilikuwa na usemi wa kawaida ambao ulipoteza rasilimali nyingi sana za HTTP/HTTPS CPU kwa kurudi nyuma. Wakala wetu mkuu, CDN, na vitendaji vya WAF viliteseka kwa sababu hiyo. Grafu inaonyesha kuwa rasilimali za kichakataji za kuhudumia trafiki ya HTTP/HTTPS hufikia karibu 100% kwenye seva kwenye mtandao wetu.
Matumizi ya CPU wakati mmoja wa kuwepo wakati wa tukio
Kwa hivyo, wateja wetu (na wateja wa wateja wetu) waliishia na ukurasa wa makosa 502 kwenye vikoa vya Cloudflare. Hitilafu 502 zilitolewa na seva za wavuti za Cloudflare ambazo bado zilikuwa na cores zisizolipishwa lakini hazikuweza kuwasiliana na michakato ya kushughulikia trafiki ya HTTP/HTTPS.
Tunajua ni usumbufu kiasi gani huu umesababisha wateja wetu. Tuna aibu sana. Na kushindwa huku kumetuzuia kushughulika vyema na tukio hilo.
Ikiwa ulikuwa mmoja wa wateja hawa, labda ulikuwa na hofu, hasira na hasira. Zaidi ya hayo, hatujapata a . Matumizi ya juu ya CPU yalitokana na sheria moja ya WAF yenye usemi duni wa kawaida ambao ulisababisha kurudi nyuma kupita kiasi. Hapa kuna usemi wa hatia: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Ingawa hii inavutia yenyewe (na nitazungumza juu yake kwa undani zaidi hapa chini), huduma ya Cloudflare ilikuwa chini kwa dakika 27 sio tu kwa sababu ya usemi mbaya wa kawaida. Ilituchukua muda kuelezea mlolongo wa matukio ambayo yalisababisha kutofaulu, kwa hivyo tulichelewa kujibu. Mwishoni mwa chapisho, nitaelezea kurudi nyuma kwa usemi wa kawaida na kukuambia nini cha kufanya nayo.
Nini kilitokea
Hebu tuanze kwa utaratibu. Nyakati zote hapa ni katika UTC.
Saa 13:42 p.m., mhandisi kwenye timu ya ngome alifanya mabadiliko madogo kwenye sheria za kugundua. kwa kutumia mchakato otomatiki. Kwa hivyo, tikiti ya ombi la mabadiliko iliundwa. Tunasimamia tikiti kama hizo kupitia Jira (picha ya skrini hapa chini).
Baada ya dakika 3, ukurasa wa kwanza wa PagerDuty ulionekana, ukiripoti tatizo na WAF. Hili lilikuwa jaribio la syntetisk ambalo hujaribu utendakazi wa WAF (tuna mamia yazo) nje ya Cloudflare ili kufuatilia utendakazi wa kawaida. Hii ilifuatwa mara moja na kurasa za arifa kuhusu majaribio mengine ya huduma ya mwisho hadi mwisho ya Cloudflare kushindwa, masuala ya trafiki duniani, makosa 502 yaliyoenea, na ripoti nyingi kutoka kwa Pointi zetu za Uwepo (PoP) katika miji kote ulimwenguni ambazo zilionyesha ukosefu. rasilimali za CPU.
Nilipokea arifa hizi kadhaa, nikatoka nje ya mkutano kwa kishindo, na nilikuwa nikielekea mezani wakati mkuu wa idara yetu ya ukuzaji wa suluhisho aliposema kuwa tumepoteza 80% ya trafiki yetu. Nilikimbilia kwa wahandisi wetu wa SRE, ambao tayari walikuwa wanashughulikia shida. Mwanzoni tulidhani ni aina fulani ya shambulio lisilojulikana.
Wahandisi wa Cloudflare SRE wametawanyika kote ulimwenguni na kufuatilia hali saa nzima. Kwa kawaida, arifa hizi hukuarifu kuhusu masuala mahususi ya ndani ya upeo mdogo, hufuatiliwa kwenye dashibodi za ndani, na hutatuliwa mara nyingi kwa siku. Lakini kurasa hizi na arifa zilionyesha jambo zito sana, na wahandisi wa SRE walitangaza mara moja kiwango cha ukali P0 na kuwasiliana na wasimamizi na wahandisi wa mfumo.
Wahandisi wetu wa London walikuwa wakisikiliza hotuba katika jumba kuu wakati huo. Mhadhara huo ulilazimika kuingiliwa, kila mtu akakusanyika katika chumba kikubwa cha mikutano, na wataalamu zaidi waliitwa. Hili halikuwa tatizo la kawaida ambalo SREs wangeweza kukabiliana nazo wenyewe. Ilikuwa ni haraka kuhusisha wataalamu sahihi.
Saa 14:00 tuliamua kuwa tatizo lilikuwa kwa WAF na hakukuwa na shambulio lolote. Timu ya utendaji ilivuta data ya CPU na ikawa wazi kuwa WAF ndio wa kulaumiwa. Mfanyakazi mwingine alithibitisha nadharia hii kwa kutumia strace. Mtu mwingine aliona kwenye magogo kwamba kulikuwa na tatizo na WAF. Saa 14:02 p.m., timu nzima ilinijia wakati ilipendekezwa kutumia global kill, utaratibu uliojengwa ndani ya Cloudflare ambao huzima kipengele kimoja duniani kote.
Jinsi tulivyoua kimataifa kwa WAF ni hadithi tofauti. Si rahisi hivyo. Tunatumia bidhaa zetu wenyewe, na tangu huduma yetu haikufanya kazi, hatukuweza kuthibitisha na kuingia kwenye paneli ya udhibiti wa ndani (kila kitu kiliporekebishwa, tuligundua kuwa baadhi ya washiriki wa timu walikuwa wamepoteza uwezo wa kufikia kwa sababu ya kipengele cha usalama ambacho huzima kitambulisho ikiwa paneli ya udhibiti wa ndani haitatumika muda mrefu).
Na hatukuweza kufikia huduma zetu za ndani, kama vile Jira au mfumo wa ujenzi. Tulihitaji utaratibu wa kurekebisha, ambao tulitumia mara chache (hii pia itahitaji kufanyiwa kazi). Hatimaye, mhandisi mmoja aliweza kuzima WAF saa 14:07, na saa 14:09, viwango vya trafiki na CPU vilirudi kawaida kila mahali. Njia zingine za ulinzi za Cloudflare zilifanya kazi kama kawaida.
Kisha tunaanza kurejesha WAF. Hali haikuwa ya kawaida, kwa hivyo tuliendesha majaribio hasi (tukijiuliza ikiwa kweli badiliko ndio lilikuwa shida) na majaribio chanya (kuhakikisha kuwa urejeshaji ulifanya kazi) katika jiji moja kwa kutumia trafiki tofauti, kuhamisha wateja wanaolipa kutoka hapo.
Saa 14:52 tulikuwa na hakika kwamba tulielewa sababu na tukafanya masahihisho, na kuwezesha WAF tena.
Jinsi Cloudflare inavyofanya kazi
Cloudflare ina timu ya wahandisi waliojitolea kusimamia sheria za WAFs. Wanajitahidi kuboresha viwango vya ugunduzi, kupunguza maoni ya uwongo, na kukabiliana haraka na vitisho vipya vinapoibuka. Katika siku 60 zilizopita, kumekuwa na maombi 476 ya mabadiliko yaliyochakatwa kwa sheria zinazodhibitiwa za WAF (wastani wa moja kila baada ya saa 3).
Mabadiliko haya mahususi yalihitaji kupelekwa katika hali ya kuiga, ambapo trafiki halisi ya mteja hupitia sheria, lakini hakuna kitu kilichozuiwa. Tunatumia hali hii ili kupima ufanisi wa sheria na kupima viwango vya uongo vya chanya na hasi vya uwongo. Lakini hata katika hali ya kuiga, sheria lazima zitekelezwe, na katika kesi hii sheria ilikuwa na usemi wa kawaida ambao ulikuwa ukitumia rasilimali nyingi za wasindikaji.
Kama unavyoona kutoka kwa ombi la mabadiliko hapo juu, tuna mpango wa kupeleka, mpango wa kurejesha, na kiungo cha utaratibu wa uendeshaji wa kawaida wa ndani (SOP) wa aina hii ya uwekaji. SOP ya kubadilisha sheria inaruhusu kuchapishwa kimataifa. Kwa kweli, huko Cloudflare, mambo yanafanywa kwa njia tofauti kabisa, na SOP inaamuru kwamba kwanza tusafirishe programu hiyo kwa majaribio na matumizi ya ndani hadi sehemu ya ndani ya uwepo (PoP) (ambayo wafanyikazi wetu hutumia), kisha kwa idadi ndogo ya wateja eneo la pekee, kisha kwa idadi kubwa ya wateja, na kisha tu kwa ulimwengu wote.
Hivi ndivyo inavyoonekana. Tunatumia git ndani kupitia BitBucket. Wahandisi wanaofanyia kazi mabadiliko huwasilisha msimbo, ambao umeundwa kwa TeamCity, na muundo unapopita, wakaguzi hupewa. Mara tu ombi la kuvuta limeidhinishwa, nambari hukusanywa na safu ya majaribio inaendeshwa (tena).
Ikiwa muundo na majaribio yatakamilika kwa mafanikio, ombi la mabadiliko litaundwa katika Jira na msimamizi au kiongozi anayefaa lazima aidhinishe mabadiliko hayo. Baada ya kuidhinishwa, kupelekwa hutokea kwenye kile kinachojulikana kama "meneja wa PoP": DOG, PIG na (mbwa, nguruwe na canary).
DOG PoP ni Cloudflare PoP (kama miji yetu mingine yote) ambayo inatumiwa na wafanyakazi wa Cloudflare pekee. PoP kwa matumizi ya ndani hukuruhusu kupata shida kabla ya trafiki ya wateja kuanza kutiririka kwenye suluhisho. Jambo la manufaa.
Ikiwa jaribio la DOG limefanikiwa, msimbo huhamia kwenye hatua ya PIG (guinea pig). Hii ni Cloudflare PoP, ambapo kiasi kidogo cha trafiki ya wateja bila malipo inapita kupitia msimbo mpya.
Ikiwa kila kitu kiko sawa, nambari itaingia Canary. Tuna Canary PoP tatu katika sehemu mbalimbali za dunia. Ndani yao, trafiki ya wateja waliolipwa na bure hupitia msimbo mpya, na hii ndiyo hundi ya mwisho ya makosa.
Mchakato wa Kutoa Programu kwenye Cloudflare
Ikiwa msimbo ni sawa katika Canary, tunaitoa. Kupitia hatua zote - DOG, PIG, Canary, dunia nzima - inachukua saa kadhaa au siku, kulingana na mabadiliko ya kanuni. Kwa sababu ya anuwai ya mtandao na wateja wa Cloudflare, tunajaribu nambari ya kuthibitisha kwa kina kabla ya kuitoa duniani kote kwa wateja wote. Lakini WAF haifuati mchakato huu haswa kwa sababu vitisho vinahitaji kushughulikiwa haraka.
Vitisho vya WAF
Katika miaka michache iliyopita, kumekuwa na ongezeko kubwa la vitisho katika matumizi ya kawaida. Hii ni kutokana na upatikanaji mkubwa wa zana za kupima programu. Kwa mfano, tuliandika hivi karibuni ).
Chanzo:
Mara nyingi sana, uthibitisho wa dhana huundwa na kuchapishwa mara moja kwenye Github ili timu zinazodumisha programu ziweze kuijaribu haraka na kuhakikisha kuwa imelindwa vya kutosha. Kwa hiyo, Cloudflare inahitaji uwezo wa kujibu mashambulizi mapya haraka iwezekanavyo ili wateja wapate fursa ya kurekebisha programu zao.
Mfano mzuri wa majibu ya haraka ya Cloudflare ni kutumwa kwa ulinzi wa hatari ya SharePoint mwezi Mei () Takriban mara tu baada ya matangazo kutolewa, tuligundua idadi kubwa ya majaribio ya kutumia uwezekano wa kuathiriwa na usakinishaji wa SharePoint wa wateja wetu. Vijana wetu wanafuatilia kila mara vitisho vipya na kuandika sheria ili kulinda wateja wetu.
Sheria iliyosababisha tatizo siku ya Alhamisi ilipaswa kulinda dhidi ya uandishi wa tovuti mbalimbali (XSS). Mashambulizi kama haya pia yamekuwa mengi zaidi katika miaka ya hivi karibuni.
Chanzo:
Utaratibu wa kawaida wa kubadilisha sheria inayodhibitiwa ya WAF ni kufanya majaribio ya ujumuishaji endelevu (CI) kabla ya kutumwa ulimwenguni. Alhamisi iliyopita tulifanya hivi na tukatoa sheria. Saa 13:31 usiku, mhandisi aliwasilisha ombi la kuvuta lililoidhinishwa na mabadiliko.
Saa 13:37 TeamCity ilikusanya sheria, ilifanya majaribio na kutoa idhini. Kitengo cha majaribio cha WAF hujaribu utendakazi wa msingi wa WAF na kina idadi kubwa ya majaribio ya vitengo vya utendaji mahususi. Baada ya majaribio ya kitengo, tulijaribu sheria za WAF kwa kutumia idadi kubwa ya maombi ya HTTP. Maombi ya HTTP angalia ni maombi gani yanapaswa kuzuiwa na WAF (kuzuia shambulio) na ambayo inaweza kuruhusiwa kupitia (ili usizuie kila kitu na uepuke chanya za uwongo). Lakini hatukujaribu utumiaji mwingi wa CPU, na kukagua magogo ya muundo wa WAF uliopita unaonyesha kuwa wakati wa utekelezaji wa mtihani wa sheria haukuongezeka, na ilikuwa ngumu kushuku kuwa hakutakuwa na rasilimali za kutosha.
Majaribio yalipita na TeamCity ilianza kupeleka mabadiliko kiotomatiki saa 13:42 p.m.
Quicksilver
Sheria za WAF zinazingatia urekebishaji wa tishio mara moja, kwa hivyo tunazitumia kwa kutumia duka la thamani kuu lililosambazwa la Quicksilver, ambalo hueneza mabadiliko kote ulimwenguni kwa sekunde. Wateja wetu wote hutumia teknolojia hii wanapobadilisha usanidi kwenye dashibodi au kupitia API, na ni shukrani kwa hiyo kwamba tunajibu mabadiliko kwa kasi ya umeme.
Hatujazungumza mengi kuhusu Quicksilver. Hapo awali tulitumia kama duka la thamani kuu linalosambazwa duniani kote, lakini kulikuwa na matatizo ya uendeshaji nayo, na tuliandika duka letu, lililonakiliwa katika zaidi ya miji 180. Sasa tunatumia Quicksilver kusukuma mabadiliko ya usanidi kwa wateja, kusasisha sheria za WAF, na kusambaza msimbo wa JavaScript ulioandikwa na wateja kwa Wafanyakazi wa Cloudflare.
Inachukua sekunde chache tu kutoka kwa kubofya kitufe kwenye dashibodi au kupiga API kufanya mabadiliko ya usanidi ulimwenguni kote. Wateja walipenda kasi hii ya usanidi. Na Wafanyakazi huwapa karibu uwekaji wa programu za kimataifa mara moja. Kwa wastani, Quicksilver hueneza takriban mabadiliko 350 kwa sekunde.
Na Quicksilver ni haraka sana. Kwa wastani, tulifikia asilimia 99 ya sekunde 2,29 ili kueneza mabadiliko kwa kila kompyuta duniani kote. Kasi kawaida ni jambo zuri. Baada ya yote, unapowezesha kazi au kufuta cache, hutokea karibu mara moja na kila mahali. Kutuma nambari kupitia Cloudflare Workers hufanyika kwa kasi sawa. Cloudflare huwaahidi wateja wake masasisho ya haraka kwa wakati ufaao.
Lakini katika kesi hii, kasi ilicheza utani wa kikatili kwetu, na sheria zilibadilika kila mahali katika suala la sekunde. Huenda umegundua kuwa msimbo wa WAF hutumia Lua. Cloudflare hutumia Lua sana katika uzalishaji na maelezo sisi . Lua WAF hutumia ndani na inatumika kurudi nyuma kwa kulinganisha. Haina njia za kulinda dhidi ya misemo ambayo hutoka nje ya udhibiti. Hapo chini nitazungumza zaidi juu ya hili na kile tunachofanya juu yake.
Kabla ya sheria kupelekwa, kila kitu kilikwenda vizuri: ombi la kuvuta liliundwa na kupitishwa, bomba la CI / CD lilikusanya na kupima msimbo, ombi la mabadiliko liliwasilishwa kwa mujibu wa SOP ambayo inasimamia kupelekwa na kurudi nyuma, na kupelekwa kukamilika.
Mchakato wa Usambazaji wa Cloudflare WAF
Hitilafu fulani imetokea
Kama nilivyosema, tunapeleka sheria kadhaa mpya za WAF kila wiki, na tuna mifumo mingi ya kulinda dhidi ya matokeo mabaya ya uwekaji kama huo. Na wakati kitu kitaenda vibaya, kawaida ni mchanganyiko wa hali kadhaa mara moja. Ikiwa unapata sababu moja tu, hii, bila shaka, inatia moyo, lakini sio kweli kila wakati. Hizi ndizo sababu ambazo kwa pamoja zilisababisha kutofaulu kwa huduma yetu ya HTTP/HTTPS.
- Mhandisi aliandika usemi wa kawaida ambao unaweza kusababisha kupita kiasi .
- Kipengele ambacho kingeweza kuzuia usemi wa kawaida kutokana na upotevu wa CPU nyingi kiliondolewa kimakosa katika urekebishaji upya wa WAF wiki kadhaa mapema—urekebishaji upya ulihitajika ili kufanya WAF kutumia rasilimali kidogo.
- Injini ya kujieleza ya kawaida haikuwa na dhamana za utata.
- Kitengo cha majaribio hakikuweza kutambua matumizi mengi ya CPU.
- SOP inaruhusu mabadiliko ya sheria zisizo za dharura kutekelezwa kimataifa bila mchakato wa hatua nyingi.
- Mpango wa kurejesha ulihitaji kuendesha muundo kamili wa WAF mara mbili, ambayo ilichukua muda mrefu.
- Tahadhari ya kwanza kuhusu matatizo ya trafiki duniani ilisababishwa kuchelewa mno.
- Tulichukua muda kusasisha ukurasa wa hali.
- Tulikuwa na matatizo ya kufikia mifumo kwa sababu ya hitilafu, na utaratibu wa bypass haukuwekwa vizuri.
- Wahandisi wa SRE walipoteza uwezo wa kufikia baadhi ya mifumo kwa sababu muda wa stakabadhi zao uliisha kwa sababu za usalama.
- Wateja wetu hawakuweza kufikia dashibodi au API ya Cloudflare kwa sababu wanapitia eneo la Cloudflare.
Nini kimebadilika tangu Alhamisi iliyopita
Kwanza, tulisimamisha kabisa kazi zote za matoleo ya WAF na tunafanya yafuatayo:
- Tunaleta upya ulinzi wa matumizi kupita kiasi wa CPU ambao tuliondoa. (Tayari)
- Kukagua mwenyewe sheria zote 3868 katika sheria zinazodhibitiwa kwa WAF ili kupata na kusahihisha kesi zingine zinazowezekana za kurudi nyuma kupita kiasi. (Uthibitishaji umekamilika)
- Tunajumuisha wasifu wa utendaji wa sheria zote katika seti ya majaribio. (Inatarajiwa: Julai 19)
- Inabadilisha hadi injini ya kawaida ya kujieleza au - zote mbili hutoa dhamana za wakati wa kukimbia. (Inatarajiwa: Julai 31)
- Tunaandika upya SOP ili kupeleka sheria kwa hatua, kama programu nyingine katika Cloudflare, lakini wakati huo huo tuna uwezo wa kusambaza kwa haraka duniani kote ikiwa mashambulizi tayari yameanza.
- Tunakuza uwezo wa kuondoa kwa haraka dashibodi ya Cloudflare na API kutoka eneo la Cloudflare.
- Inaweka sasisho za ukurasa kiotomatiki .
Muda mrefu tunaondoka kwenye WAF ya Lua niliyoandika miaka michache iliyopita. Kuhamisha WAF hadi . Kwa njia hii WAF itakuwa kasi na kupokea kiwango cha ziada cha ulinzi.
Hitimisho
Kushindwa huku kulisababisha matatizo kwetu na kwa wateja wetu. Tulichukua hatua haraka kurekebisha hali hiyo na sasa tunashughulikia kasoro katika michakato iliyosababisha ajali, na pia kuchimba kwa undani zaidi ili kujikinga na matatizo yanayoweza kutokea kwa maneno ya kawaida katika siku zijazo wakati wa kuhamia teknolojia mpya.
Tumefedheheka sana kuhusu hitilafu hii na tunaomba radhi kwa wateja wetu. Tunatumai mabadiliko haya yatahakikisha kitu kama hiki hakifanyiki tena.
Maombi. Kurudisha nyuma usemi wa kawaida
Ili kuelewa jinsi usemi:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))ulikula rasilimali zote za CPU, unahitaji kujua kidogo kuhusu jinsi injini ya kawaida ya kujieleza inavyofanya kazi. Tatizo hapa ni muundo .*(?:.*=.*). (?: na sambamba ) ni kikundi kisichokamata (yaani, usemi katika mabano umewekwa katika kundi moja).
Katika muktadha wa utumiaji mwingi wa CPU, muundo huu unaweza kuelezewa kama .*.*=.*. Katika fomu hii, muundo unaonekana kuwa ngumu sana. Lakini muhimu zaidi, katika ulimwengu halisi, misemo (kama vile misemo changamano katika sheria za WAF) ambayo huuliza injini ilingane na kipande kinachofuatwa na kipande kingine inaweza kusababisha kurudi nyuma kwa janga. Na ndiyo maana.
Kwa kujieleza mara kwa mara . inamaanisha unahitaji kulinganisha mhusika mmoja, .* - linganisha wahusika sifuri au zaidi "kwa pupa", ambayo ni, kukamata idadi kubwa ya wahusika, ili .*.*=.* inamaanisha linganisha vibambo sifuri au zaidi, kisha ulinganishe vibambo sifuri au zaidi, pata herufi halisi =, linganisha vibambo sifuri au zaidi.
Hebu tuchukue mstari wa mtihani x=x. Inalingana na usemi .*.*=.*. .*.* kabla ya alama sawa inalingana na ya kwanza x (moja ya vikundi .* inafanana na x, na wahusika wa pili - sifuri). .* baada = mechi za mwisho x.
Ulinganisho huu unahitaji hatua 23. Kundi la kwanza .* в .*.*=.* hutenda kwa pupa na kuendana na kamba nzima x=x. Injini huenda kwa kikundi kinachofuata .*. Hatuna wahusika wengine wa kulinganisha, kwa hivyo kundi la pili .* inalingana na herufi sifuri (hii inaruhusiwa). Kisha injini huenda kwenye ishara =. Hakuna alama zaidi (kikundi cha kwanza .* ametumia usemi mzima x=x), hakuna ulinganisho unaotokea.
Na kisha injini ya kujieleza ya kawaida inarudi mwanzo. Anahamia kundi la kwanza .* na kuilinganisha с x= (badala ya x=x), na kisha kuchukua kundi la pili .*. Kundi la pili .* inalinganishwa na ya pili x, na hatuna wahusika tena. Na wakati injini inafika tena = в .*.*=.*, hakuna kinachofanya kazi. Na anarudi nyuma tena.
Wakati huu kundi .* bado mechi x=, lakini kundi la pili .* tena x, na wahusika sifuri. Injini inajaribu kupata mhusika halisi = katika muundo .*.*=.*, lakini haitoki (baada ya yote, kikundi cha kwanza tayari kimeichukua .*) Na anarudi nyuma tena.
Wakati huu kundi la kwanza .* inachukua tu ya kwanza x. Lakini kundi la pili .* "kwa pupa" inakamata =x. Je, tayari umekisia nini kitatokea? Injini inajaribu kufanana na halisi =, inashindwa na hufanya urejeshaji mwingine.
Kundi la kwanza .* bado inalingana na ya kwanza x. Pili .* inachukua tu =. Bila shaka, injini haiwezi kufanana na halisi =, kwa sababu kundi la pili tayari limefanya hivi .*. Na kurudi nyuma tena. Na tunajaribu kulinganisha safu ya herufi tatu!
Kama matokeo, kundi la kwanza .* inalingana na ya kwanza tu x, pili .* - na wahusika sifuri, na injini hatimaye inafanana na halisi = katika kujieleza с = katika mstari. Ifuatayo ni kundi la mwisho .* inalinganishwa na ya mwisho x.
Hatua 23 tu kwa x=x. Tazama video fupi kuhusu kutumia Perl , ambayo inaonyesha jinsi hatua na kurudi nyuma hutokea.
Hii tayari ni kazi nyingi, lakini vipi ikiwa badala yake x=x tutakuwa na x=xx? Hiyo ni hatua 33. Na kama x=xxx? 45. Uhusiano sio mstari. Grafu inaonyesha kulinganisha kutoka x=x kwa x=xxxxxxxxxxxxxxxxxxxx (20 x baada ya =) Ikiwa tuna 20 x baada ya =, injini inakamilisha ulinganifu kwa hatua 555! (Zaidi ya hayo, ikiwa tumepoteza x= na kamba ina 20 tu x, injini itachukua hatua 4067 kuelewa kuwa hakuna mechi).
Video hii inaonyesha kurudi nyuma kwa kulinganisha x=xxxxxxxxxxxxxxxxxxxx:
Shida ni kwamba kadiri saizi ya kamba inavyoongezeka, wakati wa kulinganisha unakua kwa usawa. Lakini mambo yanaweza kuwa mabaya zaidi ikiwa usemi wa kawaida utarekebishwa kidogo. Wacha tuseme tulikuwa nayo .*.*=.*; (yaani, kulikuwa na semicolon halisi mwishoni mwa muundo). Kwa mfano, ili kulinganisha usemi kama foo=bar;.
Na hapa kurudi nyuma itakuwa janga la kweli. Kwa kulinganisha x=x itachukua hatua 90, sio 23. Na idadi hiyo inakua haraka. Kulinganisha x= na 20 x, hatua 5353 zinahitajika. Hii hapa chati. Angalia maadili ya mhimili Y ikilinganishwa na chati iliyotangulia.
Ikiwa una nia, angalia hatua zote 5353 ambazo hazikufanikiwa x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Kwa kutumia uvivu badala ya kulinganisha kwa pupa, kiwango cha kurudi nyuma kinaweza kudhibitiwa. Ikiwa tutabadilisha usemi asilia kuwa .*?.*?=.*?, kwa kulinganisha x=x itachukua hatua 11 (si 23). Kuhusu x=xxxxxxxxxxxxxxxxxxxx. Yote kwa sababu ? baada ya .* huiambia injini kulinganisha idadi ya chini ya herufi kabla ya kuendelea.
Lakini ramani za uvivu hazisuluhishi kabisa shida ya kurudi nyuma. Ikiwa tutabadilisha mfano wa janga .*.*=.*; juu ya .*?.*?=.*?;, muda wa utekelezaji utabaki vile vile. x=x bado inahitaji hatua 555, na x= na 20 x - 5353.
Kitu pekee ambacho kinaweza kufanywa (kando na kuandika tena muundo kwa utaalam zaidi) ni kuacha injini ya kawaida ya kujieleza na utaratibu wake wa kurudi nyuma. Hivi ndivyo tutakavyofanya katika wiki chache zijazo.
Suluhisho la tatizo hili limejulikana tangu 1968, wakati Kent Thompson aliandika makala ("Njia za Kupanga: Kanuni ya Utafutaji wa Maonyesho ya Kawaida"). Kifungu kinaelezea utaratibu unaokuruhusu kubadilisha usemi wa kawaida kuwa mashine za hali ya kikomo isiyo ya kubainika, na baada ya mabadiliko ya hali katika mashine za hali ya kikomo isiyo ya kibainishi, tumia algoriti ambayo muda wa utekelezaji unategemea mstari kwenye kamba inayolingana.
Mbinu za Kuandaa
Algorithm ya Utafutaji wa Maonyesho ya Kawaida
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyInaelezea njia ya kutafuta safu maalum ya wahusika katika maandishi na kujadili utekelezaji wa njia hii katika fomu ya mkusanyaji. Mkusanyaji huchukua usemi wa kawaida kama msimbo wa chanzo na hutoa mpango wa IBM 7094 kama msimbo wa kitu. Mpango wa kipengee huchukua ingizo katika mfumo wa maandishi ya utafutaji na hutoa ishara kila wakati mfuatano wa maandishi unapolinganishwa na usemi fulani wa kawaida. Nakala hiyo inatoa mifano, shida na suluhisho.
Algorithm
Kanuni za awali za utafutaji zilisababisha kurudi nyuma ikiwa utafutaji uliofaulu kwa kiasi umeshindwa kutoa matokeo.Katika hali ya mkusanyiko, algorithm haifanyi kazi na alama. Hupitisha maagizo kwa msimbo uliokusanywa. Utekelezaji ni wa haraka sana - baada ya kupitisha data juu ya orodha ya sasa, hutafuta moja kwa moja wahusika wote wanaowezekana mfululizo katika usemi wa kawaida.
Kanuni ya mkusanyo na utafutaji imejumuishwa katika kihariri cha maandishi cha kugawana wakati kama utafutaji wa muktadha. Bila shaka, hii ni mbali na matumizi pekee ya utaratibu huo wa utafutaji. Kwa mfano, lahaja ya algoriti hii inatumika kama utaftaji wa alama kwenye jedwali katika kikusanyaji.
Inachukuliwa kuwa msomaji anafahamu maneno ya kawaida na lugha ya programu ya kompyuta ya IBM 7094.Mkusanyaji
Kikusanyaji kina hatua tatu zinazoendana sambamba. Hatua ya kwanza ni uchujaji wa kisintaksia, ambao huruhusu tu misemo sahihi ya kisintaksia kupita. Hatua hii pia huingiza opereta "·" ili kuoanisha misemo ya kawaida. Katika hatua ya pili, usemi wa kawaida hubadilishwa kuwa fomu ya postfix. Katika hatua ya tatu, msimbo wa kitu huundwa. Hatua 2 za kwanza ni dhahiri, na hatutakaa juu yao.
Nakala ya Thompson haizungumzii juu ya mashine za hali isiyo ya kawaida, lakini inaelezea algorithm ya wakati wa mstari vizuri na inatoa programu ya ALGOL-60 ambayo hutoa msimbo wa lugha ya kusanyiko kwa IBM 7094. Utekelezaji ni gumu, lakini wazo ni rahisi sana.
njia ya utafutaji ya sasa. Inawakilishwa na ikoni ⊕ yenye ingizo moja na matokeo mawili.
Kielelezo cha 1 kinaonyesha utendakazi wa hatua ya tatu ya ujumuishaji wakati wa kubadilisha mfano wa usemi wa kawaida. Herufi tatu za kwanza kwenye mfano ni a, b, c, na kila moja huunda safu ya S[i] na sehemu ya NNODE.NNODE kwa msimbo uliopo ili kutoa usemi wa kawaida unaosababishwa katika ingizo moja la rafu (ona Mchoro 5)
Hivi ndivyo usemi wa kawaida ungeonekana .*.*=.*, ikiwa unafikiria kama kwenye picha kutoka kwa nakala ya Thompson.
Katika Mtini. 0 kuna majimbo matano kuanzia 0, na mizunguko 3 ambayo huanza kutoka majimbo 1, 2 na 3. Mizunguko hii mitatu inalingana na tatu. .* kwa usemi wa kawaida. Ovals 3 zilizo na dots zinalingana na ishara moja. Mviringo na ishara = inalingana na mhusika halisi =. Jimbo la 4 ni la mwisho. Ikiwa tunaifikia, basi usemi wa kawaida unalingana.
Kuona jinsi mchoro wa hali kama hii unavyoweza kutumika kwa kulinganisha usemi wa kawaida .*.*=.*, tutaangalia kulinganisha kwa kamba x=x. Programu huanza kutoka hali 0, kama inavyoonyeshwa kwenye Mtini. 1.
Ili algorithm hii ifanye kazi, mashine ya serikali lazima iwe katika majimbo kadhaa wakati huo huo. Mashine isiyo na kikomo ya kikomo itafanya mabadiliko yote yanayowezekana kwa wakati mmoja.
Kabla ya kuwa na muda wa kusoma data ya ingizo, huenda katika majimbo yote mawili ya kwanza (1 na 2), kama inavyoonyeshwa kwenye Mtini. 2.
Katika Mtini. 2 inaonyesha kile kinachotokea anapotazama kwanza x в x=x. x inaweza ramani hadi sehemu ya juu, ikitoka jimbo la 1 na kurudi hadi hali 1. Au x inaweza kuweka ramani kwa uhakika hapa chini, ikisogea kutoka jimbo la 2 na kurudi hadi jimbo la 2.
Baada ya kulinganisha ya kwanza x в x=x bado tuko katika hali ya 1 na 2. Hatuwezi kufikia hali ya 3 au 4 kwa sababu tunahitaji mhusika halisi. =.
Algorithm basi inazingatia = в x=x. Kama vile x kabla yake, inaweza kulinganishwa na mojawapo ya vitanzi viwili vya juu kutoka jimbo la 1 hadi jimbo la 1 au kutoka jimbo la 2 hadi jimbo la 2, lakini algorithm inaweza kufanana na halisi. = na kuhama kutoka jimbo la 2 hadi jimbo la 3 (na mara moja 4). Hii inaonyeshwa kwenye Mtini. 3.
Algorithm kisha inakwenda hadi ya mwisho x в x=x. Kutoka kwa majimbo 1 na 2 mabadiliko sawa yanawezekana kurudi kwa majimbo 1 na 2. Kutoka jimbo la 3 x inaweza kulinganisha nukta iliyo upande wa kulia na kurudi kwenye hali 3.
Katika hatua hii, kila mhusika x=x kuchukuliwa, na kwa kuwa tumefikia hali ya 4, usemi wa kawaida unalingana na kamba hiyo. Kila herufi huchakatwa mara moja, kwa hivyo algorithm hii ni ya mstari katika urefu wa kamba ya kuingiza. Na hakuna kurudi nyuma.
Ni wazi, baada ya kufikia hali ya 4 (wakati algorithm imelingana x=) usemi mzima wa kawaida unalinganishwa, na algorithm inaweza kukomesha bila kuzingatia hata kidogo x.
Algorithm hii inategemea mstari juu ya saizi ya kamba ya kuingiza.
Chanzo: mapenzi.com
