Tata ki te 9 tau ki muri he kamupene iti a Cloudflare, a kaore au i mahi, he kaihoko noa ahau. I te marama i muri i te whakarewatanga o Cloudflare, ka tae mai he panui i taku paetukutuku Ko te ahua kaore e mahi ana a DNS. Kua huri a Cloudflare ki , a he DNS pakaru.
I tuhi tonu ahau ki a Matthew Prince me te taitara "Kei hea taku DNS?" ka whakahokia e ia he whakautu roa ki tonu i nga korero hangarau (), i whakahoki ahau:
Mai: John Graham-Cumming
Rā: Oketopa 7, 2010, 9:14
Kaupapa: Re: Kei hea taku DNS?
Ki a Matthew PrinceHe purongo pai, mihi. Ka tino waea atu ahau mena he raru. He pai pea te tuhi i tetahi panui mo tenei ka kohia e koe nga korero hangarau katoa. Ki taku whakaaro ka koa nga tangata ki tetahi korero tuwhera me te pono. Ina koa ka whakapirihia e koe he kauwhata hei whakaatu i te tipu haere o nga waka mai i te whakarewatanga.
He pai taku aroturuki i runga i taku papaanga, ka whiwhi SMS ahau mo nga koretake katoa. Ko te aroturuki e whakaatu ana i puta te korenga mai i te 13:03:07 ki te 14:04:12. Ka mahia nga whakamatautau ia rima meneti.
E mohio ana ahau ka mohio koe. Kei te tino mohio koe kaore koe e hiahia ki to tangata ake i Uropi? 🙂
Ano ra ko ia:
Na: Matthew Prince
Rā: Oketopa 7, 2010, 9:57
Kaupapa: Re: Kei hea taku DNS?
Ki: John Graham-CummingMauruuru koe. I whakautu matou ki nga tangata katoa i tuhi. Kei te haere ahau ki te tari inaianei ka tuhia e matou tetahi mea ki runga i te blog, ka pinea ranei he panui whai mana ki runga i ta matou papa panui. Ka tino whakaae ahau, ko te pono nga mea katoa.
Inaianei he tino kamupene nui a Cloudflare, kei te mahi ahau mo taua mea, a inaianei me tuhi tuwhera au mo to tatou he, ona hua me a tatou mahi.
Nga huihuinga o Hurae 2
I te 2 o Hurae i tukuna e matou he ture hou i roto i nga Ture Whakahaere mo nga WAF na reira i runga i ia tukatuka matua tukatuka HTTP/HTTPS hokohoko i runga i te whatunga Cloudflare puta noa. Kei te whakapai tonu matou i nga ture whakahaere mo nga WAF hei whakautu ki nga whakaraeraetanga hou me nga riri. I te marama o Mei, hei tauira, ka tere matou hei whakamarumaru i tetahi whakaraeraetanga nui i SharePoint. Ko te kaupapa katoa o to tatou WAF ko te kaha ki te tuku ture tere me te ao.
Ko te mea pouri, ko te whakahoutanga o te Rapare kua pahemo he korero auau i moumou rawa nga rauemi CPU HTTP/HTTPS i runga i te hoki whakamuri. Ko ta matou takawaenga matua, CDN, me nga mahi WAF i raru. E whakaatu ana te kauwhata ka tata ki te 100% nga rauemi tukatuka mo te mahi hokohoko HTTP/HTTPS i runga i nga kaitoro i to maatau whatunga.
Te whakamahi PTM i tetahi waahi i te wa o te maiki
Ko te mutunga, ko o taatau kiritaki (me o taatau kiritaki) ka mutu ki te wharangi hapa 502 i runga i nga rohe Cloudflare. Ko nga hapa 502 i hangaia e Cloudflare o mua-mutunga tukutuku tukutuku e mau tonu ana nga waahanga kore utu engari kaore i taea te korero ki nga tukanga e whakahaere ana i te hokohoko HTTP / HTTPS.
E mohio ana matou ki te nui o te raru i puta mai i o taatau kaihoko. Ka tino whakama matou. Na tenei rahunga i aukati i a maatau ki te whakahaere tika i te raru.
Mena ko koe tetahi o enei kaihoko, ka mataku koe, ka riri me te pouri. I tua atu, kare ano matou i a . Ko te nui o te kohi PTM na te ture WAF kotahi me te kore o te korero i ia wa, na te nui o te hokinga whakamuri. Anei te korero hara: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Ahakoa he pai tenei ki a ia ano (a ka korerohia e au mo nga korero i raro nei), kua heke te ratonga Cloudflare mo nga meneti 27 ehara i te mea he kino noa te korero. He roa te wa ki te whakaahua i te raupapa o nga kaupapa i hinga ai, na reira i puhoi matou ki te whakautu. I te mutunga o te panui, ka whakaahuahia e au te hokinga whakamuri i roto i te korero auau me te korero ki a koe me aha koe.
I ahatia
Me timata tatou i runga i te raupapa. Ko nga wa katoa kei te UTC.
I te 13:42 p.m., he iti te whakarereketanga a tetahi miihini o te roopu papaahi ki nga ture rapu te whakamahi i te tukanga aunoa. Na reira, i hangaia he tiiti tono whakarereke. Ka whakahaerehia e matou enei tikiti ma Jira (whakaahua i raro nei).
I muri i nga meneti 3, ka puta mai te wharangi tuatahi o PagerDuty, e whakaatu ana i tetahi raru mo WAF. He whakamatautau waihanga e whakamatautau ana i te mahi o WAF (he rau o ratou) kei waho o Cloudflare hei tirotiro i nga mahi noa. I whai tonu tenei i nga wharangi o nga matohi mo etahi atu whakamatautau ratonga mutunga-ki-mutunga Cloudflare i rahua, nga take hokohoko o te ao, te whanui o nga hapa 502, me te maha o nga purongo mai i a tatou Tohu o te aroaro (PoP) i nga taone huri noa i te ao e tohu ana he korekore. o nga rauemi PTM.
I whiwhi au i te maha o enei matohi, i puta mai i te hui, a i taku haerenga ki te teepu ka kii mai te tumuaki o ta matou tari whakawhanake otinga kua ngaro te 80% o a matou hokohoko. I oma ahau ki o maatau miihini SRE, e mahi ana i te raru. I te tuatahi i whakaaro matou he momo whakaeke kore mohiotia.
Ko nga miihini Cloudflare SRE kua marara huri noa i te ao me te aro turuki i nga ahuatanga huri noa i te karaka. Ko te tikanga, ka whakamohio atu enei matohi ki a koe mo nga take motuhake o te rohe he iti te whānuitanga, ka whaia i runga i nga papatohu o roto, ka whakatauhia nga wa maha ia ra. Engari ko enei wharangi me nga whakamohiotanga i tohu he mea tino kino, a ka kii tonu nga miihini SRE i te taumata taumaha P0 me te whakapā atu ki nga kaiwhakahaere me nga miihini punaha.
Kei te whakarongo a matou miihini o Raanana ki tetahi kauhau i te whare nui i taua wa. Me whakakorehia te korero, ka huihui nga tangata katoa ki roto i tetahi ruma huihuinga nui, ka karangahia etahi atu tohunga. Ehara tenei i te raruraru angamaheni ka taea e nga SRE te mahi ma ratou ano. He mea akiaki ki te whakauru i nga tohungatanga tika.
I te 14:00 ka whakatauhia e matou ko te raruraru kei te WAF, kaore he whakaeke. I toia e te roopu mahi nga raraunga PTM, ka maarama ko te WAF te he. I whakapumautia e tetahi atu kaimahi tenei ariā ma te whakamahi i te strace. I kite tetahi atu i roto i nga rakau he raru ki te WAF. I te 14:02 i te ahiahi, ka tae mai te roopu katoa ki a au i te wa i kiihia ai ki te whakamahi i te patu o te ao, he tikanga i hangaia ki Cloudflare e kati ana i tetahi waahanga o te ao.
He korero rereke te pehea i patu ai matou i te ao mo te WAF. Ehara i te mea ngawari. Ka whakamahia e matou a maatau ake hua, mai i ta maatau ratonga kare i mahi, kaore i taea e matou te whakamotuhēhē me te takiuru ki te paewhiri mana o roto (i te wa i whakatikahia ai nga mea katoa, i mohio matou kua ngaro etahi o nga mema o te roopu na te mea he waahanga haumarutanga e whakakore ana i nga tohu ki te kore e whakamahia te paewhiri mana o roto mo te wa roa).
A kaore i taea e matou te toro atu ki a maatau ratonga o roto, penei i a Jira, te punaha hanga ranei. I hiahiatia e matou he tikanga whakatika, he mea kare i whakamahia e matou (me mahi ano hoki tenei). I te mutunga, i kaha tetahi miihini ki te whakakore i te WAF i te 14:07, a i te 14:09, kua hoki ano nga waka me nga taumata CPU ki nga waahi katoa. Ko te toenga o nga tikanga tiaki a Cloudflare i mahi rite noa.
Na ka anga matou ki te whakaora i te WAF. He rerekee te ahuatanga, na reira i whakahaerehia e matou nga whakamatautau kino (te patai ki a matou ano ko te huringa te raru) me nga whakamatautau pai (kia mohio kei te mahi te hurihanga) i roto i tetahi taone ma te whakamahi i nga waka motuhake, te whakawhiti i nga kaihoko utu mai i reira.
I te 14:52 i mohio matou kua mohio matou ki te take me te whakatikatika, ka taea ano te WAF.
Me pehea te mahi a Cloudflare
He roopu miihini a Cloudflare i whakatapua ki te whakahaere ture mo nga WAF. Ka whakapau kaha ratou ki te whakapai ake i nga reiti kitenga, ki te whakaiti i nga hua teka, me te whakautu tere ki nga whakatuma hou ka puta mai. I roto i nga ra 60 kua pahure ake nei, kua 476 nga tono whakarereke i tukatukahia mo nga ture whakahaere mo WAF (te toharite kotahi ia 3 haora).
Ko tenei whakarereketanga e tika ana kia horahia i roto i te aratau whaihanga, ka haere nga waka a nga kaihoko pono i roto i te ture, engari kaore he mea i araia. Ka whakamahia e matou tenei aratau ki te whakamatautau i te whai huatanga o nga ture me te ine i nga reiti pai me te reeti kino teka. Engari ahakoa i roto i te aratau whaihanga, me tino mahia nga ture, a, i tenei keehi kei roto i te ture he korero auau e pau rawa ana nga rauemi tukatuka.
Ka kite koe i te tono whakarereke i runga ake nei, he mahere tuku, he mahere whakamuri, he hononga ki tetahi tikanga whakahaere paerewa o roto (SOP) mo tenei momo tuku. Ko te SOP mo te whakarereke i tetahi ture ka taea te whakaputa puta noa i te ao. Inaa, i Cloudflare, he rereke nga mahi, a ko te SOP e kii ana ka tukuna e matou te rorohiko mo te whakamatautau me te whakamahi o roto ki tetahi waahi o roto (PoP) (e whakamahia ana e o maatau kaimahi), katahi ki te iti o nga kaihoko i roto. he waahi mokemoke, katahi ka ki te tini o nga kaihoko, katahi ano ki te ao katoa.
Ko te ahua tenei. Ka whakamahia e matou te git i roto ma te BitBucket. Ko nga miihini e mahi ana i nga huringa ka tukuna he waehere, ka hangaia ki TeamCity, a ka pahemo te hanga, ka tohua nga kai-arotake. Ina whakaaetia he tono toia, ka whakahiatohia te waehere ka whakahaerehia he raupapa whakamatautau (ano).
Mena ka oti pai te hanga me nga whakamatautau, ka hangaia he tono whakarereke i Jira me whakaae te kaiwhakahaere tika, te kaiarahi ranei i te huringa. Whai muri i te whakaaetanga, ka tukuna ki roto i te "PoP menagerie": DOG, PIG me (kuri, poaka me te kanari).
Ko te DOG PoP he Cloudflare PoP (penei i era atu taone katoa) e whakamahia ana e nga kaimahi Cloudflare anake. Ko te PoP mo te whakamahinga o roto ka taea e koe te hopu i nga raru i mua i te tiimata o te rere a nga kaihoko ki te otinga. Mea whai hua.
Mena ka angitu te whakamatautau DOG, ka neke te waehere ki te waahi PIG (guinea pig). Ko Cloudflare PoP tenei, kei reira te iti o nga hokohoko a nga kaihoko kore utu e rere ana i roto i te waehere hou.
Mena kei te pai nga mea katoa, ka uru te waehere ki Canary. E toru a matou Canary PoP i nga waahi rereke o te ao. I roto ia ratou, ko te hokohoko o nga kaihoko utu me te kore utu ka haere i roto i te waehere hou, a koinei te tirotiro whakamutunga mo nga hapa.
Tukanga Tukunga Pūmanawa i Cloudflare
Mena he pai te waehere i Canary, ka tukuna e matou. Ko te haere i nga waahanga katoa - DOG, PIG, Canary, te ao katoa - he maha nga haora, ra ranei, i runga i te huringa waehere. Na te rereketanga o te whatunga me nga kaihoko a Cloudflare, ka tino whakamatauhia e matou te waehere i mua i te tuku i te ao ki nga kaihoko katoa. Engari karekau a WAF i te whai i tenei mahi na te mea me tere te whakautu i nga whakatuma.
Whakamatau WAF
I roto i nga tau kua pahure ake nei, he nui te pikinga o nga whakatuma i roto i nga tono noa. Ko tenei na te nui ake o nga taputapu whakamatautau rorohiko. Hei tauira, i tuhi tata matou mo ).
Source:
I te nuinga o te wa, ka hangaia he tohu o te ariā ka whakaputaina tonutia ki runga i a Github kia taea ai e nga roopu e pupuri ana i te tono kia tere te whakamatautau me te whakarite kia tino tiakina. Na reira, me kaha a Cloudflare ki te urupare ki nga whakaeke hou i te wa e taea ai kia whai waahi nga kaihoko ki te whakatika i o raatau rorohiko.
He tauira pai mo te whakautu tere a Cloudflare ko te tukunga o nga whakamarumaru whakaraeraetanga SharePoint i Mei (). Tata tonu i muri i te whakaputanga o nga panui, i kite matou i te tini o nga ngana ki te whakamahi i te whakaraeraetanga i roto i nga whakaurunga SharePoint a o taatau kaihoko. Kei te aro turuki tonu a taatau taangata i nga riri hou me te tuhi ture hei tiaki i o taatau kaihoko.
Ko te ture i puta ai te raruraru i te Rapare ko te tikanga hei tiaki i nga tuhinga tuhi-pae (XSS). Kua kaha ake hoki nga whakaeke penei i nga tau tata nei.
Source:
Ko te tikanga paerewa mo te whakarereke i tetahi ture whakahaere mo te WAF ko te whakahaere i nga whakamatautau whakauru tonu (CI) i mua i te tukunga o te ao. I tera Rapare i mahia e matou tenei me te whakaputa i nga ture. I te 13:31 i te ahiahi, ka tukuna e tetahi miihini he tono kume kua whakaaetia me te whakarereke.
В 13:37 TeamCity собрал правила, прогнал тесты и дал добро. Набор тестов для WAF проверяет основной функционал WAF и состоит из большого количества модульных тестов для индивидуальных функций. После модульных тестов мы проверили правила для WAF с помощью огромного числа HTTP-запросов. HTTP-запросы проверяют, какие запросы должны блокироваться WAF (чтобы перехватить атаку), а какие можно пропускать (чтобы не блокировать все подряд и избежать ложноположительных результатов). Но мы не провели тесты на чрезмерное использование процессорных ресурсов, и изучение логов предыдущих сборок WAF показывает, что время выполнения тестов с правилом не увеличилось, и сложно было заподозрить, что ресурсов не хватит.
I paahitia nga whakamatautau ka timata a TeamCity ki te tuku aunoa i te huringa i te 13:42 p.m.
Quicksilver
Ko nga ture WAF e aro ana ki te whakatikatika i te riri tonu, na reira ka tukuna e matou ma te whakamahi i te toa uara-matua kua tohatohahia a Quicksilver, e hora ana i nga huringa ki te ao i roto i nga hēkona. Ka whakamahia e taatau kiritaki katoa tenei hangarau ina huri ana i te whirihoranga i roto i te papatohu, ma te API ranei, na reira ka whakautu matou ki nga huringa me te tere uira.
Kare ano matou i korero nui mo Quicksilver. I mua i whakamahia e matou hei toa nui-uara kua tohatoha puta noa i te ao, engari he raru te whakahaere, a ka tuhia e matou ta matou ake toa, he tauira i roto i nga taone 180 neke atu. Ka whakamahia e matou a Quicksilver ki te pana i nga huringa whirihoranga ki nga kaihoko, whakahou i nga ture WAF, me te tohatoha i te waehere JavaScript i tuhia e nga kiritaki ki nga Kaimahi Cloudflare.
He ruarua noa iho te waa mai i te paatene i te paatene i runga i te papatohu, i te waea ranei i tetahi API ki te whakarereke i te whirihoranga puta noa i te ao. I pai nga kaihoko ki tenei tere o te tatūnga. A ka hoatu e nga Kaimahi ki a ratou te tukunga rorohiko o te ao tata tonu. I te toharite, ka horahia e Quicksilver e 350 nga huringa mo ia hekona.
A he tino tere a Quicksilver. I te toharite, i tutuki i a maatau te 99 ōrau o te 2,29 hēkona ki te whakaputa huringa ki ia rorohiko huri noa. He mea pai te tere. I muri i nga mea katoa, ka taea e koe te mahi, te whakakore ranei i te keteroki, ka tupu tata tonu me nga waahi katoa. Ko te tuku waehere ma te Cloudflare Workers ka puta i te tere kotahi. Ka oati a Cloudflare ki ana kaihoko kia tere nga whakahou i te wa tika.
Engari i roto i tenei keehi, he whakakata kino te tere ki runga i a matou, ka huri nga ture ki nga waahi katoa i roto i te hēkona. Kua kite pea koe kei te whakamahi te waehere WAF i a Lua. Ka whakamahia e Cloudflare a Lua i roto i nga mahi whakaputa me nga korero taipitopito ko tatou . Ka whakamahia e Lua WAF o roto, me te whakamahi i te hokinga whakamuri mo te whakataurite. Karekau he tikanga hei whakamarumaru i nga korero ka ngaro te mana. Kei raro ake nei ka korero au mo tenei me nga mahi e mahia ana e matou.
I mua i te tukunga o nga ture, i pai te haere o nga mea katoa: i hangaia te tono toia me te whakaae, i kohia e te paipa CI/CD me te whakamatautau i te waehere, i tukuna te tono whakarereke kia rite ki te SOP e whakahaere ana i te tuku me te huri, ka oti te tuku.
Cloudflare WAF Tukanga Tukunga
Kua he tetahi
Ka rite ki taku korero, he maha nga ture WAF hou e tukuna ana e matou ia wiki, a he maha nga punaha kei a matou hei tiaki i nga hua kino o taua tukunga. A, ki te he tetahi mea, ko te tikanga he huinga o nga ahuatanga maha i te wa kotahi. Mena ka kitea e koe kotahi noa te take, he pono tenei, he pono, engari ehara i te mea pono i nga wa katoa. Koinei nga take i paheke ai to maatau ratonga HTTP/HTTPS.
- I tuhia e tetahi miihini he korero auau ka puta he nui rawa .
- Ko tetahi ahuatanga ka taea te aukati i te whakaputanga auau mai i te moumou nui rawa o te PTM i tangohia pohehetia i roto i te refactoring o te WAF i etahi wiki i mua atu—i hiahiatia te whakatikatika kia iti ake te pau o nga rauemi a te WAF.
- Karekau he taurangi uaua o te miihini korero auau.
- Kaore i taea e te huinga whakamatautau te kite i te nui o te kai PTM.
- Ka taea e te SOP te huri i nga huringa ture kore ohorere ki te huri i te ao kaore he tukanga maha-taahiraa.
- Ko te mahere whakamuri me whakahaere te hanga WAF katoa kia rua, he roa te waa.
- Ko te matohi tuatahi mo nga raru waka o te ao kua roa rawa te mahi.
- He wa poto ki te whakahou i te whaarangi mana.
- I raru matou ki te uru atu ki nga punaha na te raru, a kaore ano kia tino tika te tikanga whakawhiti.
- I ngaro te urunga a nga miihini SRE ki etahi punaha na te mea kua pau o raatau tohu mo nga take haumaru.
- Kaore o taatau kaihoko i uru ki te papatohu Cloudflare, API ranei na te mea ka haere ratou i roto i te rohe Cloudflare.
He aha nga mea kua rereke mai i tera Rapare
Tuatahi, ka mutu ta matou mahi katoa mo nga tukunga mo WAF me te mahi e whai ake nei:
- Kei te whakahou ano matou i te whakamarumaru nui o te whakamahi CPU i tangohia e matou. (Reri)
- Te taki a ringa i nga ture 3868 i roto i nga ture whakahaere mo te WAF ki te kimi me te whakatika i etahi atu keehi o te hokinga whakamuri nui. (Kua oti te manatoko)
- Ka whakauruhia e matou nga tohu mahi mo nga ture katoa i roto i te huinga whakamatautau. (Tiakihia: Hurae 19)
- Te huri ki te miihini korero auau ranei - ka whakaratohia e raua nga taurangi wa whakahaere. (Tiakihia: Hurae 31)
- Kei te tuhi ano matou i te SOP ki te tuku i nga ture i nga waahanga, penei i etahi atu rorohiko i Cloudflare, engari i te wa ano he kaha ki te tuku ohorere ki te ao mena kua timata nga whakaeke.
- Kei te whakawhanake matou i te kaha ki te tango tere i te papatohu Cloudflare me te API mai i te rohe Cloudflare.
- Whakaaunoa i nga whakahou wharangi .
Mo te wa roa kei te neke atu tatou i te Lua WAF i tuhia e au i etahi tau ki muri. Te neke WAF ki . Ma tenei ka tere ake te WAF ka whiwhi i tetahi taumata whakamarumaru.
mutunga
Na tenei korenga i raru mo matou me o taatau kaihoko. I tere ta matou mahi ki te whakatika i te ahuatanga, a kei te mahi inaianei i nga koha o nga mahi i puta ai te tukinga, me te keri hohonu rawa atu ki te tiaki i nga raru pea me nga whakaaturanga o nga wa kei te heke mai ka heke ki te hangarau hou.
Ka tino whakama matou mo tenei mate, ka mihi ki o taatau kaihoko. Ko te tumanako ma enei huringa ka kore e puta ano tetahi mea penei.
Taupānga. Te whakamuri i nga korero auau
Kia mohio ai koe me pehea te korero:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))I pau nga rauemi CPU katoa, me mohio koe mo te mahi a te miihini korero auau. Ko te raruraru i konei ko te tauira .*(?:.*=.*). (?: me te rite ) he roopu hopu-kore (ara, ko te korero i roto i te reu ka whakarōpūhia hei korero kotahi).
I roto i te horopaki o te nui o te kai PTM, ka taea te whakaahua i tenei tauira .*.*=.*. I tenei ahua, he uaua te ahua o te tauira. Engari ko te mea nui, i roto i te ao tuuturu, ko nga korero (penei i nga korero uaua i roto i nga ture WAF) e tono ana ki te miihini kia rite ki tetahi kongakonga ka whai i tetahi atu kongakonga ka arahi ki te hokinga whakamuri. Na ko te aha.
I roto i nga korero auau . te tikanga me taurite koe ki tetahi ahua, .* - Whakatauritehia te kore, neke atu ranei nga tohu "ngakau", ara, te hopu i te nuinga o nga tohu, na reira .*.*=.* te tikanga kia rite ki te kore, nui ake ranei nga tohu, katahi ka rite ki te kore, ki te maha atu ranei o nga tohu, kimihia te kupu = literal, whakaritea te kore, neke atu ranei nga tohu.
Kia mau ki te raina whakamatautau x=x. Ka rite ki te korero .*.*=.*. .*.* i mua i te taurite o te tohu ki te tohu tuatahi x (tetahi o nga roopu .* соответствует x, me te tuarua - kore pūāhua). .* muri = whakataetae whakamutunga x.
Ko tenei whakataurite me 23 nga taahiraa. Rōpū tuatahi .* в .*.*=.* ka mahi apo, ka taurite ki te aho katoa x=x. Ka neke te miihini ki te roopu e whai ake nei .*. Karekau he kiripuaki hei taurite, no reira ko te roopu tuarua .* e ōrite ana ki ngā pūāhua kore (ka whakaaetia tēnei). Na ka neke te miihini ki te tohu =. Karekau he tohu (rōpū tuatahi .* whakamahia te korero katoa x=x), karekau he whakataurite.
Na ka hoki mai ano te miihini korero auau ki te timatanga. Ka neke ia ki te roopu tuatahi .* me te whakataurite с x= (hei utu o x=x), ka eke ki te roopu tuarua .*. Rōpū tuarua .* ka whakaritea ki te tuarua x, kare ano he tohu i toe. A ka tae ano te miihini = в .*.*=.*, kahore he mahi. Na ka hoki ano ia ki muri.
Tenei wa te roopu .* ōrite tonu x=, engari ko te roopu tuarua .* kore ake x, me nga tohu kore. Kei te ngana te miihini ki te rapu i tetahi ahuatanga mooni = i roto i te tauira .*.*=.*, engari kaore e puta mai (i muri i nga mea katoa, kua noho ke te roopu tuatahi .*). Na ka hoki ano ia ki muri.
I tenei wa ko te roopu tuatahi .* ka mau i te x tuatahi anake. Engari ko te roopu tuarua .* "poka" hopu =x. Kua matapae kē koe ka aha? Ka ngana te pūkaha ki te ōrite ki te kupu =, ka taka, ka hoki ki muri.
Rōpū Tuatahi .* rite tonu ki te tuatahi x... Ko te tuarua .* tango noa =. Ae ra, kaore e taea e te miihini te rite ki te kupu =, na te mea kua mahia e te roopu tuarua tenei .*. A hoki whakamuri ano. A kei te ngana matou ki te whakaorite i te aho o nga tohu e toru!
Ko te mutunga, ko te roopu tuatahi .* ka rite ki te tuatahi anake x, tuarua .* - me nga tohu kore, ka mutu ka rite te miihini ki te kupu = i roto i te faaiteraa с = i te rarangi. Kei muri ko te roopu whakamutunga .* ka whakaritea ki te whakamutunga x.
23 kaupae mo anake x=x. Tirohia tetahi ataata poto mo te whakamahi i a Perl , e whakaatu ana me pehea e puta ai nga hikoi me te hoki whakamuri.
He maha tonu nga mahi, engari me pehea x=x ka whai tatou x=xx? E 33 nga kaupae. A ki te mea x=xxx? 45. Karekau te hononga i te rarangi. E whakaatu ana te kauwhata i te whakatairite mai i x=x ki x=xxxxxxxxxxxxxxxxxxxx (20 x после =). Mena kei a matou te 20 x i muri mai =, ka oti i te miihini te whakataurite i roto i nga hikoinga 555! (I tua atu, mena kua ngaro tatou x= a ko te aho he 20 noa iho x, ka 4067 nga mahi a te miihini kia mohio ai kaore he whakataetae).
Ko tenei ataata e whakaatu ana i nga hokinga katoa mo te whakataurite x=xxxxxxxxxxxxxxxxxxxx:
Ko te raruraru ko te mea ka piki te rahi o te aho, ka tipu te wa orite ki te tino raina. Engari ka kino ake nga mea mena ka paku whakarereketia te whakahuatanga auau. Me kii i a matou .*.*=.*; (arā, he kowhatu kiko i te pito o te tauira). Hei tauira, ki te whakataurite i tetahi korero penei foo=bar;.
Na konei ko te hoki whakamuri he tino kino. Hei whakataurite x=x ka 90 nga hikoinga, ehara i te 23. A kei te tere haere taua nama. Hei whakataurite x= me te 20 x, 5353 nga taahiraa e hiahiatia ana. Anei te tūtohi. Tirohia nga uara tuaka Y whakaritea ki te tūtohi o mua.
Mena kei te pirangi koe, tirohia nga 5353 katoa i rahua nga mahi whakarite x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Ma te whakamahi i te whakahoatanga mangere kaua ki te apo, ka taea te whakahaere i te whānuitanga o te hoki whakamuri. Mena ka huri tatou i te korero taketake ki .*?.*?=.*?, hei whakataurite x=x ka 11 nga hikoinga (ehara i te 23). Mo x=xxxxxxxxxxxxxxxxxxxx... Katoa na te mea ? после .* ka korero ki te miihini kia rite ki te iti rawa o nga tohu i mua i te neke haere.
Engari ko nga mapi mangere e kore e tino whakaoti i te raru whakamuri. Mena ka whakakapihia e tatou te tauira kino .*.*=.*; i runga i .*?.*?=.*?;, ka noho tonu te wa mahi. x=x me 555 nga kaupae, a x= me te 20 x - 5353.
Ko te mea anake ka taea (haunga te tuhi ano i te tauira mo te tino motuhake) ko te whakarere i te miihini korero auau me tana tikanga whakamuri. Koia tenei ka mahia e matou i nga wiki e tu mai nei.
Ko te otinga mo tenei raruraru kua mohiotia mai i te tau 1968, i te wa i tuhia ai e Kent Thompson tetahi tuhinga (“Nga Tikanga Papatono: Algorithm Rapu Whakaaturanga Tonu”). Ko te tuhinga e whakaatu ana i tetahi tikanga e taea ai e koe te huri i tetahi korero ki roto i nga miihini ahua mutunga kore, a, i muri i nga huringa o te kawanatanga i roto i nga miihini whenua mutunga kore-whakarite, whakamahia te algorithm e whakawhirinaki ana te waa mahi ki runga i te aho taurite.
Nga Tikanga Papatono
Hātepe Rapu Whakaaturanga Tonu
Ken Thompson
Bell Waea Laboratories, Inc., Murray Hill, New JerseyKei te whakaahua i tetahi tikanga mo te rapu i tetahi aho motuhake o nga tohu i roto i te tuhinga me te korero mo te whakatinanatanga o tenei tikanga i roto i te ahua whakahiato. Ka tangohia e te kaikoipi te whakahuatanga auau hei waehere puna me te whakaputa i te kaupapa IBM 7094 hei waehere ahanoa. Ko te kaupapa ahanoa te whakauru i roto i te ahua o te kuputuhi rapu me te tuku tohu ia wa ka tauritehia te aho o te kuputuhi ki tetahi korero auau. Ka whakaratohia e te tuhinga nga tauira, nga raruraru me nga otinga.
Algorithm
Ko nga huringa rapu o mua i hua ki te hoki whakamuri mena ka rahua te rapunga angitu ki te whakaputa hua.I roto i te aratau whakahiato, kaore te algorithm e mahi me nga tohu. Ka tuku tohutohu ki te waehere kua whakahiato. He tino tere te mahi - i muri i te tuku raraunga ki te tihi o te rarangi o naianei, ka rapu aunoa mo nga tohu karapīpiti katoa i roto i te whakaaturanga auau.
Ko te whakahiato me te rapu algorithm kua whakauruhia ki roto i te kaiwhakamahara tuhinga wa-waahi hei rapunga horopaki. Ko te tikanga, he tawhiti tenei i te tono anake o taua tikanga rapu. Hei tauira, ka whakamahia he momo rereke o tenei algorithm hei rapu tohu i roto i te ripanga i te assembler.
Ko te whakaaro kei te mohio te kaipanui ki nga korero i ia wa me te IBM 7094 reo hotaka rorohiko.Kaihanga
E toru nga wahanga o te whakahiato e rere whakarara ana. Ko te waahanga tuatahi ko te tātari wetereo, ka taea anake te whakatika i nga kii korero noa. Ko tenei taahiraa ka whakauru ano i te kaiwhakahaere "·" ki te taurite ki nga korero rite tonu. I te taahiraa tuarua, ka huri te kii auau ki te ahua postfix. I te wahanga tuatoru, ka hangaia te waehere ahanoa. Ko nga wahanga tuatahi e 2 e kitea ana, e kore matou e noho ki runga.
Kaore te tuhinga a Thompson e korero mo nga miihini whenua mutunga kore, engari he pai te whakamaarama i te waarangi algorithm me te whakaatu i tetahi kaupapa ALGOL-60 e whakaputa ana i te waehere reo huihuinga mo te IBM 7094. He uaua te whakatinanatanga, engari he tino ngawari te whakaaro.
ara rapu o naianei. E tohuhia ana e te tohu ⊕ kotahi te whakaurunga me nga putanga e rua.
Ko te Whakaahua 1 e whakaatu ana i nga mahi o te hikoi whakahiato tuatoru i te wa e huri ana i te tauira kii auau. Ko nga tohu tuatahi e toru i roto i te tauira he a, b, c, a ka hangaia e ia he urunga puranga S[i] me tetahi mara NNODE.NNODE ki te waehere o naianei hei whakaputa i te whakaputanga auau i roto i te urunga puranga kotahi (tirohia te Whakaahua 5)
Ko tenei te ahua o te korero auau .*.*=.*, ki te whakaarohia e koe i roto i nga pikitia mai i te tuhinga a Thompson.
Kei te Fig. 0 e rima nga wahanga ka timata mai i te 0, e 3 nga huringa ka timata mai i nga kawanatanga 1, 2 me te 3. Ko enei huringa e toru e rite ana ki te toru .* i roto i te korero auau. E 3 oval me nga ira e rite ana ki tetahi tohu. Oval me te tohu = e ōrite ana ki tētahi pūāhua tūturu =. Ko te whenua 4 te mutunga. Ki te tae tatou ki reira, ka rite te kii auau.
Kia kite me pehea e taea ai te whakamahi i taua hoahoa ahua mo te tauritenga korero .*.*=.*, ka titiro tatou ki te taurite aho x=x. Ka timata te hotaka mai i te kawanatanga 0, penei i te Fig. 1.
Kia mahi ai tenei algorithm, me noho te miihini kawanatanga i roto i nga kawanatanga maha i te wa kotahi. Ko te miihini mutunga kore-whakarite ka mahi i nga whakawhitinga katoa i te wa kotahi.
I mua i te wa ki te panui i nga raraunga whakauru, ka uru ki nga ahuatanga tuatahi e rua (1 me te 2), penei i te Fig. 2.
Kei te Fig. Ko te 2 e whakaatu ana i nga mea ka puta ina titiro ia ki te tuatahi x в x=x. x ka taea te mapi ki te pito o runga, mai i te kawanatanga 1 ka hoki ki te whenua 1. Ranei x Ka taea te mapi ki te waahi i raro nei, mai i te kawanatanga 2 ka hoki ki te whenua 2.
Whai muri i te whakaōrite i te tuatahi x в x=x kei roto tonu matou i nga whenua 1 me te 2. Kaore e taea e matou te eke ki te kawanatanga 3, 4 ranei na te mea e hiahia ana matou ki te ahua mau. =.
Ka whakaarohia e te algorithm = в x=x. Pērā i te x i mua atu, ka taea te whakaōrite ki tētahi o ngā koropiko e rua o runga mai i te āhua 1 ki te āhua 1 mai i te āhua 2 ki te āhua 2, engari ka taea e te hātepee te taurite ki te kupu tūturu. = ka neke mai i te whenua 2 ki te whenua 3 (me te 4 tonu). Ka whakaatuhia tenei ki te Fig. 3.
Ka neke te algorithm ki te whakamutunga x в x=x. Mai i nga whenua 1 me te 2 ka taea ano nga whakawhitinga ki nga whenua 1 me 2. Mai i te kawanatanga 3 x ka taurite ki te tohu kei te taha matau ka hoki ki te ahua 3.
I tenei wahanga, ia ahua x=x kua whakaarohia, a, i te mea kua tae tatou ki te whenua 4, ka rite te kii auau ki taua aho. Ka tukatukahia ia ahuatanga kotahi, no reira he rarangi te roa o te aho whakauru tenei algorithm. A kahore he hokinga whakamuri.
Maamaa, i muri i te taenga ki te ahua 4 (i te wa e rite ana te algorithm x=) kua rite te katoa o nga korero auau, a ka mutu pea te algorithm me te kore e whakaarohia x.
Ko tenei algorithm e whakawhirinaki ana ki te rahi o te aho whakauru.
Source: will.com