N+1 problém a jeho řešení

Nejnovější projekty aktuálně implementované v Shopsysu využívají javascriptový storefront, který komunikuje se zbytkem aplikace pomocí frontendového GraphQL API. Technologie GraphQL umožňuje klientovi na základě definice schématu získat velké množství dat i jedním jediným dotazem. Záleží pouze na fantazii a šikovnosti klienta, jinak řečeno konzumenta API.

Vzhledem k tomu, že endpoint pro GraphQL je veřejně dostupný, konzumentem nemusí být nutně pouze samotná storefrontová aplikace, ale například i potenciální útočník, který má v úmyslu aplikaci poškodit. Proto jsme museli učinit kroky směrem k zabezpečení API a připravit ho mimo jiné na případné pokusy o přetížení. Při ladění performance a ošetřování všemožných hrozeb přišlo na stůl i téma N+1 problému. Přestože N+1 je obecný antipattern, v tomto článku si ho popíšeme konkrétně v kontextu GraphQL.

Co je to N+1 problém?

Jedná se o situaci, kdy při odpovědi na GraphQL dotaz musí aplikace iterovat nad výsledkem a provádět dodatečné dotazy (ať už jsou to dotazy na relační databázi, nebo třeba do Elasticsearch). V podstatě pokud API na náš základní dotaz vrací 100 položek, tak “N” značí 100 dodatečných dotazů, které musí aplikace ještě vykonat pro donačtení dat ke každému záznamu a “+1” značí ten jeden původní dotaz (např. jednoduchý “SELECT * FROM Products).

Jak poznat riziko N+1 problému?

Abychom mohli eliminovat riziko N+1 problému, museli jsme jej nejdříve v našem projektu správně identifikovat. Klíčové bylo položit si dvě otázky:

• Existuje v API možnost získat kolekci entit?
• Mají tyto entity nadefinovánu nějakou vazbu?

V momentě, kdy jsme si na obě otázky odpověděli “ANO”, odhalili jsme místo, kde hrozí N+1 problém. Bylo důležité si uvědomit, že na našem projektu vůbec nemusel existovat rizikový dotaz, ale že problém byl v samotném API. Jak již bylo zmíněno v úvodu, API je veřejné a komukoliv umožňuje zeptat se na cokoliv. Útočník může přetížit API například položením dotazu níže.

query {

  products {

    categories {

      products {

        categories {

          name

        }

      }

    }

  }

}

Dotaz v překladu do češtiny znamená  “dej mi všechny produkty e-shopu, ke každému všechny jeho kategorie, ke každé kategorii její produkty a ke každému produktu jména jeho kategorií”. To sice v reálné aplikaci nedává smysl, ale možnost položit takový dotaz pořád existuje. Tedy i v případě optimalizace všech našich dotazů, byl N+1 problém stále potenciální hrozbou pro náš projekt.

Typické příklady N+1 problému

Při bližším zkoumání se nám podařilo vytipovat konkrétní místa, která byla zatížena N+1 hrozbou. Typicky se jednalo o následující příklady:

Multijazyčné entity, které mají své překlady uloženy v samostatných tabulkách

V případě, že si někdo na API vyžádal všechny kategorie produktů a ke každé kategorii chtěl vypsat její jméno, na pozadí proběhly následující dotazy:

• SELECT * FROM categories (tzn. dotaz označovaný jako “+1”)
• SELECT name FROM category_translations WHERE category_id = XX (tzn. “N” dalších dotazů, kde “N” odpovídá počtu kategorií vrácených prvním dotazem)

Jakékoliv další relační vazby mezi entitami

Příkladem může být dotaz na seznam všech objednávek uživatele spolu s položkami daných objednávek. Kolik měl uživatel objednávek, tolik proběhlo dodatečných dotazů do tabulky s položkami objednávek.

Vazby entit v indexech Elasticsearch

V Elasticsearch máme například data článků blogu. Každý článek může mít navázané produkty. Do indexu článků se tedy exportují ID produktů. Pokud jsme si na API vyžádali všechny články blogu a k nim produkty, tak kromě jednoho dotazu na Elasticsearch pro seznam článků se provedlo ještě N dalších dotazů na index produktů. Opět, kolik článků, tolik dodatečných dotazů na produkty.

Jak jsme vyřešili N+1 problém?

Pro vyřešení N+1 problému jsme využili dvou základních technik – eager loading (nenašel jsem lepší český překlad než “dychtivé načítání dat”) a batch loading (česky “hromadné načítání dat”).

Eager loading

Pro vysvětlení této techniky se můžeme vrátit k příkladu s překládanými názvy kategorií. Abychom zabránili N+1 problému, s kategoriemi rovnou načítáme i jejich překlady. Nově tedy existuje pouze jeden SQL dotaz:

SELECT * FROM categories JOIN category_translations

Překlady jsou tak vráceny spolu s kategoriemi a díky objektově relačnímu mapování Doctrine jsou překlady hned načteny do paměti. Ve chvíli, kdy chceme získat jméno kategorie, již dále neprobíhají žádné dodatečné dotazy do databáze.

Batch loading

V tomto případě místo okamžitého volání dodatečných dotazů pouze postupně ukládáme potřebné identifikátory do paměti (můžeme říci do aplikační cache). Následně na základě uložených identifikátorů získáme dodatečná data hromadně. Výsledky hromadného dotazu následně napárujeme na jednotlivé záznamy původního dotazu. Pro implementaci hromadného načítání využíváme knihovnu overblog/dataloader-bundle.

Pokud se naposledy vrátíme k příkladu s kategoriemi, z původních N dotazů typu 

SELECT name from category_translations WHERE category_id = XX

jsme tak vytvořili jediný hromadný dotaz v tomto tvaru:

SELECT name from category_translations WHERE category_id IN (XX, XY, XZ…)

Tuto techniku využíváme nejen pro dotazy do databáze, ale i do Elasticsearch, jehož API umožňuje volat více dotazů najednou (pomocí “msearch”).

Slovo závěrem

N+1 problém nemusí být nutně problémem v případě, kdy víme, že číslo N nebude nikdy příliš vysoké. Při našich optimalizacích jsme tedy neřešili naprosto všechna místa, kde by se problém mohl akademicky vyskytnout, ale hlavně ta místa, která by při špatném použití (nebo správném zneužití) mohla aplikaci dostat do problémů. Pro zabezpečení robustnosti API jsme využili i další techniky, které už s N+1 problémem přímo nesouvisí, například nacenění komplexity jednotlivých polí ve schématu API a určení maximální komplexity a hloubky GraphQL dotazů. Tyto postupy si můžeme blíže popsat v samostatném článku někdy příště.