#200 - Tìm hiểu về Postgres GIN Index

Dec 07, 2021

Trong số này, chúng ta sẽ cùng tìm hiểu về:

WIDeText: một framework Deep Learning của Airbnb
Cách JIT tăng hiệu suất của Java như thế nào?
Cách Facebook xây dựng hệ thống Zoncolan
Read-after-write inconsistency và cách phòng tránh
Tìm hiểu về Postgres GIN Index
Lời giải bài toán Product of Array Except Self
Sự kiện Grokking Techtalk #43 về Payment Gateway Demystified

Những bài viết hay

WIDeText: A Multimodal Deep Learning Framework

WIDeText là một framework Deep Learning đa thể thức dựa trên PyTorch, được xây dựng bởi Airbnb để giúp việc phát triển và chế tạo các hệ thống phân loại trở nên dễ dàng hơn.

Thông thường đặc tính trong các hệ thống phân loại rơi vào một vài loại và ứng với nó là các kiến trúc mô hình tối ưu cho từng loại. Ví dụ:

Image Channel: gồm ảnh listing, ảnh tiện ích, ... có MobileNet, ResNet.
Text Channel: gồm chú thích của ảnh, nhận xét, mô tả, ... có mô hình NLP như CNN, LSTM, Transformers
Dense Channel: gồm các đặc tính phân loại, số học như các loại tiện ích trong một ngôi nhà, điểm chất lượng của ảnh, thông tin về vị trí, ... có GBDT
Wide Channel: gồm các embedding có sẵn được tạo ra bởi một mô hình nào đó từ trước và có thể được tận dụng trực tiếp để làm trình phân loại có tính quyết định

Cái tên WIDeText thực chất bắt nguồn từ việc ghép của các loại channel trên: Wide, Image, Deep, Text.

Khái niệm cốt lõi ở đây là "model fusion". Họ muốn tận dụng nhiều kiến trúc mô hình state-of-the-art cho nhiều loại feature khác nhau và ghép các embeddings để tăng hiệu năng của classifier cuối cùng. Tức là sẽ xây dựng dựng mô hình bằng cách kết hợp nhiều khối - ngưởi dùng có thể dễ dàng cắm thêm các channel vào hoặc rút bớt ra, điều chỉnh kiến trúc của chúng tùy theo mục tiêu.

WIDeText giúp tăng tốc độ phát triển mô hình và giảm thời gian triển khai từ hàng tuần xuống hàng ngày. Việc có framework end-to-end cho cả quá trình huấn luyện và triển khai giúp người dựng mô hình tận dụng được nhiều đặc tính thô nhất có thể, khiến việc debug mô hình trở nên dễ dàng hơn.

Mời các bạn đọc bài viết gốc để có thêm thông tin chi tiết về framework này cũng như ví dụ về việc ứng dụng nó khi phát triển Room Type Classification cho các bức ảnh được đăng trên Airbnb.

How the JIT compiler boosts Java performance in OpenJDK

Trình biên dịch Just-in-time (JIT) là yếu tố chính giúp chương trình đạt hiệu suất cao trong Java Virtual Machine (JVM). Bài viết này giới thiệu đến bạn về biên dịch JIT trong HotSpot, JVM của OpenJDK.

Về mặt cơ bản, kỹ thuật biên dịch sử dụng trong các trình biên dịch JIT giống với kỹ thuật mà các trình biên dịch GNU (GCC) sử dụng. Sự khác biệt cơ bản là JIT chạy cùng một tiến trình với ứng dụng và sử dụng chung tài nguyên với chính ứng dụng đó, điều này cũng có nghĩa là nó đi kèm với một sự đánh đổi về mặt hiệu năng.

Trong thực tế, mô hình thực thi của JVM trong HotSpot có thể được tổng hợp như sau:

Bytecode khi được thực thi thông dịch sẽ có độ trễ bằng không.
Những phương thức được thực thi thường xuyên sẽ được phát hiện và được biên dịch sang mã máy.
Sau khi bytecode đã được biên dịch, quá trình thực thi sẽ chuyển sang thực thi bằng mã đó.

Cụ thể, trình thông dịch sẽ đếm số lần một phương thức được gọi. Nếu tần suất thực thi vượt qua một ngưỡng cố định, nó sẽ xếp phương thức vào một hàng đợi để chờ được biên dịch. Trình biên dịch chạy ở một luồng song song với luồng thực thi mã Java sẽ xử lý yêu cầu biên dịch trên. Trong khi quá trình biên dịch đang diễn ra, quá trình thực thi thông dịch vẫn tiếp tục. Khi mã đã biên dịch xong, trình thông dịch sẽ chuyển sang thực thi bằng mã máy.

Vì vậy, sự đánh đổi ở đây chính là sự cân bằng giữa việc thực thi thông dịch có đặc điểm bắt đầu nhanh/thực thi chậm và thực thi bằng mã máy đã biên dịch có đặc điểm ngược lại, bắt đầu chậm/thực thi nhanh.

Sau khi đọc bài viết, bạn sẽ có cái nhìn tổng quan về mô hình thực thi đa lớp của HotSpot và cách nó cân bằng các tài nguyên được yêu cầu bởi các ứng dụng Java. Tác giả cũng đưa ra 2 ví dụ chứng minh cách trình biên dịch JIT sử dụng các kỹ thuật nâng cao — khử tối ưu hóa (deoptimization) và suy đoán (speculation) — để tăng hiệu suất ứng dụng.

Zoncolan: How Facebook uses static analysis to detect and prevent security issues

Tất cả các phần mềm đều không thể tránh khỏi được những lỗ hổng bảo mật dù ít hay nhiều. Đặc biệt là với những dự án hay công ty lớn khi mà codebase của họ lớn đến nổi mà các kỹ sư an ninh không thể kiểm tra hết được. Ở bài viết sau đây, các đội ngũ kỹ sư ở Facebook nói về cách họ đã xây dựng hệ thống Zoncolan như thế nào để có thể phát hiện và ngăn ngừa các lỗ hổng an ninh cho hơn 100 triệu dòng code Hack (PHP của Facebook).

Để xây dựng được Zoncolan một cách hiệu quả, các đội ngũ kỹ sư ở Facebook đã dùng static analysis để theo dõi cách các functions được biểu hiện và kết nối với nhau như thế nào. Từ đó, họ có thể tạo ra control-flow graph và call graph để mà có thể truy vấn từ một điểm nhất định khi một biến hoặc dữ liệu được đi vô của một function cho tới điểm cuối cùng mà biến đó hoặc dữ liệu đó được sử dụng. Từ các thông tin này, các kỹ sư an ninh có thể tạo các rules để giảm thiểu các lỗ hổng an ninh ở codebase hiện tại ở Facebook.

Góc Distributed System

Read-after-write inconsistency và cách phòng tránh

Vấn đề chính của read-after-write là: khi client thực hiện write vào một cụm replicas, hệ thống cần 1 khoảng thời gian để replicate dữ liệu. Nếu ngay sau đó client thực hiện read, có khả năng là read dữ liệu cũ.

Read-after-write consistency là một hình thái của eventually consistency, nhưng điều ngược lại không đúng. Điểm khác biệt nằm ở chỗ:

eventually consistency là chấp nhận delay cho các client đọc dữ liệu mới được ghi bởi một client X.
read-after-write consistency khắt khe hơn một chút: đảm bảo client X phải đọc được ngay lập tức dữ liệu mà nó vừa ghi. Còn những client khác thì vẫn có delay theo eventually consistency.

Read-after-write consistency rất phổ biến. Ví dụ: khi user thực hiện update ảnh avatar trên social network, user đó cần phải thấy sự thay đổi ngay lập tức. Tuy nhiên những user khác có thể chỉ thấy sự thay đổi sau một khoảng delay.

Cách phòng tránh

Nguyên nhân chính của read-after-write inconsistency là do client thực hiện read và write trên hai datasource khác nhau. Có nhiều cách để phòng tránh vấn đề này:

Write synchronously: khi dữ liệu được ghi vào write replica, dữ liệu đó sẽ ngay lập tức được replicate sang các node khác. Write chỉ được thông báo là thành công cho client khi quá trình replication diễn ra thành công. Cách này sẽ làm chậm quá trình ghi, và có khả năng lỗi khi một trong các node replicas bị fail.
Write asynchronously: kĩ thuật thường sử dụng là user-pinning (hay sticky routing). Client sẽ được chỉ định luôn read và write vào cùng một replica. Trạng thái mapping này có thể được lưu ở một datastore khác.
Lazy lookup: Áp dụng đối với hệ thống có read-only replicas (có node chỉ write và có node chỉ read). Khi đó, user-pinning không có tác dụng vì mọi client đều write vào một chỗ và read ở một chỗ khác. Lazy lookup (hay Backup read) được áp dụng, khi đó client read vào replica không có dữ liệu, nó sẽ thực hiện lệnh read tiếp theo thẳng vào write replica. Tuy nhiên cách này cần có cơ chế phát hiện outdated data, và write replica có thể bị quá tải.

Bạn có nghĩ ra cách nào tối ưu hơn cả để giải quyết vấn đề read-after-write không? Góc DS kì sau sẽ giải đáp.

Góc Database

Understanding Postgres GIN Indexes: The Good and the Bad

Thêm, điều chỉnh hay xóa index là một phần quan trọng trong công việc phát triển các ứng dụng sử dụng database. Đối với các kiểu dữ liệu phức tạp trên Postgres như JSONB, array types, full text search, một index B-Tree đơn giản sẽ không hoạt động tốt bằng GIN index.

GIN index đã được thêm vào Postgres từ phiên bản 8.2 cách đây ... 15 năm và trở thành một công cụ vô cùng quan trọng tới ngày nay. GIN index có thể giúp ta lập chỉ mục (index) với những thứ mà một B-Tree thông thường không thể như JSONB hoặc full text search. Tuy nhiên GIN index cũng có thể gây ra những tác dụng phụ nếu sử dụng không đúng cách.

Trong bài viết này, chúng ta sẽ cùng đi sâu vào tìm hiểu GIN index trong Postgres, cách xây dựng, và cũng tham khảo thêm từ nhiều bài viết khác đã được viết trong nhiều năm qua bởi cộng đồng.

Chúng ta sẽ bắt đầu từ việc xem xét GIN index có thể làm gì, cấu trúc của chúng, và những tính huống hay được sử dụng thông thường. Sau đó ta sẽ xem xét một tình huống thực tế tới từ Gitlab, liên quan tới GIN index trên một table với hơn 1000 update mỗi phút. Và cuối cùng, ta sẽ xem xét sự cân bằng giữa chi phí dành cho GIN và hiệu suất của nó.

Vậy GIN Index là gì?

“The GIN index type was designed to deal with data types that are subdividable and you want to search for individual component values (array elements, lexemes in a text document, etc)” - Tom Lane

GIN index ban đầu được tạo ra bởi Teodor Sigaev và Oleg Bartunov, được phát hành lần đầu tiên trong Postgres 8.2, vào ngày 5 tháng 12 năm 2006 - gần 15 năm trước. Kể từ đó, GIN đã có nhiều cải tiến, nhưng cấu trúc cơ bản vẫn tương tự.

GIN là viết tắt của cụm từ "Generalized Inverted Index". Từ "Inverted" ở đây liên quan tới cấu trúc của index, là cách xây dựng một table-encompassing tree, mà trong đó một single row có thể được biểu diễn ở nhiều vị trí trong cây. Điều này trái ngược với B-Tree, một index entry sẽ trỏ đến một row cụ thể.

Một bài viết khác giải thích về GIN index bởi Oleg Bartunov và Alexander Korotkov tại PGConf 2012 tại Prague. Trong bài này, họ đã mô tả GIN index như là một mục lục trong cuốn sách. Trong đó, con trỏ chính là số trang!

Nhiều entry có thể được kết hợp lại cho một kết quả như ví dụ sau đây:

Tuy nhiên GIN index có những nhược điểm, đó là chi phí khi update là khá lớn. Chính cấu trúc đặc biệt của GIN index, nhiều index entry cho một single row, dẫn tới chi phí update index là rất lớn.

Mặc định thì cơ chế fastupdate được bật sẽ trì hoãn việc cập nhật GIN index. Nó sẽ gom việc update các index lại vào cùng 1 thời điểm. Dữ liệu bị hoãn lại sẽ nằm trong một danh sách chờ xử lý (pending list), sau đó sẽ được đẩy vào main index khi đạt 1 trong 3 điều kiện sau:

gin_pending_list_limit đạt giới hạn 4MB
Có lệnh gọi tới hàm gin_clean_pending_list
Autovacuum trên table (pending list sẽ được clear vào cuối quá trình vacuum)

Đây là một hoạt động khá tốn kém, dẫn tới việc một câu lệnh UPDATE / INSERT thứ N có thể đột nhiên chậm hơn rất nhiều (gin_pending_list_limit đạt ngưỡng). Tình huống này đã xảy ra tại Gitlab gần đây, các bạn có thể đọc thêm tại đây

Các bạn có thể đọc thêm tại bài viết gốc để tìm hiểu xem các team Gitlab đã giải quyết bài toán này như thế nào nhé. GIN index là một công cụ rất mạnh, nhưng cũng đi kèm với những hạn chế. Chúng ta cần sử dụng GIN index một cách hiệu quả và cẩn thận, đặc biệt là trên các table có tần suất ghi dữ liệu lớn.

Góc Lập Trình

Đề tuần này: Number of Closed Islands

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

Đề bài: Product of Array Except Self

Lời giải

Lời giải đầu tiên cho bài này là sử dụng 2 vòng lặp lồng nhau. Tại mỗi phần tử i ta có thể dễ dàng tính tích không bao gồm nums[i] bằng một vòng lặp. Độ phức tạp time complexity là O(n^2)

Để tối ưu time complexity, ta cần có quan sát sau: kết quả tại vị trí i là tích của left prefix product và right prefix product của mảng đầu vào dịch đi 1 phần tử. Mời bạn đọc tham khảo ví dụ sau:

nums = [1, 2, 3, 4]

Với bảng trên, ta dễ dàng tính được ans[i] = leftPrefixProduct[i] * rightPrefixProduct[i]

Trên thực tế, ta không cần thiết phải tạo thêm 2 mảng leftPrefixProduct và rightPrefixProduct, cách thực hiện giải thuật như sau: https://pastebin.com/19QL32g0

Tech Talks

Grokking Techtalk #43: Payment Gateway Demystified

Đối với các hệ thống thương mại điện tử, việc tích hợp với một cổng thanh toán trực tuyến (payment gateway) sẽ là yêu cầu cơ bản nhất, dịch vụ thanh toán này ngoài việc cần phải chính xác, chúng còn phải mang lại trải nghiệm tốt cho người sử dụng, xử lý được những sự cố có thể xảy ra trong quá trình thực hiện và đặc biệt là phải bảo mật. Đây là một bài toán khó về mặt kỹ thuật để có thể thiết kế và xây dựng một cách hiệu quả!

Trong Techtalk #43 này, các bạn tham gia sẽ được chia sẻ về những thành phần của một payment gateway, quá trình xử lý một transaction, cách thức lưu trữ thông tin thanh toán, xử lý hoàn tiền,.. và những vấn đề gặp phải khác khi xây dựng một cổng thanh toán trực tuyến. Chủ đề sẽ đi qua các nội dung sau:

Payment Domain Knowledge
Payment Gateway Integration: Create Order, Check Order Amount (Optional), Browser Redirect, Instant Payment Notification (IPN), Payment Query (QueryDR)
Advance Concept: Tokenization, Credit Card Authorization / Reversal / Settle

Thông tin sự kiện:

Thời gian: 09:00 - 11:00 Thứ 7, 11/12/2021
Địa điểm: Online qua Zoom & Livestream on Youtube Grokking Vietnam
Link đăng ký: https://forms.gle/CGsrm491iHTWVfhM8

Code & Tools

Góc Sponsors

ENGINEERING RECRUITMENT FROM GRAB

Grab is Southeast Asia’s leading superapp, providing everyday services such as mobility, deliveries (food, packages, groceries), mobile payment and financial services to millions of Southeast Asians. At Grab, we believe that talent is the heart of the company. Therefore, we strive to create a wonderful working environment to optimize the potential of our Grabbers to achieve our common mission: drive Southeast Asia forward by creating economic empowerment for everyone.

Why you will love working at Grab:

MacBook and 24-inches-monitor are provided.
Attractive salary and performance bonus.
Extra Medical Insurance from 1st joined date.
14 days Annual leaves + 5 days of other leaves
GrabFlex allowance (up to 4.500.000 VND per month) for Family’s vacation, Education, Gym, Learning, etc…
GrabLove as vouchers for using Grab’s services.
Relocation opportunities to Regional or other countries.
Online Learning System & Offline Training courses are provided.
Opportunity to work, learn & grow with world-class professional engineers.
Opportunity to work for South East Asian Tech Decacorn.
Working day: Monday - Friday.

Join our Squad team today to drive Southeast Asia forward!

Check out our open positions at https://grab.careers/jobs/

Apply directly to ta.vn@grab.com as: Full Name_Applied position_Grokking

Quotes

I wanted to minimize my frustration during programming, so I want to minimize my effort in programming. That was my primary goal in designing Ruby. I want to have fun in programming myself.

—Yukihiro Matsumoto (Matz), creator of Ruby