#189 - Pinterest đã mở rộng hệ thống quảng cáo bằng cách nào?

Sep 20, 2021

Grokking Newsletter là newsletter hàng tuần của Grokking cho các bạn software engineers người Việt.

Trong số này: Cách Pinterest mở rộng hệ thống quảng cáo, các thói quen giúp tăng năng suất lập trình, bài talk của Rich Hickey về cách xây dựng một hệ thống, v.v...

Những bài viết hay

How we scaled the size of Pinterest — medium.com

Vào tháng 5 năm 2020, Pinterest hợp tác với Shopify cho phép người bán upload danh mục sản phẩm lên Pinterest, tạo Product Pin và quảng cáo. Điều này làm tăng đáng kể số lượng quảng cáo (ad) trong kho cho recommendation engine. Hệ thống lúc đó mặc dù vẫn đáp ứng tốt trong vài năm, nhưng đội ngũ sớm gặp phải nhiều vấn đề khi mở rộng quy mô quảng cáo của công ty:

- Nghẽn cổ chai bộ nhớ. Pinterest lưu bộ index của ad candidate trong memory, và chia làm 9 shards vì hạn chế phần cứng. Lượng quảng cáo trong kho tăng dẫn đến kích thước index cũng tăng, kiến hệ thống bắt đầu đạt đến giới hạn. Đội ngũ có xem xét vài giải pháp ngắn hạn như thêm số lượng shards, hoặc mở rộng theo chiều dọc (vertical scaling), nhưng đều bác bỏ vì sẽ tốn thêm chi phí trong tương lai

- Áp lực lên CPU từ Garbage Collector. Go Garbage Collector (GC) được tối ưu hoá rất nhiều và cung cấp hiệu suất tốt cho hầu hết trường hợp, nhưng đối với hệ thống với tỉ lệ memory allocate cao, GC bắt đầu chiếm CPU từ chương trình chính, dẫn đến những lần tăng đột biến 10% trong CPU, ảnh hưởng đến độ trễ.

Để hỗ trợ sự tăng trưởng nhanh chóng này, đội ngũ Pinterest đã tận dụng store key-value ( KV) và tối ưu bộ nhớ trong Go để tăng trưởng kích thước kho ad lên 60 lần. Việc sử dụng store key-value cluster thay cho memory store giúp đơn giản hoá đáng kể hệ thống, nhưng đồng thời gây vấn đề mới về độ trễ và chi phí cơ sở hạ tầng. Pinterest giải quyết vấn đề này bằng xử lí song song và caching, giảm traffic tới KV store tới 94%. Trong thực tế, Pinterest đã tăng 4 lần kích thước ad index trong năm 2020 chỉ vài tháng sau khi launch hệ thống mới này, đồng thời giảm đáng kể chi phí bảo trì nhờ đơn giản hoá hệ thống. Trong bài viết, tác giả có miêu tả chi tiết hệ thống cũ, vấn đề và giải pháp tương ứng theo format khá rõ ràng dễ hiểu, mời các bạn tham khảo nhé.

5 SQL queries Data Engineer và Data Scientist nên biết

1. Sử dụng APPLY Operator

Bạn đã bao giờ thấy một chút khó khăn khi cần tìm một hay một số cụ thể những transactions cuối cùng mà một nhóm khách hàng đã thực hiện chưa? Bạn gặp khó khăn với việc cố gắng sử dụng kết hợp row_number(), top 1, cùng với GROUP và ORDER BY? Có một cách dễ dàng hơn là sử dụng APPLY Operator.

2. Recursive CTE

CTEs đệ quy (Common Table Expressions) có tác dụng riêng khi cần xử lý dữ liệu phân cấp, chẳng hạn như cấu trúc tổ chức của một công ty. CTEs đệ quy là các CTEs tự tham chiếu và chứa ít nhất hai CTE query definitions: một CTE neo (anchor) và một CTE đệ quy (recursive).

3. UNPIVOT

Đôi khi, bạn cần phải xử lý một table, có thể đã được trích xuất từ một file Excel với cấu trúc không hợp lý cho việc query. Ví dụ, thay vì Year là một cột trong bảng, thì các giá trị của chúng (2018, 2019, 2020) lại được sử dụng như các cột tương ứng. Toán tử quan hệ UNPIVOT sẽ nhanh chóng xoay các cột (2018, 2019, 2020) thành các giá trị cột và biến đổi chúng sang một dạng chuẩn hóa hơn trong SQL, giúp việc query dữ liệu dễ dàng và thuận tiện hơn.

4. INTERSECT và EXCEPT

Toán tử EXCEPT được dùng để trả về các hàng trong lệnh SELECT đầu tiên mà không trả về trong lệnh SELECT thứ hai.

Về lý thuyết, bạn có thể tạo ra cùng một tập kết quả từ EXCEPT và INTERSECT bằng cách sử dụng OUTER và INNER joins tương ứng. Nhưng nếu không có UNIQUE KEY và phép JOIN yêu cầu nhiều cột, thì việc sử dụng EXCEPT và INTERSECT sẽ đơn giản và gọn gàng hơn

5. Running Totals

Tính giá trị total tại một thời điểm cụ thể là một yêu cầu gần như không thể thiếu đối với bất kì Data Analyst nào. Việc sử dụng các window functions thực sự giúp đơn giản hóa việc đó. Window functions tương tự như GROUP BY, ngoại trừ việc thay vì chạy trên toàn bộ tập kết quả, chúng hoạt động trên một tập các hàng và trả về một giá trị tổng hợp duy nhất cho mỗi hàng.

Hãy cùng tìm hiểu gió dụ cụ thể cho mỗi queries kể trên trong bài viết của tác giả.

The Habits of Productive Developers

“Productive” trong tiếng Anh thường được hiểu một cách đơn giản là tính hiệu quả. Nhưng cụ thể hơn, nó mang 2 ý nghĩa tách biệt với nhau bao gồm hiệu suất (efficiency) và hiệu quả (effectiveness) trong công việc mà chúng ta thực hiện hàng ngày.

Hiệu suất là khả năng hoàn thành công việc nào đó với thời gian, tiền bạc, công sức,… bỏ ra ít nhất.

Hiệu quả là mức độ hoàn hảo, mức độ thành công của kết quả công việc mà chúng ta đã thực hiện.

Thông thường ta thường có xu hướng cố gắng thực hiện công việc một cách nhanh nhất có thể, tức là chú ý nhiều đến hiệu suất công việc và bỏ quả yếu tố hiệu quả trong công việc. Ngược lại nếu quá chú tâm đến hiệu quả công việc làm hiệu suất chậm đi thì giá trị công việc mang lại cũng không tốt. Nói chung, kết quả công việc sẽ là tốt nhất khi chúng ta có thể cân bằng được 2 yếu tố trên.

Trong bài viết, tác giả đã nêu lên 14 phương pháp đơn giản giúp cân bằng giữa “hiệu suất” và “hiệu quả” làm việc cho một lập trình viên. Một số phương pháp nổi bật bao gồm:

- Học cách tạo kế hoạch cụ thể. Thực hiện một số phân tích về các yêu cầu, kỳ vọng cần đáp ứng, cách bạn có thể giải quyết vấn đề,… Suy nghĩ từ nhiều góc nhìn khác nhau (khách hàng, team phát triển,…) để có thể đáp ứng một cách linh hoạt với sự thay đổi.

- Hãy tự động hóa các tác vụ thủ công. Bạn là một lập trình viên, đừng làm việc cho nó, mà hãy bắt nó làm việc cho mình.

- Không ngừng học hỏi thêm những điều mới.

"Simple Made Easy" - Rich Hickey (2011)

Trong bài talk này, Rich Hickey (Creator của ngôn ngữ Clojure và designer của database Datomic) Một trong những bài talk nổi tiếng nhất của Rich Hickey (Creator của ngôn ngữ Clojure và designer của database Datomic). Trong phần đầu, Rich phân tích sự khác biệt giữa simplicity (sự đơn giản) và ease (sự dễ dàng). Từ đó ông nhấn mạnh sự quan trọng, lợi ích của simplicity khi thiết kế và xây dựng bất kỳ một hệ thống phần mềm nào. Ở nửa sau, Rich trình bài các khái niệm, công cụ và những câu hỏi mà chúng ta có thể sử dụng để xây dựng một hệ thống đơn giản (simple system).

Góc Lập Trình

Đề ra tuần này:

Cho một array số nguyên nums, trả về độ dài của subsequence tăng dần dài nhất.

Một subsequence là một array có thể được dẫn xuất từ một array bằng cách xóa một số hoặc không có phần tử nào mà không thay đổi thứ tự của các phần tử còn lại. Ví dụ, [3,6,2,7] là một subsequence của [0,3,1,6,2,2,7].

Follow-up: giải bài trên với giải thuật có time complexity O(n log(n))

Ví dụ 1:

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation: Subsequence tăng dần dài nhất là [2,3,7,101]

Ví dụ 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Ví dụ 3:

Input: nums = [7,7,7,7,7,7,7]

Output: 1

Các bạn có thể thử sức tại đây: https://leetcode.com/problems/longest-increasing-subsequence/

Lời giải tuần trước

Đề bài

https://www.hackerrank.com/challenges/ctci-merge-sort/problem

Lời giải

Lời giải

Đề bài yêu cầu đếm số cặp nghịch đảo trong mảng, ta có thể dễ dàng giải bài này bằng việc duyệt toàn bộ các cặp trong mảng, và đếm những cặp (a[i], a[j]) thoả mãn điều kiện a[i] > a[j] với i < j. Giải thuật này có độ phức tạp time complexity là O(n^2).

Tuy nhiên, có thể nhận thấy việc duyệt và so sánh từng cặp khá tương đồng với các thuật toán sắp xếp, ta có thể tiếp cận theo hướng này để tối ưu thuật toán.

Nếu ta có 2 mảng đã được sắp xếp theo thứ tự giảm dần như sau: arr1 = [5, 3], arr2 = [4,3], ta có arr1[0] > arr2[0] (vì 5 > 4), vậy số lượng cặp đảo nghịch là arr2.length - 0 vì arr1[0] > arr2[i] với tất cả 0 <= i < arr2.length.

Dựa vào hướng tiếp cận trên, ta có thể thực hiện giải thuật merge sort như sau: https://pastebin.com/tJqvjP85

Giải thuật có độ phức tạp time complexity là O(nlogn), space complexity là O(n).

Góc Database

Entropy là một vấn đề hay gặp trong các hệ dữ liệu phân tán. Hiểu một cách nôm na thì entropy ám chỉ việc dữ liệu lưu trữ giữa các node bị mất đồng bộ và trở nên khác biệt, thường là do lỗi mạng (network partition).

Các hệ dữ liệu phân tán khác nhau sẽ có những chiến lược khác nhau để giải quyết bài toán entropy này, lớp lời giải được dùng để giải quyết sẽ được gọi là anti-entropy.

Một trong các kỹ thuật phổ biến trong nhóm lời giải cho anti-entropy là sử dụng Merkle Tree được sử dụng ở Cassandra. Gần đây, một kỹ thuật mới đang được sử dụng nhiều là delta-state-CRDT (Delta State Conflict-Free Replicated Data Types).

Để hiểu thêm về delta-state CRDT, góc DB tuần này mời các bạn cùng xem bài thuyết trình vào năm ngoái của Sailesh Mukil, software engineer làm việc ở Netflix. Trong bài thuyết trình này Sailesh sẽ giới thiệu về Dynomite, một hệ dữ liệu phân tán được phát triển bởi Netflix ban đầu hướng đến xây dựng lớp cache cho Cassandra, nhưng dần dần đã trở thành phương án thay thế Cassandra cho một số lớp bài toán. Một trong các điểm nổi bật của Dynamite đó là sử dụng delta-state-CRDT để giải quyết bài toán entropy.

Mời các bạn cùng tham khảo video bài thuyết trình ở đây.

Code & Tools

https://buck.build/

Đính chính

Trong số tuần trước, do có một sai sót trong quá trình biên tập, nên đường link trong bài viết "Góc Database" không chính xác.

Chúng tôi xin gửi lại tới bạn đọc đường dẫn chính xác như sau: https://15445.courses.cs.cmu.edu/fall2020/slides/17-twophaselocking.pdf

BTT Grokking Newsletter xin cáo lỗi cùng bạn đọc.

Góc Sponsors

Database documentation tự động với dbdocs.io

[Nội dung tài trợ] dbdocs.io là một công cụ giúp các bạn Dev có thể tự sinh ra nguyên trang document về cấu trúc database của mình chỉ bằng vài dòng lệnh command-line. Nó giúp quá trình planning và design database trong team dev dễ dàng hơn.

Hiện team dbdocs (ở TPHCM) đang tìm thêm 2 bạn fullstack/backend engineers để tham gia phát triển sản phẩm dev tool này. Bạn nào quan tâm có thể xem thêm tại: https://careers.holistics.io/job-openings/open-source-full-stack-engineer

(Team dbdocs cũng là team xây dựng công cụ dbdiagram.io phổ biến mà nhiều bạn dev đang dùng.)

Quotes

“Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.”

— Stan Kelly-Bootle