No laila, e noʻonoʻo kākou. He 5 popoki i paa iloko o ka rumi, a no ka hele ana e hoala i ka mea nona, pono lakou a pau e ae like i keia mea iwaena o lakou iho, no ka mea, hiki wale ia lakou ke wehe i ka puka me elima o lakou e hilinai ana. Inā ʻo ka pōpoki ʻo Schrödinger kekahi o nā pōpoki, a ʻaʻole ʻike nā pōpoki ʻē aʻe e pili ana i kāna hoʻoholo ʻana, e kū mai ka nīnau: "Pehea lākou e hana ai?"
Ma kēia ʻatikala, e haʻi wau iā ʻoe ma nā ʻōlelo maʻalahi e pili ana i ka ʻāpana theoretical o ka honua o nā ʻōnaehana hoʻolaha a me nā loina o kā lākou hana. E noʻonoʻo hoʻi au i ka manaʻo nui ma lalo o Paxos.
Ke hoʻohana nā mea hoʻomohala i nā ʻōnaehana kapuaʻi, nā ʻikepili like ʻole, a me ka hana ʻana i nā pūʻulu o ka nui o nā nodes, ua hilinaʻi lākou e piha ka ʻikepili, palekana, a loaʻa mau. Akā ma hea nā mea hōʻoia?
ʻO ka mea nui, ʻo nā mea hōʻoia i loaʻa iā mākou he mau mea hoʻolako. Ua wehewehe ʻia lākou i loko o ka palapala penei: "He hilinaʻi kēia lawelawe, loaʻa iā ia kahi SLA, mai hopohopo, e hana nā mea āpau e like me kāu e manaʻo ai."
Manaʻo mākou i ka mea maikaʻi loa, no ka mea, ua hōʻoiaʻiʻo mai nā poʻe akamai mai nā ʻoihana nui e maikaʻi nā mea a pau. ʻAʻole mākou e nīnau i ka nīnau: no ke aha, ʻoiaʻiʻo, hiki i kēia ke hana? Aia kekahi kumu kūpono no ka hana kūpono o ia ʻōnaehana?
Ua hele aku nei au i a ua hoʻoikaika nui ʻia e kēia kumuhana. Ua like nā haʻawina ma ke kula me nā papa helu helu ma mua o kekahi mea pili i nā ʻōnaehana kamepiula. Akā ʻo kēia ke ʻano o nā algorithms koʻikoʻi a mākou e hoʻohana ai i kēlā me kēia lā, me ka ʻike ʻole, i hōʻoia ʻia i ka manawa hoʻokahi.
Hoʻohana ka hapa nui o nā ʻōnaehana hoʻolaha i ka Paxos consensus algorithm a me kāna mau hoʻololi like ʻole. ʻO ka mea maikaʻi loa, ʻo ia ka mana a, ma ke kumu, hiki ke hōʻoia i ka hiki ke loaʻa o kēia algorithm me kahi peni a me ka pepa. I ka hoʻomaʻamaʻa, hoʻohana ʻia ka algorithm i nā ʻōnaehana nui e holo ana ma kahi nui o nā nodes i nā ao.
He kiʻi maʻalahi o ka mea e kūkākūkā ʻia ma hope: ka hana a nā pūkaua ʻeluaE nānā kākou no kahi pumehana .
Loaʻa iā mākou ʻelua pūʻali - ʻulaʻula a keʻokeʻo. Aia nā pūʻali keʻokeʻo ma ke kūlanakauhale i hoʻopilikia ʻia. Aia nā pūʻali koa ʻulaʻula i alakaʻi ʻia e nā Generala A1 a me A2 ma nā ʻaoʻao ʻelua o ke kūlanakauhale. ʻO ka hana a ka poʻe ʻulaʻula e hoʻouka i ke kūlanakauhale keʻokeʻo a lanakila. Eia naʻe, ʻoi aku ka liʻiliʻi o ka pūʻali o kēlā me kēia pūʻali koa ʻulaʻula ma mua o ka pūʻali keʻokeʻo.
Nā kūlana lanakila no nā ʻulaʻula: pono nā pūkaua ʻelua e hoʻouka i ka manawa like i mea e loaʻa ai ka lanakila helu ma mua o nā keʻokeʻo. No ka hana ʻana i kēia, pono nā generals A1 a me A2 e ʻaelike me kekahi. Inā hoʻouka kaʻawale nā mea a pau, e eo nā ʻulaʻula.
No ka loaʻa ʻana o kahi ʻaelike, hiki i nā generals A1 a me A2 ke hoʻouna i nā ʻelele i kekahi i kekahi ma o ka ʻāina o ke kūlanakauhale keʻokeʻo. Hiki i ka ʻelele ke hoʻokō maikaʻi i kahi pūʻali koa a i ʻole ke keakea ʻia e ka ʻenemi. Nīnau: aia anei ke ʻano o ke kamaʻilio ʻana ma waena o nā pūkaua lauoho ʻulaʻula (ke kaʻina o ka hoʻouna ʻana i nā ʻelele mai A1 a i A2 a ʻo ia hoʻi mai A2 a i A1), kahi i hōʻoia ʻia ai lākou e ʻae i kahi hoʻouka kaua ma ka hola X. ʻO ka manaʻo o ka hōʻoia ʻana, e loaʻa i nā pūkaua ʻelua ka hōʻoia maopopo ʻana e kūʻē maoli kekahi hoa (kekahi pūʻali koa) i ka manawa X.
Inā hoʻouna ʻo A1 i kahi ʻelele iā A2 me ka ʻōlelo: "E hoʻouka kaua i kēia lā i ke aumoe!" ʻAʻole hiki i ka General A1 ke hoʻouka me ka hōʻoia ʻole mai General A2. Inā hiki mai ka ʻelele mai A1, a laila hoʻouna ʻo General A2 i ka hōʻoia me ka memo: "ʻAe, e pepehi kākou i nā keʻokeʻo i kēia lā." Akā i kēia manawa ʻaʻole ʻike ʻo General A2 inā ua hiki mai kāna ʻelele a ʻaʻole paha, ʻaʻohe ona hōʻoiaʻiʻo inā e hoʻouka ʻia ka hoʻouka kaua. Pono hou ʻo General A2 i ka hōʻoia.
Inā mākou e wehewehe hou aku i kā lākou kamaʻilio ʻana, ʻike maopopo ʻia ʻaʻohe mea e pili ana i ka nui o nā pōʻai hoʻololi memo, ʻaʻohe ala e hōʻoiaʻiʻo ai ua loaʻa i nā generals ʻelua kā lākou mau memo (me ka manaʻo e hiki ke keakea ʻia kēlā me kēia ʻelele).
ʻO ka pilikia ʻelua Generals he hōʻike maikaʻi loa ia o kahi ʻōnaehana puʻupuʻu maʻalahi loa kahi ʻelua nodes me ke kamaʻilio hilinaʻi ʻole. 'O ia ho'i, 'a'ohe o mākou hō'oia 100% ua ho'onohonoho 'ia lākou. Kūkākūkā ʻia nā pilikia like ma ka pālākiō nui ma hope o ka ʻatikala.
Hoʻokomo mākou i ka manaʻo o nā ʻōnaehana māhele
ʻO ka ʻōnaehana puʻunaue ʻia he pūʻulu o nā kamepiula (ma hope aku e kapa mākou iā lākou nodes) hiki ke hoʻololi i nā memo. ʻO kēlā me kēia node he ʻano ʻano ʻokoʻa. Hiki i kahi node ke hana i nā hana ma kāna iho, akā i mea e kamaʻilio ai me nā node ʻē aʻe, pono ia e hoʻouna a loaʻa i nā leka.
Pehea e hoʻokō pono ʻia ai nā memo, he aha nā protocols i hoʻohana ʻia - ʻaʻole ia he mea hoihoi iā mākou i kēia ʻano. He mea nui e hiki i nā nodes o kahi ʻōnaehana māhele ke hoʻololi i ka ʻikepili me kekahi me ka hoʻouna ʻana i nā leka.
ʻAʻole paʻakikī loa ka wehewehe ʻana, akā pono mākou e noʻonoʻo he nui nā ʻano o ka ʻōnaehana puʻupuʻu i mea nui iā mākou.
Nā ʻano o nā ʻōnaehana puʻunaue
- Kauike - hiki i nā hanana like ʻole a i ʻole nā hanana like i ka ʻōnaehana. Eia kekahi, e noʻonoʻo mākou i nā hanana e hiki mai ana ma nā node ʻelua ʻokoʻa i hiki ke hui like ʻole inā ʻaʻole mākou i ʻike maopopo i ke ʻano o kēia mau hanana. Akā, ma ke ʻano he kānāwai, ʻaʻole mākou.
- ʻAʻohe uaki honua. ʻAʻole mākou i ʻike maopopo i nā hanana ma muli o ka nele o ka uaki honua. I ka honua maʻamau o ka poʻe, ua maʻa mākou i ka loaʻa ʻana o nā uaki a me ka manawa. Hoʻololi nā mea a pau i ka wā e pili ana i nā ʻōnaehana hoʻolaha. ʻO nā uaki atomika ultra-precise ke neʻe nei, a aia paha nā kūlana i hiki ʻole iā mākou ke haʻi i ka mea o nā hanana ʻelua i hana mua. No laila, ʻaʻole hiki iā mākou ke hilinaʻi i ka manawa.
- ʻO ka hemahema kūʻokoʻa o nā node ʻōnaehana. Aia kekahi pilikia ʻē aʻe: hiki ke hele hewa kekahi mea no ka mea ʻaʻole mau kā mākou mau node. Hiki i ka paʻakikī ke hāʻule, hiki i ka mīkini virtual i ke ao ke hoʻomaka hou, hiki i ka pūnaewele ke poni a nalowale nā memo. Eia kekahi, aia paha nā kūlana kahi e hana ai nā nodes, akā i ka manawa like e hana kūʻē i ka ʻōnaehana. Ua loaʻa i ka papa hope o nā pilikia he inoa ʻokoʻa: pilikia . ʻO ka hiʻohiʻona kaulana loa o kahi ʻōnaehana puʻupuʻu me kēia pilikia ʻo Blockchain. Akā i kēia lā ʻaʻole mākou e noʻonoʻo i kēia papa kūikawā o nā pilikia. E hoihoi mākou i nā kūlana i hiki ʻole ai i hoʻokahi a ʻoi aʻe paha nā node ke hāʻule.
- Nā hiʻohiʻona kamaʻilio (nā hoʻohālike memo) ma waena o nā nodes. Ua hoʻokumu mua mākou e kamaʻilio nā nodes ma ka hoʻololi ʻana i nā memo. ʻElua mau hiʻohiʻona memo kaulana: synchronous a me asynchronous.
Nā hiʻohiʻona o ke kamaʻilio ma waena o nā nodes i nā ʻōnaehana puʻunaue
Hoʻohālike like - ʻike maopopo mākou aia kahi delta i ʻike ʻia o ka manawa e hōʻoiaʻiʻo ʻia ai kahi leka e hiki ai mai kekahi node a i kekahi. Inā ua hala kēia manawa a ʻaʻole i hiki mai ka leka, hiki iā mākou ke ʻōlelo palekana ua hāʻule ka node. Ma kēia kŘkohu, loaʻa iā mākou nā manawa kali e wānana.
Hoʻohālike like ʻole - ma nā hiʻohiʻona asynchronous mākou e noʻonoʻo ai ua pau ka manawa kali, akā ʻaʻohe delta o ka manawa ma hope e hiki ai iā mākou ke hōʻoiaʻiʻo ua hāʻule ka node. ʻO kēlā mau mea. Hiki ke lōʻihi ka lōʻihi o ka manawa kali no ka memo mai kahi node. He wehewehe koʻikoʻi kēia, a e kamaʻilio hou mākou e pili ana.
ʻO ka manaʻo o ka ʻae ʻana i nā ʻōnaehana puʻupuʻu
Ma mua o ka wehewehe ʻana i ka manaʻo o ka ʻae ʻana, e noʻonoʻo kākou i kahi laʻana o kahi kūlana e pono ai mākou, ʻo ia hoʻi - Hoʻopiʻi Mīkini Mokuʻāina.
Loaʻa iā mākou kekahi log i puʻunaue ʻia. Makemake mākou e paʻa a loaʻa nā ʻikepili like ma nā node āpau o ka ʻōnaehana puʻunaue. Ke aʻo kekahi o nā nodes i kahi waiwai hou e kākau ana i ka log, lilo kāna hana i ka hāʻawi ʻana i kēia waiwai i nā nodes ʻē aʻe a pau i mea e hoʻonui ʻia ai ka log ma nā nodes āpau a neʻe ka ʻōnaehana i kahi kūlana kūlike hou. I kēia hihia, he mea nui e ʻae nā nodes i waena o lākou iho: ʻae nā nodes a pau he pololei ka waiwai hou i manaʻo ʻia, ʻae nā nodes a pau i kēia waiwai, a ma kēia hihia hiki i nā mea a pau ke kākau i ka waiwai hou i ka log.
Ma nā huaʻōlelo ʻē aʻe: ʻaʻohe o nā nodes i kūʻē i ka loaʻa ʻana o ka ʻike pili pono, a ʻaʻole pololei ka waiwai i manaʻo ʻia. ʻO ka ʻaelike ma waena o nā nodes a me ka ʻaelike ma kahi waiwai kūpono i ʻae ʻia he ʻaelike i loko o kahi ʻōnaehana puʻunaue. Ma hope aʻe, e kamaʻilio mākou e pili ana i nā algorithms e ʻae i kahi ʻōnaehana puʻupuʻu e hōʻoiaʻiʻo ʻia e hiki i ka ʻae.
ʻOi aku ka maʻamau, hiki iā mākou ke wehewehe i kahi algorithm consensus (a i ʻole kahi algorithm consensus wale nō) ma ke ʻano he hana e hoʻoili ai i kahi ʻōnaehana māhele mai ka mokuʻāina A i ka mokuʻāina B. Eia kekahi, ʻae ʻia kēia mokuʻāina e nā nodes a pau, a hiki i nā nodes a pau ke hōʻoia. E like me ka mea i ʻike ʻia, ʻaʻole like ʻole kēia hana e like me ka mea i ʻike mua ʻia.
Nā Pono o ka Algorithm Consensus
Pono e loaʻa i ka algorithm consensus ʻekolu mau waiwai i mea e hoʻomau ai ka ʻōnaehana a loaʻa kahi holomua i ka neʻe ʻana mai kahi mokuʻāina ai kekahi mokuʻāina:
- Hoʻohui – pono e like ka waiwai o na node hana pono a pau (ma na atikala, ua kapaia keia waiwai he waiwai palekana). ʻO nā node a pau e hana nei (ʻaʻole i hāʻule a nalowale ka pilina me nā poʻe ʻē aʻe) pono e hele i kahi ʻaelike a ʻae i kekahi waiwai maʻamau.
He mea nui ka hoʻomaopopo ʻana ma aneʻi ʻo nā nodes o ka ʻōnaehana puʻupuʻu a mākou e noʻonoʻo nei makemake e ʻae. ʻO ia hoʻi, ke kamaʻilio nei mākou e pili ana i nā ʻōnaehana i hiki ke hāʻule wale kekahi mea (no ka laʻana, hāʻule kekahi node), akā i loko o kēia ʻōnaehana ʻaʻohe ʻano nodes e hana kūʻē i nā poʻe ʻē aʻe (ka hana a nā generals Byzantine). Ma muli o kēia waiwai, e mau ana ka ʻōnaehana.
- ano hoopono - inā hāʻawi nā node hana pololei i ka waiwai like v, 'o ia ho'i, pono e 'ae kēlā me kēia node hana pono i kēia waiwai v.
- Hoʻopau - ʻo nā node hana pono a pau e lawe i kekahi waiwai (waiwai ola), e hiki ai i ka algorithm ke holomua i ka ʻōnaehana. Pono kēlā me kēia kanaka e hoʻohana pono i ka node ma hope a ma hope paha e ʻae i ka waiwai hope a hōʻoia: "Noʻu, he ʻoiaʻiʻo kēia waiwai, ʻae wau me ka ʻōnaehana holoʻokoʻa."
He laʻana o ka hana ʻana o ka consensus algorithm
ʻOiai ʻaʻole maopopo loa nā waiwai o ka algorithm. No laila, e hōʻike mākou me kahi laʻana i nā pae o ka algorithm consensus maʻalahi e hele ai i loko o kahi ʻōnaehana me kahi hiʻohiʻona memo synchronous, kahi e hana ai nā nodes a pau e like me ka mea i manaʻo ʻia, ʻaʻole nalowale nā memo a ʻaʻohe mea e haki (e hana maoli anei kēia?).
- Hoʻomaka ia me kahi noi male (Propose). E noʻonoʻo kākou ua pili ka mea kūʻai aku i kahi node i kapa ʻia ʻo "Node 1" a hoʻomaka i kahi kālepa, e hāʻawi ana i kahi waiwai hou i ka node - O. Mai kēia manawa, e kapa mākou iā "Node 1" noi. Ma ke ʻano he mea noi, pono ʻo "Node 1" e hoʻolaha i ka ʻōnaehana holoʻokoʻa he ʻikepili hou kona, a hoʻouna ʻo ia i nā leka i nā node ʻē aʻe: "E nānā! Ua hiki mai ka manaʻo "ʻO" iaʻu a makemake wau e kākau i lalo! E ʻoluʻolu e hōʻoia e hoʻopaʻa pū ʻoe iā "O" i kāu moʻolelo.
- ʻO ka pae aʻe ke koho balota no ka waiwai i manaʻo ʻia (Voting). No ke aha ia? Loaʻa paha i nā node ʻē aʻe ka ʻike hou aʻe, a loaʻa iā lākou ka ʻikepili ma ke kālepa like.
Ke hoʻouna ʻia ka node "Node 1" i kāna noi, e nānā nā node ʻē aʻe i kā lākou mau moʻolelo no ka ʻikepili ma kēia hanana. Inā ʻaʻohe kūʻē, hoʻolaha nā nodes: "ʻAe, ʻaʻohe aʻu ʻikepili ʻē aʻe no kēia hanana. ʻO ka waiwai "O" ka ʻike hou loa e pono ai mākou.Ma nā hihia ʻē aʻe, hiki i nā nodes ke pane i "Node 1": "E hoʻolohe! Loaʻa iaʻu nā ʻikepili hou e pili ana i kēia kālepa. ʻAʻole 'O', akā he mea maikaʻi aʻe. "
Ma ke kahua koho, hoʻoholo nā node: ʻae lākou a pau i ka waiwai like, a i ʻole kekahi o lākou e kūʻē, e hōʻike ana he ʻikepili hou aʻe kāna.
- Inā kūleʻa ka pōʻai koho a makemake nā mea a pau, a laila neʻe ka ʻōnaehana i kahi pae hou - e ʻae i ka waiwai (E ʻae). "Node 1" e hōʻiliʻili i nā pane a pau mai nā node ʻē aʻe a me nā hōʻike: "Ua ʻae nā mea a pau i ka waiwai "O"! I kēia manawa ke haʻi aku nei au ʻo "ʻO" ko mākou manaʻo hou, like no kēlā me kēia! E kākau i loko o kāu puke liʻiliʻi, mai poina. E kākau i loko o kāu moʻolelo!”
- Hoʻouna nā nodes i koe i ka hōʻoia (Accepted) ua kākau lākou i ka waiwai "O"; ʻaʻohe mea hou i hiki mai i kēia manawa (he ʻano hana ʻelua-phase commit). Ma hope o kēia hanana koʻikoʻi, manaʻo mākou ua pau ka hana i puʻunaue ʻia.
No laila, ʻo ka algorithm consensus i kahi hihia maʻalahi he ʻehā mau ʻanuʻu: noi, koho (koho), ʻae (ʻae), hōʻoia i ka ʻae (ʻae ʻia).
Inā ʻaʻole hiki iā mākou ke ʻae i ka ʻaelike, a laila hoʻomaka hou ka algorithm, e noʻonoʻo ana i ka ʻike i hāʻawi ʻia e nā nodes i hōʻole e hōʻoia i ka waiwai i manaʻo ʻia.
Consensus algorithm i loko o kahi ʻōnaehana asynchronous
Ma mua o kēia, ua maʻalahi nā mea a pau, no ka mea, ke kamaʻilio nei mākou e pili ana i kahi hiʻohiʻona memo synchronous. Akā ʻike mākou i kēia ao hou ua maʻa mākou e hana i nā mea āpau asynchronously. Pehea e hana ai kekahi algorithm like i loko o kahi ʻōnaehana me kahi ʻano memo asynchronous, kahi mākou i manaʻoʻiʻo ai hiki ke lōʻihi ka manawa kali no ka pane ʻana mai kahi node (ma ke ala, hiki ke noʻonoʻo ʻia ka hemahema o kahi node e like me ka laʻana. hiki i ka node ke pane no ka manawa lōʻihi).
I kēia manawa ua ʻike mākou i ka hana ʻana o ka algorithm consensus ma ke kumu, he nīnau no kēlā poʻe heluhelu nīnau i hana i kēia mamao: ehia mau nodes i loko o kahi ʻōnaehana N nodes me kahi ʻano memo asynchronous hiki ke hāʻule i hiki i ka ʻōnaehana ke hiki i ka ʻae?
ʻO ka pane pololei a me ka hōʻoia ʻana aia ma hope o ka mea hao.ʻO ka pane pololei: 0. Inā hāʻule hoʻokahi node i loko o kahi ʻōnaehana asynchronous, ʻaʻole hiki i ka ʻōnaehana ke loaʻa i ka ʻaelike. Ua hōʻoia ʻia kēia ʻōlelo ma ka FLP theorem, kaulana i kekahi mau pōʻai (1985, Fischer, Lynch, Paterson, loulou i ka mea kumu ma ka hope o ka ʻatikala): "ʻO ka hiki ʻole ke loaʻa i ka ʻae like ʻole inā hāʻule hoʻokahi node. .”
E nā kāne, a laila pilikia mākou, ua maʻa mākou i nā mea āpau asynchronous. A eia nō. Pehea e hoʻomau ai i ke ola?
Ke kamaʻilio wale nei mākou no ke kumumanaʻo, no ka makemakika. He aha ka manaʻo o "ʻaʻole hiki ke hoʻokō ʻia" ka unuhi ʻana mai ka ʻōlelo makemakika i kā mākou - ʻenekinia? ʻO kēia ke ʻano "ʻaʻole hiki ke hoʻokō mau ʻia", ʻo ia hoʻi. Aia kekahi hihia i hiki ʻole ke ʻae ʻia. He aha kēia hihia?
ʻO kēia ka hewa o ka waiwai ola i hōʻike ʻia ma luna. ʻAʻohe o mākou ʻaelike maʻamau, a ʻaʻole hiki i ka ʻōnaehana ke holomua (ʻaʻole hiki ke hoʻopau i ka manawa palena) inā ʻaʻohe pane mai nā nodes a pau. No ka mea, i loko o kahi ʻōnaehana asynchronous ʻaʻohe o mākou manawa pane a ʻaʻole hiki iā mākou ke ʻike inā ua hāʻule ka node a i ʻole e lōʻihi ana ka manawa e pane ai.
Akā ma ka hoʻomaʻamaʻa hiki iā mākou ke loaʻa kahi hopena. E hiki i kā mākou algorithm ke hana no ka manawa lōʻihi i ka hihia o ka hāʻule (hiki paha ke hana mau loa). Akā i ka hapanui o nā kūlana, ke holo pololei ka hapa nui o nā node, e holomua ana mākou i ka ʻōnaehana.
Ma ka hoʻomaʻamaʻa, pili mākou i nā hiʻohiʻona kamaʻilio partially synchronous. Hoʻomaopopo ʻia ka ʻāpana synchrony penei: ma ka hihia maʻamau, loaʻa iā mākou kahi kumu hoʻohālike asynchronous, akā ua hoʻolauna mua ʻia kekahi manaʻo o ka "manawa hoʻokū honua" o kekahi manawa i ka manawa.
ʻAʻole hiki mai kēia manawa i ka manawa no kekahi manawa lōʻihi, akā pono e hiki mai i kekahi lā. E kani ana ka uaki pumehana, a mai ia manawa hiki ke wānana i ka delta manawa e hiki mai ai na memo. Mai kēia manawa, huli ka ʻōnaehana mai asynchronous i synchronous. Ma ka hoʻomaʻamaʻa, pili mākou i nā ʻōnaehana like.
Hoʻoponopono ka Paxos algorithm i nā pilikia consensus
He ʻohana ia o nā algorithms e hoʻoponopono ai i ka pilikia consensus no nā ʻōnaehana ʻāpana synchronous, ma muli o ka hiki ke hāʻule paha kekahi mau node. ʻO ka mea kākau o Paxos . Ua hāʻawi ʻo ia i kahi hōʻoia kūpono o ke ola a me ka pololei o ka algorithm ma 1989.
Akā, ua lilo ka hōʻoiaʻiʻo mai kahi mea liʻiliʻi. Ua hoʻokuʻu ʻia ka paʻi mua ma 1998 (33 ʻaoʻao) e wehewehe ana i ka algorithm. E like me ka mea i ʻike ʻia, paʻakikī loa ka hoʻomaopopo ʻana, a i ka makahiki 2001 ua paʻi ʻia kahi wehewehe o ka ʻatikala, a lawe ʻia i 14 mau ʻaoʻao. Hāʻawi ʻia ka nui o nā paʻi i mea e hōʻike ai i ka ʻoiaʻiʻo ʻaʻole maʻalahi ka pilikia o ka ʻae ʻana, a ma hope o ia mau algorithm e waiho nei kahi hana nui a ka poʻe akamai.
He mea hoihoi 'o Leslie Lamport pono'ī i kāna haʻi'ōlelo ma ka ʻatikala wehewehe ʻelua aia hoʻokahi ʻōlelo, hoʻokahi laina (ʻaʻole ʻo ia i kuhikuhi i ka mea), hiki ke unuhi ʻia ma nā ʻano like ʻole. A ma muli o kēia, ʻaʻole holo pololei ka nui o nā hoʻokō Paxos hou.
ʻO kahi kikoʻī kikoʻī o ka hana a Paxos e ʻoi aku ma mua o hoʻokahi ʻatikala, no laila e hoʻāʻo wau e haʻi pōkole i ka manaʻo nui o ka algorithm. Ma nā loulou ma ka hope o kaʻu ʻatikala e ʻike ʻoe i nā mea no ka luʻu hou ʻana i kēia kumuhana.
Nā kuleana ma Paxos
Loaʻa i ka Paxos algorithm kahi manaʻo o nā kuleana. E noʻonoʻo kākou i ʻekolu mau mea nui (aia nā hoʻololi me nā kuleana hou aku):
- Nā mea noi (hiki ke hoʻohana ʻia nā huaʻōlelo: alakaʻi a hoʻonohonoho paha). ʻO kēia nā kāne e aʻo e pili ana i kahi waiwai hou mai ka mea hoʻohana a lawe i ke kuleana o ke alakaʻi. ʻO kā lākou hana, ʻo ia ka hoʻomaka ʻana o nā noi no kahi waiwai hou a hoʻonohonoho i nā hana hou aʻe o nā nodes. Eia kekahi, ʻae ʻo Paxos i ke alo o nā alakaʻi i kekahi mau kūlana.
- Nā mea ʻae (nā mea koho). He mau node kēia e koho ana e ʻae a hōʻole paha i kekahi waiwai. He mea koʻikoʻi ko lākou kuleana, no ka mea, aia ka hoʻoholo ma luna o lākou: he aha ka mokuʻāina e hele ai ka ʻōnaehana (a ʻaʻole paha) ma hope o ka pae aʻe o ka algorithm consensus.
- Nā haumāna. Nodes e ʻae a kākau i ka waiwai hou i ʻae ʻia ke loli ke kūlana o ka ʻōnaehana. ʻAʻole lākou e hoʻoholo, loaʻa wale ka ʻikepili a hiki ke hāʻawi i ka mea hoʻohana hope.
Hiki i hoʻokahi node ke hoʻohui i kekahi mau kuleana ma nā kūlana like ʻole.
ʻO ka manaʻo o ka quorum
Manaʻo mākou he ʻōnaehana kā mākou N nodes A o lakou ka nui loa F hāʻule paha nā nodes. Inā hāʻule nā nodes F, pono e loaʻa iā mākou ka liʻiliʻi 2F+1 nā pona ʻae.
Pono kēia i loaʻa iā mākou ka hapa nui, ʻoiai i ke kūlana maikaʻi loa, nā nodes "maikaʻi" e hana pololei. ʻo ia F+1 "maikaʻi" nodes i ʻae, a e ʻae ʻia ka waiwai hope. A i ʻole, aia paha kahi kūlana e lawe ai kā mākou hui kūloko i nā manaʻo like ʻole a ʻaʻole hiki ke ʻae i waena o lākou iho. No laila, pono mākou i ka hapa nui loa e lanakila ai i ka balota.
ʻO ka manaʻo maʻamau e pili ana i ka hana ʻana o ka Paxos consensus algorithm
ʻO ka Paxos algorithm e pili ana i ʻelua mau ʻanuʻu nui, a laila ua māhele ʻia i ʻelua mau ʻanuʻu i kēlā me kēia:
- Māhele 1a: Hoʻomākaukau. I ka wā hoʻomākaukau, hōʻike ke alakaʻi (mea noiʻi) i nā node a pau: “Ke hoʻomaka nei mākou i kahi manawa koho hou. He pōʻai hou kā mākou. ʻO ka helu o kēia pōʻai he n. I kēia manawa e hoʻomaka mākou e koho. I kēia manawa, hōʻike wale ia i ka hoʻomaka ʻana o kahi pōʻai hou, akā ʻaʻole hōʻike i kahi waiwai hou. ʻO ka hana o kēia pae, ʻo ia ka hoʻomaka ʻana i kahi pōʻai hou a hoʻomaopopo i kēlā me kēia kanaka i kāna helu kūʻokoʻa. He mea koʻikoʻi ka helu pōʻai, ʻoi aku ka waiwai ma mua o nā helu koho balota a pau mai nā alakaʻi a pau. No ka mea, mahalo i ka helu poepoe e hoʻomaopopo ai nā node ʻē aʻe o ka ʻōnaehana i ke ʻano hou o ka ʻikepili o ke alakaʻi. Loaʻa paha i nā node ʻē aʻe nā hopena koho mai nā pōʻai hope loa a haʻi wale i ke alakaʻi aia ʻo ia ma hope o nā manawa.
- Māhele 1b: Hoʻohiki. I ka loaʻa ʻana o ka helu o ka pae koho hou i nā node ʻae, ʻelua mau hopena:
- ʻOi aku ka helu n o ka balota hou ma mua o ka helu o kekahi koho balota mua i komo ai ka mea ʻae. A laila hoʻouna ka mea ʻae i kahi ʻōlelo hoʻohiki i ke alakaʻi ʻaʻole ia e komo hou i nā balota me ka helu haʻahaʻa ma mua o n. Inā ua koho mua ka mea ʻae i kekahi mea (ʻo ia hoʻi, ua ʻae ʻo ia i kekahi waiwai i ka lua o ka māhele), a laila hoʻopili ʻo ia i ka waiwai i ʻae ʻia a me ka helu o ka balota i komo ai i kāna ʻōlelo hoʻohiki.
- Inā ʻaʻole, inā ʻike mua ka mea ʻae e pili ana i ka balota helu kiʻekiʻe, hiki iā ia ke haʻalele wale i ka pae hoʻomākaukau a pane ʻole i ke alakaʻi.
- Māhele 2a: E ʻae. Pono ke alakaʻi e kali no kahi pane mai ka ʻaha kūkā (ka hapa nui o nā nodes i ka ʻōnaehana) a, inā loaʻa ka helu i koi ʻia o nā pane, a laila ʻelua mau koho no ka hoʻomohala ʻana i nā hanana:
- Ua hoʻouna aku kekahi o ka poʻe ʻae i nā waiwai a lākou i koho mua ai. I kēia hihia, koho ke alakaʻi i ka waiwai mai ka balota me ka helu kiʻekiʻe. E kāhea kākou i kēia waiwai x, a hoʻouna ʻo ia i kahi leka i nā node a pau e like me: "E ʻae (n, x)", kahi o ka waiwai mua ka helu koho mai kāna hana Propose ponoʻī, a ʻo ka waiwai ʻelua ka mea i hōʻuluʻulu ʻia e nā mea a pau. ʻo ia hoʻi. ka waiwai a makou e koho ai.
- Inā ʻaʻohe o ka poʻe ʻae i hoʻouna i kekahi waiwai, akā ua hoʻohiki wale lākou e koho balota i kēia pōʻai, hiki i ke alakaʻi ke kono iā lākou e koho i ko lākou waiwai, ʻo ka waiwai i lilo ai ʻo ia i alakaʻi ma kahi mua. E kapa aku kakou ia y. Hoʻouna ʻo ia i kahi leka i nā node āpau e like me: "E ʻae (n, y)", e like me ka hopena mua.
- Māhele 2b: ʻAe ʻia. Eia kekahi, ʻo nā nodes ʻae, i ka loaʻa ʻana o ka leka "Accept(...)" mai ke alakaʻi, e ʻae pū me ia (e hoʻouna i ka hōʻoia i nā nodes āpau e ʻae lākou i ka waiwai hou) inā ʻaʻole lākou i hoʻohiki i kekahi ('ē aʻe) ) alakaʻi e komo i ke koho pāloka me ka helu poepoe n' > n, inā ʻaʻole lākou e nānā i ka noi hōʻoia.
Inā pane ka hapa nui o nā nodes i ke alakaʻi, a ua hōʻoia lākou a pau i ka waiwai hou, a laila ua manaʻo ʻia ka waiwai hou. Hooray! Inā ʻaʻole i loaʻa ka hapa nui a i ʻole nā nodes i hōʻole e ʻae i ka waiwai hou, a laila hoʻomaka nā mea āpau.
ʻO kēia ke ʻano o ka Paxos algorithm e hana ai. He nui nā subtleties o kēlā me kēia pae, ʻaʻole mākou i noʻonoʻo i nā ʻano like ʻole o nā hemahema, nā pilikia o nā alakaʻi he nui a ʻoi aku ka nui, akā ʻo ke kumu o kēia ʻatikala e hoʻolauna wale i ka mea heluhelu i ka honua o ka hoʻoili ʻana i ka helu kiʻekiʻe.
He mea kūpono hoʻi e ʻike ʻaʻole ʻo Paxos wale nō o kāna ʻano, aia kekahi mau algorithms, no ka laʻana, , akā he kumuhana kēia no kekahi ʻatikala.
Nā loulou i nā mea no ke aʻo hou ʻana
pae hoʻomaka:
- , Preethi Kasireddy, ʻatikala blog ma Medium
- , Adi Kancherla, blog 'atikala ma Medium
- , Itai Aberahama, blog
- , Ittai Aberahama, moʻomanaʻo moʻomanaʻo
Leslie Laport pae:
- , Fischer, Lynch a me Paterson, pepa noiʻi, 1985
- , Leslie Lamport, pepa noiʻi, 1998
- , Leslie Lamport, pepa noiʻi, 2001
Source: www.habr.com