#202 - Những điều học được ở vị trí Software Architect

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

Tendermint thuộc dòng consensus Practical Byzantine Fault Tolerance (PBFT) hoạt động hiệu quả trong hệ thống tính tới lỗi Byzantine, được sử dụng phổ biến trong các mạng lưới blockchain. Đặc điểm của PBFT nói chung và Tendermint nói riêng là việc đồng thuận xảy ra dựa vào quá trình trao đổi các bản tin giữa các node được chia làm 3 phase chính: Propose - Vote - Commit. Điều kiện tiên quyết để đạt được đồng thuận là 2/3 tổng số node cùng đồng ý với giá trị đề xuất. Tendermint thực hiện việc đồng thuận theo từng vòng, ở mỗi vòng các node phải trải qua 3 giai đoạn kể trên. Ứng với mỗi giai đoạn, mỗi node sẽ phải đợi nhận đủ 2/3 số bản tin của giai đoạn đó hoặc là đạt thời gian timeout trước khi chuyển sang giai đoạn tiếp theo. Cũng như các thuật toán đồng thuận khác, các tính chất của Tendermint cũng bao gồm:

Để hiểu rõ hơn cơ chế hoạt động của Tendermint, mời bạn xem bài viết gốc: https://arxiv.org/pdf/1807.04938.pdf

Ở chuyên mục Góc Database kỳ trước, chúng ta đã được biết đến HyperLogLog, thuật toán giúp ước tính được số lượng phần tử duy nhất trong một tập hợp lên đến vài trăm triệu phần tử mà chỉ cần một lượng bộ nhớ rất nhỏ.

HyperLogLog có một đặc tính khá đặc biệt đó là có thể dùng để ước tính kết quả hợp (union) của hai tập hợp một cách dễ dàng. Ví dụ như bạn có hai tập hợp A và tập hợp B lần lượt được biểu diễn bởi hai bộ thanh ghi (registers) Ra và Rb được xây dựng dựa theo HyperLogLog, bằng cách kết hợp hai bộ thanh ghi Ra và Rb với nhau thành một bộ thanh ghi mới Rab, bạn có thể dùng để ước tính được A hợp B (A union B).

Tuy nhiên, để ước tính kết quả A giao B (A intersect B) thì HyperLogLog lại không phù hợp. Đến với góc Database kỳ này, mời bạn cùng tìm hiểu về kỹ thuật MinHash, một kỹ thuật giúp ước tính được “độ tương đồng” (similarity) của hai tập hợp. 

MinHash sẽ dựa trên một chỉ số gọi là chỉ số Jaccard (Jaccard index, hay còn gọi là Jaccard similarity coefficient). Chỉ số Jaccard của hai tập hợp A và B sẽ được tính như sau:

Theo định nghĩa này thì J(A,B) sẽ nằm trong khoảng từ 0 đến 1 (0<=J<=1). Khi hai tập A và B giống hoàn toàn với nhau thì J=1, còn khi hai tập A và B khác hoàn toàn nhau thì J=0.

Bằng cách chỉ lưu trữ k phần tử nhỏ nhất của hai tập hợp A và B, thuật toán MinHash sẽ giúp chúng ta tính được chỉ số Jaccard của hai tập hợp, từ đó sẽ ước tính được kích thước của phép giao giữa hai tập A và B.

Kết hợp HyperLogLog và MinHash, chúng ta sẽ có được một phương pháp đầy đủ hơn giúp ước tính được kích thước của các tập hợp cùng kết quả các phép toán hợp (union), giao (intersect) của hai tập hợp, từ đó có thể ứng dụng cho các bài toán như ước tính lưu lượng, ước tính tập hợp người dùng cho quảng cáo, …

Mời các bạn cùng xem clip này để hiểu thêm về MinHash.

Đề tuần này: Making A Large Island

Đề bài: Maximal Square

Đề bài yêu cầu tìm diện tích của ma trận vuông lớn nhất chỉ chứa số “1”. Cách đầu tiên ta có thể thử là tại mỗi ô “1”, ta mở rộng độ dài của của cạnh lên 1 đơn vị và kiểm tra xem ma trận vuông mới có chứa toàn số “1” hay không? Cách thực hiện có thể mô tả như sau:

1. Duyệt toàn bộ các ô, nếu ô chứa số “1”, ta thực hiện bước 2

2. Tăng độ dài của cạnh lên 1 đơn vị và tiến hành kiểm tra

 a. Nếu ma trận vuông mới chứa toàn số “1”, ta cập nhật diện tích lớn nhất và tiếp tục bước 2 để tìm kiếm ma trận vuông lớn hơn.

 b. Nếu ma trận vuông mới có chứa số “0”, ta di chuyển sang ô tiếp theo, lặp lại từ bước 1

Giải thuật trên có độ phức tạp time complexity là O(m^2 * n^2), với m, n là số dòng, cột của ma trận đầu vào.

Để tối ưu time complexity của bài toán này, trước hết ta cần một quan sát như sau:

Để dễ hiểu, mời bạn đọc xem công thức sau:

Gọi L(i, j) là độ dài của ma trận vuông lớn nhất tại ô [i][j], L[i][j] được tính bằng:

Với công thức đệ quy như trên ta có thể dễ dàng giải bài toán này theo quy hoạch động (Dynamic Programming) như sau: https://pastebin.com/LPGizKUd

Độ phức tạp time complexity, space complexity của giải thuật là O(m*n).

Ta hoàn toàn có thể tối ưu space complexity của giải thuật xuống O(m) (hoặc O(n)), mời bạn đọc thử thực hiện.

One Mount là tập đoàn kiến tạo hệ sinh thái công nghệ lớn nhất Việt Nam, cung cấp các giải pháp và dịch vụ xuyên suốt chuỗi giá trị, từ lĩnh vực dịch vụ tài chính, phân phối, bất động sản và bán lẻ, với ba sản phẩm chủ lực: VinShop, VinID, OneHousing.

Với trụ sở tại Hà Nội, Hồ Chí Minh và quy tụ hơn 1.500 nhân sự xuất sắc, One Mount tâm huyết xây dựng môi trường làm việc:

Các vị trí hấp dẫn đang mở tuyển: 

Tham khảo các thông tin về văn hóa, môi trường làm việc, cơ hội nghề nghiệp tại One Mount: