Spis treści
1. Problem produkcyjny
System analizuje historię zamówień, aby wykrywać zestawy produktów często kupowanych razem. To typowy workflow backendowy, który w developmentcie wygląda niewinnie, na małych danych działa, a potem nagle rozpada się przy pierwszym naprawdę dużym kliencie.
Logi z produkcji pokazały najgorszy przypadek bardzo wyraźnie: około 6300 zamówień i 1500 unikalnych produktów. Na takim wejściu job nigdy się nie kończył. Brak zakończenia oznaczał brak wygenerowanych zestawów i brak wartości dla dalszych etapów produktu.
To jest nasz ulubiony rodzaj problemu: nie kosmetyka, tylko usunięcie realnego ograniczenia systemu.
2. Dlaczego Apriori poległo
Poprzednia implementacja bazowała na Apriori z Accord.NET. Apriori generuje kandydatów poziom po poziomie, więc przy dużej liczbie unikalnych produktów koszt rośnie dramatycznie. Tutaj teoria problemu nie była detalem, tylko sednem awarii: eksplozja kombinatoryczna.
Złożoność kombinatoryczna
Apriori skaluje się wraz z przestrzenią kandydatów. Przy odpowiednio dużej liczbie produktów ta przestrzeń eksploduje.
Cancellation, które nie anulowało
Biblioteka wystawiała CancellationToken, ale nie sprawdzała go w gorących pętlach. W praktyce wsparcie dla anulowania było martwym kodem.
Dodatkowy narzut po drodze
Był koszt konwersji danych, droższe lookupy i pośrednia droga przez association rules tylko po to, by wrócić do tych itemsetów, których faktycznie potrzebowaliśmy.
Wniosek był prosty: to nie był problem do dostrojenia. Tu trzeba było zmienić algorytm.
Rozważaliśmy też poprawkę upstream. Chcieliśmy otworzyć pull request z nową wersją podejścia do Accord.NET, ale repozytorium projektu jest zarchiwizowane i nie jest już aktywnie rozwijane. Dlatego finalnie wdrożyliśmy i utrzymujemy to rozwiązanie we własnym stacku.
3. Co dowieźliśmy
Zamieniliśmy Apriori na własną implementację FP-Growth. FP-Growth nie generuje kandydatów, kompresuje transakcje do FP-Tree i wydobywa częste zbiory bezpośrednio przez pattern growth. Dla tego typu obciążenia to po prostu lepszy model obliczeń.
Co zmieniło się w kodzie
- Wprowadziliśmy czystą granicę między logiką biznesową a algorytmem wydobywania zestawów.
- Stary, rozproszony przepływ został zastąpiony jednym ujednoliconym torem wykonania opartym o DI.
- Algorytm został odseparowany do dedykowanego modułu machine learning.
- Dodaliśmy zunifikowane testy poprawności, anulowania i skali dla wszystkich implementacji.
- Przebenchmarkowaliśmy kilka wariantów FP-Growth i do produkcji weszło V5 jako zwycięzca.
Najfajniejsze w tym PR-ze jest to, że nie tylko przykrywa stary bottleneck. On zostawia po sobie kod, który łatwo podmieniać, benchmarkować i rozwijać bez zgadywania.
4. Wyniki benchmarków
BenchmarkDotNet na Apple M4 z .NET 8 pokazał skalę zmiany bez żadnych niedomówień. Stare podejście kończyło się timeoutem na dużych danych. Nowe liczy wynik w milisekundach.
Mały benchmark
1k zamówień / 100 produktów
Accord Apriori: 1556 ms
FP-Growth V5: 1,9 ms
Duży benchmark
10k zamówień / 2k produktów
Accord Apriori: timeout
FP-Growth V5: 11,4 ms
Po drodze przetestowaliśmy kilka wariantów wewnętrznych. V5 wygrało, bo trzyma węzły w płaskiej liście i używa jednego współdzielonego słownika na drzewo, kluczowanego przez (parentId << 32 | item). To usunęło koszt słowników per node, który ograniczał wcześniejsze wersje przy dużych drzewach.
Poprawność nie została poświęcona dla szybkości. PR kończy się z 44 przechodzącymi testami i porównaniem wariantów względem zachowania referencyjnego.
5. Dlaczego to ważne
Dobra praca nad wydajnością rzadko polega na dłubaniu w jednej gorącej pętli. Największa wartość powstaje wtedy, gdy cofamy się krok wstecz, weryfikujemy prawdziwy bottleneck i zmieniamy sam kształt rozwiązania.
Dlatego właśnie warto pochwalić się tą zmianą. Naprawia problem produkcyjny, upraszcza architekturę, poprawia obserwowalność i zostawia system w stanie, w którym kolejne eksperymenty można mierzyć, a nie zgadywać.
Celowo skracamy tu szczegóły implementacyjne, ale efekt jest prosty: ten sam workflow działa teraz stabilnie także na dużych zbiorach danych.
Masz backendowy job, który timeoutuje na produkcji?
Lubimy brzydkie bottlenecki: stare biblioteki, ślepe zaułki algorytmiczne, wolne batch joby i systemy, które psują się dopiero przy skali. Jeśli to brzmi znajomo, możemy to rozebrać na części.
