Dizajniranje Facebook Messengera

Osmislimo uslugu instant messaginga poput Facebook Messengera gdje korisnici mogu međusobno slati tekstualne poruke putem web i mobilnih sučelja.

Što je Facebook Messenger?

Facebook Messenger je softverska aplikacija koja svojim korisnicima pruža usluge SMS-a zasnovane na tekstu. Korisnici programa Messenger mogu razgovarati sa svojim Facebook prijateljima i sa mobitela i sa Facebook stranice.

Zahtjevi i ciljevi sustava

Naš Messenger treba ispunjavati sljedeće zahtjeve:

Funkcionalni preduvjeti:

  1. Messenger bi trebao podržavati međusobne razgovore između korisnika.
  2. Messenger bi trebao pratiti mrežne / izvanmrežne statuse svojih korisnika.
  3. Messenger bi trebao podržavati trajno pohranjivanje povijesti chata.

Nefunkcionalni zahtjevi:

  1. Korisnici bi trebali imati iskustvo razgovora u stvarnom vremenu s minimalnom latencijom.
  2. Naš bi sustav trebao biti visoko dosljedan; korisnici bi trebali moći vidjeti istu povijest chatova na svim svojim uređajima.
  3. Messenger je visoka dostupnost; možemo tolerirati nižu dostupnost zbog dosljednosti.

Prošireni zahtjevi:

  • Grupni chatovi: Messenger treba podržavati više ljudi koji međusobno razgovaraju u grupi.
  • Push notifications: Messenger trebao bi biti u mogućnosti obavijestiti korisnike novih poruka kad su offline.

Procjena kapaciteta i ograničenja

Pretpostavimo da imamo 500 milijuna aktivnih korisnika dnevno i u prosjeku svaki korisnik pošalje 40 poruka dnevno; to nam daje 20 milijardi poruka dnevno.

Procjena pohrane: Pretpostavimo da je poruka u prosjeku 100 bajtova, tako da bismo za jedan dan mogli pohraniti sve poruke za pohranu 2TB.

20 milijardi poruka * 100 bajtova => 2 TB / dan

Za pohranu petogodišnje povijesti chatanja trebalo bi nam 3,6 petabajta za pohranu.

2 TB * 365 dana * 5 godina ~ = 3,6 PB

Osim poruka za chat, trebali bismo pohraniti i podatke o korisnicima, metapodatke o porukama (ID, vremenski žig itd.). Da i ne spominjemo, gornji izračun ne uzima u obzir sažimanje i replikaciju podataka.

Procjena propusnosti: Ako naša usluga svakodnevno dobiva 2TB podataka, to će nam pružiti 25MB dolaznih podataka u sekundi.

2 TB / 86400 sec ~ = 25 MB / s

Budući da svaka dolazna poruka mora izaći na drugog korisnika, trebat će nam ista količina propusne širine 25MB / s i za učitavanje i za preuzimanje.

Procjene visoke razine:

Dizajn na visokoj razini

Na visokoj razini trebat će nam poslužitelj za chat koji će biti središnji dio koji će organizirati svu komunikaciju između korisnika. Kad korisnik želi poslati poruku drugom korisniku, on će se povezati na chat poslužitelj i poslati poruku poslužitelju; Poslužitelj potom tu poruku prosljeđuje drugom korisniku i također je pohranjuje u bazu podataka.

Detaljan tijek rada izgledao bi ovako:

  1. Korisnik A šalje poruku User-B-u preko poslužitelja za chat.
  2. Poslužitelj prima poruku i šalje potvrdu korisniku-A.
  3. Poslužitelj pohranjuje poruku u svoju bazu podataka i šalje je korisniku B.
  4. Korisnik B prima poruku i potvrdu šalje poslužitelju.
  5. Poslužitelj obaviješta User-A da je poruka uspješno isporučena Korisniku B.

Detaljan dizajn komponenata

Pokušajmo prvo izgraditi jednostavno rješenje gdje se sve izvodi na jednom poslužitelju. Naš sustav treba na visokoj razini obraditi sljedeće slučajeve upotrebe:

  1. Primanje dolaznih poruka i isporučivanje odlaznih poruka.
  2. Pohranjivanje i preuzimanje poruka iz baze podataka.
  3. Vodite evidenciju o tome tko je korisnik na mreži ili je otišao izvan mreže i obavijestite sve relevantne korisnike o tim promjenama statusa.

Razgovarajmo o tim scenarijima jedan po jedan:

Rukovanje porukama

Kako bismo učinkovito slali / primali poruke? Da bi mogao slati poruke, korisnik se mora povezati s poslužiteljem i postavljati poruke za ostale korisnike. Da bi dobio poruku s poslužitelja, korisnik ima dvije mogućnosti:

  1. Model izvlačenja: Korisnici mogu povremeno pitati poslužitelja da li postoje nove poruke za njih.
  2. Model potiskivanja: korisnici mogu držati vezu otvorenom s poslužiteljem i mogu ovisiti o poslužitelju da će ih obavijestiti kad god postoje nove poruke.

Ako krenemo s našim prvim pristupom, tada poslužitelj mora pratiti poruke koje još čekaju na isporuku, a čim se korisnik koji prima prima poveže se s poslužiteljem i zatraži novu poruku, poslužitelj može vratiti sve čeka poruke. Kako bi umanjili kašnjenje za korisnika, oni moraju provjeravati poslužitelj prilično često, a većinu vremena dobit će prazan odgovor ako nema poruke na čekanju. Ovo će izgubiti puno resursa i ne izgleda kao učinkovito rješenje.

Ako krenemo s drugim pristupom, gdje svi aktivni korisnici održavaju vezu otvorenom s poslužiteljem, tada čim poslužitelj primi poruku, on može odmah proslijediti poruku namijenjenom korisniku. Na ovaj način poslužitelj ne mora pratiti poruke na čekanju, a imat ćemo minimalno kašnjenje, jer se poruke isporučuju odmah na otvorenu vezu.

Kako će klijenti održavati otvorenu vezu s poslužiteljem? Možemo koristiti HTTP Long Polling ili WebSockets. Tijekom dužeg ispitivanja klijenti mogu zatražiti informacije od poslužitelja s očekivanjem da poslužitelj možda neće odmah odgovoriti. Ako poslužitelj nema novih podataka za klijenta kada primi anketu, umjesto da pošalje prazan odgovor, poslužitelj drži zahtjev otvorenim i čeka da informacije o odgovoru postanu dostupne. Nakon što dobije nove informacije, poslužitelj odmah šalje odgovor klijentu, dovršavajući otvoreni zahtjev. Nakon primitka odgovora poslužitelja, klijent može odmah izdati još jedan zahtjev poslužitelja za buduća ažuriranja. To daje mnoga poboljšanja u kašnjenjima, propusnosti i performansama. Zahtjev za dugi upitnik može prekinuti ili dobiti prekid veze s poslužiteljem, u tom slučaju klijent mora otvoriti novi zahtjev.

Kako poslužitelj može učinkovito pratiti svu otvorenu vezu kako bi preusmjeravao poruke korisnicima? Poslužitelj može održavati tablicu hash-a, pri čemu bi "ključ" bio UserID, a "vrijednost" objekt veze. Dakle, svaki put kada poslužitelj primi poruku za korisnika, pregledava tog korisnika u hash tablici kako bi pronašao objekt veze i šalje poruku na otvoreni zahtjev.

Što će se dogoditi kada poslužitelj primi poruku za korisnika koji je otišao van mreže? Ako se prijemnik prekinuo, poslužitelj može obavijestiti pošiljatelja o neuspjehu isporuke. Ako se radi o privremenom prekidu veze, npr., Prijamnik je davno zahtjeva za anketom dugo vremena anketirao, tada treba očekivati ​​ponovno uspostavljanje veze od korisnika. U tom slučaju možemo zatražiti od pošiljatelja da pokuša ponovo poslati poruku. Taj bi se pokušaj mogao uklopiti u logiku klijenta tako da korisnici ne moraju ponovno unositi poruku. Poslužitelj također može pohraniti poruku neko vrijeme i pokušati je poslati nakon što se primatelj ponovno poveže.

Koliko nam servera za chat treba? Planirajmo 500 milijuna veza u bilo kojem trenutku. Ako pretpostavimo da suvremeni poslužitelj može u bilo kojem trenutku podnijeti 50K istodobne veze, trebat će nam 10K takvih poslužitelja.

Kako možemo znati koji poslužitelj drži vezu s kojim korisnikom? Možemo uvesti softver za uravnoteživanje opterećenja ispred naših chat poslužitelja; koji mogu preslikati svaki UserID na poslužitelj radi preusmjeravanja zahtjeva.

Kako poslužitelj treba obraditi zahtjev za isporuku? Nakon primanja nove poruke, poslužitelj mora učiniti sljedeće: 1) Spremite poruku u bazu podataka 2) Pošaljite poruku primatelju i 3) Pošaljite potvrdu pošiljatelju.

Poslužitelj za chat prvo će pronaći poslužitelja koji drži vezu za prijemnik i proslijediti poruku tom poslužitelju kako bi ga poslao primatelju. Poslužitelj za chat tada može poslati potvrdu pošiljatelju; ne trebamo čekati spremanje poruke u bazu podataka (to se može dogoditi u pozadini). Pohranjivanje poruke raspravlja se u sljedećem odjeljku.

Kako glasnik održava redoslijed poruka? Možemo pohraniti vremensku oznaku sa svakom porukom, a to je vrijeme kada server prima poruku. To još uvijek neće osigurati ispravno naručivanje poruka klijentima. Scenarij u kojem vremenska oznaka poslužitelja ne može odrediti točan redoslijed poruka izgledao bi ovako:

  1. User-1 šalje poruku M1 poslužitelju za User-2.
  2. Poslužitelj prima M1 na T1.
  3. U međuvremenu, User-2 šalje poruku M2 na poslužitelj za User-1.
  4. Poslužitelj prima poruku M2 na T2, tako da je T2> T1.
  5. Poslužitelj šalje poruku M1 korisniku-2 i M2 korisniku-1.

Tako će User-1 prvo vidjeti M1, a zatim M2, dok će User-2 prvo vidjeti M2, a zatim M1.

Da bismo to riješili, moramo zadržati redoslijedni broj sa svakom porukom za svakog klijenta. Ovaj redoslijedni broj određuje će točno naručivanje poruka za svakog korisnika. Ovim rješenjem oba će klijenta vidjeti različit prikaz redoslijeda poruka, ali taj će prikaz biti dosljedan na svim uređajima.

Spremanje i preuzimanje poruka iz baze podataka

Kad god chat server primi novu poruku, treba je pohraniti u bazu podataka. Da bismo to učinili, imamo dvije mogućnosti:

  1. Pokrenite zasebnu nit koja će raditi s bazom podataka za spremanje poruke.
  2. Pošaljite asinhroni zahtjev u bazu podataka da biste poruku pohranili.

Moramo imati na umu određene stvari prilikom dizajniranja naše baze podataka:

  1. Kako učinkovito raditi s bazenom veza baze podataka.
  2. Kako pokušati ponovo neuspjeli zahtjevi.
  3. Gdje upisati one zahtjeve koji nisu uspjeli ni nakon nekih pokušaja.
  4. Kako ponovo pokušati ove zabilježene zahtjeve (koji nisu uspjeli nakon ponovnog pokušaja) kada su se svi problemi riješili.

Koji sustav za pohranu trebamo koristiti? Moramo imati bazu podataka koja može podržati vrlo visoku stopu malih ažuriranja i brzo dohvatiti niz zapisa. To je potrebno jer imamo ogroman broj malih poruka koje je potrebno umetnuti u bazu podataka, a prilikom postavljanja upita korisnik je uglavnom zainteresiran za uzastopni pristup porukama.

Ne možemo koristiti RDBMS poput MySQL ili NoSQL poput MongoDB jer si ne možemo priuštiti čitanje / pisanje redaka iz baze podataka svaki put kada korisnik primi / pošalje poruku. Ovo ne samo da će osnovne operacije naše usluge pokrenuti s visokim kašnjenjem, već će stvoriti i veliko opterećenje baza podataka.

Oba naša zahtjeva lako se mogu ispuniti rješenjem baza podataka sa širokim stupcima poput HBase. HBase je NoSQL baza podataka orijentirana na stupac koja može pohraniti više vrijednosti prema jednom ključu u više stupaca. HBase se modelira po Googleovom BigTableu i pokreće se na vrhu Hadoop Distribuiranog datotečnog sustava (HDFS). HBase grupira podatke kako bi spremili nove podatke u memorijski međuspremnik i kad je međuspremnik pun, podatke sprema na disk. Ovakav način pohrane pomaže ne samo u brzom pohranju puno malih podataka, već i prikupljanju redaka ključem ili skeniranju raspona reda. HBase je također učinkovita baza podataka za pohranu podataka promjenjivih veličina, što također zahtijeva naša služba.

Kako klijenti trebaju učinkovito dohvaćati podatke s poslužitelja? Klijenti bi trebali paginirati tijekom dohvaćanja podataka s poslužitelja. Veličina stranice može biti različita za različite klijente, npr. Mobiteli imaju manje ekrane, tako da nam treba manji broj poruka / razgovora u okviru za pregled.

Upravljanje statusom korisnika

Moramo pratiti mrežni / izvanmrežni status korisnika i obavijestiti sve relevantne korisnike kad god se dogodi promjena. Budući da na poslužitelju održavamo objekt veze za sve aktivne korisnike, iz ovoga možemo lako saznati trenutni status korisnika. S 500M aktivnih korisnika u bilo kojem trenutku, ako moramo emitirati svaku promjenu statusa svim relevantnim aktivnim korisnicima, trebat će puno resursa. Oko toga možemo učiniti sljedeće optimizacije:

  1. Kad god klijent pokrene aplikaciju, može povući trenutni status svih korisnika na popisu svojih prijatelja.
  2. Kad god korisnik pošalje poruku drugom korisniku koji je otišao van mreže, možemo pošiljatelju poslati neuspjeh i ažurirati status klijenta.
  3. Kad god korisnik dođe putem interneta, poslužitelj može uvijek emitirati taj status s odgodom od nekoliko sekundi da vidi hoće li korisnik odmah nestati izvan mreže.
  4. Klijenti mogu izvući status s poslužitelja o onim korisnicima koji se prikazuju na korisničkom prikazu. Ovo ne bi trebalo biti česta operacija, jer poslužitelj emitira mrežni status korisnika i neko vrijeme možemo živjeti s nelagodnim izvanmrežnim statusom korisnika.
  5. Kad god klijent započne novi chat s drugim korisnikom, tada možemo povući status.

Sažetak dizajna: Klijenti će otvoriti vezu s chat serverom za slanje poruke; poslužitelj će ga potom proslijediti traženom korisniku. Svi aktivni korisnici održat će vezu otvorenom s poslužiteljem za primanje poruka. Kad god stigne nova poruka, poslužitelj za chat će je poslati na primatelja na zahtjev za dugom anketom. Poruke se mogu pohraniti u HBase koji podržava brza mala ažuriranja i pretraživanja na temelju raspona. Poslužitelji mogu emitirati mrežni status korisnika drugim relevantnim korisnicima. Klijenti mogu povući ažuriranja statusa za korisnike koji su vidljivi u klijentovom prozoru za pregled rijetko.

Podjela podataka

Budući da ćemo spremati puno podataka (3.6PB pet godina), moramo ih distribuirati na više poslužitelja baza podataka. Kakva će biti naša shema podjele?

Particioniranje na temelju UserID: Pretpostavimo da smo particionirali na temelju hash-a UserID-a kako bismo mogli zadržati sve poruke korisnika u istoj bazi podataka. Ako je jedan DB-ov dio 4TB, pet godina ćemo imati „3.6PB / 4TB ~ = 900“ dijelova. Radi jednostavnosti, pretpostavimo da držimo 1K krhotine. Tako ćemo pronaći broj dijeljenja pomoću "hash (UserID)% 1000" i pohraniti / preuzeti podatke odatle. Ova shema particija također će vrlo brzo dohvatiti povijest chatova za bilo kojeg korisnika.

U početku možemo početi s manje poslužitelja baza podataka s više komada koji se nalaze na jednom fizičkom poslužitelju. Budući da na poslužitelju možemo imati više instanci baze podataka, lako možemo pohraniti više particija na jedan poslužitelj. Naša hash funkcija mora razumjeti ovu logičku shemu particioniranja kako bi mogla mapirati više logičkih particija na jednom fizičkom poslužitelju.

Budući da ćemo pohraniti neograničenu povijest poruka, možemo započeti s velikim brojem logičkih particija koje će se preslikati na manji broj fizičkih poslužitelja, a kako se povećava naša potražnja za pohranom, možemo dodati još fizičkih poslužitelja za distribuciju naših logičkih particija.

Particioniranje na temelju MessageID-a: Ako pohranimo različite poruke korisnika na zasebne dijelove baze podataka, dohvaćanje niza poruka chata bilo bi vrlo sporo, tako da ne bismo trebali prihvaćati ovu shemu.

Cache

Nekoliko nedavnih poruka (recimo zadnjih 15) možemo spremiti u nekoliko nedavnih razgovora koji su vidljivi u korisničkom prikazu (recimo zadnjih 5). Budući da smo odlučili pohraniti sve korisničke poruke na jedan dio, predmemorija za korisnika trebala bi u potpunosti biti smještena i na jednom stroju.

Balansiranje opterećenja

Trebat će nam balansator opterećenja pred našim chat poslužiteljima; koji može preslikati svaki UserID na poslužitelj koji drži vezu za korisnika, a zatim zahtjev usmjeriti na taj poslužitelj. Slično, trebao bi nam i balans za opterećenje za naše predmemorijske poslužitelje.

Tolerancija pogreške i replikacija

Što će se dogoditi kad poslužitelj za chat ne uspije? Naši poslužitelji za chat održavaju veze s korisnicima. Ako poslužitelj odlazi, trebamo li osmisliti mehanizam za prijenos tih veza na neki drugi poslužitelj? Iznimno je teško prekinuti TCP veze s drugim poslužiteljima; jednostavniji je pristup tako da se klijenti automatski ponovo povežu ako se veza izgubi.

Trebamo li pohraniti više primjeraka korisničkih poruka? Ne možemo imati samo jednu kopiju korisničkih podataka, jer ako se poslužitelj koji drži podatke ili se trajno pokvari, nemamo mehanizam za vraćanje tih podataka. Za ovo ili moramo pohraniti više kopija podataka na različite poslužitelje ili koristiti tehnike poput kodiranja Reed-Solomona da bismo ih distribuirali i replicirali.

Prošireni zahtjevi

Grupni chat

U našem sustavu možemo imati zasebne grupne objekte za chat koji se mogu pohraniti na chat poslužitelje. Objekt grupnog chata identificirao je GroupChatID i također će održavati popis ljudi koji su dio tog chata. Naš uravnoteživač opterećenja može usmjeriti svaku poruku grupnog chata na temelju GroupChatID-a, a poslužitelj koji rukovodi tim grupnim chatom može ponoviti preko svih korisnika chata kako bi pronašao poslužitelj koji upravlja vezom svakog korisnika za dostavu poruke.

U baze podataka možemo pohraniti sve grupne chatove u zasebnu tablicu podijeljenu na temelju GroupChatID.

Push obavijesti

U našem trenutačnom dizajnu korisnici mogu slati poruke samo aktivnim korisnicima i ako korisnik koji prima primaj, mi šaljemo neuspjeh korisniku koji ga šalje. Push obavijesti omogućit će našem sustavu slanje poruka izvanmrežnim korisnicima.

Za Push obavijesti, svaki se korisnik može prijaviti sa svog uređaja (ili web preglednika) kako bi dobio obavijesti kad god dođe nova poruka ili događaj. Svaki proizvođač održava skup poslužitelja koji upravlja guranjem tih obavijesti prema korisniku.

Da bi u našem sustavu bile objavljene push obavijesti, morali bismo postaviti poslužitelj za obavijesti koji će primati poruke za izvanmrežne korisnike i slati ih na proizvođač push obavijesti s pritiskom koji će ih slati na uređaj korisnika.