#218 - Ứng dụng Machine Learning vào bài toán định tuyến phương tiện
Trong số này, chúng ta tìm hiểu về:
Cách time series database có thể handle lượng dữ liệu lớn như thế nào.
Machine Learning và bài toán định tuyến phương tiện.
Kỹ thuật tạo Code Coupon tại eBay.
Reading in Database System.
Bài toán House Robber và lời giải bài LRU Cache.
Mời các bạn cùng đọc.
Những bài viết hay
Machine learning speeds up vehicle routing
Bài toán định tuyến phương tiện (vehicle routing) là một dạng của bài toán tối ưu tổ hợp. Một ví dụ tiêu biểu là bài toán giao hàng chặng cuối (last-mile delivery), yêu cầu vận chuyển hàng hóa từ kho trung tâm tới nhiều thành phố, đồng thời vẫn phải giữ chi phí di chuyển ở mức thấp.
Để giải dạng bài này, ta thường sử dụng các thuật toán heuristic để tìm ra những giải pháp đủ tốt. Các thuật toán được thiết kế trước đây có thể giải quyết vấn đề này cho vài trăm thành phố, nhưng chạy quá chậm ở quy mô lớn hơn. Thường ta không thể tìm được giải pháp tốt nhất để giải quyết vấn đề, đơn giản là vì có quá nhiều giải pháp tiềm năng.
Các nhà nghiên cứu tại MIT đã ứng dụng ML (Machine Learning) để giải quyết vấn đề này. Trước tiên, họ sử dụng thuật toán để chia bài toán giao hàng ra thành nhiều bài toán con, ví dụ 200 bài toán con cho định tuyến giữa 2000 thành phố. Sau đó, thay vì giải toàn bộ các bài toán con, họ làm giàu tiến trình này bằng cách sử dụng một thuật toán ML mới để nhận diện các bài toán con nào là có giá trị nhất để giải, nhằm tăng chất lượng của giải pháp trong khi sử dụng tài nguyên tính toán thấp hơn nhiều lần. Cụ thể trong bài toán định tuyến phương tiện, họ đã tăng tốc độ giải các thuật toán từ 10 đến 100 lần.
Phương pháp nêu trên, learning-to-delegate, có thể áp dụng cho nhiều bài toán tương tự, ví dụ như điều phối hoặc tìm đường đi cho robot kho vận. Phương pháp này cho phép tự động đẩy nhanh tốc độ heuristics cho những bài toán lớn, bất kể heuristics hay vấn đề là gì.
(by philong)
How databases handle 10 million devices in high-cardinality benchmarks
Trong một cơ sở dữ liệu theo dạng time series, mỗi hàng sẽ gồm các cột chứa thông tin để định danh và phân loại. Trong trường hợp của một hệ thống IoT, do số lượng thiết bị và cảm biến lớn, nên cơ sở dữ liệu thường sẽ có kích thước rất lớn. Giả sử một hệ thống có 1000 thiết bị IoT ở 20 địa điểm, các thiết bị này chạy trên 5 phiên bản firmware, và mỗi thiết bị có 5 loại cảm biến. Khi đó, số phần tử của bộ dữ liệu sẽ là 500,000 (1000 x 20 x 5 x 5). Con số này sẽ tăng theo cấp số mũ khi ta thêm thiết bị hoặc phiên bản firmware mới, điều này rất dễ dẫn tới việc mất kiểm soát về bộ dữ liệu.
Với bộ dữ liệu đa dạng về mặt thuộc tính (high-cardinality) như vậy, cơ sở dữ liệu của sẽ có tính chất sau:
1. Bảng dữ liệu sẽ cần index ở nhiều cột
2. Mỗi cột được index sẽ chứa nhiều giá trị duy nhất
Trong bài viết này, tác giả chứng minh tính hiệu quả của QuestDB bằng cách benchmark với các loại cơ sở dữ liệu dạng time series khác (như ClickHouse, influxdb hay TimescaleDB), và giải thích vì sao QuestDB có thể dễ dàng xử lý dữ liệu dạng time series với lượng dữ liệu lớn và nhiều thuộc tính.
Mời bạn đọc tìm hiểu chi tiết tại link bên dưới.
(by nhij)
The Engineering Behind Coded Coupons, eBay’s New Seller Tool
Trên sàn Ebay, làm sao để người bán hàng tự tạo coupon để chia sẻ công khai ngay trên website hoặc gửi qua các kênh tiếp thị riêng của họ, và in ra để gửi kèm theo gói hàng nhằm khuyến khích khách hàng cũ quay lại? Chỉ trong 5 tháng sau khi phát hành, Coded Coupons Tool (CCT) đã thu hút hơn một triệu khách hàng Ebay sử dụng tính năng này.
CCT được phát triển với tech-stack mới của Ebay như Raptor và NodeJS, sử dụng cơ chế ghi kép (dual-write). Hệ thống quản lý cơ sở dữ liệu quan hệ của Oracle giúp người bán (seller) linh hoạt kiểm soát việc cung cấp các mã chiết khấu và đảm bảo tính nhất quán giao dịch của người mua (buyer), còn MongoDB cluster giúp scale cho hàng tỉ lượt xem, hiển thị thông tin chiết khấu tại các vị trí chiến lược trong quá trình tìm kiếm và giao dịch của người mua.
Mảng Seller. Ebay thiết kế kiến trúc mảng Seller dựa trên nguyên lý backend-for-frontend, hay còn gọi là “Experience Services”. Hệ thống hoạt động song song giữa Java/Scala và NodeJS mang đến trải nghiệm tối ưu cho người dùng, cải thiện thời gian phản hồi và giảm tỉ lệ xảy ra lỗi. Khi buyer tạo và đặt giờ cho coupon, event sẽ được đẩy vào hệ thống BES (Business Event Stream), lưu tại cassini-db phục vụ cho các mục đích tăng trải nghiệm người mua như đánh chỉ mục cho hàng khuyến mãi khi hiển thị kết quả tìm kiếm, cập nhật dữ liệu nhất quán…
Mảng Buyer. Như đã đề cập, kiến trúc mảng Buyer sử dụng cơ chế ghi kép.
Để đáp ứng được nhu cầu scale cao, Ebay lựa chọn MongoDB cluster cho một số trang như khuyến mãi hay chi tiết khuyến mãi. Tiêu biểu nhất là trang xem mặt hàng (View Item), đạt gần 4 tỉ lượt truy cập mỗi ngày.
Với các trang Giỏ hàng và Giao dịch, yêu cầu tính nhất quán và toàn vẹn dữ liệu cao hơn thì cơ sở dữ liệu quan hệ như Oracle là lựa chọn của Ebay.
Mời bạn đọc tìm hiểu chi tiết tại link bên dưới.
(by quangle)
Góc Data
Readings in Database Systems, 5th Edition
Reading in Database system, hay còn gọi là The Redbook, là một quyển tổng hợp các bài báo kinh điển trong lĩnh vực Data Management từ năm 1988 đến nay.
Trong quyển sách này, các tác giả tổng hợp lại một vài bài báo mà theo các tác giả là quan trọng và có tầm ảnh hưởng lên các thiết kế của các hệ thống quản trị data hiện đại. Bên cạnh việc liệt kê các bài báo, các tác giả còn đưa ra những nhận định của mình giúp chúng ta có một cái nhìn tổng quan về cách những công nghệ lõi liên quan đến data đã biến đổi như thế nào theo thời gian, từ đó cũng sẽ giúp ta hiểu rõ hơn về những bài toán ở hiện tại.
Trong mỗi phiên bản mới được tái bản sau vài năm, các tác giả lại cập nhật danh sách các bài báo cũng như điều chỉnh các nhận định của mình.
Bản mới nhất của quyển sách này là quyển được tái bản lần 5, mời các bạn đọc ở link sau.
(by n^4)
Góc Lập Trình
Đề ra tuần này: House Robber III
Lời giải đề bài tuần trước: LRU Cache
LRUCache là viết tắt của Least Recently Used Cache, đây là phương pháp phổ biến nhất để cập nhật cache bằng cách loại bỏ những giá trị ít được sử dụng gần đây nhất.
Do đây là cache, vì vậy ta cần thực hiện các thao tác "get - truy xuất dữ liệu", "put - cập nhật dữ liệu", nhanh nhất có thể. Cách nhanh nhất để thực hiện những việc này là sử dụng bảng băm (HashTable hoặc HashMap).
Để đảm bảo tính chất "loại bỏ những giá trị ít được sử dụng gần đây nhất" của LRUCache, ta cần biết những giá trị nào được sử dụng gần đây nhất. Ta có thể sử dụng LinkedList với quy ước: giá trị được sử dụng cuối cùng luôn ở đầu của LinkedList. Như vậy, khi ta thêm giá trị mới vào LRUCache, giá trị mới luôn nằm ở đầu của LinkedList.
Với quy ước trên, giá trị nằm ở cuối LinkedList là giá trị ít được sử dụng gần đây nhất. Khi số lượng phần tử trong LRUCache vượt quá quy định, ta đơn giản chỉ cần xóa đi giá trị nằm ở cuối LinkedList và key tương ứng trong HashMap.
Tổng kết lại, ta có cấu trúc dữ liệu vào giải thuật như sau:
1. Ta sử dụng LinkedList để lưu trữ giá trị cache với quy ước: "giá trị được sử dụng cuối cùng luôn ở đầu của LinkedList".
2. Ta sử dụng HashMap để lưu trữ cache key và tham chiếu tới node chứa giá trị trong LinkedList.
3. Khi hàm int get(int key) được gọi, ta kiểm tra HashMap và di chuyển node tương ứng lên đầu của LinkedList.
4. Khi hàm void put(int key, int value) được gọi, ta thêm một node mới vào đầu của LinkedList, đồng thời cập nhật HashMap. Nếu số lượng phần tử vượt quá quy định, ta xoá đi giá trị nằm ở cuối LinkedList, đồng thời xóa key tương ứng trong HashMap.
Thao tác xóa node trong Singly Linked List có độ phức tạp thời gian Time Complexity là O(n), để tối ưu xuống O(1), ta có thể sử dụng Doubly Linked List.
Giải thuật được thực hiện như sau: https://pastebin.com/z5ErNZhB
Cả hàm get và put đều có độ phức tạp thời gian Time Complexity là O(1).
(by phucnh)
Code & Tools
Kubeflow: Đây là công cụ giúp triển khai machine learning trên Kubernetes một cách đơn giản và dễ dàng mở rộng.
Góc Sponsors
Là một trong những siêu ứng dụng hàng đầu ở khu vực Đông Nam Á, Grab cung cấp đa dạng dịch vụ cho hơn 187 triệu người dùng tại 428 thành phố ở tám quốc gia. Tại Grab, chúng tôi tin rằng nhân tài chính là trái tim của công ty, vì vậy chúng tôi luôn cố gắng tạo ra một môi trường tuyệt vời để tối ưu hoá tiềm năng của các Grabbers.
Những lý do bạn sẽ thích làm việc ở Grab:
Đồng nghiệp thân thiện, chuyên môn cao.
Môi trường làm việc đa quốc gia, cân bằng giữa cuộc sống và công việc (work-life balance)
Được tham gia giải quyết các bài toán khó (high scale, high traffic), với nhiều impact (vài trăm triệu người dùng)
Lương tháng 13 + lương thưởng bonus theo hiệu quả công việc.
Rất nhiều khoá học training đào tạo nội bộ cũng như đào tạo được cung cấp bởi các đối tác như Microsoft, Amazon, ..
Hiện văn phòng R&D của Grab đang tuyển nhiều vị trí như: Backend Developer, Frontend Developer, DevOps Engineer, Lead Software Engineer, ... Bạn có thể tham khảo tại Jobs - Grab Careers để biết thêm chi tiết.
Quotes
“Dynamic typing: The belief that you can’t explain to a computer why your code works, but you can keep track of it all in your head.”
— @chris__martin
Bạn đánh giá nội dung số newsletter này thế nào?
(1 = Rất tệ / 5 = Rất tốt)
(Việc đánh giá của các bạn là rất quan trọng, sẽ giúp chúng tôi liên tục cải thiện nội dung newsletter tốt hơn)