Chia sẻ nhỏ của Võ Văn Hoàng Tuân
Xin chào các bạn,
Thông qua một vài sự kiện, thầy có dịp gặp được bạn Võ Văn Hoàng Tuân là một cựu thành viên của đội OLP trường mình. Hiện tại Hoàng Tuân đang là sinh viên năm cuối, tuy nhiên đã có 1 công việc cực kỳ xịn xò mà nhiều sinh viên tốt nghiệp cũng chưa dám mơ ước. Bài chia sẻ được đăng tại fanpage của nhóm, nhưng thầy reup lại lên web để mọi người tiện theo dõi và hy vọng truyền 1 chút động lực cho các bạn tiếp tục theo đuổi đam mê lập trình của mình.
Nội dung bài chia sẻ của Hoàng Tuân
Hello mọi người, anh xin giới thiệu 1 chút về anh nhé. Anh là Tuân, hiện tại đang là sinh viên năm cuối ở trường mình. Anh đang là BackEnd và DevOps cho 1 sàn giao dịch tiền điện tử lớn thứ 6 trên thế giới từ khi đầu năm 3 tới giờ đã là gần 2 năm. Anh từng là cựu thành viên của đội tuyển mình 2 năm nên anh cũng muốn quay lại chia sẽ 1 chút kiến thức nho nhỏ của mình để mở rộng phong trào học tập ở đội tuyển mình nhé.
Cách mà anh đã cùng team optimize lại Maching Engine (thuật toán khớp lệnh) để có thể handle được 50.000.000 orders/s
Matching Engine là một phần quan trọng trong hệ thống giao dịch trên thị trường tài chính. Nó có nhiệm vụ khớp các lệnh mua và bán của các nhà đầu tư để tạo ra các giao dịch. Trong bài viết này, anh sẽ hướng dẫn cách xây dựng một Matching Engine bằng cấu trúc Tree.
Cấu trúc Tree là một cấu trúc dữ liệu phổ biến trong việc lưu trữ và quản lý dữ liệu. Trong trường hợp này, anh sẽ sử dụng một cấu trúc Tree con là Binary Search Tree (BST), là một loại cấu trúc Tree trong đó các phần tử được sắp xếp theo thứ tự tăng dần hoặc giảm dần. (Mọi người có thể search trên GG về cấu trúc này nha)
BST bao gồm các nút, mỗi nút chứa một giá trị và hai nút con. Nút con bên trái chứa giá trị nhỏ hơn giá trị của nút cha, nút con bên phải chứa giá trị lớn hơn giá trị của nút cha. BST cho phép tìm kiếm, thêm và xóa các giá trị với độ phức tạp thời gian trung bình O(log n). (log n nên chạy nhanh lắm hehe)
Để xây dựng Matching Engine bằng cấu trúc Tree, anh sẽ thực hiện các bước sau:
Tạo cấu trúc dữ liệu cho Order: Order là một đối tượng chứa thông tin về giá và số lượng lệnh mua hoặc bán.
Tạo cấu trúc dữ liệu cho Node: Node là một nút trong BST, chứa một Order và hai con trỏ đến nút con bên trái và bên phải.
Tạo hàm Insert: Hàm này sẽ chèn một Order mới vào BST. Nếu BST rỗng, nó sẽ trả về một nút mới với Order này. Nếu BST không rỗng, hàm sẽ so sánh giá trị của Order với giá trị của nút hiện tại và chèn Order vào nút con bên trái hoặc bên phải.
Tạo hàm Remove: Hàm này sẽ xóa một Order khỏi BST. Nếu BST rỗng hoặc Order không tồn tại trong BST, hàm sẽ trả về BST hiện tại. Nếu Order tồn tại trong BST, hàm sẽ tìm nút chứa Order này và thay thế nó bằng nút con bên trái hoặc bên phải.
Tạo hàm Match: Hàm này sẽ khớp các lệnh mua và bán trong BST. Nếu có một Order mua hoặc bán với giá tốt nhất, hàm sẽ trả về nó và xóa nó khỏi BST.
Sử dụng các hàm trên để xây dựng hệ thống Matching Engine.
Tuy nhiên, anh cần lưu ý rằng đây chỉ là một ví dụ đơn giản và để xây dựng một hệ thống Matching Engine. Thực tế cần phải xem xét nhiều yếu tố khác như caching order book, transaction in database, load balancing, ... mới có thể chạy với con số ở trên mà anh đề cập tới.
À nhân đây là anh khuyên mọi người nên có 1 trang blog của riêng mình, để chia sẽ kinh nghiệm những gì mình đã làm, đã research được, viết bài ở trên các group công nghệ lớn. Lúc đó doanh nghiệp sẽ để ý tới các em, và sẽ cho em những cơ hội việc làm tốt, đó là cách mà anh đã được công ty hiện tại chú ý tới. Blog của anh ở đây https://medium.com/@vovanhoangtuan mọi người có thể vô xem, và anh có hay viết bài (à cũng không hay lắm, 1 năm 1 bài 😄😄) ở group lớn như J2Team.
Nhận xét