View profile

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

Grokking Vietnam
Grokking Vietnam
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
Góc Distributed System
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
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ó.
“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:
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 leftPrefixProductrightPrefixProduct, cách thực hiện giải thuật như sau: https://pastebin.com/19QL32g0
Tech Talks
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
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Viet Nam