Peaaegu 9 aastat tagasi oli Cloudflare väike ettevõte ja ma ei töötanud selle heaks, olin lihtsalt klient. Kuu aega pärast Cloudflare'i käivitamist sain teate, et minu veebisait DNS ei paista töötavat. Cloudflare on teinud muudatuse ja DNS oli katki.
Kirjutasin kohe Matthew Prince'ile pealkirjaga "Kus on minu DNS?" ja ta saatis tagasi pika vastuse, mis oli täis tehnilisi üksikasju (), millele ma vastasin:
Autor: John Graham-Cumming
Kuupäev: 7. oktoober 2010, 9:14
Teema: Re: Kus on minu DNS?
Saaja: Matthew PrinceLahe aruanne, aitäh. Probleemide korral helistan kindlasti. Tõenäoliselt tasub selle kohta postitus kirjutada, kui olete kogu tehnilise teabe kogunud. Ma arvan, et inimesed naudivad avatud ja ausat lugu. Eriti kui lisate sellele graafikud, mis näitavad, kuidas liiklus on pärast käivitamist kasvanud.
Minu saidil on hea jälgimine ja iga rikke kohta saan SMS-i. Seire näitab, et rike tekkis 13:03:07 kuni 14:04:12. Testid tehakse iga viie minuti järel.
Olen kindel, et saate sellest aru. Kas olete kindel, et teil pole Euroopas oma inimest vaja? 🙂
Ja ta vastas:
Saatja: Matthew Prince
Kuupäev: 7. oktoober 2010, 9:57
Teema: Re: Kus on minu DNS?
Saaja: John Graham-CummingAitäh. Vastasime kõigile, kes kirjutasid. Olen praegu teel kontorisse ja kirjutame midagi blogisse või kinnitame oma teadetetahvlile ametliku postituse. Olen täiesti nõus, ausus on kõik.
Nüüd on Cloudflare tõesti suur ettevõte, ma töötan selle heaks ja pean nüüd avalikult kirjutama meie veast, selle tagajärgedest ja tegudest.
2. juuli sündmused
2. juulil võtsime WAF-ide hallatavates reeglites kasutusele uue reegli, mille tõttu igal protsessori tuumal, mis töötleb HTTP/HTTPS-liiklust Cloudflare'i võrgus kogu maailmas. Täiustame pidevalt WAFide hallatavaid reegleid, et reageerida uutele haavatavustele ja ohtudele. Mais näiteks kiirustasime et kaitsta SharePointi tõsise haavatavuse eest. Meie WAF-i mõte on reeglite kiire ja globaalne juurutamine.
Kahjuks sisaldas eelmise neljapäeva värskendus regulaaravaldist, mis raiskas liiga palju HTTP/HTTPS-i protsessori ressursse taganemisele. Selle tulemusena said kannatada meie puhverserveri, CDN-i ja WAF-i põhifunktsioonid. Graafik näitab, et protsessori ressursid HTTP/HTTPS-liikluse teenindamiseks ulatuvad meie võrgu serverites peaaegu 100%-ni.
Protsessori kasutamine ühes kohalolekupunktis intsidendi ajal
Selle tulemusena said meie kliendid (ja meie klientide kliendid) Cloudflare'i domeenides vealehe 502. 502 viga genereerisid Cloudflare'i esiotsa veebiserverid, millel olid endiselt vabad tuumad, kuid mis ei suutnud suhelda HTTP/HTTPS-liiklust haldavate protsessidega.
Teame, kui palju ebamugavusi see meie klientidele on tekitanud. Meil on kohutavalt häbi. Ja see ebaõnnestumine takistas meil juhtunuga tõhusalt tegeleda.
Kui kuulusite nende klientide hulka, olite tõenäoliselt hirmul, vihane ja ärritunud. Pealegi pole meil olnud a . Kõrge protsessori tarbimine oli tingitud ühest WAF-i reeglist koos halvasti sõnastatud regulaaravaldisega, mis põhjustas liigse tagasiliikumise. Siin on süüdi väljend: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Kuigi see on omaette huvitav (ja ma räägin sellest üksikasjalikumalt allpool), oli Cloudflare'i teenus maas 27 minutit mitte ainult halva regulaaravaldise tõttu. Ebaõnnestumiseni viinud sündmuste jada kirjeldamine võttis aega, mistõttu reageerisime aeglaselt. Postituse lõpus kirjeldan regulaaravaldises tagasiteed ja ütlen, mida sellega teha.
Mis juhtus
Alustame järjekorras. Kõik ajad on siin UTC-aja järgi.
Kell 13 tegi tulemüüri meeskonna insener avastamisreeglites väikese muudatuse kasutades automaatset protsessi. Vastavalt sellele loodi muutmistaotluse pilet. Selliseid pileteid haldame Jira kaudu (ekraanipilt allpool).
3 minuti pärast ilmus PagerDuty esimene leht, mis teatas probleemist WAF-iga. See oli sünteetiline test, mis testib WAF-ide (meil on neid sadu) funktsionaalsust väljaspool Cloudflare'i, et jälgida normaalset tööd. Sellele järgnesid koheselt leheküljed hoiatusteateid teiste Cloudflare'i täisteenuse testide ebaõnnestumise, globaalsete liiklusprobleemide, laialt levinud 502 vigade ja paljude maailma linnade kohalolekupunktide (PoP) aruannete kohta, mis viitasid puudumisele. protsessori ressurssidest.
Sain mitu neist hoiatustest, tormasin koosolekult välja ja olin teel laua juurde, kui meie lahenduste arenduse osakonna juhataja ütles, et oleme kaotanud 80% liiklusest. Jooksin meie SRE inseneride juurde, kes juba probleemi kallal töötasid. Alguses arvasime, et see on mingi tundmatu rünnak.
Cloudflare SRE insenerid on üle maailma laiali ja jälgivad olukorda ööpäevaringselt. Tavaliselt teavitavad need hoiatused teid konkreetsetest kohalikest piiratud ulatusega probleemidest, neid jälgitakse sisemistel armatuurlaudadel ja neid lahendatakse mitu korda päevas. Kuid need lehed ja teatised viitasid millelegi tõeliselt tõsisele ning SRE insenerid kuulutasid kohe välja raskusastme P0 ning võtsid ühendust juhtkonna ja süsteemiinseneridega.
Meie Londoni insenerid kuulasid sel hetkel peasaalis loengut. Loeng tuli katkestada, kõik kogunesid suurde konverentsiruumi ja kutsuti juurde spetsialiste. See ei olnud tüüpiline probleem, millega SRE-d ise hakkama saaksid. Kiiresti oli vaja kaasata õiged spetsialistid.
Kell 14:00 tegime kindlaks, et probleem oli WAF-is ja rünnakut ei olnud. Jõudlusmeeskond tõmbas protsessori andmed ja sai selgeks, et süüdi oli WAF. Teine töötaja kinnitas seda teooriat strace abil. Keegi teine nägi logides, et WAF-iga on probleem. Kell 14 jõudis kogu meeskond minu juurde, kui tehti ettepanek kasutada globaalset tapmist – Cloudflare’i sisseehitatud mehhanismi, mis lülitab ühe komponendi kogu maailmas välja.
See, kuidas me WAF-i jaoks ülemaailmset tapmist tegime, on teine lugu. See pole nii lihtne. Kasutame oma tooteid ja alates meie teenusest ei töötanud, me ei saanud autentida ja sisemisse juhtpaneeli sisse logida (kui kõik oli parandatud, saime teada, et mõned meeskonnaliikmed kaotasid juurdepääsu turvafunktsiooni tõttu, mis keelab mandaadid, kui sisemist juhtpaneeli ei kasutata kaua aega).
Ja me ei pääsenud oma siseteenustele, nagu Jira või ehitussüsteem. Vajasime lahendusmehhanismi, mida kasutasime harva (see tuleb samuti välja töötada). Lõpuks õnnestus ühel inseneril kell 14:07 WAF välja lülitada ning kell 14:09 oli liiklus ja protsessori tase kõikjal tagasi normaalne. Ülejäänud Cloudflare'i kaitsemehhanismid töötasid tavapäraselt.
Seejärel asusime WAF-i taastama. Olukord oli tavapärasest erinev, nii et tegime ühes linnas negatiivsed testid (küsisime endalt, kas muudatus oli tõesti probleem) ja positiivsed testid (veendusime, et tagasipööramine toimis) ühes linnas, kasutades eraldi liiklust, kandes maksvaid kliente sealt üle.
Kell 14:52 olime veendunud, et saime põhjusest aru ja tegime paranduse ning lülitasime WAF-i uuesti sisse.
Kuidas Cloudflare töötab
Cloudflare'il on inseneride meeskond, kes on pühendunud WAF-ide reeglite haldamisele. Nad püüavad parandada avastamismäära, vähendada valepositiivseid tulemusi ja reageerida kiiresti uutele ohtudele, kui need ilmnevad. Viimase 60 päeva jooksul on WAF-i hallatud reeglite jaoks töödeldud 476 muutmistaotlust (keskmiselt üks iga 3 tunni järel).
See konkreetne muudatus tuli juurutada simulatsioonirežiimis, kus tegelik kliendiliiklus läbib reeglit, kuid midagi pole blokeeritud. Kasutame seda režiimi reeglite tõhususe testimiseks ning valepositiivsete ja valenegatiivsete määrade mõõtmiseks. Kuid isegi simulatsioonirežiimis tuleb reegleid tegelikult täita ja antud juhul sisaldas reegel regulaaravaldist, mis kulutas liiga palju protsessori ressursse.
Nagu näete ülaltoodud muudatustaotlusest, on meil seda tüüpi juurutamise jaoks juurutusplaan, tagasipööramisplaan ja link sisestandardse tööprotseduuri (SOP) juurde. Reegli muutmise SOP võimaldab selle globaalselt avaldada. Tegelikult tehakse Cloudflare'is asju täiesti erinevalt ja SOP näeb ette, et esmalt saadame tarkvara testimiseks ja sisekasutuseks sisemisse kohalolekupunkti (PoP) (mida meie töötajad kasutavad), seejärel väikesele arvule klientidele eraldatud asukohta, seejärel suurele hulgale klientidele ja alles siis kogu maailmale.
See näeb välja selline. Kasutame giti sisemiselt BitBucketi kaudu. Muudatuste kallal töötavad insenerid esitavad koodi, mis on loodud TeamCitysse, ja kui järg läbib, määratakse ülevaatajad. Kui tõmbamistaotlus on heaks kiidetud, koostatakse kood ja käivitatakse (uuesti) testide seeria.
Kui ehitamine ja testid on edukalt lõpule viidud, luuakse Jiras muudatustaotlus ja asjakohane haldur või müügivihje peab muudatuse heaks kiitma. Pärast heakskiitmist viiakse kasutusele nn PoP-menaaž: KOER, PIG ja (koer, siga ja kanaarilind).
DOG PoP on Cloudflare'i PoP (nagu kõik teisedki meie linnad), mida kasutavad ainult Cloudflare'i töötajad. Sisekasutuseks mõeldud PoP võimaldab teil probleeme tabada enne, kui kliendiliiklus lahendusse hakkab voolama. Kasulik asi.
Kui KOERA test on edukas, liigub kood PIG (merisiga) etappi. See on Cloudflare PoP, kus väike hulk tasuta kliendiliiklust liigub läbi uue koodi.
Kui kõik on korras, läheb kood Kanaarile. Meil on kolm Canary PoP-i maailma eri paigus. Nendes käib tasuliste ja tasuta klientide liiklus uue koodi kaudu ning see on viimane vigade kontroll.
Tarkvara väljalaskeprotsess Cloudflare'is
Kui kood on Kanaaril korras, vabastame selle. Kõikide etappide – KOER, PIG, Kanaari, kogu maailma – läbimine võtab olenevalt koodivahetusest mitu tundi või päeva. Cloudflare'i võrgu ja klientide mitmekesisuse tõttu testime koodi põhjalikult enne selle ülemaailmselt kõigile klientidele avaldamist. Kuid WAF ei järgi seda protsessi konkreetselt, sest ohtudele tuleb kiiresti reageerida.
WAF-ähvardused
Viimastel aastatel on levinud rakenduste ohud märkimisväärselt suurenenud. Selle põhjuseks on tarkvara testimise tööriistade suurem kättesaadavus. Näiteks kirjutasime hiljuti ).
Allikas:
Väga sageli luuakse kontseptsiooni tõend ja avaldatakse see kohe Githubis, et rakendust hooldavad meeskonnad saaksid seda kiiresti testida ja tagada selle piisava turvalisuse. Seetõttu vajab Cloudflare võimalust uutele rünnakutele võimalikult kiiresti reageerida, et klientidel oleks võimalus oma tarkvara parandada.
Suurepärane näide Cloudflare'i kiirest reageerimisest on SharePointi haavatavuse kaitsete juurutamine mais (). Peaaegu kohe pärast teadaannete tegemist märkasime tohutul hulgal katseid kasutada ära meie klientide SharePointi installide haavatavust. Meie poisid jälgivad pidevalt uusi ohte ja kirjutavad oma klientide kaitsmiseks reegleid.
Neljapäeval probleemi põhjustanud reegel pidi kaitsma saidiülese skriptimise (XSS) eest. Ka sellised rünnakud on viimastel aastatel palju sagenenud.
Allikas:
WAF-i hallatud reegli muutmise standardprotseduur on pideva integratsiooni (CI) testimine enne globaalset kasutuselevõttu. Eelmisel neljapäeval tegime seda ja kehtestasime reeglid. Kell 13 esitas insener heakskiidetud tõmbetaotluse koos muudatusega.
Kell 13:37 kogus TeamCity reeglid kokku, tegi testid ja andis loa. WAF-i testikomplekt testib WAF-i põhifunktsioone ja koosneb suurest hulgast üksikute funktsioonide ühikutestidest. Pärast ühikuteste testisime WAF-i reegleid, kasutades tohutul hulgal HTTP-päringuid. HTTP-päringud kontrollivad, millised päringud peaks WAF-i poolt blokeerima (ründe pealtkuulamiseks) ja milliseid saab läbi lasta (et mitte kõike blokeerida ja vältida valepositiivseid tulemusi). Kuid me ei testinud liigset CPU kasutust ja eelmiste WAF-i ehituste logide uurimine näitab, et reeglitesti täitmise aeg ei pikenenud ja oli raske kahtlustada, et ressursse ei jätku.
Testid läbisid ja TeamCity alustas muudatuse automaatset juurutamist kell 13.
Elavhõbe
WAF-i reeglid keskenduvad vahetule ohtude kõrvaldamisele, seega juurutame need Quicksilveri hajutatud võtmeväärtuste salvestusruumi abil, mis levitab muudatusi globaalselt sekunditega. Kõik meie kliendid kasutavad seda tehnoloogiat, kui nad muudavad konfiguratsiooni armatuurlaual või API kaudu ja just tänu sellele reageerime muutustele välkkiirelt.
Me pole Quicksilverist palju rääkinud. Varem kasutasime globaalselt levitatava võtmeväärtuste poena, kuid sellega tekkisid tööprobleemid ja me koostasime oma poe, mida kopeeriti enam kui 180 linnas. Nüüd kasutame Quicksilverit konfiguratsioonimuudatuste edastamiseks klientidele, WAF-reeglite värskendamiseks ja klientide kirjutatud JavaScripti koodi levitamiseks Cloudflare Workersile.
Armatuurlaual oleva nupu klõpsamisest või API kutsumisest kuni konfiguratsiooni muutmiseni kogu maailmas kulub vaid mõni sekund. Klientidele meeldis selline seadistamise kiirus. Ja Workers pakub neile peaaegu kohest ülemaailmset tarkvara juurutamist. Keskmiselt levitab Quicksilver umbes 350 muudatust sekundis.
Ja Quicksilver on väga kiire. Keskmiselt saavutasime 99. protsentiili 2,29 sekundit, et levitada muudatusi kõigis arvutites üle maailma. Kiirus on tavaliselt hea asi. Lõppude lõpuks, kui lubate funktsiooni või tühjendate vahemälu, juhtub see peaaegu kohe ja kõikjal. Koodi saatmine Cloudflare Workersi kaudu toimub sama kiirusega. Cloudflare lubab oma klientidele kiireid värskendusi õigel ajal.
Aga antud juhul tegi kiirus meile julma nalja ja reeglid muutusid kõikjal sekunditega. Võib-olla olete märganud, et WAF-kood kasutab Lua. Cloudflare kasutab Luat laialdaselt tootmises ja detailides me . Lua WAF kasutab sisemiselt ja rakendab sobitamiseks tagasiteed. Sellel pole mehhanisme, mis kaitseksid kontrolli alt väljuvate väljendite eest. Allpool räägin sellest lähemalt ja sellest, mida me sellega teeme.
Enne reeglite juurutamist sujus kõik sujuvalt: tõmbetaotlus loodi ja kinnitati, CI/CD konveier kogus ja testis koodi, muudatustaotlus esitati vastavalt juurutamist ja tagasipööramist reguleerivale SOP-le ning juurutamine oli lõpetatud.
Cloudflare WAF-i juurutamisprotsess
Midagi läks valesti
Nagu ma ütlesin, juurutame igal nädalal kümneid uusi WAF-reegleid ja meil on palju süsteeme, mis kaitsevad sellise juurutamise negatiivsete tagajärgede eest. Ja kui midagi läheb valesti, on see tavaliselt mitme asjaolu kombinatsioon korraga. Kui leiate ainult ühe põhjuse, on see muidugi rahustav, kuid see pole alati tõsi. Need on põhjused, mis koos viisid meie HTTP/HTTPS-teenuse rikkeni.
- Insener kirjutas regulaaravaldise, mille tulemuseks võib olla ülemäärane avaldis .
- Funktsioon, mis oleks võinud takistada regulaaravaldise liigset protsessorit raiskamast, eemaldati ekslikult WAF-i ümbertegemisel mitu nädalat varem – ümberkujundamine oli vajalik selleks, et WAF tarbiks vähem ressursse.
- Regulaaravaldise mootoril polnud keerukuse garantiisid.
- Testkomplekt ei suutnud tuvastada liigset protsessori tarbimist.
- SOP võimaldab mittekiireloomulisi reeglimuudatusi ülemaailmselt ilma mitmeastmelise protsessita kasutusele võtta.
- Tagasipööramise plaan nõudis täieliku WAF-i koostamist kaks korda, mis võttis kaua aega.
- Esimene hoiatus globaalsete liiklusprobleemide kohta käivitati liiga hilja.
- Olekulehe värskendamine võttis veidi aega.
- Meil oli probleeme süsteemidele juurdepääsuga tõrke tõttu ja möödaviiguprotseduur polnud hästi välja töötatud.
- SRE insenerid kaotasid juurdepääsu mõnele süsteemile, kuna nende mandaadid aegusid turvakaalutlustel.
- Meie klientidel ei olnud juurdepääsu Cloudflare'i armatuurlauale ega API-le, kuna nad läbivad Cloudflare'i piirkonna.
Mis on eelmisest neljapäevast muutunud
Esiteks peatasime täielikult kogu töö WAF-i väljalasete kallal ja teeme järgmist.
- Võtame uuesti kasutusele eemaldatud protsessori ülekasutuskaitse. (Valmis)
- WAF-i hallatavate reeglite kõigi 3868 reegli käsitsi kontrollimine, et leida ja parandada muid võimalikke liigse tagasilöömise juhtumeid. (Kinnitamine lõpetatud)
- Lisame kõigi testikomplekti reeglite toimivusprofiili. (Oodatav: 19. juuli)
- Lülitumine regulaaravaldise mootorile või - mõlemad pakuvad tööaja garantiid. (Eeldatav: 31. juuli)
- Kirjutame SOP-i ümber, et juurutada reegleid etapiviisiliselt, nagu muu Cloudflare'i tarkvara, kuid samal ajal on meil võimalus globaalse hädaolukorra juurutamiseks, kui rünnakud on juba alanud.
- Arendame välja võimalust kiiresti eemaldada Cloudflare'i armatuurlaud ja API Cloudflare'i piirkonnast.
- Lehtede värskenduste automatiseerimine .
Pikas perspektiivis oleme eemaldumas Lua WAF-ist, mille kirjutasin paar aastat tagasi. WAF-i teisaldamine asukohta . Nii on WAF kiirem ja saab täiendava kaitsetaseme.
Järeldus
See rike tekitas probleeme meile ja meie klientidele. Tegutsesime olukorra parandamiseks kiiresti ja tegeleme nüüd krahhi põhjustanud protsesside vigade kallal, samuti kaevame veelgi sügavamale, et vältida tulevikus uuele tehnoloogiale üleminekul regulaaravaldistega seotud võimalikke probleeme.
Meil on selle katkestuse pärast väga piinlik ja vabandame oma klientide ees. Loodame, et need muudatused tagavad, et midagi sellist enam ei korduks.
Rakendus. Regulaaravaldiste tagasiminek
Väljendi mõistmiseks:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))söönud ära kõik protsessori ressursid, peate natuke teadma, kuidas standardne regulaaravaldise mootor töötab. Probleemiks on siin muster .*(?:.*=.*). (?: ja vastavad ) on mittehõive rühm (st sulgudes olev avaldis on rühmitatud ühe avaldisena).
Protsessori liigse tarbimise kontekstis võib seda mustrit kirjeldada järgmiselt .*.*=.*. Sellisel kujul tundub muster tarbetult keeruline. Veelgi olulisem on aga see, et reaalses maailmas võivad väljendid (nagu keerulised avaldised WAF-reeglites), mis paluvad mootoril sobitada fragmendi, millele järgneb teine fragment, viia katastroofilise taganemiseni. Ja sellepärast.
Regulaaravaldises . tähendab, et peate sobima ühe tähemärgiga, .* - sobitage null või enam tähemärki "ahnelt", st püüdke maksimaalselt märke, nii et .*.*=.* tähendab nulli või enama tähemärgi vastendamist, seejärel nulli või enama tähemärgi vastendamist, leidke literaal = märk, sobitage null või enam märki.
Võtame katsejoone x=x. See vastab väljendile .*.*=.*. .*.* enne kui võrdusmärk ühtib esimesega x (üks rühmadest .* vastab xja teine - null tähemärki). .* pärast = vastab viimaseks x.
See võrdlus nõuab 23 sammu. Esimene rühm .* в .*.*=.* tegutseb ahnelt ja sobib kogu stringiga x=x. Mootor liigub järgmisesse rühma .*. Meil pole rohkem tegelasi, keda sobitada, seega teine rühm .* vastab nullile (see on lubatud). Seejärel liigub mootor märgi juurde =. Rohkem sümboleid pole (esimene rühm .* kasutas kogu väljendit x=x), võrdlust ei toimu.
Ja siis naaseb regulaaravaldise mootor algusesse. Ta liigub edasi esimesse rühma .* ja võrdleb seda с x= (asemel x=x) ja võtab seejärel teise rühma .*. Teine rühm .* võrreldakse teisega x, ja meil pole jälle ühtegi tegelast. Ja kui mootor jälle jõuab = в .*.*=.*, miski ei tööta. Ja ta taandub jälle.
Seekord grupp .* ikka sobib x=, kuid teine rühm .* mitte rohkem x, ja null tähemärki. Mootor püüab leida sõnasõnalist tegelast = mustris .*.*=.*, kuid ei tule välja (lõppude lõpuks on esimene rühm selle juba hõivanud .*). Ja ta taandub jälle.
Seekord esimene grupp .* võtab ainult esimese x. Aga teine rühm .* "ahnelt" lööb =x. Kas olete juba arvanud, mis juhtub? Mootor üritab sõnasõnale vastata =, ebaõnnestub ja teeb uue tagasikäigu.
Esimene rühm .* vastab ikka esimesele x... Teine .* ainult võtab =. Muidugi ei saa mootor sõnasõnale vastata =, sest teine rühm on seda juba teinud .*. Ja jälle tagasiminek. Ja me püüame sobitada kolmest tähemärgist koosneva jada!
Selle tulemusena esimene rühm .* sobib ainult esimesega x, teiseks .* - null tähemärgiga ja mootor sobib lõpuks sõnasõnaga = väljenduses с = järjekorras. Järgmine on viimane rühm .* võrreldakse viimasega x.
Ainult 23 sammu x=x. Vaadake lühikest videot Perli kasutamise kohta , mis näitab, kuidas sammud ja tagasiminek toimuvad.
See on juba palju tööd, aga mis siis, kui selle asemel x=x me saame x=xx? See on 33 sammu. Ja kui x=xxx? 45. Suhe ei ole lineaarne. Graafik näitab võrdlust alates x=x kuni x=xxxxxxxxxxxxxxxxxxxx (20 x pärast =). Kui meil on 20 x pärast =, mootor lõpetab sobitamise 555 sammuga! (Pealegi, kui oleme kaotanud x= ja string koosneb lihtsalt 20-st x, teeb mootor 4067 sammu, et mõista, et vasteid pole).
See video näitab võrdluseks kõiki tagasikäike x=xxxxxxxxxxxxxxxxxxxx:
Probleem on selles, et stringi suuruse kasvades pikeneb sobitamisaeg ülilineaarselt. Kuid asjad võivad muutuda veelgi hullemaks, kui regulaaravaldist veidi muudetakse. Oletame, et meil oli .*.*=.*; (st mustri lõpus oli sõnasõnaline semikoolon). Näiteks selleks, et sobitada väljendit nagu foo=bar;.
Ja siin oleks tagasiminek tõeline katastroof. Võrdluseks x=x see võtab 90 sammu, mitte 23. Ja see arv kasvab kiiresti. Et võrrelda x= ja 20 x, on vaja 5353 sammu. Siin on diagramm. Vaadake telgede väärtusi Y võrreldes eelmise diagrammiga.
Kui olete huvitatud, vaadake kõiki 5353 ebaõnnestunud sobitamise sammu x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Kasutades pigem laisat kui ahnet sobitamist, saab tagasilöömise ulatust kontrollida. Kui muudame algse avaldise .*?.*?=.*?, võrdluseks x=x see võtab 11 sammu (mitte 23). Nagu x=xxxxxxxxxxxxxxxxxxxx. Kõik sellepärast ? pärast .* käsib mootoril enne edasiliikumist ühtida minimaalse arvu tähemärke.
Kuid laisk kaardistamine ei lahenda täielikult taganemise probleemi. Kui asendame katastroofilise näite .*.*=.*; edasi .*?.*?=.*?;, jääb täitmisaeg samaks. x=x nõuab ikkagi 555 sammu ja x= ja 20 x - 5353.
Ainus asi, mida saab teha (lisaks mustri täieliku ümberkirjutamise täpsemaks muutmiseks), on loobuda regulaaravaldise mootorist koos selle tagasiliikumise mehhanismiga. Seda me järgmise paari nädala jooksul teeme.
Selle probleemi lahendus on olnud teada alates 1968. aastast, mil Kent Thompson artikli kirjutas (“Programmeerimismeetodid: regulaaravaldise otsingu algoritm”). Artiklis kirjeldatakse mehhanismi, mis võimaldab regulaaravaldise teisendada mittedeterministlikeks lõplike olekumasinateks ning peale olekumuutusi mittedeterministlikes lõplikes olekumasinates kasutada algoritmi, mille täitmise aeg sõltub sobitatud stringist lineaarselt.
Programmeerimismeetodid
Regulaaravaldise otsingu algoritm
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseySee kirjeldab meetodit tekstist konkreetse märgijada otsimiseks ja käsitleb selle meetodi rakendamist kompilaatori kujul. Kompilaator võtab regulaaravaldise lähtekoodina ja toodab IBM 7094 programmi objektkoodina. Objektprogramm võtab sisendi otsinguteksti kujul ja saadab signaali iga kord, kui tekstistring seatakse vastavusse antud regulaaravaldisega. Artiklis on näiteid, probleeme ja lahendusi.
Algoritm
Varasemad otsingualgoritmid viisid tagasiteele, kui osaliselt edukas otsing ei andnud tulemust.Koostamisrežiimis algoritm sümbolitega ei tööta. See edastab juhised kompileeritud koodile. Täitmine on väga kiire – pärast andmete edastamist aktiivse loendi ülaossa otsib see regulaaravaldises automaatselt kõik võimalikud järjestikused märgid.
Kompileerimis- ja otsingualgoritm sisaldub ajajagamise tekstiredaktoris kontekstuaalse otsinguna. Loomulikult pole see sellise otsinguprotseduuri ainus rakendus. Näiteks kasutatakse selle algoritmi varianti sümbolite otsimiseks tabelis assembleris.
Eeldatakse, et lugeja tunneb regulaaravaldisi ja IBM 7094 arvutiprogrammeerimiskeelt.Koostaja
Kompilaator koosneb kolmest paralleelselt töötavast etapist. Esimene etapp on süntaksi filtreerimine, mis võimaldab läbida ainult süntaktiliselt õigeid regulaaravaldisi. See samm lisab regulaaravaldistele sobitamiseks ka operaatori "·". Teises etapis teisendatakse regulaaravaldis postfix-vormingusse. Kolmandas etapis luuakse objektikood. Esimesed 2 etappi on ilmsed ja me ei peatu neil.
Thompsoni artiklis ei räägita mittedeterministlikest lõplikest olekumasinatest, küll aga selgitatakse hästi lineaarse aja algoritmi ja esitatakse ALGOL-60 programm, mis genereerib IBM 7094 jaoks koostekeele koodi. Teostus on keeruline, kuid idee on väga lihtne.
praegune otsingutee. Seda tähistab ühe sisendi ja kahe väljundiga ikoon ⊕.
Joonis 1 näitab kolmanda kompileerimisetapi funktsioone regulaaravaldise näite teisendamisel. Näites olevad kolm esimest märki on a, b, c ja igaüks neist loob virna kirje S[i] ja välja NNODE.NNODE olemasolevale koodile, et genereerida sellest tulenev regulaaravaldis ühes pinu kirjes (vt joonis 5)
Selline näeks välja regulaaravaldis .*.*=.*, kui kujutate seda ette nagu Thompsoni artikli piltidel.
Joonisel fig. 0 on viis olekut, mis algavad 0-st, ja 3 tsüklit, mis algavad olekutest 1, 2 ja 3. Need kolm tsüklit vastavad kolmele .* regulaaravaldises. 3 täppidega ovaali vastavad ühele sümbolile. Ovaalne märgiga = sobib sõnasõnalise tähemärgiga =. Seisund 4 on lõplik. Kui jõuame selleni, siis regulaaravaldis sobitatakse.
Et näha, kuidas saab sellist olekudiagrammi kasutada regulaaravaldise sobitamiseks .*.*=.*, vaatame stringide sobitamist x=x. Programm algab olekust 0, nagu on näidatud joonisel fig. 1.
Selle algoritmi toimimiseks peab olekumasin olema korraga mitmes olekus. Mittedeterministlik lõplik masin teeb kõik võimalikud üleminekud üheaegselt.
Enne kui on aega sisendandmete lugemiseks, läheb see mõlemasse esimesse olekusse (1 ja 2), nagu on näidatud joonisel fig. 2.
Joonisel fig. 2 näitab, mis juhtub, kui ta vaatab esimest x в x=x. x saab kaardistada ülemise punktiga, minnes olekust 1 ja tagasi olekusse 1. Or x saab kaardistada alloleva punktiga, minnes olekust 2 ja tagasi olekusse 2.
Pärast esimese sobitamist x в x=x oleme endiselt olekutes 1 ja 2. Me ei saa jõuda olekusse 3 või 4, kuna vajame sõnasõnalist märki =.
Algoritm arvestab seejärel = в x=x. Nagu x enne seda, saab selle sobitada kahe ülemise tsükliga olekust 1 olekusse 1 või olekust 2 olekusse 2, kuid algoritm võib sobida literaaliga = ja liikuda olekust 2 olekusse 3 (ja kohe 4). See on näidatud joonisel fig. 3.
Seejärel liigub algoritm viimase juurde x в x=x. Olekust 1 ja 2 on samad üleminekud võimalikud tagasi olekutesse 1 ja 2. Olekust 3 x saab sobitada parempoolse punkti ja minna tagasi olekusse 3.
Selles etapis iga tegelane x=x ja kuna oleme jõudnud olekusse 4, vastab regulaaravaldis sellele stringile. Iga märki töödeldakse üks kord, seega on see algoritm sisendstringi pikkuses lineaarne. Ja ei mingit taganemist.
Ilmselgelt pärast olekusse 4 jõudmist (kui algoritm on ühtinud x=) sobitatakse kogu regulaaravaldis ja algoritm võib lõppeda ilma seda üldse arvesse võtmata x.
See algoritm sõltub lineaarselt sisendstringi suurusest.
Allikas: www.habr.com