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

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.

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.

Autor programuje v Javascriptu, PHP, Javě, Golangu… ve všem možném. Ve volném čase probádává nejrůznější zákoutí světa programovacích jazyků a databází a všeho kolem nich.

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Komentáře: 9

Přehled komentářů

Janci rank service
Jakub Kulhan Re: rank service
Tomáš
Jakub Kulhan Re:
harrison314 Radenie
Kačka Re: Nabíráme
Jakub Kulhan Re: Radenie
karel Re:
Tomáš Re:
Zdroj: https://www.zdrojak.cz/?p=16045