przemuh.dev

Kr贸tka historia o optymalizacji

11/8/2020

Jaki艣 czas temu na Twitterze zamie艣ci艂em zrzut ekranu pokazuj膮cy flame-chart z narz臋dzia Profiler. Pracowa艂em wtedy nad popraw膮 wydajno艣ci aplikacji, kt贸r膮 rozwijamy w Egnyte. Pewna funkcjonalno艣膰, dla du偶ej ilo艣ci danych, zajmowa艂a strasznie du偶o czasu - 3,5 minuty! Przez ten czas w aplikacji pokazywany by艂 "kr臋cio艂ek", a u偶ytkownik nie wiedzia艂, czy co艣 si臋 dzieje, czy mo偶e co艣 si臋 zawiesi艂o. Po kilku dniach pracy z Profilerem uda艂o mi si臋 zaimplementowa膰 poprawki, kt贸re zredukowa艂y czas potrzebny do oblicze艅 z 3,5 minuty do 35 sekund. W tym wpisie chcia艂bym opisa膰 jak do tego doszed艂em.

Opis funkcjonalno艣ci

Zacznijmy od opisu funkcjonalno艣ci, kt贸ra kr贸tko m贸wi膮c kula艂a pod wzgl臋dem wydajno艣ci. Jednym z g艂贸wnych widok贸w w naszej apce jest tzw. "Sensitive Content". Pokazujemy tu list臋 folder贸w z plikami, kt贸re zawieraj膮 wra偶liwe dane. To mog膮 by膰 numery kart kredytowych, dane medyczne, personalne i nie tylko. Dane te mog膮 podchodzi膰 pod jedn膮 z kilkunastu wbudowanych polityk np. HIPA, GDPR, ale r贸wnie偶 dajemy mo偶liwo艣膰 u偶ytkownikom zdefiniowana w艂asnej polityki np. w oparciu o utworzony wcze艣niej s艂ownik. Pocz膮tkowo widok "Sensitive Content" pokazywa艂 tylko p艂ask膮 list臋 folder贸w. W zesz艂ym roku nasz Product Owner wraz z zespo艂em UX doszli do wniosku, 偶e praca z p艂ask膮 list膮 folder贸w mo偶e by膰 nieefektywna. Zamiast tego du偶o lepszym, i w zasadzie bardziej naturalnym sposobem reprezentacji danych, b臋dzie drzewko folder贸w.

Widok Sensitive Content List
Widok Sensitive Content List

Algorytm budowania drzewa

Podej艣膰 do drzewek by艂o ju偶 u nas w projekcie kilka. G艂贸wnie opiera艂y si臋 one na w艂asno艣ci folderu jakim by艂o unikalne folderId. Niestety, w przypadku "Sensitive Content" nie mogli艣my tego u偶y膰, poniewa偶 nie wszystkie foldery mog艂y zawiera膰 wra偶liwe dane, a tylko dla takich folder贸w dostawali艣my folderId.

/Shared/A/B/

W tym wypadku mamy 3 foldery (Shared, A, B), z czego tylko dla B dostajemy folderId

Takich lokacji z SC (Sensitive Content) mo偶e by膰 multum. Problem wydajno艣ci pojawia艂 si臋 ju偶 przy 250 tysi膮cach lokacji. A 偶e nie jest to wyj膮tek utwierdzi艂 nas klient, u kt贸rego znale藕li艣my prawie milion folder贸w. To w艂a艣nie dla 1M element贸w listy, czas budowania drzewka wynosi艂 3,5 minuty. Dlatego te偶, moje zadanie polega艂o na tym, 偶e drzewko dla 1M element贸w ma si臋 budowa膰 w mniej ni偶 60s.

Wracaj膮c do algorytmu. Prosty - jak budowa cepa - tak by si臋 wydawa艂o :)

  1. We藕 ca艂膮 艣cie偶k臋 i podziel j膮 na fragmenty wg. separatora np. /
  2. Ka偶dy folder wsad藕 do dw贸ch struktur: "drzewiastej" i "p艂askiej"
  3. Je艣li folder nie ma folderId traktuj go jako meta-folder

Dla uproszczenia pomijam kwesti臋 tego, 偶e wspieramy r贸偶ne 藕r贸d艂a danych i te separatory mog膮 si臋 mocno r贸偶ni膰 :) Co wi臋cej, jak si臋 p贸藕niej okaza艂o, niekt贸re 藕r贸d艂a danych mog膮 mie膰 dwa foldery o tej samej nazwie, na tym samym poziomie zagnie偶d偶enia 馃槺. I jak je rozr贸偶ni膰? Pomin臋 te偶 kwesti臋 tego, 偶e wynikowe drzewo mieli艣my przedstawi膰 w formie "sparse-tree". W skr贸cie - chodzi o to, 偶e je艣li folder zawiera tylko jeden sub-folder, to 艣cie偶ka rodzica powinna by膰 zwini臋ta/scalona.

Lista:

/Shared/A/B/C
/Shared/A/B/D

-->
Drzewo:

/Shared/A/B
    /C
    /D

Pierwsza, a w zasadzie druga implementacja

Jak ju偶 wspomnia艂em wcze艣niej, nie by艂o to pierwsze drzewo, jakie mieli艣my wy艣wietli膰 w aplikacji. W zupe艂nie innym widoku, te偶 mieli艣my zrobi膰 sparse-tree i nie chcieli艣my mie膰 kilku r贸偶nych implementacji. Dlatego napisali艣my prosty modu艂 do budowania i zarz膮dzania drzewkiem. Oparty zosta艂 o dwa ma艂e komponenty:

  • funkcj臋 buildTree, kt贸ra przyjmowa艂a p艂ask膮 tablic臋 w臋z艂贸w i miejsce (艣cie偶k臋 w drzewie) od kt贸rego mia艂a te w臋z艂y wstawia膰
  • "plasterek" (slice) z redux-toolkit, kt贸ry zarz膮dza艂 struktur膮 drzewa (rozwijanie, zwijanie w臋z艂贸w itp.)

Ca艂e drzewo, a w zasadzie te dwie struktury "drzewiasta" i "p艂aska", trzymane by艂y w reduxie w nast臋puj膮cy spos贸b:

{
    tree: {
        path: "", // root
        children: {
            "Shared": { // path-part or folder name as a key
                path: "/Shared",
                children: {
                    "A": {
                        path: "/Shared/A",
                        children: {}
                    }
                }
            }
        }
    },

    paths: {
        "/Shared": {
            meta: true,
            ...nodeProps
        }
        "/Shared/A": {
            meta: false,
            folderId: "some-unique-id",
            ...nodeProps
        }
    }
}

Tak膮 struktur臋 otrzymujemy z pomocniczej funkcji buildTree.

Dzi臋ki zastosowaniu redux-toolkit, a co za tym idzie biblioteki immer, mogli艣my w bardzo prosty spos贸b wykonywa膰 operacje na drzewie:

const initialTreeState = {
  initialized: false,
  tree: {
    path: "",
    children: {},
  },
  paths: {},
}

export const createTreeSlice = treeName =>
  createSlice({
    name: treeName,
    initialState: initialTreeState,
    reducers: {
      insertTree: ({ tree, paths }, { payload }) => {
        paths = {
          ...paths,
          ...payload.paths,
        }
        const node = getNodeByPath(payload.parentPath || "", tree)
        node.children = payload.tree.children
      },

      toggleNode: ({ tree }, { payload: path }) => {
        const node = getNodeByPath(path, tree)
        node.expanded = !node.expanded
      },
    },
  })

Pomocnicza funkcja getNodeByPath s艂u偶y do wyszukiwania w臋z艂a po 艣cie偶ce. Potrafi te偶 wyszuka膰 w臋ze艂 w sparse-tree.

Pierwsze podej艣cia do optymalizacji i pierwsze b艂臋dy

No i wszystko pi臋knie-艂adnie, ale przyszed艂 klient, 1 milion folder贸w i jebs... Product Owner zak艂ada Epic w Jirze pt. "Support 1M folders on SC tree view". Szybka burza m贸zg贸w i od razu kosz pe艂en pomys艂贸w:

  • a mo偶e by tak budowa膰 drzewo w locie, jak parsujemy JSONa?
  • a mo偶e by tak budowa膰 drzewo w web-workerze, przynajmniej nie zablokujemy g艂贸wnego w膮tku na 3,5 minuty?
  • a mo偶e by tak, pizgn膮膰 to wszystko i wyjecha膰 w Bieszczady? 鉀 馃悜

A mo偶e by tak...

Pierwszy b艂膮d - nikt nawet nie odpali艂 Profilera, 偶eby zobaczy膰 co zajmuje tyle czasu. Ka偶dy za艂o偶y艂, 偶e obecna implementacja drzewka wymiata i lepiej by膰 nie mo偶e. Sam Profiler na pierwszy rzut oka nie jest prostym narz臋dziem i mo偶e to by艂o powodem tego, 偶e rzucili艣my si臋 wtedy na tego typu pomys艂y jak budowanie drzewa "w locie" czy przeniesienie tego do web-workera. Warto te偶 podkre艣li膰, 偶e sam Epic w Jirze powsta艂 ju偶 jaki艣 czas temu, a do samej implementacji usiad艂em w po艂owie pa藕dziernika.

Pewnie zastanawiacie si臋 - ale jak to w locie? Przecie偶 jak idzie request to dopiero jak przyjdzie odpowied藕 to przegl膮darka parsuje JSONa i daje odpowied藕. Tak, ale...w tym przypadku nasi backendowcy te偶 musieli podzia艂a膰 troch臋 w kwestii optymalizacji i zamiast zwraca膰 pe艂ne dane to zacz臋li t臋 nasz膮 list臋 SC zwraca膰 na zasadzie stream'u. Dzi臋ki temu mogli艣my np. wykorzysta膰 bibliotek臋 oboe.js to parsowania JSONa w locie.

Oczywi艣cie spr贸bowa艂em tego podej艣cia, no bo w ko艅cu kto艣 to wpisa艂 do zadania w Jirze, trzeba by艂o sprawdzi膰 co nie? 馃槣 Fajnie, JSON parsowa艂 si臋 "w locie", ale stream zamiast 10s trwa艂 30s, a jeszcze nie zacz膮艂em nawet budowa膰 drzewa. Dlatego odpu艣ci艂em i postanowi艂em poszuka膰 gdzie indziej.

Web-worker

Podej艣cie z web-workerem te偶 przetestowa艂em. Ale tu napotka艂em zupe艂nie inny problem. Ok - mog臋 sobie pobra膰 1M element贸w i zbudowa膰 na tej podstawie drzewo, ale musz臋 je p贸藕niej przes艂a膰 z w膮tku web-workera do w膮tku g艂贸wnego. Struktura drzewa jest do艣膰 obszerna, razem z danymi, kt贸re zapisywali艣my w tej p艂askiej strukturze paths. Je艣li chcemy przes艂a膰 tak du偶e dane z jednego w膮tku do drugiego, przegl膮darka musi te dane zserializowa膰, przes艂a膰, a nast臋pnie ponownie sparsowa膰. To te偶 powodowa艂o "zamro偶enie" przegl膮darki na czas przesy艂ania z jednego miejsca pami臋ci do drugiego. Oczywi艣cie s膮 sposoby na przes艂anie "bezpo艣rednie" (bez kopiowania) poprzez tzw. Transferable Objects np. ArrayBuffer, ale uzna艂em, 偶e na chwil臋 obecn膮 to mo偶e by膰 gra nie warta 艣wieczki i postanowi艂em sprawdzi膰, czy faktycznie ta nasza implementacja drzewka by艂a tak zajebista jak my艣leli艣my 馃槣

Profiler podej艣cie pierwsze

Usiad艂em przed ekranem komputera, odpali艂em dev-toolsy i wcisn膮艂em przycisk "record" w Profilerze. Po chwili dosta艂em taki kolorowy wykresik, kt贸ry przypomnia艂 mi czasy defregmentatora dysk贸w z Windowsa 98 馃ぃ

Flame graph
Flame graph

Pierwsze co rzuci艂o mi si臋 w oczy to ten fioletowy kolor, kt贸ry zanurkowa艂 bardzo, bardzo g艂臋boko. Po bli偶szym spojrzeniu okaza艂o si臋, 偶e bardzo du偶o tych fioletowych element贸w to sprawka immer.js. Szybki rzut oka w dokumentacj臋 i boom! strza艂 w dziesi膮tk臋. Okazuje si臋, 偶e przy "wk艂adaniu" du偶ej ilo艣ci danych poprzez immer mo偶emy przyspieszy膰 ten proces poprzez Object.freeze tutaj wi臋cej info. Zabieg ten pozwoli艂 mi na zej艣cie z 12,54s na 11,24s dla 54K element贸w. Dla 1M skok by艂 oczywi艣cie proporcjonalnie wi臋kszy. No ale to nadal nie by艂o to...

Od profilera, do 藕r贸de艂

Wiedzieli艣cie, 偶e jak klikniecie na dany blok w Profilerze, a nast臋pnie przeniesiecie si臋 do pliku, to dostaniecie czasy dla poszczeg贸lnych blok贸w kodu? Nie!? 馃槑 To teraz ju偶 wiecie ;)

Czasy przed optymalizacj膮 dla buildTree
Czasy przed optymalizacj膮 dla buildTree

To co si臋 rzuca w oczy to 229ms dla zbudowania prostego ci膮gu znak贸w 馃く jakim jest aktualna 艣cie偶ka. Okaza艂o si臋, 偶e to zwyk艂e niedopatrzenie mo偶na by艂o zast膮pi膰 kr贸tszym kawa艂kiem kodu, kt贸ry koniec ko艅c贸w zajmuje 1.7ms.

Czasy po optymalizacji dla buildTree
Czasy po optymalizacji dla buildTree

Pomy艣licie - (ironicznie) wow... 227ms... "brawo Ty" 馃憦. Czym jest 227ms? Je艣li spojrzymy na to jako pojedyncz膮 warto艣膰 - to fakt...mikro-optymalizacja. Ale pami臋tajcie, 偶e celem by艂o obs艂u偶enie 1M element贸w, a operacja sklejania 艣cie偶ki dotyczy艂a ka偶dego sub-folderu.

M贸j spread operator AKA Object.assign taki pi臋kny

Jak zrobi膰 p艂ytk膮 kopi臋 obiektu, b膮d藕 rozszerzy膰 inny obiekt - nic prostszego - spread operator .... Je艣li musicie wspiera膰 przegl膮darki takie jak IE11, to pewnie korzystacie z babel.js - tak jak my...no i taki spread operator, koniec ko艅c贸w jest t艂umaczony na Object.assign (w wielkim uproszczeniu).

Object.assign jest stosunkowo wolny i przy wi臋kszej skali mo偶e sprawia膰 problem. W tym przypadku postawi艂em na zwyk艂e kopiowanie per klucz. Dzi臋ki temu prostemu zabiegowi zbi艂em 154ms do 44ms. I znowu, dla pojedynczych element贸w to nie ma absolutnie 偶adnego znaczenia, ale kiedy iterujemy po du偶ym zbiorze danych takie optymalizacje mog膮 zdzia艂a膰 cuda.

Dan Abramov o Object.assign
Dan Abramov o Object.assign

Agregacja warto艣ci

Po "podkr臋ceniu" immera i wyrzuceniu kliku Object.assign, b膮d藕 przepisaniu ich na prost膮 p臋tl臋, sko艅czy艂y mi si臋 pomys艂y na "proste" optymalizacje. Trzeba by艂o podkr臋ci膰 sam spos贸b budowania drzewa.

Poprzednia implementacja, dzieli艂a sobie SC lokacje wg. 藕r贸d艂a i dla ka偶dego z nich budowa艂a pod-drzewo. Dla ka偶dego pod-drzewa liczone by艂y zagregowane warto艣ci (np. je艣li folder sam w sobie zawiera艂 10 SC, ale mia艂 dodatkowo 50 sub-folder贸w, chcieli艣my pokaza膰 zsumowane warto艣ci). Dla ka偶dego takiego pod-drzewa, wykonywane by艂y sumowania, a nast臋pnie w臋ze艂 藕r贸d艂a by艂 aktualizowany wg. zsumowanych warto艣ci dla wszystkich folder贸w.

Ka偶da taka operacja wrzuca艂a co艣 do stanu w redux'ie. Pomy艣la艂em - a na co to komu? A komu to potrzebne? Przecie偶 nie pokazujemy drzewa dop贸ki wszystko nie jest policzone i zaktualizowane. Dlatego, zmieni艂em kod tak, aby najpierw zbudowa膰 w pami臋ci ca艂e drzewo wraz z policzonymi zagregowanymi warto艣ciami, a nast臋pnie za pomoc膮 jednej operacji, wsadzi膰 zbudowane drzewo do reduxa.

Co wi臋cej - w wymaganiach drzewka, by艂o napisane, 偶e pewne w臋z艂y mia艂y by膰 domy艣lnie rozwini臋te np. pierwszy poziom + potencjalnie wcze艣niej zaznaczony element na li艣cie (z listy do drzewka mo偶na przej艣膰 za pomoc膮 prostego przycisku). Wcze艣niej operacje rozwijania by艂y wyzwalane za pomoc膮 akcji toggleNode. To te偶 zmieni艂em - zamiast odpala膰 reduxow膮 akcj臋, po prostu zmieniam warto艣膰 expanded na true bezpo艣rednio w obiekcie w臋z艂a.

Mo偶na zapyta膰 - co Ci to da艂o drogi Panie?

Dla 54K element贸w zjecha艂em z czasu 12,25s na 2,4s 馃殌

艁ogie艅 w szopie :) Product Owner ca艂y w skowronkach.

Wow

Testy dla 1M

Poprosi艂em backendowc贸w, 偶eby przygotowali mi 艣rodowisko do test贸w dla 1M element贸w. Chcia艂em sprawdzi膰 czy moje optymalizacje dla 54K znajd膮 uzasadnienie. No i u艣miech nie uciek艂 z mej twarzy :)

Przed optymalizacj膮 czas budowania drzewa wynosi艂 ~3,5 minuty. Po zaaplikowaniu wy偶ej wymienionych zmian uda艂o si臋 zjecha膰 do 59s.

Mniej wi臋cej ~70% oszcz臋dno艣ci. W sumie mo偶na by powiedzie膰 - job done - mia艂o si臋 budowa膰 w mniej ni偶 60s... 59 to mniej ni偶 60 馃槄 Jest git...

Troch臋 by艂em ju偶 zm臋czony tym grzebaniem w de-facto w nie swoim kodzie...ale kumpel z zespo艂u s艂usznie stwierdzi艂:

No fajnie, fajnie, ale dla mnie nadal to jest wolno.

Doda艂 te偶 potem, 偶e nic mi nie ujmuje i wg. niego wykona艂em kawa艂 dobrej roboty...ale trudno by艂o si臋 z nim nie zgodzi膰. Od momentu klikni臋cia w element nawigacji, do czasu wy艣wietlenia widoku, u偶ytkownik musia艂 poczeka膰 艂膮cznie 90s:

  • 25s pobieranie danych (streaming)
  • 6s przegl膮darka parsuje JSONa
  • 59s budowanie drzewa

Jako u偶ytkownik, gdybym przez 90s widzia艂 tylko spinner ("kr臋cio艂ek") to by mnie szlag trafi艂 :) Nie chc臋 my艣le膰, co czuli nasi u偶ytkownicy jak musieli czeka膰 3,5 minuty...pewnie 偶aden nie wytrzyma艂 馃槄

...no...ale wracaj膮c...kumpel m贸wi: "wolno"...no to ja od razu: "co!? wolno!? ja Ci poka偶臋!" 馃ぃ

Generowanie ID

Znowu zanurkowa艂em w Profiler. Dla meta-folder贸w generowny by艂 folderId. By艂o to spowodowane tym, 偶e inne miejsce w kodzie tego id potrzebowa艂o (mniejsza o to). Koniec ko艅c贸w to generowane id nic nie znaczy艂o (nigdy nie by艂o wysy艂ane do backendu). Kto艣 jednak wymy艣li艂, 偶e to meta-folder-id ma by膰 haszem ze 艣cie偶ki...

export const createUniqueIdForLocation = path => btoa(encodeURIComponent(path))

Funkcja btoa koduje ci膮g znak贸w jako base64. Sama w sobie trwa 艣rednio 0,25ms...czyli u艂amek milisekund. Ale gdy mocniej si臋 zastanowimy - a na co komu ten hasz? a na co komu to potrzebne?

Ale po co?

No w艂a艣nie! Je艣li meta-folder-id to tylko base64 ze 艣cie偶ki, kt贸ra de facto zawiera艂a te偶 w sobie id 藕r贸d艂a, wi臋c by艂a unikatowa wzgl臋dem ca艂ej listy, to po co to w og贸le ten ca艂y hash?

-            id: createUniqueIdForLocation(path),
+            id: path,
             name: getLocationName(path),

Ten jeden diff sprawi艂, 偶e dla 1M element贸w zszed艂em z 59s na 35s, co da艂o ~40% zysku 馃く

Czyli teraz klient nie czeka艂 ju偶 90s a 66s - 艂膮cznie z pobieraniem i parsowaniem danych! Bior膮c pod uwag臋, 偶e wymagania m贸wi艂y o budowaniu drzewka w czasie mniejszym ni偶 60s, to chyba Product Owner oraz klienci powinni by膰 zadowoleni 馃槄

Dalsze kroki

Oczywi艣cie nie spoczywamy na laurach. Blokowanie u偶ytkownika na 60s nadal jest kiepskim pomys艂em, dlatego dalej my艣limy o ulepszeniu implementacji. By膰 mo偶e wyrzucimy to w ko艅cu do web-workera. Kto wie? Mo偶e uda mi si臋 dzi臋ki temu zebra膰 materia艂 na nast臋pnego posta 馃槈.

Podsumowanie

Lekcja pierwsza - zamiast gdyba膰 i sypa膰 pomys艂ami z kapelusza o web-workerach, lepiej odpali膰 Profiler.

Lekcja druga - je艣li operujesz w du偶ej skali, iterujesz po du偶ym zbiorze danych, to optymalizacje na poziomie ms dla jednej iteracji potrafi膮 czyni膰 cuda 馃殌

Lekcja trzecia - do reduxa wrzucaj dopiero wtedy, kiedy jeste艣 got贸w 馃挭

Lekcja czwarta - je艣li nie ma potrzeby, to nie komplikuj sytuacji 馃槈 (patrz ID & btoa).

Mam nadziej臋, 偶e dzi臋ki tej historii si臋gniecie wcze艣niej do Profilera i uda si臋 Wam poprawi膰 wydajno艣膰 nie jednej aplikacji.