#243 - BehindTheBug, When Indexing Gone Wrong
News
WhatsApp data breach sees nearly 500 million user records up for sale — www.techradar.com
Thông tin người dùng của WhatsApp bị rò rỉ và rao bán.
Những bài viết hay
#BehindTheBug — Indexing Gone Wrong
(by quangle)
Series #BehindTheBug được đội ngũ kỹ sư tại Swiggy Bytes tổng hợp lại những issues trong quá trình phát triển sản phẩm mà họ gặp phải. Trong bài biết này, họ sẽ cùng thảo luận về vấn đề đánh index (idx) database chưa hiệu quả gây ra những ảnh hưởng không tốt đến hoạt động của hệ thống Swiggy Instamart và cách khắc phục.
Issue đã xảy ra ở picker-service, một service phục vụ cho nhóm pickers (những bạn đóng gói sau khi nhận được đơn đặt hàng từ users), sau khi triển khai API mới giúp tính toán hiệu suất làm việc của các bạn. API thực hiện truy vấn dữ liệu làm việc trong vòng 30 ngày của mỗi bạn picker từ database master (relational DB). Đội ngũ kỹ sư cũng đã tính toán trước việc truy xuất dữ liệu sẽ gặp nhiều thách thức khi số lượng records trả về có thể lên đến vài triệu. Vì vậy, để tối ưu thời gian tìm kiếm, họ đã áp dụng kỹ thuật đánh composite-index (comp-idx) trên 2 cột lần lượt là picked_timestamp (1) và picker_identifier (2).
Sau khi triển khai lên production, họ nhận được alert liên quan đến độ trễ Kafka consumer từ order topic do có sử dụng chung resource của database picker master trên. Quá trình investigate bắt đầu, nhóm nhận thấy tỷ lệ sử dụng CPU hit gần 90% (bình thường rate sẽ khoảng 20 - 30%) và chỉ số IOPS Read tăng gần chạm ngưỡng 8000 (max config: 10.000).
Việc debug được tiếp tục cho đến khi họ phát hiện comp-idx đã bị sai thứ tự, cột picked_timestamp được đánh ưu tiên do có tỉ lệ cardinality cao hơn nhưng thứ tự nên đánh idx phải là (picker_identifier, picked_timestamp) thay vì (picked_timestamp, picker_indentifier) như hiện tại. Lý do ở đây chính là khi đánh comp-idx trong câu query có điều kiện (=) và các điều kiện (>, <, >=, <=, IN), thì cột chứa điều kiện (=) nên được đặt đầu tiên và các điều kiện còn lại sẽ theo sau. Việc chọn cột có chứa điều kiện bất đẳng thức lên trước trong cụm idx làm cho optimizer của DB thực hiện các đánh giá trước khi quyết định chọn tìm kiếm bằng idx hoặc tồn tại những giá trị mà optimizer buộc phải chọn hướng scan toàn bộ bảng. Để tìm hiểu kỹ hơn kỹ thuật đánh index này cũng như kết quả của việc cải thiện, mời bạn đọc cùng tham khảo chi tiết bài viết
How we deploy to production over 100 times a day
(by nhij)
Lập trình viên có thể nhanh chóng nhận được phản hồi của người dùng và kiểm chứng xem liệu ý tưởng của họ có hoạt động hiệu quả hay không nếu họ có thể triển khai nhanh chóng các tính năng mới hay bản vá lỗi lên môi trường production. Trong bài viết này, đội ngũ kỹ sư của Monzo đã chia sẻ cách họ tối ưu toàn diện từ văn hóa, công cụ tới kiến trúc hệ thống để có thể triển khai lên production hơn 100 lần/ngày một cách an toàn.
Cloudflare servers don't own IPs anymore – so how do they connect to the Internet?
Trong blog này, tác giả sẽ sẽ thảo luận về cách quản lý các địa chỉ IP Cloudflare được sử dụng để truy xuất dữ liệu từ Internet, cách thiết kế mạng đầu ra đã phát triển như thế nào, cách tối ưu hóa nó để sử dụng tốt nhất không gian IP có sẵn và giới thiệu công nghệ soft-anycast.
A Primer on Distributed Systems Observability
Trong vài năm qua, mức độ phức tạp của kiến trúc hệ thống đã tăng lên đáng kể, đặc biệt là trong các kiến trúc phân tán, dựa trên microservices. Trong hầu hết các trường hợp, việc gỡ lỗi và xem log là cực kỳ khó và không hiệu quả, đặc biệt khi chúng ta có hàng trăm hoặc thậm chí hàng nghìn microservices. Trong bài viết này, tác giả sẽ giới thiệu observability và monitoring systems là gì, cũng như các pattern quan trọng trong observability.
Góc Lập Trình
Đề ra tuần này: Lowest Common Ancestor of a Binary Tree II
(by ndaadn)
Cho trước một cây nhị phân với nút gốc root, trả về nút tổ tiên chung gần nhất (Lowest Common Ancestor - LCA) của hai nút p và q bất kì. Nếu một trong hai nút p hoặc q không tồn tại trong cây, trả về null. Tất cả các giá trị của các nút trong cây là duy nhất.
Ví dụ:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Lời giải tuần trước: Two City Scheduling
(by ndaadn)
Cách giải đơn giản nhất cho bài toán tìm tổng chi phí ít nhất với một điều kiện cho trước là cài đặt giải thuật đệ quy tìm tất cả các cách lựa chọn, sau đó trả về giá trị chi phí nhỏ nhất.
Đối với bài toán trên ta có thể cài đặt giải thuật đệ quy như sau:
Giải thích:
Gọi i là tổng số người được gửi đến thành phố A
Gọi j là tổng số người được gửi đến thành phố B.
Ở mỗi bước đệ quy, ta có thể chọn gửi người thứ (i + j) đến thành phố A hoặc B. Vì đề bài ràng buộc số người được gửi đến thành phố A và B phải bằng nhau, ta mặc định chọn thành phố còn lại khi đã chọn đủ một nửa số người đến một thành phố.
Ứng với mỗi vị trí, ta đều có 2 cách chọn, tuy nhiên ta chỉ phải thực hiện lựa chọn với một nửa số ứng viên, vậy nên độ phức tạp giải thuật trên là O(2^n) với n là một nửa số ứng viên.
Áp dụng kỹ thuật memoization ta có thể tối ưu lời giải thành lời giải quy hoạch động top down và giảm độ phức tạp xuống còn O(n^2) như sau:
Bài toán còn có một cách giải bằng giải thuật tham lam như sau.
Giả sử ta chọn gửi tất cả mọi người đến thành phố A. Gọi tổng chi phí lúc này là cost.
Gọi refund(i) là chi phí ta có thể được hoàn trả khi chọn gửi người thứ i đến thành phố B. Lúc này refund(i) = cost(i)[0] - cost[i][1]
Dễ dàng nhận ra nếu sắp xếp lại mảng refund và chọn n giá trị đầu tiên của mảng refund, ta có thể nhận được số tiền được hoàn trả lớn nhất, từ đó tính được tổng chi phí ít nhất.
Độ phức tạp thuật toán chính là độ phức tạp của bước sắp xếp O((2n)log(2n)).
Code & Tools
Dozzle - một ứng dụng nhỏ gọn cung cấp giao diện trực quan giúp bạn có thể theo dõi log từ Docker một cách dễ dàng ngay trên trình duyệt web. Ngoài ra, công cụ còn hỗ trợ bạn tải file log về máy local của một hoặc nhiều cụm containers đang hoạt động trên Docker.
Feedback
Bạn đánh giá nội dung số newsletter này thế nào?
(1 = Rất tệ / 5 = Rất tốt)
(Việc đánh giá của các bạn là rất quan trọng, sẽ giúp chúng tôi liên tục cải thiện nội dung newsletter tốt hơn)
Grokking mang lại cho các bạn những kiến thức mới mẻ và hữu ích thông qua:
Tech Talk: Là một hoạt động thường xuyên của Grokking từ những ngày đầu thành lập. Tại đây các diễn giả chia sẻ kiến thức xoay quanh Computer Science và Software Engineer. Các buổi Tech Talk đều được record và upload lên kênh youtube của Grokking.
Grokking Knowledge Graph: Tập hợp những nguồn kiến thức phong phú với hơn 1000 bài viết chọn lọc, các đầu sách, khóa học, v.v… Các bài viết đều được gán nhãn để giúp bạn đọc dễ dàng tìm kiếm.
Webinar: Là chương trình kết nối các kỹ sư Việt Nam và các kỹ sư đang làm việc tại các công ty công nghệ hàng đầu thế giới.
Dijkstra: Một ấn phẩm được xuất bản bởi các thành viên của Grokking. Với những bài viết đào sâu vào kỹ thuật và kiến thức khoa học máy tính.
Kipalog: Nền tảng chia sẻ kiến thức dành cho các lập trình viên.
Newsletter: Những bài viết hay về công nghệ sẽ được gửi tới bạn hàng tuần qua email.
Xin hẹn gặp lại các bạn vào tuần sau.
Quotes
“Sufficiently advanced abstractions are indistinguishable from obfuscation.”
— @raganwald