Přejít k navigační liště

Zdroják » Databáze » Jak Skrz.cz řadí 20K nabídek podle real-time analytiky

Jak Skrz.cz řadí 20K nabídek podle real-time analytiky

Články Databáze

Myslíte, že seřadit tisíce nabídek za pár milisekund je jednoduché? Připočtěte k tomu, že se řazení přizpůsobuje chování stovek online uživatelů. Aneb jak jsme spojili Elasticsearch, RabbitMQ, PHP a Go.

Nálepky:

Na Skrz.cz je denně aktivních přes 20 tisíc nabídek, např. stránka skrz.cz/pobyty obsahuje v době psaní 1758 nabídek. Návštěvník nemá šanci projít všechny. Proto musíme nabídky řadit tak, aby se nahoře zobrazily ty, které jsou nejlepší a nejrelevantnější tomu, co uživatel teď konkrétně hledá a o co obecně má/nemá zájem[1].

Nedám tu konkrétní vzorec, podle kterého se na Skrzu nabídky řadí, ale popíšu technologie, které používáme, a jak jsme k nim došli. (Samotný vzorec ranku nabídky je stejně jen už vynásobení pár čísel se správnými vahami…)

Redesign Rewrite 2014

Vánoce 2013 a povánoční výprodeje často dokázaly shodit celý Skrz. V té době se data pro výpisy se vybírala z MySQL, některá data se zakešovala v Redisu, celý frontend stavěl na home-made PHP frameworku, Ulrice. V MySQL byly nejrůznější denormalizované předpočítané pohledy na data, avšak ani to nestačilo. Rozhodli jsme pro výpisy nabídek (které tvoří největší procento čtení z MySQL) začít používat Elasticsearch; nejdříve jen pro fulltextové vyhledávání, ale nakonec i pro všechny ostatní. S tím souvisel i postupný přechod na Ulriky na Symfony[2]. Z nejhorší možné chyby – přepisu aplikace – se stal základ, na kterém se dá skvěle stavět.

Rok 2014 se nesl ve znamení technologických novinek i nadále – důležitou změnou ke konci roku bylo nasazení RabbitMQ. Přes “králíka” teď tečou v průměru stovky zpráv za sekundu (v peaku jednotky tisíc). Všechno, co návštěvník udělá, se trackuje a vyhodnocuje – načte si stránku, podívá se na nabídku, klikne na tlačítko, zavře nějaký boxík, odejde na web k partnerovi, na webu partnera si službu/zboží objedná atd. To všechno jsou actions a jdou přes action exchange. Na ní je napojeno X consumerů – jeden např. odečítá peníze z účtů při prokliku ven ze Skrzu. Většina jich ale počítá různé statistiky a chytristiky.

Trackování akcí uživatelů probíhá přes aplikaci, které říkáme hitserver[3] – server napsaný v ReactPHP (jako Node.JS, akorát že v PHP). Hledali jsme knihovnu pro RabbitMQ s podporou asynchronního přístupu ReactPHP. Ze začátku jsme použili React/STOMP. Komunikace přes STOMP však nebyla výkonná, jak bychom potřebovali, deklarace front a vlastností musela probíhat ručně nebo přes jinou knihovnu. Problémy mě nakonec přiměly napsat knihovnu BunnyPHP – poskytuje stejné rozhraní pro synchronní i asynchronní komunikaci a je daleko rychlejší než React/STOMP nebo php-amqplib.

Chceme rank A/B testovat

Ranking nabídek se počítal cronem jednou za pár minut, mezivýsledky podle toho, jestli je bylo potřeba persistovat, nebo ne, se ukládaly do MySQL, resp. do Redisu. Výpočet se postupně zesložiťoval, přibývaly další podmínky, další proměnné, měnily se váhy apod., výpočet tedy trval déle a déle. Řešilo se to tak, že se interval cronu zvětšoval a zvětšoval. A/B testování bylo omezené opravdu na možnost A, nebo možnost B. Tak to i vypadalo v Elasticsearch – dva fieldy. Při výdeji stránky se jen rozhodlo, do které skupiny uživatel patří, a podle toho se poslala query do Elasticsearch s řazením podle prvního nebo druhého fieldu. Rank musel být vždy obecný, nešel touto cestou řešit personalizovaný rank pro každého uživatele zvlášť. Mimo to, že výpočet ranku trval dlouho, zabralo hodně času i uložení ranku do MySQL (jako primární databáze) a následný update dat z MySQL do Elasticsearch.

Jak se zbavit potíží popsaných výše? Důležité bylo si uvědomit, že rank je efemérní. Proč by se měl ukládat do MySQL? Proč by se měl ukládat do Elasticsearch? Je potřeba pouze vzít výsledky vyhledávání/filtrace a seřadit je. Řešit tohle aplikačně v PHP by bylo velmi náročné na paměť a procesorový čas – řazení musí probíhat co nejblíže datům.

Řešení

Elasticsearch na to měl odpověď – _script-based sorting. Skriptu se dají předat parametry (např. i ID uživatele). Vrátit může cokoli, podle čeho půjdou dokumenty seřadit. Kvůli výkonu a možnostem jsme se rozhodli jít cestou native script pluginu.

Aby se mohly jednoduše spouštět a vypínat různé verze ranku, nešlo samotný algoritmus přímo napsat do pluginu – každá změna by znamenala restart Elasticsearch. Rank native script v Elasticsearch je tedy naprosto hloupý, jediné, co potřebuje, je URL, na kterou se má připojit pro získání ranku. Hodnotu, kterou mu služba na dané URL vrátí, předá Elasticsearch jako skóre dokumentu a na krátkou dobu si ji zakešuje, aby se pro hot položky nepřetěžovala rank service.

Složitější než udělat samotný plugin bylo najít způsob, jakým bude komunikovat se service pro výpočet ranku. Komunikace musí být rychlá, zvládat desetitisíce požadavků za sekundu a ideálně být nezávislá na platformě.

Ve Skrzu mám zkušenosti s nejrůznějšími způsoby komunikace přes HTTP (JSON-RPC, XML-RPC, SOAP, vlastní-RPC, RESTful…) pro interní a externí API i s RPC přes RabbitMQ pro interní API. Na chvíli si odmysleme serializační formát dat (jestli je to JSON, XML nebo něco jiného) a podívejme se pouze na přenosový protokol. U HTTP je problém, pokud začnete otevírat nové TCP spojení pro každý požadavek, že brzy narazíte na maximální počet naráz otevřených file descriptorů. Navíc otevírání TCP má svou režii. Při poolu keep-alive spojení (pošle se více requestů v jednom spojení) zase nastane problém s head-of-line blocking (jeden pomalý požadavek zdržuje vyřizování ostatních).

RPC přes RabbitMQ odstraňuje oba výše zmíněné problémy HTTP – má jedno multiplexované TCP spojení, dokáže tedy zpracovávat více requestů naráz a přijímat odpovědi out-of-order. Nicméně má úplně jiný problém – velkou latenci kvůli tomu, že požadavky jdou z klienta do brokeru, z brokeru do service, zpět do brokeru a z brokeru do klienta – 2 naprosto zbytečné network hopy a k tomu režie zpracování requestu a odpovědi brokerem.

Přenos tedy musí probíhat napřímo a multiplexovaně, aby jeden request nemohl blokovat zpracování dalších. Co se týče serializace, lepší je používat co nejméně ukecané (nejlépe tedy binární) formáty. Rozhodování jsem nakonec zúžil na Thrift (používá Facebook) a gRPC (používá Google). A vyhrálo gRPC. S Thriftem jsem se zlobil více jak den, než jsem to vzdal. Nedokázal jsem ani vygenerovat kód klienta (v Javě) a serveru (v Go), aby spolu komunikovali. Špatná message poslaná do klienta v Elasticsearch pluginu dokázala shodit celou JVM s OutOfMemoryError. Zato gRPC fungovalo hned a bez problémů, vč. automatického reconnectu.

Pro service jsem použil Go. Je to velmi jednoduchý jazyk a je ještě jednodušší výslednou aplikaci nasadit – zkompiluje se do statické binárky a nakopíruje na server. Tam stačí jen spustit. Pro komunikaci s RabbitMQ používá github.com/streadway/amqp, service si drží svůj vlastní stav v BoltDB (embedded databázi) a poskytuje rozhraní pro komunikaci přes gRPC. Místo oficiální knihovny pro Protocol Buffers github.com/golang/protobuf je nasazena github.com/gogo/protobuf. Ta pro serializaci a deserializaci místo reflexe vygeneruje kód na míru každé struktuře – výsledkem je až 10krát lepší výkon.

Závěr

Elasticsearch plugin je v plánu rozšiřovat o další funkce. V současné době běží více verzí ranku vedle sebe a můžeme nad implementací a samotným algoritmem mnohem rychleji iterovat než kdy dříve. Krom toho jsme ušetřili mnoho zápisů do MySQL a do Elasticsearch, za což jsou obě databáze vděčné.

Pokud se chceš o podobných tématech, co se řeší ve Skrzu, dozvědět víc, sleduj @SkrzCzDev na Twitteru a/nebo přijď 21.10. na Skrz Dev Cirkus.

Skrz Dev Circus

21. října proběhne ve Skrz.cz již třetí setkání Skrz DEV cirkus! Tentokrát na téma „algoritmy co přemýšlejí za vás”. V čem jsou naše setkání jiná než běžná školení? Špičkoví odborníci z oboru se pravidelně scházejí ve Skrz.cz, aby představili konkrétní řešení problémů namísto nudné teorie a balastu.


[1] Doporučuji hledat whitepapery s keywords jako ranking, learning to rank, personalization, recommendation system ad.

[2] Jak jsme se s přepisem na Symfony a propojení se stavajícím řešením popasovali, se dá dočíst na @SkrzCzDev blogu.

[3] I na hitserveru používáme Symfony pomocí bridge podobnému tomuto – převede ReactPHP request na Symfony request a naopak Symfony response na ReactPHP response.

Komentáře

Subscribe
Upozornit na
guest
9 Komentářů
Nejstarší
Nejnovější Most Voted
Inline Feedbacks
View all comments
Janci

rozumiem tomu spravne, ze pri kazdom hladani sa na kazdu polozku vysledku zavola rank service? kolko dotazov na rank service ide z jedneho hladania?

Tomáš

hezké řešení, líbí se mi jak jste se s problémem vypořádali. Udělali byste to stejně, kdybyste to teď dělali na zeléné louce?

Jak to vidím takhle zdálky a strašně jednoduše, šel bych jinou cestou. Položek máte málo, uživatelů také, vše se vám vejde do RAM… Například bych vzal velkej hrnec, goučko, zamíchal bych to, přidal krapet shared memory a okořenil to trochou redisu pro persistenci a sync více nodů (nebo klidně na to zneužít replikační protokol elasticu). Za pár dní vaření máte první koláčky…

Elasticsearch mi v tom připadá až moc těžkopádný, nedělá nic jiného než točí celým strojem, jen aby seřadil pár tisíc položek s rankingem, který si stejně vyzobá externě. V elasticu bych nechal pouze historii, nejspíš jí tam máte, ale live data strčil do paměti a vařil z nich chutné jídlo…

Jak řešíte ranking a ruční prioritizaci nebo marketing dostal zákaz to ovlivňovat? Výpočet rankingu máte dopředu stanovený podle nějakých vah za jednotlivé akce nebo se snažíte dalekovíce předvídat o co je zájem nebo co zákazník ještě nekoupil nebo co by už mohl znovu koupit?

PS: nenabíráte?

harrison314

Viete mi povedat, ake algoritmy pouzivate na vypocet zoradnia produktov a odporucani?
Kludne aj vo vseobecnosti.

Kačka

Tomáši, nechceš rovnou dorazit na naší zítřejší akci? https://www.facebook.com/events/499649220196217/

Kačka

karel

Také mi to dělo připadá na vrabce trochu velké,
já mám než elastic raději sphinxsearch je sním trošku víc trápení, ale výsledek stojí za to.
Ale vážně těch položek je opravdu docela málo na takovéhle řešení.

Tomáš

Díky za odpověď, já si právě myslím, že to vše lze udělat bez elasticu jednodušeji :) No, spíše vím to, už jsem pár řešení postavil a low latency distribuované aplikace jsou můj pevný bod v tomhle rychlém světě.

Rozumím vašemu řešení i důvodu proč jste ho použili, nejspíš bych také u něj skončil, ale třeba na co asi musíte narážet je škálování (ten go tcp server bude vždy brzda), vývoj (vývojář nejspíš nebude mít tuhle mašinérii u sebe, ale bude používat sdílený vývojový cluster) a testování (daleko hůře s tímhle lze psát int. testy a automatizaci).

S personalizací to může být jiná zábava :), já vždy narážel vlastně na to, že neumím segmentovat správně nabídky nebo že jim nerozumím. Pokud si někdo koupí zájezd, těžko mu budu nabízet večeři v Praze, raději bych chtěl v místě zájezdu, stejně tak mu těžko budu nabízet zájezd zase za týden. Máte tohle nějak řešené nebo jste se ještě tak daleko nedostali? Tenhle trh už moc nesleduji.

PS: díky za nabídku :), neptal jsem se pro sebe, ale mám kolem sebe několik lidí, kteří tápou, tak je pingnu. Na Cirkus jsem koukal, děkuji, možná někdy příště, přednášky mě neberou, ale diskuze může být plodná.

Enum a statická analýza kódu

Mám jednu univerzální radu pro začínající programátorty. V učení sice neexistují rychlé zkratky, ovšem tuhle radu můžete snadno začít používat a zrychlit tak tempo učení. Tou tajemnou ingrediencí je statická analýza kódu. Ukážeme si to na příkladu enum.

Pocta C64

Za prvopočátek své programátorské kariéry vděčím počítači Commodore 64. Tehdy jsem genialitu návrhu nemohl docenit. Dnes dokážu lehce nahlédnout pod pokličku. Chtěl bych se o to s vámi podělit a vzdát mu hold.