Kako je Stackoverflow pao zbog lošeg regularnog izraza (i vratio se za samo pola sata)

Stackoverflow je juče pao, doduše, na samo pola sata.

Glavni razlog je taj što zbog zlonamernog posta, jedan od regularnih izraza je postao veoma zahtevan i počeo da jede većinu procesorske moći CPU-a na serverima. Da stvar bude gora, taj post je bio na naslovnoj, pa se regularni izraz pozivao non-stop. Verovatno mislite, ko još otvara homepage Stackoverflowa? Pa, oni su koristili homepage za healthcheck na loadbalanacerima. Pa su onda loadbalanceri lepo izbacili ceo sajt iz rotacije, jer je healtcheck trajao predugo. I ta-da, ceo Stack Overflow (ceo Stack Exchange) je pao!

Kako se ovo desilo? Na svakom postu, oni koriste regularni izraz

^[\s\u200c]+|[\s\u200c]+$

koji bi trebalo da ukloni sve unikod space-ove sa početka i kraja posta. Jednostavno zar ne?

Prostija verzija problematičnog dela Regex-a je “\s+$”, tj. svi space-ovi sa kraja stringa. Iako je ovo veoma čitljivo za programere, Regex radi na malo drugačiji način. On će pohlepno krenuti da čita karakter po karakter od početka posta. Učita jedan, vidi da li je ispunjava “\s”, ako da,nastavlja da čita space-ove. Međutim, ako naleti na neki drugi karakter sem space-a, Regex je nevalidan i mora da krene is početka.

Ovo ne zvuči kao veliki problem, kad je npr. rečenica u pitanju. Međutim, post koji im je pravio problem je imao 20000 razmaka. Što znači, Regex učita 20000 znakova, skonta da poslednji karakter nije space, pa vrati se na početak i pokuša da proveri 19999 karaktera. I ovo padne, pa se on vrati na početak da pokuša dalje. I tako u nedogled. Znači on je morao da proveri da li je karaker koji čita space 20000 + 19999 + 19998 + .. + 2 + 1 = 199 999 000 puta. Što nije mali broj operacije i traje. Složenost nije O(e) nego O(n²) što je bilo više nego dovoljno.

Kao hotfix, zamenili su regex sa substring metodom. I tako rešili problem. Posle ovoga, dodate su mere predostrožnosti:

• Proveriti ostale regex-e da li imaju slične probleme
• Dodata je mogućnost da loadbalance-ri isključe healtcheck (jer bi verovatno ostatak sajta radio)
• I napravljena je lista “šta raditi u vandredim situacijama”

Ono što je potpuno fascinantno je da im je trebalo 10 minuta da vide razlog, 14 minuta da poprave kod i 10 minuta da deploy-uju novu verziju softvera. Koliko ustvari znači dobro postavljen Continuous Deployment, kao i naravno inžinjeri koji su bili OnCall.