Optimizing Go: From 3k req/s/core to 480k req/s/core

Transcript

1. Optimization 3k req/s/core to 480k req/s/core
2. DDoS
3. Layers
4. User Agents 537 Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; FREE; .NET CLR 1.1.4322) 272 Mozilla/4.0 (compatible; MSIE 6.0; MSIE 5.5; Windows NT 4.0) Opera 7.0 [en] 269 Mozilla/4.0 (compatible; MSIE 6.0; MSIE 5.5; Windows NT 5.0) Opera 7.02 Bork-edition [en] 264 Opera/8.00 (Windows NT 5.1; U; en) 264 Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; KKman2.0) 261 Mozilla/4.0 (compatible; MSIE 5.5; Windows NT 5.0; .NET CLR 1.1.4322) 258 Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; SV1; .NET CLR 2.0.50727) 255 Mozilla/4.0 (compatible; MSIE 5.0; Windows NT; DigExt) 253 Opera/7.60 (Windows NT 5.2; U) [en] (IBM EVV/3.0/EAK01AG9/LE) 251 Opera/7.54 (Windows NT 5.1; U) [pl] 251 Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.2; WOW64; SV1; .NET CLR 2.0.50727) 251 Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.0; T312461) 248 Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.2; Win64; AMD64) 247 Mozilla/4.0 (compatible; MSIE 5.5; Windows NT 4.0) 243 Mozilla/4.0 (compatible; MSIE 5.5; Windows NT 5.0)
5. Referer 172 http://pvppw.ru/ 166 text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,*/*;q=0.5 164 az-us 162 zh, en-us; q=0.8, en; q=0.6 161 http://zhyk.ru/ 160 en-en,en;q=0.8,en-us;q=0.5,en;q=0.3 157 http://www.niagarastar.ru/ 152 az-ua 150 http://kremlin.ru/ 150 application/xml, image/png, text/html 149 text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8 149 http://premier.gov.ru/ 148 text/x-dvi; q=.8; mxb=100000; mxt=5.0, text/x-c 147 text/html, */* 147 en-us,en;q=0.5
6. Architecture
7. Architecture
8. Architecture
9. Manageable λ • Reduce the set of clients that you coordinate the state of, say top k
10. Algorithms • Space Saving algorithm (https://icmi.cs.ucsb.edu/ research/tech_reports/reports/2005-23.pdf) • An implementation in Go (https://github.com/ cloudflare/golibs)
11. Perfect!
12. Benchmark Test • func BenchmarkFoo(b *testing.B) • b.N • http://dave.cheney.net/2013/06/30/how-to-write- benchmarks-in-go
13. Slow! (3k req/s/core)
14. Benchmark CPU Profile • go test -bench=. -cpuprofile=cpu.out
16. Virtual CPU
17. Real CPU Profile • Copying memory is expensive • Copy pointers instead
18. Keeping Elements Sorted • Array worst case: O(n) • Priority queue: O(log n)
19. O(n), O(log n)
20. First Pass Optimization • Reduce the size of memory needed to be copied • Reduce the number of times copying is needed
21. 75k req/s/core
22. Wrong Output!
23. Correctness • Processing rate was approaching workable • But the rate estimation was grossly inaccurate
24. The Distribution 0 2.5 5 7.5 10 A F B O U C D E G H I J K L M N P Q R S T Requests
25. Lesson • Read the paper properly • Streaming algorithms tend to output estimates • Know in what scenarios they fail
26. Naïve Approach • Use a map for counting • There is no second bullet
27. Find Top k • Quicksort: O(n log n) • Quickselect: O(n)
28. O(n log n), O(n)
29. Reduce Data Set • Prune the map of ultra low values • Use sort from standard library
30. 120k req/s/core
31. Test In Production
32. More Like
33. Test In Production • Run in dark mode (no side effects) • Needs to be faster to keep up with attacks during peak load
34. Hello perf top
35. Garbage • String manipulation produces garbage • Cannot use slices as keys in maps, use arrays
36. 480k req/s/core
38. Takeaway • Start simple • Benchmark • Profile • Verify correctness • Back-of-the-envelope calculations are helpful
39. Future Work • This was put into production • Later, we switched to using lock-free algorithms where possible to reduce the load on CPU
40. We Are Hiring
41. –Abraham Lincoln “Join CloudFlare.”
42. –Me “Special thanks to Albert Strasheim and Stephan Lachowsky.”
43. The End • Ashish Gandhi • @ashishgandhi_ • a@a10i.org • Easy questions?