Baada ya miezi ya uhandisi, marekebisho na kufukuzana na race conditions, injini yetu ya kuunganisha abiria na madereva kwa wakati halisi sasa iko imara.
Kama hujawahi kujenga kitu kama hiki, sentensi hiyo huenda inasikika ndogo kuliko ilivyo. Abiria anabonyeza "Agiza safari". Mahali fulani karibu, madereva kumi na wawili wanasogea katikati ya msongamano, na simu ya kila mmoja inatuma mahali alipo kila baada ya sekunde chache. Ndani ya sehemu ya sekunde, lazima tuamue nani kati yao apate safari hiyo, na tuhakikishe hakuna abiria mwingine anayempata dereva huyo huyo wakati huo huo.
Kumpata dereva wa karibu zaidi aliye tayari ndani ya milisekunde, hapo ndipo mambo yanapokuwa magumu.
Kufika hapa kulihitaji makala za utafiti na vikao vya ubao mweupe hadi usiku wa manane, utekelezaji tulioutupa, majaribio ya mzigo yaliyoanguka, na hitilafu zilizojitokeza tu pale maombi mawili yalipofika ndani ya milisekunde chache kati yao. Ilituchukua miezi. Itakuchukua takriban dakika kumi kusoma.
Kwa hiyo, tunakuchambulia yote hapa. Insha hii ni sehemu ya mfululizo wetu wa kihandisi, na ni kila kitu ambacho tungependa mtu atuambie siku ya kwanza. Ikiwa unajenga chochote kinachounganisha watu na vitu vinavyosogea, tumaini letu ni rahisi: ruka miezi tuliyotumia, na anzia pale tulipofikia.
Somo kubwa kwanza, kwa sababu ndilo tulilojifunza kwa njia ngumu: kumpata dereva wa karibu ni sehemu rahisi. Kuunganisha abiria na dereva ni tatizo la ushindani wa wakati mmoja (concurrency) lililojificha kama tatizo la utafutaji.
Kwa nini "tafuta dereva wa karibu zaidi" haifanyi kazi
Toleo la kijinga linakwenda hivi: pakia madereva wote walio mtandaoni, hesabu umbali kutoka kwa kila mmoja hadi kwa abiria, panga, kisha chagua wa kwanza.
Linafanya kazi vizuri kabisa kwenye onyesho lenye madereva kumi. Katika mji halisi linaanguka, kwa sababu tatu.
Haliwezi kukua. Kulinganisha kila ombi na kila dereva ni kazi inayoongezeka kadiri idadi ya madereva inavyoongezeka, kwa kila ombi, na hasa wakati mahitaji yako juu zaidi. Saa za msongamano ndizo saa ambazo huwezi kumudu kuwa mzito.
Dunia inasogea wakati unafikiri. Mahali alipo dereva tayari pamepitwa na wakati kidogo unapopasoma. Dereva aliyekuwa tayari ulipoanza kutafuta anaweza kuwa amekubali safari nyingine, amezima programu au amepoteza mtandao kabla hujamaliza.
Abiria wawili wanaweza kumtaka dereva mmoja wakati huo huo. Hii ndiyo inayouma. Maombi mawili yanafika kwa tofauti ya milisekunde chache kutoka mitaa jirani. Utafutaji wote miwili unamwona dereva yule yule kama wa karibu zaidi aliye tayari. Wote wanampangia dereva huyo. Abiria mmoja anapata safari; mwingine anabaki akimsubiri dereva ambaye hatakuja kamwe.
Injini yetu ya kuunganisha imejengwa kwa tabaka tatu, moja kwa kila tatizo: H3 na Redis kupunguza ukubwa wa utafutaji, haversine kupanga kinachobaki, na kufuli za atomiki za Redis kuhakikisha dereva anaweza kuchukuliwa mara moja tu.
Tabaka la kwanza: kuifanya dunia iwe ndogo kwa H3
Utafutaji wa haraka zaidi ni ule ambao hauhitaji kuufanya kabisa. Kabla hatujapima umbali wowote, tunawaweka kando karibu madereva wote wa mji.
Kufanya hivyo, tunatumia H3, faharasa ya kijiografia ya chanzo huria iliyoundwa na Uber. H3 inaifunika sayari nzima kwa gridi ya hexagoni, katika viwango kumi na sita, kuanzia seli zenye ukubwa wa nchi hadi seli ndogo kuliko mita moja ya mraba. Kila nukta duniani iko ndani ya hexagoni moja tu katika kila kiwango, na kila hexagoni ina kitambulisho kifupi.
Kila mara simu ya dereva inapotuma mahali alipo, tunapageuza kuwa seli ya H3 na kumrekodi dereva ndani ya seti ya Redis ya seli hiyo. Dereva anapoingia hexagoni mpya, tunamhamisha kutoka seti ya zamani kwenda mpya. Redis inahifadhi faharasa nzima kwenye kumbukumbu, kwa hiyo kuisoma kunachukua mikrosekunde chache tu.
Abiria anapoagiza safari, hatuulizi "madereva wote wako wapi?". Tunauliza swali dogo zaidi: "nani yuko ndani ya hexagoni hii, na zile zinazoizunguka?"
import { latLngToCell, gridDisk } from "h3-js";
// Simplified for this article.
async function findCandidates(lat: number, lng: number, vehicleType: string) {
const origin = latLngToCell(lat, lng, RESOLUTION);
// Widen the search one ring of hexagons at a time until we find drivers.
for (let k = 0; k <= MAX_RINGS; k++) {
const cells = gridDisk(origin, k);
const ids = await redis.sunion(
...cells.map((cell) => `drivers:${vehicleType}:${cell}`),
);
if (ids.length > 0) return ids;
}
return [];
}
Tunatafuta kuelekea nje, pete kwa pete. Pete ya sifuri ni hexagoni ya abiria mwenyewe. Pete ya kwanza inaongeza hexagoni sita zinazoizunguka, pete ya pili kumi na mbili zinazozizunguka hizo, na kuendelea hivyo, hadi tupate madereva wa kutosha au tufike mpaka wa kile kinachohesabika kuwa "karibu". Ombi katikati ya eneo la biashara lenye shughuli nyingi kwa kawaida linapata madereva mara moja. Ombi pembezoni mwa mji linapanua utafutaji hadi linapowapata.
Kwa nini hexagoni, na si miraba
Hapa ndipo watu kwa kawaida huuliza kwa nini hatukutumia gridi rahisi ya miraba, au geohash.
Mraba una aina mbili za majirani: wanne wanaoshiriki upande mmoja, na wanne wanaogusana kwenye kona tu na walio mbali zaidi kwa kiasi kinachoonekana. Hexagoni ina majirani sita, na wote wako umbali sawa kutoka katikati yake. Unapopanua utafutaji pete kwa pete, hexagoni zinakua kwa umbo linalokaribia duara, ambalo ndilo maana halisi ya "karibu". Miraba inakua kwa umbo la almasi au sanduku, yenye kona zilizopotoka.
Sababu muhimu zaidi si ya kihisabati. H3 inaipa kampuni nzima lugha moja ya kuzungumzia mahali. Kitambulisho kile kile cha hexagoni kinachoendesha uunganishaji pia kinatuwezesha kuhesabu madereva na mahitaji katika mtaa, kupaka rangi ramani za joto za Twende Simulation Engine, na kulinganisha sehemu moja ya mji na nyingine. Faharasa ya kijiografia ambayo huduma yako ya kuunganisha peke yake ndiyo inayoielewa ni fursa iliyopotea.
Redis ina amri za kijiografia zilizojengwa ndani zinazoweza kujibu moja kwa moja "nani yuko ndani ya kilomita 2 kutoka nukta hii?", na kwa bidhaa nyingi hizo ndizo chaguo sahihi. Sisi tulichagua H3 kwa sababu tulitaka seli yenyewe, si swali peke yake.
Tabaka la pili: kupanga kwa haversine
H3 inatupa orodha fupi. Sasa tunahitaji mpangilio.
Kwa kila dereva aliye kwenye orodha, tunahesabu umbali hadi kwa abiria kwa kutumia fomula ya haversine, inayokokotoa umbali wa duara kuu kati ya nukta mbili kwenye tufe kutokana na latitudo na longitudo zao:
const EARTH_RADIUS_M = 6_371_000;
function haversine(lat1: number, lng1: number, lat2: number, lng2: number) {
const toRad = (deg: number) => (deg * Math.PI) / 180;
const dLat = toRad(lat2 - lat1);
const dLng = toRad(lng2 - lng1);
const a =
Math.sin(dLat / 2) ** 2 +
Math.cos(toRad(lat1)) * Math.cos(toRad(lat2)) * Math.sin(dLng / 2) ** 2;
return 2 * EARTH_RADIUS_M * Math.asin(Math.sqrt(a));
}
Ni nafuu, inatabirika, na kwenye orodha fupi inamaliza kufumba na kufumbua.
Haversine si sahihi, na bado tunaitumia
Tunataka kuwa wakweli hapa, kwa sababu hii ni aina ya njia ya mkato ambayo makala za kihandisi mara nyingi huipita kimya kimya.
Haversine inapima umbali kwa mstari wa moja kwa moja, kama ndege anavyoruka, na abiria hawasafiri kama ndege. Madereva wawili wanaweza wote kuwa mita 600 mbali: mmoja kwenye barabara iliyonyooka, na mwingine upande wa pili wa mto, wa soko au wa mlima wenye barabara moja tu inayouzunguka. Haversine inasema wako karibu kwa usawa. Abiria anayesubiri mahali pa kuchukuliwa anajua sivyo.
Tunakubali mabadilishano hayo kwa makusudi. Kukokotoa njia halisi za barabara kwa kila dereva kwa kila ombi kunagharimu muda na pesa, na mara nyingi mpangilio wa mstari wa moja kwa moja na ule wa barabara vinakubaliana. Pale vinapotofautiana, tofauti ni dakika moja au mbili, si upande mwingine wa mji.
Mtazamo wetu ni kwamba unapaswa kuwa sahihi kabisa pale tu ambapo usahihi unabadilisha matokeo, na wa gharama nafuu kila mahali pengine. Haversine ni kichujio cha bei nafuu kinachotosha. Makadirio ya muda wa kufika kwa kufuata barabara ndiyo tabaka la usahihi, na katika miji ya pili, ambako mtandao wa barabara una njia nyingi zisizotokea na njia mbadala chache, hilo ndilo tabaka tunalotarajia litakuwa na umuhimu zaidi kadiri muda unavyokwenda.
Tabaka la tatu: kumchukua dereva mara moja tu
Sasa sehemu iliyochukua muda mrefu zaidi.
Utafutaji na upangaji vinaweza kukuambia dereva bora ni nani. Haviwezi kuzuia maombi mawili yasifikie jibu lile lile wakati huo huo. Kila tulichoeleza hadi sasa kinasoma hali inayoshirikiwa, na usomaji ni wa kweli tu katika sekunde ile unapoufanya.
Suluhisho ni kufanya kumchukua dereva kuwe operesheni ya atomiki: inayofanikiwa yote au kushindwa yote, bila wakati wowote katikati ambapo mtu mwingine anaweza kupenya. Tunafanya hivyo kwa kufuli ya Redis:
// Claim the driver only if nobody else holds them.
const claimed = await redis.set(
`lock:driver:${driverId}`,
requestId,
"PX", LOCK_TTL_MS, // expire automatically if we crash
"NX", // only set if the key doesn't already exist
);
if (claimed !== "OK") {
// Someone else got there first: move on to the next candidate.
}
NX maana yake ni "weka ufunguo huu tu kama bado haupo". Redis inatekeleza amri hii kiatomiki, kwa hiyo maombi mawili yakijaribu kumchukua dereva mmoja wakati huo huo, moja tu linapata OK na lingine halipati kitu. Lililoshindwa halisubiri wala halijaribu tena dereva yule yule. Linahamia moja kwa moja kwa anayefuata kwenye orodha yake.
PX inaipa kufuli muda wa kuisha. Seva iliyomchukua dereva ikianguka katikati ya mchakato, dereva hafungiwi milele. Kufuli inatoweka yenyewe na dereva anarudi kwenye kundi la madereva walio tayari.
Kuifungua kufuli nako ni uamuzi. Unapaswa kufungua tu kufuli ambayo bado ni yako. Ikiwa kufuli yako tayari imeisha muda na ombi lingine limemchukua dereva huyo huyo, DEL ya kibubu ingefungua kufuli yao. Kwa hiyo tunalinganisha na kufuta kwa hatua moja ya atomiki, kwa kutumia hati fupi ya Lua ambayo Redis inaiendesha bila kukatizwa:
if redis.call("GET", KEYS[1]) == ARGV[1] then
return redis.call("DEL", KEYS[1])
end
return 0
Pale dereva anapokutana na kufuli
Hakuna kati ya haya kisichoonekana kwa madereva. Ombi la safari linapofika kwenye simu ya dereva, dereva ana muda mfupi wa kulikubali. Madereva wawili wakijibu ofa zinazoingiliana, au ofa ikiisha muda wakati dereva anabonyeza "Kubali", kufuli ndiyo inayoamua. Dereva aliyeshindwa anaona ujumbe kwenye programu: "Umechelewa! Ombi hili limeisha muda au limepewa mtu mwingine."
Ujumbe huo ni tabaka la concurrency likionyeshwa wazi kadiri tunavyoweza. Ni afadhali sana tumwambie dereva amekosa safari kuliko kutuma madereva wawili kwa abiria mmoja, au dereva mmoja kwa abiria wawili.
Kufuli si hakikisho
Msimamo mmoja zaidi, kwa wahandisi wanaosoma hii.
Kufuli ya Redis ni bora sana kuzuia maombi mawili yasifanye kazi ile ile wakati mmoja. Peke yake, si uthibitisho kwamba mfumo uko sahihi. Saa hupotoka, mitandao husita na michakato hukwama. Kufuli inaweza kuisha muda wakati mchakato ulioishikilia bado unadhani unammiliki dereva.
Somo tulilopata kutokana na kufukuzana na race conditions: ichukulie kufuli kama njia ya haraka, si neno la mwisho. Hatua inayothibitisha safari kwa kweli inapaswa kukagua, wakati wa kuandika, kwamba dereva bado yuko tayari na bado ni wako. Uhakika unatokana na tabaka ambazo kila moja inadhani lililotangulia linaweza kushindwa.
Kile ambacho "sehemu ya sekunde" kinanunua hasa
Ukiyaunganisha yote, uunganishaji mmoja unaonekana hivi:
- Mahali alipo abiria panageuzwa kuwa seli ya H3.
- Tunapanua pete kwa pete ndani ya Redis hadi tupate madereva wa karibu wa aina sahihi ya chombo: gari, XL au bodaboda.
- Tunawapanga kwa umbali wa haversine.
- Tunajaribu kumchukua bora zaidi kiatomiki. Tukishindwa, tunahamia anayefuata.
- Dereva aliyechukuliwa anapokea ombi na ana muda mfupi wa kulikubali.
Yote haya yanatokea ndani ya sehemu ya sekunde, na yanabaki sahihi wakati abiria wengi wanaagiza safari kwa wakati mmoja, ambao ndio wakati pekee unaojalisha kweli.
Kasi katika kuunganisha si majivuno. Kila sekunde abiria anayosubiri kando ya barabara bila uthibitisho ni sekunde anayotumia kujiuliza kama asimamishe bodaboda ya kwanza itakayopita. Katika miji ambako usafiri salama na wa kuaminika si jambo la kawaida, kuunganishwa kwa haraka na kwa usahihi ni ahadi ya kwanza tunayoitimiza katika kila safari.
Msimamo wetu, bila kuzunguka
Ikiwa unajenga jukwaa linalounganisha watu na chochote kinachosogea, kama safari, usambazaji au wafanyakazi wa uwandani, hiki ndicho tungekuambia:
- Punguza tatizo kabla ya kulitatua. Faharasa nzuri ya kijiografia inageuza "tafuta mji mzima" kuwa "tafuta mtaa".
- Chagua faharasa ya kijiografia ambayo kampuni nzima inaweza kuizungumza. Tulichagua H3 kwa ajili ya kuunganisha, na tukapata uchambuzi wa data, ramani za joto na uigaji karibu bure.
- Kuwa sahihi pale tu ambapo usahihi unabadilisha matokeo. Haversine kupanga, njia za barabara pale barabara zinapotofautiana.
- Jenga kwa ajili ya mashindano, si kwa ajili ya onyesho. Ikiwa maombi mawili yanaweza kugongana, yatagongana, na kwa kawaida katika saa yako yenye shughuli nyingi zaidi.
Hatujengi tu programu ya kuita usafiri. Tunajenga miundombinu ya usafiri salama, wa umeme na wa kuaminika kwa miji ya Afrika. Injini ya kuunganisha inayomfikisha abiria kwa dereva sahihi, haraka na mara moja tu, ndipo yote hayo yanapoanzia.

