Duela ia 9 urte Cloudflare enpresa txiki bat zen, eta ez nuen horretarako lanik egiten, bezero bat baino ez nintzen. Cloudflare abiarazi eta hilabetera, jakinarazpen bat jaso nuen nire webgunea Badirudi DNSk ez duela funtzionatzen. Cloudflare-k aldaketa bat egin du , eta DNS hautsita zegoen.
Berehala idatzi nion Matthew Princeri "Non dago nire DNS?" izenburuarekin eta erantzun luze bat bidali zidan xehetasun teknikoz beteta (), eta erantzun nion:
Egilea: John Graham-Cumming
Eguna: 7eko urriaren 2010a, 9:14
Gaia: Re: Non dago nire DNS?
Nori: Matthew PrinceTxosten polita, eskerrik asko. Zalantzarik gabe deituko dut arazoak izanez gero. Ziurrenik merezi du honi buruzko mezu bat idaztea informazio tekniko guztia bildu ondoren. Jendeak istorio ireki eta zintzo batez gozatuko duela uste dut. Batez ere, grafikoak eransten badituzu, abiarazi zenetik trafikoa nola hazi den erakusteko.
Jarraipen ona daukat nire webgunean, eta hutsegite bakoitzari buruzko SMS bat jasotzen dut. Jarraipenaren arabera, hutsegitea 13:03:07tik 14:04:12ra gertatu da. Probak bost minuturo egiten dira.
Ziur asmatuko duzula. Ziur ez duzula zure pertsonarik behar Europan? π
Eta hark erantzun:
Egilea: Matthew Prince
Eguna: 7eko urriaren 2010a, 9:57
Gaia: Re: Non dago nire DNS?
Nori: John Graham-CummingEskerrik asko. Idatzi duten guztiei erantzun diegu. Bulegora noa orain eta blogean zerbait idatziko dugu edo gure iragarki-taulan argitalpen ofizial bat jarriko dugu. Erabat ados nago, zintzotasuna dena da.
Orain Cloudflare oso enpresa handia da, horretarako lan egiten dut, eta orain argi idatzi behar dut gure akatsari, bere ondorioei eta gure ekintzei buruz.
Uztailaren 2ko ekitaldiak
Uztailaren 2an arau berri bat kaleratu genuen Kudeatutako Arauetan WAFetarako prozesadorearen nukleo guztietan HTTP/HTTPS trafikoa prozesatzen mundu osoan Cloudflare sarean. WAFen kudeatutako arauak etengabe hobetzen ari gara ahultasun eta mehatxu berriei erantzuteko. Maiatzean, esaterako, presaka ibili ginen SharePoint-en ahultasun larri baten aurka babesteko. Gure WAFaren helburu osoa arauak azkar eta globalki zabaltzeko gaitasuna da.
Zoritxarrez, joan den osteguneko eguneraketak HTTP/HTTPS CPU baliabide gehiegi alferrik galtzen zituen adierazpen erregular bat zuen atzera egiteko. Ondorioz, gure proxy nagusia, CDN eta WAF funtzioek jasan zuten. Grafikoak erakusten du HTTP/HTTPS trafikoa zerbitzatzeko prozesadorearen baliabideak ia % 100era iristen direla gure sareko zerbitzarietan.
PUZaren erabilera gertakari batean presentzia puntu batean
Ondorioz, gure bezeroek (eta gure bezeroen bezeroek) 502 errore orri batekin amaitu zuten Cloudflare domeinuetan. 502 errore sortu ziren Cloudflare frontend web zerbitzariek, oraindik nukleo libreak zituzten baina ezin izan ziren HTTP/HTTPS trafikoa kudeatzen duten prozesuekin komunikatu.
Badakigu horrek zenbat eragozpen eragin dituen gure bezeroei. Lotsa izugarria dugu. Eta hutsegite horrek gertakariari modu eraginkorrean aurre egitea eragotzi zigun.
Bezero horietako bat bazina, ziurrenik beldurra, haserre eta atsekabetuta egongo zinen. Gainera, ez dugu izan . CPU-kontsumo handia WAF arau batengatik izan zen, gaizki idatzitako adierazpen erregular batekin, eta horrek gehiegizko atzerakada eragin zuen. Hona hemen errudun adierazpena: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Hau berez interesgarria den arren (eta xehetasun gehiagorekin hitz egingo dut behean), Cloudflare zerbitzua 27 minutuz egon zen behera, ez bakarrik adierazpen erregular txarragatik. Porrota ekarri zuten gertaeren sekuentzia deskribatzeko pixka bat behar izan genuen, beraz, motel ibili ginen erantzuten. Argitalpenaren amaieran, atzera egitea adierazpen arrunt batean deskribatuko dut eta horrekin zer egin esango dizut.
Zer gertatu zen
Has gaitezen ordenan. Hemen ordu guztiak UTC-n daude.
13:42an, suebaki taldeko ingeniari batek aldaketa txiki bat egin du detekzio arauetan prozesu automatiko bat erabiliz. Horren arabera, aldaketa eskatzeko txartel bat sortu zen. Jira-ren bidez kudeatzen ditugu horrelako sarrerak (beheko pantaila-argazkia).
3 minuturen buruan, PagerDuty-ren lehen orrialdea agertu zen, WAF-ren arazo baten berri emanez. Cloudflare-tik kanpo WAFen (ehunka ditugu) funtzionaltasuna probatzen duen proba sintetikoa izan zen, funtzionamendu normala kontrolatzeko. Berehala, Cloudflare-ren amaierako zerbitzuen probak huts egiteari buruzko abisu-orriak, trafiko-arazo globalak, 502 akats hedatuak eta mundu osoko hirietan gure Presentzia Puntuetatik (PoP) txosten ugari agertu ziren. CPU baliabideak.
Alerta horietako hainbat jaso nituen, bilera batetik atera nintzen eta mahaira bidean nengoela gure soluzioen garapen saileko buruak trafikoaren %80 galdu genuela esan zuenean. Gure SRE ingeniariengana joan nintzen, jada arazoan lanean ari zirenak. Hasieran eraso ezezagun bat zela pentsatu genuen.
Cloudflare SRE ingeniariak munduan zehar sakabanatuta daude eta egoera etengabe kontrolatzen dute. Normalean, alerta hauek eremu mugatuko tokiko arazo zehatzen berri ematen dizute, barneko paneletan egiten dute jarraipena eta egunean hainbat aldiz konpontzen dira. Baina orri eta jakinarazpen hauek benetan zerbait larria adierazten zuten, eta SRE ingeniariek berehala P0 larritasun maila deklaratu zuten eta kudeaketa eta sistemaren ingeniariekin harremanetan jarri ziren.
Gure Londresko ingeniariak hitzaldi bat entzuten ari ziren areto nagusian une horretan. Hitzaldia eten behar izan zen, denak hitzaldi areto handi batean bildu ziren eta espezialista gehiago deitu ziren. Hau ez zen SREek beren buruari aurre egin zezaketen ohiko arazoa. Premiazkoa zen espezialista egokiak inplikatzea.
14:00etan zehaztu genuen arazoa WAFarekin zegoela eta ez zela erasorik egon. Errendimendu-taldeak CPUren datuak atera zituen eta argi geratu zen WAFa zela errua. Beste langile batek teoria hori baieztatu zuen strace erabiliz. Beste norbaitek erregistroetan ikusi zuen WAFarekin arazo bat zegoela. 14:02etan, talde osoa etorri zitzaidan hilketa globala erabiltzea proposatu zutenean, Cloudflare-n integratutako mekanismoa, mundu osoan osagai bat ixten duena.
WAF-rako hilketa globala nola egin genuen beste istorio bat da. Ez da hain erraza. Gure produktuak erabiltzen ditugu, eta gure zerbitzutik ez du funtzionatu, ezin izan dugu autentifikatu eta barne kontrol-panelean saioa hasi (dena konpondu zenean, taldekide batzuek sarbidea galdu zutela jakin genuen, kredentzialak desgaitzen dituen segurtasun-eginbide baten ondorioz, barne-kontrol-panela erabiltzen ez bada. Denbora luze).
Eta ezin izan genuen gure barne zerbitzuetara iritsi, Jira edo eraikuntza sistemara bezala. Konponbiderako mekanismo bat behar genuen, gutxitan erabiltzen genuena (hau ere landu beharko da). Azkenik, ingeniari batek WAF desgaitzea lortu zuen 14:07an, eta 14:09an, trafikoa eta CPU mailak normaltasunera itzuli ziren nonahi. Cloudflare-ren gainerako babes-mekanismoek normaltasunez funtzionatu zuten.
Ondoren, WAF berreskuratzeari ekin genion. Egoera ohikoa zen, beraz, proba negatiboak egin genituen (aldaketa benetan arazoa ote zen galdetuz) eta proba positiboak (erretiratzeak funtzionatzen zuela ziurtatuz) hiri batean trafiko bereizia erabiliz, ordainpeko bezeroak handik transferituz.
14:52an arrazoia ulertu eta zuzenketa bat egin genuela sinetsita geunden, eta WAF berriro gaitu genuen.
Nola funtzionatzen duen Cloudflare
Cloudflare-k WAFen arauak kudeatzeko ingeniari talde bat du. Detekzio tasak hobetzen, positibo faltsuak murrizten eta mehatxu berriei azkar erantzuten saiatzen dira, sortzen diren heinean. Azken 60 egunetan, 476 aldaketa-eskaera prozesatu dira WAF-rako kudeatutako arauetarako (batez beste, 3 orduz behin).
Aldaketa zehatz hau simulazio moduan zabaldu behar zen, non benetako bezeroen trafikoa arautik pasatzen den, baina ez da ezer blokeatzen. Modu hau arauen eraginkortasuna probatzeko eta positibo faltsuak eta negatibo faltsuak neurtzeko erabiltzen dugu. Baina simulazio moduan ere, arauak benetan exekutatu behar dira, eta kasu honetan arauak prozesadorearen baliabide gehiegi kontsumitzen zuen adierazpen erregular bat zuen.
Goiko aldaketa-eskaeran ikus dezakezun bezala, inplementazio-plan bat, itzulera-plan bat eta barne-prozedura operatibo estandar baterako (SOP) esteka ditugu inplementazio mota honetarako. Arau bat aldatzeko SOPak mundu osoan argitaratzeko aukera ematen du. Egia esan, Cloudflare-n, gauzak guztiz ezberdin egiten dira, eta SOP-ek agintzen du lehenik softwarea probak egiteko eta barne erabiltzeko barneko presentzia-puntu batera (PoP) bidaltzen dugula (gure langileek erabiltzen dutena), gero bezero kopuru txiki bati. kokapen isolatu bat, gero bezero kopuru handi bati, eta gero mundu osora.
Honela dirudi. BitBucket bidez git erabiltzen dugu barnean. Aldaketetan lan egiten duten ingeniariek TeamCity-n eraikitako kodea bidaltzen dute eta eraikuntza pasatzen denean, ebaluatzaileak esleitzen dira. Behin tira-eskaera onartzen denean, kodea muntatu eta proba batzuk egiten dira (berriro).
Eraikuntza eta probak behar bezala amaitzen badira, aldaketa eskaera bat sortzen da Jira-n eta dagokion kudeatzaileak edo arduradunak aldaketa onartu beharko du. Onartu ondoren, hedapena "PoP menagerie" izenekoan gertatzen da: TXAKURRA, TXERRIA eta (txakurra, txerria eta kanarioa).
DOG PoP Cloudflare PoP bat da (gure hiri guztietan bezala), Cloudflare-ko langileek soilik erabiltzen dutena. Barne erabilerarako PoP-ek arazoak harrapatzeko aukera ematen dizu bezeroen trafikoa konponbidera iristen hasi aurretik. Gauza erabilgarria.
DOG proba arrakastatsua bada, kodea TXERRIK (Cobaya) fasera mugitzen da. Hau Cloudflare PoP da, non doako bezeroen trafiko kopuru txiki bat kode berriaren bidez pasatzen den.
Dena ondo badago, kodea Kanarietara doa. Kanariar hiru PoP ditugu munduko leku ezberdinetan. Horietan, ordaindutako eta doako bezeroen trafikoa kode berritik pasatzen da, eta hau da akatsen azken egiaztapena.
Softwarea askatzeko prozesua Cloudflare-n
Kanarian kodea ondo badago, askatzen dugu. Etapa guztiak igarotzea - ββTXAKURRA, TXERRIA, Kanariar, mundu osoa - hainbat ordu edo egun behar ditu, kode aldaketaren arabera. Cloudflare-ren sarearen eta bezeroen aniztasuna dela eta, guztiz probatzen dugu kodea bezero guztiei globalki kaleratu aurretik. Baina WAFek ez du prozesu hau zehazki jarraitzen mehatxuei azkar erantzun behar zaielako.
WAF mehatxuak
Azken urteotan, mehatxuak ugaritu egin dira ohiko aplikazioetan. Hau software probatzeko tresnen erabilgarritasun handiagoa dela eta. Adibidez, duela gutxi idatzi dugu ).
Iturria:
Askotan, kontzeptu-froga bat sortu eta berehala argitaratzen da Github-en, aplikazioa mantentzen duten taldeek azkar probatu dezaten eta behar bezala babestuta dagoela ziurtatzeko. Hori dela eta, Cloudflare-k eraso berriei ahalik eta azkarren erantzuteko gaitasuna behar du, bezeroek beren softwarea konpontzeko aukera izan dezaten.
Cloudflare-ren erantzun azkarraren adibide bikaina maiatzean SharePoint ahultasunen babesak ezartzea da (). Iragarpenak egin eta ia berehala, gure bezeroen SharePoint instalazioetan ahultasuna ustiatzeko saiakera ugari nabaritu ditugu. Gure mutilak etengabe kontrolatzen ari dira mehatxu berriak eta arauak idazten ari dira gure bezeroak babesteko.
Ostegunean arazoa eragin zuen arauak guneen arteko scripten (XSS) aurka babestu behar zuen. Eraso horiek ere askoz ere maizago bihurtu dira azken urteotan.
Iturria:
WAF baterako kudeatutako arau bat aldatzeko prozedura estandarra integrazio jarraitua (CI) probak egitea da inplementazio globala baino lehen. Joan den ostegunean hau egin genuen eta arauak zabaldu genituen. 13:31ean, ingeniari batek onartutako tira-eskaera aurkeztu zuen aldaketa batekin.
13:37an TeamCity-k arauak bildu, probak egin eta baimena eman zuen. WAF proba-multzoak WAF-ren oinarrizko funtzionaltasuna probatzen du eta funtzio indibidualetarako unitate-proba ugari ditu. Unitate-probak egin ondoren, WAF-rako arauak probatu ditugu HTTP eskaera ugari erabiliz. HTTP eskaerak WAFek zein eskaera blokeatu behar dituen (erasoa atzemateko) eta zeintzuk baimendu daitezkeen egiaztatzen dute (dena ez blokeatzeko eta positibo faltsuak ekiditeko). Baina ez genuen PUZaren gehiegizko erabilera probatu, eta aurreko WAF-en eraikitzeen erregistroak aztertzeak erakusten du arauen probaren exekuzio-denbora ez zela handitu, eta zaila zen susmatzea nahikoa baliabide ez zela egongo.
Probak gainditu eta TeamCity 13:42an hasi zen aldaketa automatikoki zabaltzen.
Quicksilver
WAF arauak berehalako mehatxuen konponketan oinarritzen dira, beraz, Quicksilver-en banatutako gako-balioen biltegia erabiliz zabaltzen ditugu, aldaketak segundotan hedatzen dituen mundu osoan. Gure bezero guztiek teknologia hori erabiltzen dute aginte-panelean edo APIaren bidez konfigurazioa aldatzen dutenean, eta horri esker, tximista-abiadurarekin erantzuten diegu aldaketei.
Ez dugu asko hitz egin Quicksilver-i buruz. Aurretik erabiltzen genuen Mundu osoan banatutako gako-balioen denda gisa, baina funtzionamendu-arazoak izan zituen horrekin, eta gure denda propioa idatzi genuen, 180 hiri baino gehiagotan errepikatua. Orain Quicksilver erabiltzen dugu bezeroei konfigurazio-aldaketak bultzatzeko, WAF arauak eguneratzeko eta bezeroek idatzitako JavaScript kodea Cloudflare Workers-i banatzeko.
Segundo gutxi batzuk besterik ez dira behar aginte-paneleko botoi bat sakatu edo API batera deitzetik mundu osoan konfigurazio-aldaketa bat egiteko. Bezeroek konfigurazio-abiadura hau maite zuten. Eta Workers-ek software globalaren ia berehalako hedapena ematen die. Batez beste, Quicksilver-ek 350 aldaketa inguru hedatzen ditu segundoko.
Eta Quicksilver oso azkarra da. Batez beste, 99 segundoko 2,29. pertzentilea lortu dugu aldaketak mundu osoko ordenagailu guztietara hedatzeko. Abiadura gauza ona da normalean. Azken finean, funtzio bat gaitzen duzunean edo cachea garbitzen duzunean, ia berehala eta nonahi gertatzen da. Cloudflare Workers-en bidez kodea bidaltzea abiadura berean gertatzen da. Cloudflare-k bere bezeroei une egokian eguneratze azkarrak agintzen die.
Baina kasu honetan, abiadurak txantxa ankerra egin zigun, eta arauak nonahi aldatzen ziren segundo gutxitan. Baliteke WAF kodeak Lua erabiltzen duela konturatu izana. Cloudflare-k Lua asko erabiltzen du ekoizpenean eta xehetasunetan dugu . Lua WAF erabiltzen du barnean eta parekatzeko atzerakada aplikatzen du. Ez du kontroletik kanpo dauden esamoldeetatik babesteko mekanismorik. Jarraian gehiago hitz egingo dut honi buruz eta zer egiten ari garen horri buruz.
Arauak zabaldu aurretik, dena ondo joan zen: pull eskaera sortu eta onartu zen, CI/CD kanalizazioak kodea bildu eta probatu zuen, aldaketa eskaera inplementazioa eta atzerapena arautzen dituen SOParen arabera aurkeztu zen eta hedapena amaitu zen.
Cloudflare WAF inplementazio prozesua
Zerbait gaizki joan da
Esan dudan bezala, hamaika WAF arau berri zabaltzen ditugu astero, eta sistema asko ditugu inplementazio horren ondorio negatiboetatik babesteko. Eta zerbait gaizki doanean, aldi berean hainbat zirkunstantziaren konbinazioa izan ohi da. Arrazoi bakarra aurkitzen baduzu, hori, noski, lasaigarria da, baina ez da beti egia. Hauek dira elkarrekin gure HTTP/HTTPS zerbitzuaren porrota ekarri duten arrazoiak.
- Ingeniari batek gehiegizko eragin dezakeen adierazpen erregular bat idatzi zuen .
- Adierazpen erregularrak CPU gehiegi xahutzea eragotzi zezakeen funtzio bat oker kendu zen WAFaren birfaktorizazioan hainbat aste lehenago: birfactorizazioa beharrezkoa zen WAFek baliabide gutxiago kontsumitzeko.
- Adierazpen erregular motorrak ez zuen konplexutasun bermerik.
- Proba-multzoak ezin izan du detektatu CPU gehiegizko kontsumoa.
- SOP-ek larrialdikoak ez diren arau-aldaketak mundu osoan zabaltzea ahalbidetzen du, urrats anitzeko prozesurik gabe.
- Berrezartzeko planak WAF eraikitze osoa bi aldiz exekutatu behar zuen, eta horrek denbora luzea izan zuen.
- Mundu mailako trafiko arazoei buruzko lehen alerta beranduegi piztu zen.
- Denbora pixka bat behar izan dugu egoera orria eguneratzeko.
- Arazoak izan ditugu sistemetara sartzeko, akats baten ondorioz, eta saihesbide prozedura ez zegoen ondo ezarrita.
- SRE ingeniariek sistema batzuetarako sarbidea galdu zuten, segurtasun arrazoiengatik kredentzialak iraungi zirelako.
- Gure bezeroek ez zuten Cloudflare panel edo APIrako sarbidea izan Cloudflare eskualde batetik igarotzen direlako.
Joan den ostegunetik aldatu dena
Lehenik eta behin, WAF-rako kaleratzeen lan guztiak erabat gelditu ditugu eta honako hau egiten ari gara:
- Kendu genuen CPU gehiegizko erabilera babesa berriro sartzen ari gara. (Prest)
- Kudeatutako arauetako 3868 arau guztiak eskuz egiaztatzea WAF-rako, gehiegizko atzerapenaren beste kasu posible batzuk aurkitzeko eta zuzentzeko. (Egiaztapena osatu da)
- Arau guztien errendimendu-profila sartzen dugu proba multzoan. (Aurreikuspena: uztailak 19)
- Adierazpen erregular motorra aldatzea edo - biek exekuzio-garaiaren bermeak eskaintzen dituzte. (Aurreikuspena: uztailak 31)
- SOP berridazten ari gara arauak etapaka zabaltzeko, Cloudflare-ko beste software batzuk bezala, baina, aldi berean, mundu mailako larrialdietarako gaitasuna dugu erasoak dagoeneko hasi badira.
- Cloudflareren aginte-panela eta APIa Cloudflare eskualdetik premiaz kentzeko gaitasuna garatzen ari gara.
- Orriaren eguneraketak automatizatzea .
Epe luzera duela urte batzuk idatzi nuen Lua WAFetik urruntzen ari gara. WAF-ra mugitzen . Horrela WAF azkarragoa izango da eta babes maila gehigarria jasoko du.
Ondorioa
Porrot honek arazoak eragin zizkigun guri eta gure bezeroei. Azkar jokatu dugu egoera zuzentzeko eta orain istripua eragin duten prozesuen akatsak lantzen ari gara, baita are gehiago sakontzen teknologia berrietara migratzean adierazpen erregularrak izan ditzaketen arazoetatik babesteko.
Oso lotsatuta gaude etenaldi honek eta barkamena eskatzen diegu gure bezeroei. Espero dugu aldaketa hauek horrelako zerbait berriro ez gertatzea ziurtatzea.
Aplikazio. Adierazpen erregularrak atzera egitea
Adierazpena nola ulertzen den:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))CPU baliabide guztiak jan, apur bat jakin behar duzu nola funtzionatzen duen adierazpen erregular estandarraren motorra. Hemen arazoa eredua da .*(?:.*=.*). (?: eta dagozkionak ) harrapatzen ez den talde bat da (hau da, parentesi arteko adierazpena adierazpen bakar gisa biltzen da).
CPU gehiegizko kontsumoaren testuinguruan, eredu hau honela deskriba daiteke .*.*=.*. Forma honetan, ereduak alferrikako konplexua dirudi. Baina are garrantzitsuagoa dena, mundu errealean, motorra zati bat eta beste zati batekin bat etortzea eskatzen duten esamoldeek (WAF arauetako esamolde konplexuak bezala) atzerakada hondamendia ekar dezakete. Eta horregatik.
Adierazpen erregularrean . karaktere batekin bat egin behar duzula esan nahi du, .* - lotu zero edo gehiago karaktere "greedily", hau da, karaktere gehienez harrapatzea, horrela .*.*=.* Zero karaktere edo gehiago bat etortzea esan nahi du, gero zero edo karaktere gehiago bat etortzea, aurkitu literala = karakterea, bat zero edo gehiago karaktere.
Har dezagun proba-lerroa x=x. Adierazpenari dagokio .*.*=.*. .*.* berdin zeinua lehenengoarekin bat etorri baino lehen x (Taldeetako bat .* ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ x, eta bigarrena - zero karaktere). .* ondoren = azken partidak x.
Konparazio honek 23 urrats behar ditu. Lehenengo taldea .* Π² .*.*=.* gutiziaz jokatzen du eta kate osoarekin bat egiten du x=x. Motorra hurrengo taldera mugitzen da .*. Ez daukagu ββparekatzeko pertsonaia gehiago, beraz, bigarren taldea .* zero karaktere bat dator (hau onartzen da). Ondoren, motorra seinalera mugitzen da =. Ez dago ikur gehiago (lehen taldea .* esamolde osoa erabili zuen x=x), ez da konparaziorik gertatzen.
Eta gero, adierazpen erregular motorra hasierara itzultzen da. Lehen taldera pasatzen da .* eta konparatzen du Ρ x= (ordez x=x), eta gero bigarren taldea hartzen du .*. Bigarren taldea .* bigarrenarekin alderatzen da x, eta berriro ez zaigu pertsonaiarik geratzen. Eta motorra berriro iristen denean = Π² .*.*=.*, ezer ez dabil. Eta atzera egiten du berriro.
Oraingoan taldea .* oraindik partidak x=, baina bigarren taldea .* Gehiagorik ez x, eta zero karaktere. Motorra pertsonaia literal bat aurkitzen saiatzen ari da = ereduan .*.*=.*, baina ez da ateratzen (azken finean, lehen taldeak dagoeneko okupatu du .*). Eta atzera egiten du berriro.
Oraingoan lehenengo taldea .* lehenengo x bakarrik hartzen du. Baina bigarren taldea .* "zikorki" harrapatzen du =x. Asmatu al duzu jada zer gertatuko den? Motorra literalarekin bat egiten saiatzen da =, huts egin eta beste atzerakada bat egiten du.
Lehenengo taldeko .* oraindik lehenarekin bat dator x... Bigarrena .* bakarrik hartzen du =. Noski, motorra ezin da bat egin literalarekin =, bigarren taldeak dagoeneko egin duelako .*. Eta berriro atzeraka. Eta hiru karaktere-kate bat lotzen saiatzen ari gara!
Ondorioz, lehenengo taldea .* lehenengoarekin bakarrik bat dator x, bigarrena .* - zero karaktererekin, eta motorra azkenean literalarekin bat dator = adierazpenean Ρ = lerroan. Hurrengoa azken taldea da .* azkenekoarekin alderatzen da x.
23 urrats soilik x=x. Ikusi Perl erabiltzeari buruzko bideo labur bat , urratsak eta atzeraka nola gertatzen diren erakusten duena.
Hau dagoeneko lan handia da, baina zer gertatuko balitz x=x izango dugu x=xx? Hori da 33 urrats. Eta bada x=xxx? 45. Erlazioa ez da lineala. Grafikoak alderaketa bat erakusten du x=x to x=xxxxxxxxxxxxxxxxxxxx (20 x ondoren =). Ondoren 20 x baditugu =, motorrak 555 urratsetan osatzen du parekatzea! (Gainera, galdu badugu x= eta katea besterik gabe 20z osatuta dago x, motorrak 4067 urrats emango ditu parekorik ez dagoela ulertzeko).
Bideo honek konparaziorako atzerabide guztiak erakusten ditu x=xxxxxxxxxxxxxxxxxxxx:
Arazoa da soka-tamaina handitzen den heinean, uztartze-denbora superlinealki hazten dela. Baina gauzak are okerrago egin daitezke adierazpen erregularra apur bat aldatzen bada. Demagun genuela .*.*=.*; (hau da, ereduaren amaieran puntu eta kom literal bat zegoen). Adibidez, bezalako esamolde batekin lotzeko foo=bar;.
Eta hemen atzera egitea benetako hondamendia izango litzateke. Konparaziorako x=x 90 urrats emango ditu, ez 23. Eta kopuru hori azkar hazten ari da. Konparatzeko x= eta 20 x, 5353 urrats behar dira. Hona hemen taula. Begiratu ardatzaren balioak Y aurreko grafikoarekin alderatuta.
Interesatzen bazaizu, begiratu bat etortzen diren 5353 urrats guztiak x=xxxxxxxxxxxxxxxxxxxx ΠΈ .*.*=.*;
Bat-etortze alferrak erabili beharrean, atzera egiteko norainokoa kontrolatu daiteke. Jatorrizko esamoldea aldatzen badugu .*?.*?=.*?, konparaziorako x=x 11 urrats emango ditu (ez 23). Gisa x=xxxxxxxxxxxxxxxxxxxx... Dena delako ? ondoren .* aurrera jarraitu aurretik, motorrari gutxieneko karaktere kopuru batekin bat etortzeko esaten dio.
Baina alfer-mapeek ez dute guztiz konpontzen atzera egiteko arazoa. Adibide katastrofikoa ordezkatzen badugu .*.*=.*; on .*?.*?=.*?;, exekuzio denbora berdina izango da. x=x oraindik 555 urrats eskatzen ditu, eta x= eta 20 x - 5353.
Egin daitekeen gauza bakarra (eredua guztiz berridazteaz gain, espezifikotasun handiagoa lortzeko) adierazpen erregularraren motorra alde batera uztea da, atzera egiteko mekanismoarekin. Hau da hurrengo asteetan egingo duguna.
Arazo honen konponbidea 1968tik ezagutzen da, Kent Thompsonek artikulu bat idatzi zuenetik ("Programazio-metodoak: Adierazpen erregular bilaketa-algoritmoa"). Artikuluak adierazpen erregular bat egoera finitu ez-deterministikoko makinetan bihurtzeko aukera ematen duen mekanismo bat deskribatzen du, eta egoera-aldaketa ez-deterministikoko makinetan egoera-aldaketen ondoren, exekuzio-denbora bat datorren katearen araberakoa den algoritmo bat erabili.
Programazio metodoak
Adierazpen erregularrak bilatzeko algoritmoa
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyTestuan karaktere kate zehatz bat bilatzeko metodo bat deskribatzen du eta metodo honen ezarpena konpilatzaile moduan eztabaidatzen du. Konpilatzaileak adierazpen erregularra hartzen du iturburu-kode gisa eta IBM 7094 programa ekoizten du objektu-kode gisa. Objektu-programak bilaketa-testu moduan hartzen du sarrera eta seinale bat igortzen du testu-kate bat adierazpen erregular batekin parekatzen den bakoitzean. Artikuluak adibideak, arazoak eta irtenbideak eskaintzen ditu.
Algoritmoa
Aurreko bilaketa-algoritmoek atzera egin zuten bilaketa partzialki arrakastatsu batek emaitzarik lortzen ez bazuen.Konpilazio moduan, algoritmoak ez du ikurrekin funtzionatzen. Konpilatutako kodeari argibideak pasatzen dizkio. Exekuzioa oso azkarra da: datuak uneko zerrendaren goialdera pasa ondoren, automatikoki bilatzen ditu adierazpen erregularrean jarraian daitezkeen karaktere guztiak.
Konpilazio- eta bilaketa-algoritmoa denbora partekatzeko testu-editorean sartzen da testuinguruko bilaketa gisa. Jakina, hau bilaketa-prozeduraren aplikazio bakarretik urrun dago. Esate baterako, algoritmo honen aldaera bat sinboloen bilaketa gisa erabiltzen da mihiztatzaileko taula batean.
Irakurleak esamolde erregularrak eta IBM 7094 ordenagailu programazio-lengoaia ezagutzen dituela suposatzen da.Konpilatzailea
Konpilatzaileak hiru fase ditu paraleloan. Lehen fasea sintaxi-iragazkia da, eta horrek sintaktikoki zuzenak diren adierazpen erregularrak baino ez ditu pasatzen uzten. Urrats honek "Β·" operadorea ere txertatzen du adierazpen erregularrak bat etortzeko. Bigarren urratsean, adierazpen erregularra postfix formara bihurtzen da. Hirugarren fasean, objektu-kodea sortzen da. Lehenengo 2 etapak begi bistakoak dira, eta ez gara horietan geldituko.
Thompson-en artikuluak ez du egoera finitu gabeko makinei buruz hitz egiten, baina denbora linealaren algoritmoa ondo azaltzen du eta IBM 60rako mihiztadura-lengoaiaren kodea sortzen duen ALGOL-7094 programa bat aurkezten du. Inplementazioa zaila da, baina ideia oso erraza da.
uneko bilaketa-bidea. Sarrera bakarra eta bi irteera dituen β ikono batez adierazten da.
1. irudiak hirugarren konpilazio-urratsaren funtzioak erakusten ditu adierazpen erregular baten adibidea eraldatzen denean. Adibideko lehen hiru karaktereak a, b, c dira eta bakoitzak S[i] pila-sarrera eta NNODE eremu bat sortzen ditu.NNODE lehendik dagoen kodean sortzen den adierazpen erregularra pila-sarrera bakarrean sortzeko (ikus 5. irudia)
Honela izango litzateke adierazpen erregular bat .*.*=.*, Thompsonen artikuluko irudietan bezala imajinatzen baduzu.
Irudian. 0 bost egoera daude 0tik hasita, eta 3., 1. eta 2. egoeretatik abiatzen diren 3 ziklo. Hiru ziklo hauek hiruri dagozkio. .* adierazpen erregular batean. Puntudun 3 obalo ikur bati dagozkio. Obalatua zeinu batekin = karaktere literal batekin bat dator =. 4. egoera behin betikoa da. Bertara iristen bagara, adierazpen erregularra bat dator.
Adierazpen erregularrak parekatzeko egoera-diagrama hori nola erabil daitekeen ikusteko .*.*=.*, kateen bat etortzea aztertuko dugu x=x. Programa 0 egoeratik abiatzen da, irudian ikusten den bezala. 1.
Algoritmo honek funtziona dezan, egoera-makinak hainbat egoeratan egon behar du aldi berean. Makina finitu ez-determinista batek trantsizio posible guztiak egingo ditu aldi berean.
Sarrerako datuak irakurtzeko astirik izan baino lehen, lehenengo egoeretara doa (1 eta 2), irudian ikusten den bezala. 2.
Irudian. 2. lehenengoari begiratzean zer gertatzen den erakusten du x Π² x=x. x goiko puntura mapatu daiteke, 1. egoeratik eta 1. egoerara itzuliz. Edo x beheko puntura mapatu daiteke, 2. egoeratik eta 2. egoerara itzuliz.
Lehenengoa parekatu ondoren x Π² x=x oraindik 1 eta 2 egoeretan gaude. Ezin gara 3 edo 4 egoerara heldu karaktere literal bat behar dugulako =.
Orduan algoritmoak kontuan hartzen du = Π² x=x. Aurretik x bezala, 1 egoeratik 1. egoerara edo 2. egoeratik 2. egoerara goiko bi begiztekin pareka daiteke, baina algoritmoak literalarekin bat egin dezake. = eta 2. egoeratik 3. egoerara joan (eta berehala 4). Hau irudian ageri da. 3.
Ondoren, algoritmoa azkenera pasatzen da x Π² x=x. 1 eta 2 egoeretatik trantsizio berdinak posible dira 1 eta 2 egoeretara itzultzeko. 3. egoeratik x eskuineko puntuarekin bat etor daiteke eta 3. egoerara itzuli.
Etapa honetan, pertsonaia bakoitza x=x kontuan hartuta, eta 4. egoerara iritsi garenez, adierazpen erregularrak bat dator kate horrekin. Karaktere bakoitza behin prozesatzen da, beraz, algoritmo hau lineala da sarrerako katearen luzeran. Eta atzera egin gabe.
Jakina, 4. egoerara iritsi ondoren (algoritmoa bat datorrenean x=) Adierazpen erregular osoa bat dator, eta algoritmoa amai daiteke batere kontuan hartu gabe x.
Algoritmo hau sarrerako katearen tamainaren araberakoa da linealki.
Iturria: www.habr.com