Anenge makore 9 apfuura Cloudflare yaive kambani diki, uye ini handina kuishandira, ndaingova mutengi. Mwedzi mushure mekutanga Cloudflare, ndakagamuchira chiziviso chekuti webhusaiti yangu DNS inoita kunge isiri kushanda. Cloudflare yakaita shanduko kune , uye pakanga pane DNS yakatyoka.
Ndakabva ndanyorera kuna Matthew Prince ine zita rekuti "DNS yangu iripi?" uye akatumira mhinduro refu izere neruzivo rwehunyanzvi (), ndakapindura kuti:
Kubva: John Graham-Cumming
Date: Gumiguru 7, 2010, 9:14
Musoro: Re: DNS yangu iripi?
Kuna: Matthew PrinceChirevo chakanaka, ndatenda. Ndichafona zvechokwadi kana paine matambudziko. Zvingangodaro zvakakodzera kunyora positi nezve izvi kana iwe uchinge waunganidza ese ruzivo rwehunyanzvi. Ndinofunga kuti vanhu vachanakidzwa nenyaya yakavhurika uye yakatendeseka. Kunyanya kana iwe ukabatanidza magirafu kwairi kuratidza kuti traffic yakakura sei kubva pakatangwa.
Ndine kutarisa kwakanaka pane yangu saiti, uye ndinogamuchira SMS nezve kutadza kwese. Kuongorora kunoratidza kuti kukundikana kwakaitika kubva 13:03:07 kusvika 14:04:12. Miedzo inoitwa maminitsi mashanu ega ega.
Ndine chokwadi chekuti uchazvinzwisisa. Une chokwadi here kuti haudi munhu wako muEurope? π
Uye akapindura:
Kubva: Matthew Prince
Date: Gumiguru 7, 2010, 9:57
Musoro: Re: DNS yangu iripi?
Kuna: John Graham-CummingNdatenda. Takapindura vese vakanyora. Ndiri munzira kuenda kuhofisi izvozvi uye tichanyora chimwe chinhu pablogi kana kubaya chinyorwa chepamutemo pabhodhi redu rekuzivisa. Ndinobvumirana zvachose, kutendeseka ndicho chinhu chose.
Iye zvino Cloudflare ikambani yakakura chaizvo, ndinoishandira, uye zvino ndinofanira kunyora pachena pamusoro pekukanganisa kwedu, migumisiro yayo uye zviito zvedu.
Zviitiko zveChikunguru 2
Musi waChikunguru 2nd takaburitsa mutemo mutsva muManaged Mitemo yeWAFs nekuda kwayo pane yega yega processor core kugadzirisa HTTP/HTTPS traffic pane Cloudflare network pasi rese. Isu tiri kugara tichivandudza mitemo inogadziriswa yeWAFs mukupindura kusagadzikana kutsva uye kutyisidzira. Muna May, somuenzaniso, takakurumidza kudzivirira kubva panjodzi yakakomba muSharePoint. Yese poindi yeWAF yedu kugona kukurumidza uye pasi rose kuendesa mitemo.
Nehurombo, yemusi weChina wapfuura gadziriso yaive neyakajairwa kutaura iyo yakapambadza yakawandisa HTTP/HTTPS CPU zviwanikwa pakudzosera kumashure. Yedu yepakati proxy, CDN, uye WAF mabasa akatambura semhedzisiro. Iyo girafu inoratidza kuti processor zviwanikwa zvekushandira HTTP/HTTPS traffic inosvika zana muzana pamaseva munetiweki yedu.
Kushandiswa kweCPU pane imwe nguva yekuvapo panguva yechiitiko
Nekuda kweizvozvo, vatengi vedu (uye vatengi vedu vatengi) vakaguma vaine 502 kukanganisa peji muCloudflare domains. 502 mhosho dzakagadzirwa neCloudflare kumberi-kumagumo ewebhu maseva anga achiri nemahara cores asi akatadza kutaurirana nemaitiro ekubata HTTP/HTTPS traffic.
Isu tinoziva kuti izvi zvakakonzera kukanganisa kwakadii vatengi vedu. Takanyara zvisingaite. Uye kukundikana uku kwakatitadzisa kubata nemazvo chiitiko ichi.
Kana iwe waive mumwe wevatengi ava, unenge uchitya, wakatsamwa uye wakagumbuka. Uyezve, hatina kumbova nea . Kushandiswa kweCPU kwakakwira kwaikonzerwa nemutemo mumwe weWAF uine kushomeka kwemazwi nguva dzose izvo zvakakonzera kudzosera kumashure zvakanyanya. Heinoi mhosva kutaura: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Kunyange izvi zvichinakidza pachazvo (uye ini ndichataura nezvazvo zvakadzama pazasi), iyo Cloudflare sevhisi yaive pasi kwemaminetsi makumi maviri nemanomwe kwete nekuda kwekutaura kwakashata nguva dzose. Zvakatora nguva kuti titsanangure kutevedzana kwezviitiko zvakakonzera kukundikana, saka takanonoka kupindura. Pakupera kwechinyorwa, ini ndichatsanangura kudzokera kumashure mune yenguva dzose kutaura uye kukuudza zvekuita nazvo.
Chii chaitika
Ngatitangei muhurongwa. Nguva dzese pano dziri muUTC.
Na13:42 p.m., injiniya pachikwata chefirewall akaita shanduko diki kumitemo yekuona. kushandisa otomatiki maitiro. Saizvozvo, tikiti rekukumbira shanduko rakagadzirwa. Isu tinotarisira matikiti akadaro kuburikidza neJira (screenshot pazasi).
Mushure memaminitsi matatu, peji rekutanga rePagerDuty rakaonekwa, richitaura dambudziko neWAF. Iyi yaive bvunzo yekugadzira iyo inoedza mashandiro eWAFs (tine mazana awo) kunze kweCloudflare kutarisa kushanda kwakajairika. Izvi zvakabva zvateverwa nemapeji echenjedzo nezve mamwe Cloudflare kupera-ku-kuguma-sevhisi bvunzo kutadza, nyaya dzetraffic dzepasi rose, kukanganisa kwakapararira kwe3, uye toni yemishumo kubva kuPoints of Presence (PoP) mumaguta epasirese yakaratidza kushomeka. yeCPU zviwanikwa.
Ndakatambira akati wandei echenjedzo idzi, ndikabuda mumusangano, uye ndakanga ndiri munzira kuenda kutafura apo mukuru wedhipatimendi redu rekugadzirisa mhinduro akati takanga tarasikirwa ne80% yetraffic yedu. Ndakamhanyira kune vedu SRE mainjiniya, avo vakanga vatoshanda padambudziko. Pakutanga takafunga kuti kwaiva kumwe kurwiswa kusingazivikanwi.
Cloudflare SRE mainjiniya akapararira pasirese uye anotarisisa mamiriro acho nguva dzese. Kazhinji, zviziviso izvi zvinokuzivisa iwe nezvenyaya dzenzvimbo dzenzvimbo shoma, dzinotevedzwa pamadhibhodhi emukati, uye dzinogadziriswa kakawanda pazuva. Asi aya mapeji uye zviziviso airatidza chimwe chinhu chakakomba, uye mainjiniya eSRE akabva angozivisa iyo yekuomarara nhanho P0 uye akabata manejimendi uye masisitimu mainjiniya.
Mainjiniya edu eLondon akanga achiteerera hurukuro muhoro huru panguva iyoyo. Hurukuro yacho yaifanira kumbomiswa, vanhu vose vakaungana muimba huru yemusangano, uye nyanzvi dzakawanda dzakadanwa. Iri rakanga risiri dambudziko rakajairwa iro SREs dzaigona kubata nadzo. Zvaiva zvekukurumidzira kubatanidza nyanzvi dzakakodzera.
Na14:00 takaona kuti dambudziko raive neWAF uye pakanga pasina kurwisa. Chikwata chekuita chakadhonza data reCPU uye zvakava pachena kuti WAF yaive mhosva. Mumwe mushandi akasimbisa dzidziso iyi achishandisa strace. Mumwewo akaona mumatanda kuti paita dambudziko neWAF. Na14:02 p.m., timu yese yakauya kwandiri payakanzi ishandise kuuraya kwepasirese, nzira yakavakirwa muCloudflare inovhara chikamu chimwe pasi rese.
Kuuraya kwatakaita pasi rose kweWAF inyaya yakasiyana. Hazvisi nyore kudaro. Isu tinoshandisa zvigadzirwa zvedu, uye kubva sevhisi yedu hazvina kushanda, hatina kukwanisa kutendesa uye kupinda mukati mekutonga kwemukati (kana zvese zvagadziriswa, takadzidza kuti dzimwe nhengo dzechikwata dzakarasikirwa nekuwana nekuda kwechinhu chekuchengetedza chinodzima zvitupa kana iyo yemukati control panel ikasashandiswa nguva refu).
Uye isu hatina kukwanisa kusvika kumasevhisi edu emukati, seJira kana sisitimu yekuvaka. Isu taida workaround mechanism, yataishandisa zvisingaite (izvi zvinodawo kugadziriswa). Pakupedzisira, mumwe mainjiniya akakwanisa kudzima WAF na14:07, uye na14:09, traffic uye CPU mazinga akange adzokera kune zvakajairika kwese kwese. Dzimwe nzira dzekudzivirira dzeCloudflare dzakashanda semazuva ese.
Ipapo takatanga kudzoreredza iyo WAF. Mamiriro acho aive kunze kweakajairika, saka takamhanyisa bvunzo dzisina kunaka (tichizvibvunza kana shanduko yaive dambudziko) uye bvunzo dzakanaka (kuita shuwa kuti rollback yakashanda) mune rimwe guta tichishandisa yakaparadzana traffic, kutamisa vatengi vanobhadhara kubva ipapo.
Na14:52 takave nechokwadi chekuti takanzwisisa chikonzero uye takagadzirisa, uye takagonesa WAF zvakare.
Cloudflare inoshanda sei
Cloudflare ine timu yeinjiniya yakazvipira kutonga mitemo yeWAFs. Vanoedza kuvandudza mazinga ekuona, kuderedza maitiro enhema, uye nekukurumidza kupindura kune zvitsva zvinotyisidzira sezvazvinobuda. Mumazuva makumi matanhatu apfuura, kwave ne60 zvikumbiro zvekuchinja zvakagadziridzwa pamitemo inotungamirwa yeWAF (avhareji yemaawa matatu ega ega).
Iyi shanduko chaiyo yaida kuisirwa mune yekufananidza modhi, uko chaiyo mutengi traffic inopfuura nemutemo, asi hapana chakavharika. Isu tinoshandisa iyi modhi kuti tiedze kushanda kwemitemo uye kuyera iyo yenhema yakanaka uye yemanyepo yakaipa mitengo. Asi kunyangwe mune yekufananidza modhi, iyo mitemo inofanirwa kunyatso itwa, uye mune iyi nyaya mutemo waive nekutaura kwakajairwa kwaidya yakawandisa processor zviwanikwa.
Sezvauri kuona kubva pachikumbiro chekuchinja pamusoro, isu tine chirongwa chekuendesa, chirongwa chekudzosera kumashure, uye chinongedzo kune yemukati mwero wekushanda maitiro (SOP) yerudzi urwu rwekutumirwa. Iyo SOP yekushandura mutemo inobvumira kuti ibudiswe pasi rose. Chaizvoizvo, paCloudflare, zvinhu zvinoitwa zvakasiyana zvachose, uye SOP inoraira kuti isu titange tatumira iyo software yekuyedza uye yekushandisa mukati kune yemukati nzvimbo yekuvapo (PoP) (iyo inoshandiswa nevashandi vedu), tozoenda kune vashoma nhamba yevatengi nzvimbo iri yoga, ipapo kune nhamba huru yevatengi, uye ipapo chete kupasirese.
Izvi ndizvo zvazvinoita. Isu tinoshandisa git mukati kuburikidza neBitBucket. Mainjiniya anoshanda pane shanduko anoendesa kodhi, iyo yakavakirwa kuTeamCity, uye kana kuvaka kwapfuura, vanoongorora vanopihwa. Kana chikumbiro chekudhonza chabvumidzwa, kodhi inounganidzwa uye nhevedzano yebvunzo inoitiswa (zvakare).
Kana iyo kuvaka uye bvunzo dzakapera zvinobudirira, chikumbiro chekuchinja chinogadzirwa muJira uye maneja akakodzera kana mutungamiri anofanira kubvumidza shanduko. Mushure memvumo, kutumirwa kunoitika mune inonzi "PoP menagerie": DOG, PIG uye. (imbwa, nguruve uye canary).
DOG PoP ndeye Cloudflare PoP (semamwe ese emaguta edu) iyo inoshandiswa chete nevashandi veCloudflare. PoP yekushandiswa kwemukati inobvumidza iwe kubata matambudziko mutengi asati atanga kuyerera mumhinduro. Chinhu chinobatsira.
Kana iyo DOG bvunzo yakabudirira, iyo kodhi inoenda kuPIG (guinea pig) nhanho. Iyi iCloudflare PoP, uko hushoma hwevatengi vemahara traffic inoyerera kuburikidza nekodhi nyowani.
Kana zvese zvakanaka, kodhi inopinda muCanary. Tine matatu eCanary PoPs munzvimbo dzakasiyana dzepasi. Mavari, traffic yevatengi vakabhadharwa uye yemahara inopfuura nepakati kodhi nyowani, uye iyi ndiyo yekupedzisira cheki yezvikanganiso.
Software Release process pa Cloudflare
Kana iyo kodhi yakanaka muCanary, tinoiburitsa. Kuenda nematanho ese - DOG, PIG, Canary, nyika yese - inotora maawa akati wandei kana mazuva, zvichienderana nekushandurwa kwekodhi. Nekuda kwekusiyana kweCloudflare's network uye vatengi, isu tinoyedza kodhi kodhi tisati taiburitsa pasi rose kune vese vatengi. Asi WAF hainyatso kutevedzera maitiro aya nekuti kutyisidzira kunoda kupindurwa nekukasira.
WAF kutyisidzira
Mumakore mashoma apfuura, kwave nekuwedzera kukuru kwekutyisidzira mumashandisirwo akafanana. Izvi zvinokonzerwa nekuwanikwa kukuru kwesoftware yekuongorora maturusi. Semuenzaniso, isu munguva pfupi yapfuura takanyora nezve ).
Source:
Kazhinji, humbowo hwepfungwa hunogadzirwa uye nekukasira kuburitswa paGithub kuitira kuti zvikwata zvinochengeta application zvikurumidze kuiyedza uye kuona kuti yakachengetedzwa zvakakwana. Naizvozvo, Cloudflare inoda kugona kupindura kutsva kurwiswa nekukurumidza sezvinobvira kuitira kuti vatengi vawane mukana wekugadzirisa software yavo.
Muenzaniso wakanaka wemhinduro yekukurumidza yeCloudflare ndeyekutumirwa kweSharePoint kuchengetedzwa kwenjodzi muna Chivabvu () Nguva pfupi mushure mekunge zviziviso zvaitwa, takaona huwandu hukuru hwekuyedza kushandisa kusazvibata mukumisikidzwa kwevatengi vedu SharePoint. Vakomana vedu vanogara vachitarisa kutyisidzira kutsva uye kunyora mitemo kuchengetedza vatengi vedu.
Mutemo wakakonzera dambudziko nemusi weChina waifanirwa kudzivirira kubva kuyambuka-saiti scripting (XSS). Kurwiswa kwakadaro kwawedzerawo mumakore achangopfuura.
Source:
Iyo yakajairwa maitiro ekushandura mutemo unotungamirwa weWAF ndeyekuita inoenderera yekubatanidza (CI) bvunzo isati yatumirwa pasi rose. Nemusi weChina wapfuura takaita izvi tikaburitsa mitemo. Na13:31 p.m., injiniya akaendesa chikumbiro chakatenderwa chekudhonza neshanduko.
Na13:37 TeamCity yakaunganidza mitemo, yakamhanya bvunzo ndokupa kuenderera mberi. Iyo WAF bvunzo suite inoedza musimboti mashandiro eWAF uye ine nhamba huru yemayuniti bvunzo dzemabasa ega. Mushure mebvunzo dzeyuniti, takaedza mitemo yeWAF tichishandisa nhamba huru yezvikumbiro zveHTTP. Zvikumbiro zveHTTP tarisa kuti zvikumbiro zvipi zvinofanira kuvharwa neWAF (kudzivisa kurwiswa) uye izvo zvinogona kubvumirwa kuburikidza (kuitira kuti usavhara zvinhu zvose uye udzivise zvinyorwa zvenhema). Asi isu hatina kuyedza yakawandisa CPU kushandiswa, uye kuongorora matanda ekare WAF anovaka anoratidza kuti mutemo bvunzo nguva haina kuwedzera, uye zvaive zvakaoma kufungidzira kuti hapazove nezviwanikwa zvakakwana.
Miedzo yakapfuura uye TeamCity yakatanga kutumira otomatiki shanduko na13:42 p.m.
Quicksilver
Mitemo yeWAF inotarisa pakugadzirisa kutyisidzira nekukurumidza, saka tinoitumira tichishandisa Quicksilver's distributed key-value store, iyo inoparadzira shanduko pasi rose mumasekonzi. Vese vatengi vedu vanoshandisa tekinoroji iyi kana vachinge vachinja magadzirirwo mudhibhodhi kana kuburikidza neAPI, uye ndezvekutenda kwazviri kuti isu tinopindura shanduko nekumhanya kwemheni.
Hatina kutaura zvakawanda nezve Quicksilver. Kare taishandisa sechitoro chakaparadzirwa pasi rose, asi pakanga paine matambudziko ekushanda nazvo, uye takanyora chitoro chedu, chakadzokororwa mumaguta anopfuura zana nemakumi masere. Isu ikozvino tinoshandisa Quicksilver kusundira shanduko yekuchinja kune vatengi, kugadzirisa WAF mitemo, uye kugovera JavaScript kodhi yakanyorwa nevatengi kune Cloudflare Workers.
Zvinongotora masekondi mashoma kubva pakudzvanya bhatani pane dashboard kana kufonera API kuita shanduko yekuchinja pasi rese. Vatengi vakada iyi kumhanya kwekuseta. Uye Vashandi vanovapa inenge pakarepo yepasi rose software deployment. Paavhareji, Quicksilver inoparadzira nezve 350 shanduko pasekondi.
Uye Quicksilver inokurumidza chaizvo. Paavhareji, takawana 99th percentile ye2,29 seconds kuparadzira shanduko kumacomputer ese pasi rese. Kumhanya kazhinji chinhu chakanaka. Mushure mezvose, kana iwe uchigonesa basa kana kujekesa cache, zvinoitika ipapo ipapo uye kwese. Kutumira kodhi kuburikidza neCloudflare Workers kunoitika nekumhanya kwakafanana. Cloudflare inovimbisa vatengi vayo kukurumidza kugadzirisa panguva chaiyo.
Asi muchiitiko ichi, kumhanya kwaitamba jee reutsinye patiri, uye mitemo yakachinja kwese kwese mumasekondi. Iwe unogona kunge waona kuti WAF kodhi inoshandisa Lua. Cloudflare inoshandisa Lua zvakanyanya mukugadzira uye ruzivo isu tiri . Lua WAF inoshandisa mukati uye inoshandisa backtracking yekufananidza. Haina nzira dzekudzivirira kubva kune matauriro asingadzoreki. Pazasi ini ndichataura zvakawanda nezve izvi uye zvatiri kuita nezvazvo.
Mitemo isati yashandiswa, zvinhu zvose zvakafamba zvakanaka: chikumbiro chekudhonza chakagadzirwa uye chakabvumirwa, pombi yeCI / CD yakaunganidza uye yakaedzwa code, chikumbiro chekuchinja chakaendeswa maererano neSOP inotungamirira kutumirwa uye kudzorerwa shure, uye kushandiswa kwakapedzwa.
Cloudflare WAF Deployment Process
Pane chakaipa
Sezvandakataura, isu tinotumira akawanda emitemo mitsva yeWAF svondo rega rega, uye isu tine akawanda masisitimu aripo ekudzivirira kubva kune yakaipa mhedzisiro yekutumirwa kwakadaro. Uye kana chimwe chinhu chisina kumira zvakanaka, kazhinji kacho musanganiswa wemamiriro akati wandei panguva imwe chete. Kana iwe ukawana chikonzero chimwe chete, izvi, zvechokwadi, zvinosimbisa, asi hazvisi zvechokwadi nguva dzose. Izvi ndizvo zvikonzero zvakakonzera kutadza kwesevhisi yedu yeHTTP/HTTPS.
- Mumwe injiniya akanyora kutaura kwenguva dzose uko kungaguma nokunyanyisa .
- Chinhu chaigona kunge chakadzivirira kutaura kwenguva dzose kubva mukuparadza yakawandisa CPU yakabviswa zvisizvo mukudzokorodza kweWAF mavhiki akati wandei apfuura-iyo refactoring yaidiwa kuita kuti WAF idye zviwanikwa zvishoma.
- Injini yenguva dzose yekutaura yakanga isina zvivimbiso zvakaoma.
- Test suite haina kukwanisa kuona mashandisirwo eCPU zvakanyanya.
- Iyo SOP inobvumira shanduko dzisiri dzechimbichimbi dzemitemo kuti dzifambiswe pasi rose pasina nhanho dzakawanda.
- Chirongwa chekudzosera chaida kumhanya yakazara WAF kuvaka kaviri, izvo zvakatora nguva yakareba.
- Yambiro yekutanga pamusoro pematambudziko emigwagwa yepasi rose yakakonzerwa nekunonoka.
- Takatora nguva kugadzirisa peji remamiriro.
- Isu takave nematambudziko ekuwana masisitimu nekuda kwekukanganisa, uye nzira yekupfuura haina kunyatso kusimbiswa.
- SRE mainjiniya akatadza kuwana mamwe masisitimu nekuti zvitupa zvakapera nekuda kwezvikonzero zvekuchengetedza.
- Vatengi vedu havana kuwana Cloudflare dashboard kana API nekuti vanoenda kuburikidza neCloudflare dunhu.
Chii chachinja kubva China chapfuura
Kutanga, isu takamisa zvachose basa rese pakuburitswa kweWAF uye tiri kuita zvinotevera:
- Tiri kudzoreredza iyo CPU yekudzivirira yakawandisa yatakabvisa. (Tagadzirira)
- Kutarisa nemaoko ese 3868 mitemo mumitemo inotungamirwa yeWAF kuwana nekugadzirisa dzimwe nyaya dzinogona kuitika dzekudzosera kumashure zvakanyanya. (Kuongorora kwapera)
- Isu tinosanganisira performance profiling yemitemo yese mu test set. (Inotarisirwa: Chikunguru 19)
- Kuchinjira kuinjini yenguva dzose yekutaura kana - ese ari maviri anopa runtime garandi. (Inotarisirwa: Chikunguru 31)
- Isu tiri kunyora zvakare iyo SOP kuti tiise mitemo mumatanho, senge mamwe masoftware muCloudflare, asi panguva imwechete tine kugona kutumirwa kwepasirese kana kurwiswa kwatotanga.
- Tiri kugadzira kugona kubvisa nekuchimbidza Cloudflare dashboard uye API kubva mudunhu reCloudflare.
- Zvigadziriso zvemapeji otomatiki .
Nguva refu tiri kutama kubva kuLua WAF yandakanyora makore mashoma apfuura. Kufambisa WAF kuenda . Nenzira iyi WAF ichakurumidza uye inogamuchira imwe nhanho yekudzivirira.
mhedziso
Kukundikana uku kwakakonzera dambudziko kwatiri isu nevatengi vedu. Takaita nekukurumidza kugadzirisa mamiriro ezvinhu uye tiri kushanda pazvikanganiso zvakakonzera kuparara, pamwe nekuchera zvakadzika kuti tidzivirire matambudziko anogona kuitika nekutaura nguva dzose mune ramangwana kana tichitamira kune tekinoroji nyowani.
Isu tinonyara kwazvo nekudzima uku uye tinokumbira ruregerero kune vatengi vedu. Tinovimba shanduko idzi dzichaita kuti chinhu chakadai hachiitike zvakare.
Application. Kudzosera kumashure mazwi enguva dzose
Kuti unzwisise kuti sei chirevo:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))yakadya zvese zveCPU zviwanikwa, iwe unofanirwa kuziva zvishoma nezve iyo yakajairwa yekutaura injini inoshanda. Dambudziko riri pano ndiyo muenzaniso .*(?:.*=.*). (?: uye dzinoenderana ) iboka risiri rokutapa (ndiko kuti, chirevo chiri mumaparenthesi chakaiswa muboka seshoko rimwechete).
Muchirevo chekushandisa zvakanyanya CPU, iyi pateni inogona kutsanangurwa se .*.*=.*. Mune chimiro ichi, muenzaniso wacho unotaridzika zvisina kufanira. Asi zvinotonyanya kukosha, munyika chaimo, matauriro (semazwi akaomarara mumitemo yeWAF) anokumbira injini kuti ienderane nechidimbu chinoteverwa nechimwe chimedu zvinogona kutungamira mukudzokera shure. Uye ndosaka.
Mukutaura nguva dzose . zvinoreva kuti iwe unofanirwa kuenzanisa hunhu humwe, .* - fananidza zero kana anopfuura mavara "nemakaro", kureva, kutora huwandu hwemavara, kuti .*.*=.* zvinoreva match zero kana mamwe mavara, wobva wafananidza zero kana akawanda mavara, tsvaga iwo chaiwo = chimiro, fananidza zero kana akawanda mavara.
Ngatitorei mutsetse webvunzo x=x. Zvinoenderana nekutaura .*.*=.*. .*.* pamberi pechiratidzo chakaenzana chinoenderana nekutanga x (rimwe remapoka .* ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ck x, uye yechipiri - zero mavara). .* mushure = machisi ekupedzisira x.
Kuenzanisa uku kunoda matanho makumi maviri nematatu. Boka rokutanga .* Π² .*.*=.* anoita nemakaro uye anofananidza tambo yacho yose x=x. Injini inoenda kuboka rinotevera .*. Hatichina mamwe mavara anoenderana, saka boka rechipiri .* inofanana ne zero mavara (izvi zvinotenderwa). Ipapo injini inotamira kune chiratidzo =. Hapasisina zviratidzo (boka rekutanga .* akashandisa kutaura kwese x=x), hapana kuenzanisa kunoitika.
Uye ipapo injini yenguva dzose yekutaura inodzokera pakutanga. Anoenda kuboka rekutanga .* uye anoienzanisa Ρ x= (panzvimbo x=x), obva atora boka rechipiri .*. Boka rechipiri .* inofananidzwa neyechipiri x, uye hatina zvakare mavara asara. Uye kana injini yasvika zvakare = Π² .*.*=.*, hapana chinoshanda. Uye anodzokera shure zvakare.
Panguva ino boka .* achiri machisi x=, asi boka rechipiri .* hapachina x, uye zero mavara. Injini iri kuedza kutsvaga hunhu chaihwo = mumuenzaniso .*.*=.*, asi haabudi (shure kwezvose, boka rekutanga rakatotora .*) Uye anodzokera shure zvakare.
Panguva ino boka rekutanga .* inotora yekutanga x chete. Asi boka rechipiri .* "nemakaro" anotorwa =x. Watofungidzira kuti chii chichaitika? Injini inoedza kuenzanisa iyo chaiyo =, inokundikana uye inoita imwe kudzokera shure.
Boka rekutanga .* zvichiri kuenderana neyokutanga x... Yechipiri .* inotora chete =. Chokwadika, injini haigoni kuenderana nechaiyo =, nokuti boka rechipiri rakatoita izvi .*. Uye zvakare kudzokera shure. Uye isu tiri kuyedza kuenzanisa tambo yevatatu mavara!
Somugumisiro, boka rokutanga .* inofanana neyokutanga chete x, chepiri .* - ine zero mavara, uye injini inozopedzisira yafanana neiyo chaiyo = mukutaura Ρ = mumutsetse. Rinotevera ndiro boka rekupedzisira .* inofananidzwa neyekupedzisira x.
23 matanho chete x=x. Tarisa vhidhiyo pfupi nezve kushandisa Perl , iyo inoratidza kuti nhanho uye kudzokera kumashure kunoitika sei.
Iri ratova basa rakawanda, asi ko kana pane kudaro x=x tichava nazvo x=xx? Ndiwo nhanho makumi matatu nematatu. Uye kana x=xxx? 45. Hukama hahuna mutsara. Girafu inoratidza kuenzanisa kubva x=x up to x=xxxxxxxxxxxxxxxxxxxx (20 x ΠΏΠΎΡΠ»Π΅ =) Kana isu tine 20 x mushure =, injini inopedza kuenzanisa mumatanho 555! (Uyezve, kana isu takarasikirwa x= uye tambo yacho inongosanganisira makumi maviri x, injini inotora 4067 matanho ekunzwisisa kuti hapana machisi).
Vhidhiyo iyi inoratidza zvese zvekudzokera kumashure kwekuenzanisa x=xxxxxxxxxxxxxxxxxxxx:
Dambudziko nderekuti sezvo saizi yetambo inowedzera, nguva yekufananidza inokura zvakanyanya-mutsara. Asi zvinhu zvinogona kutonyanya kuipa kana kutaura kwenguva dzose kwakagadziridzwa zvishoma. Ngatitii takanga tine .*.*=.*; (ndiko kuti, pakanga paine semicolon chaiyo pamagumo epateni). Semuenzaniso, kuenzanisa chirevo chakadai foo=bar;.
Uye pano kudzokera shure kungava njodzi chaiyo. Kuenzanisa x=x ichatora matanho 90, kwete 23. Uye nhamba iyoyo iri kukura nokukurumidza. Kuenzanisa x= uye 20 x, 5353 matanho anodiwa. Heino chati. Tarisa paaxis values Y zvichienzaniswa nechati yapfuura.
Kana iwe uchifarira, tarisa ese 5353 akundikana matanho ekufananidza x=xxxxxxxxxxxxxxxxxxxx ΠΈ .*.*=.*;
Kupfurikidza nokushandisa usimbe panzvimbo pokuenzanisa kwokukara, ukuru hwokudzokera shure hunogona kudzorwa. Kana tikashandura chirevo chepakutanga kuti .*?.*?=.*?, kuenzanisa x=x ichatora matanho gumi nerimwe (kwete 11). Nezve x=xxxxxxxxxxxxxxxxxxxx... Zvese nekuti ? ΠΏΠΎΡΠ»Π΅ .* inoudza injini kuti ifanane nenhamba shoma yemavara isati yaenderera mberi.
Asi simbe mepu haigadzirise zvachose dambudziko rekudzokera shure. Kana tikatsiva muenzaniso wenjodzi .*.*=.*; pamusoro .*?.*?=.*?;, nguva yekuuraya icharamba yakafanana. x=x zvichiri kuda nhanho 555, uye x= uye 20 x - 5353.
Chinhu chega chinogona kuitwa (kunze kwekunyora patsva patani kune yakanyanya kujeka) kusiya iyo yenguva dzose yekutaura injini ine yayo yekudzosera kumashure. Izvi ndizvo zvatichange tichiita mumasvondo mashoma anotevera.
Mhinduro yedambudziko iri yave ichizivikanwa kubvira 1968, apo Kent Thompson akanyora chinyorwa ("Nzira dzekuronga: Regular Expression Search Algorithm"). Chinyorwa chinotsanangura nzira inobvumidza iwe kushandura chirevo chenguva dzose kuita isiri-deterministic finite state machines, uye mushure mekuchinja kwemamiriro mune isiri-deterministic finite state michina, shandisa algorithm iyo nguva yekuuraya inoenderana nemutsara patambo yakafananidzwa.
Zvirongwa Nzira
Regular Expression Search Algorithm
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyInotsanangura nzira yekutsvaga tambo chaiyo yemavara muzvinyorwa uye inokurukura nezvekushandiswa kweiyi nzira mucompiler fomu. Iyo compiler inotora iyo yakajairwa kutaura sesource kodhi uye inogadzira iyo IBM 7094 chirongwa sechinhu kodhi. Chirongwa chechinhu chinotora kupinza muchimiro chemavara ekutsvaga uye chinoburitsa chiratidzo nguva yega yega tambo yemavara inofananidzwa neinopihwa yenguva dzose kutaura. Chinyorwa chinopa mienzaniso, matambudziko uye mhinduro.
Algorithm
Zvekare kutsvaga maalgorithms akakonzera kudzosera kumashure kana kutsvaga kwakabudirira zvishoma kwakatadza kuburitsa mhedzisiro.Mukubatanidza maitiro, iyo algorithm haishande nezviratidzo. Inopfuudza mirairo kune yakaunganidzwa kodhi. Kuuraya kunokurumidza - mushure mekupfuudza data kumusoro kwechinyorwa chazvino, inotsvaga otomatiki mavara ese anoteedzana mukutaura kwenguva dzose.
Iyo yekubatanidza uye yekutsvaga algorithm inosanganisirwa mune yekugovera-nguva yekugovera mameseji edhita sekutsvaga kwemamiriro ezvinhu. Zvechokwadi, izvi zviri kure nekushandiswa chete kwemaitiro akadaro ekutsvaga. Semuenzaniso, musiyano weiyi algorithm inoshandiswa sechiratidzo chekutsvaga mutafura muassembler.
Zvinofungidzirwa kuti muverengi anojairana nemataurirwo enguva dzose uye IBM 7094 komputa programming mutauro.Compiler
Iyo compiler ine nhanho nhatu dzinomhanya dzakafanana. Nhanho yekutanga ndeye kusefa kwe syntax, iyo inobvumira chete syntactically yakarurama yenguva dzose mataurirwo kupfuura. Danho iri rinoisawo "Β·" mushandisi kuti aenderane nemataurirwo enguva dzose. Munhanho yechipiri, kutaura kwakajairika kunoshandurwa kuita postfix fomu. Padanho rechitatu, kodhi yechinhu inogadzirwa. Matanho ekutanga e2 ari pachena, uye isu hatisi kuzogara pazviri.
Thompson's article haitauri nezve nondeterministic finite state machines, asi inotsanangura linear time algorithm zvakanaka uye inopa ALGOL-60 purogiramu inogadzira kodhi yemutauro wegungano yeBM 7094. Kuitwa kunonyengera, asi pfungwa yacho iri nyore kwazvo.
nzira yekutsvaga yazvino. Inomiririrwa ne β icon ine imwe yekupinda uye maviri anobuda.
Mufananidzo 1 unoratidza mabasa edanho rechitatu rekubatanidza paunenge uchishandura muenzaniso wenguva dzose wekutaura. Iwo mavara matatu ekutanga mumuenzaniso a, b, c, uye imwe neimwe inogadzira stack yekupinda S[i] uye NNODE munda.NNODE kune kodhi iripo kuti ibudise inokonzeresa yekutaura mune imwechete stack yekupinda (ona Mufananidzo 5)
Izvi ndizvo zvinoita kutaura nguva dzose .*.*=.*, kana iwe uchifungidzira sezviri mumifananidzo kubva kuchinyorwa chaThompson.
Mumufananidzo. 0 pane matunhu mashanu anotangira pana 0, uye 3 mitsara inotangira kubva kumatunhu 1, 2 na 3. Matatu aya anoenderana netatu. .* mukutaura nguva dzose. 3 ovals ane madots anoenderana nechiratidzo chimwe. Oval ine chiratidzo = zvinoenderana nechimiro chaicho =. State 4 ndiyo yekupedzisira. Kana tikasvika pairi, ipapo kutaura kwenguva dzose kunofananidzwa.
Kuti uone kuti dhiyagiramu yehurumende yakadai ingashandiswa sei kuenzanirana nekutaura nguva dzose .*.*=.*, tichatarisa tambo inoenderana x=x. Chirongwa chinotanga kubva mudunhu 0, sezvakaratidzwa muFig. 1.
Kuti iyi algorithm ishande, muchina wehurumende unofanirwa kunge uri mumatunhu akati wandei panguva imwe chete. A non-deterministic finite muchina ichaita zvese zvinogoneka shanduko panguva imwe chete.
Isati yawana nguva yekuverenga data rekuisa, inoenda mumatunhu ese ekutanga (1 uye 2), sezvakaratidzwa muFig. 2.
Mumufananidzo. 2 inoratidza zvinoitika kana akatarisa kwekutanga x Π² x=x. x inogona mepu kuenda kumusoro, kubva mudunhu 1 uye kudzokera kudunhu 1. Kana x inogona mepu kune iyo iri pazasi, ichibva mudunhu 2 uye kudzokera kudunhu 2.
Mushure mekuenzanisa yekutanga x Π² x=x tichiri mumatunhu 1 ne2. Hatikwanise kusvika padanho 3 kana 4 nekuti tinoda hunhu chaihwo. =.
Iyo algorithm inobva yafunga = Π² x=x. Senge x pamberi payo, inogona kuenzaniswa kune imwe yeaviri epamusoro zvishwe kubva mudunhu 1 kuenda kudunhu 1 kana kubva mudunhu 2 kuenda kudunhu 2, asi iyo algorithm inogona kuenzanisa chaiyo. = uye famba kubva mudunhu 2 kuenda kudunhu 3 (uye nekukurumidza 4). Izvi zvinoratidzwa muFig. 3.
Iyo algorithm inobva yaenda kune yekupedzisira x Π² x=x. Kubva kumatunhu 1 ne2 shanduko dzakafanana dzinogoneka kudzokera kumatunhu 1 ne2. Kubva mudunhu 3 x inogona kuenzanisa poindi kurudyi uye kudzokera kudunhu 3.
Panguva ino, munhu mumwe nomumwe x=x yakatariswa, uye sezvo tasvika pachinhanho chechina, chirevo chenguva dzose chinoenderana netambo iyoyo. Chimiro chega chega chinogadziriswa kamwe chete, saka iyi algorithm ine mutsara mukureba kwetambo yekupinza. Uye hapana kudzokera shure.
Zviripachena, mushure mekusvika mudunhu 4 (apo iyo algorithm yafanana x=) iyo yose yenguva dzose kutaura inofananidzwa, uye algorithm inogona kupera pasina kufunga nezvayo zvachose x.
Iyi algorithm inoenderana nemutsara pakukura kwetambo yekupinza.
Source: www.habr.com