Vấn đề thực tế: thuật toán tìm và tra cứu cơ sở dữ liệu

[jefflieu]

Post bài này cho mọi người nói nhảm chơi.
Ngày xửa ngày xưa, trong một công ty nọ, người ta làm ra cái máy để thống kê các luồng IP (Internet Protocol) lưu thông trong hệ thống mạng.
Một luồng được xác định như sau:
Địa chỉ IP nguồn (32-bit) + Địa chỉ IP đích (32-bit), Cổng nguồn, cổng đích ở lớp giao tiếp TCP/UDP ... tổng cộng là 96-bit cho một luồng. Đó là chuẩn IP phiên bản 4 (IPv4) Chuẩn IP phiên bản 6 (IPv6), một luồng có thể cần (288 bit) để xác định. Tạm gọi thông tin này là ID (Identification).

Các thông số thống kê của luồng (chẳng hạn như băng thông (bandwidth) mà luồng này chiếm) sẽ được lưu trữ trong 1 cơ sở dữ liệu (database). Như vậy để update thông số của một luồng, người ta sẽ dùng ID như một khóa (key) để truy xuất thông tin cũ và cập nhật thông tin mới của luồng.

Thống kê cho thấy, quá trình tìm kiếm mất khá nhiều thời gian và chiếm khá nhiều CPU (cần kiếm khoảng 1000 luồng trở lên).

Công ty đó bèn tìm cách dùng FPGA để tìm và quản lý cơ sở dữ liệu ở dưới embedded-card thay vì ở trên CPU. Trong mạng internet, tốc độ 1Gigabit, mỗi frame (khoảng 1500Bytes) được truyền trong khoảng 13 microsecond. Như vậy FPGA phải tìm cho ra frame này thuộc luồng nào trong 13us.

Đó vấn đề là vậy. Anh em nói nhảm về phương án làm cho dzui .

[qmk]

Bạn tìm thử giải pháp ntop. Nó dùng PC thường capture được luồng 1G.
Mình nghĩ tốc độ PC bây giờ khả năng xử lý cực cao chỉ cần tối ưu code là việc này khả thi.

Dùng FPGA thứ nhất phải thực hiện Link Layer, sau đó nhận packet lưu lên RAM, và thực hiện tìm kiếm thực sự mà nói thì không biết có nhanh hơn là viết trên PC hay không vì bandwidth giữa RAM và FPGA không thể so với bandwidth giữa RAM và CPU của các máy bây giờ. Mình nghĩ một giải pháp ở tầng driver của PC tốt hơn.

[qmk]

Mình nhớ giải pháp mình làm khi thực hiện fragment/defragment là mình tính một cái 1st index khoảng 32 bit thôi. Ví dụ như tổng của IP dst, scr và UDP port chẳng hạn. Bạn làm cái so sánh này nếu có nhiều hơn 1 kết quả mới so sánh chi tiết.
Như vậy một phép for (i = 0; i < 1000; i++) if (inx_value == idx[i]) {làm gì đó;} chắc chỉ chạy cỡ nano giây trên máy i5 hiện tại.
Nhớ viết multithread để share tải giữa các CPU với nhau.
Nếu bạn chỉ thống kê bạn cũng chẳng cần nhận đủ gói làm gì lấy vài header đầu là đủ rồi.
Thường cổng 1G chẳng bao giờ full tải

[jefflieu]

Mình nhớ giải pháp mình làm khi thực hiện fragment/defragment là mình tính một cái 1st index khoảng 32 bit thôi. Ví dụ như tổng của IP dst, scr và UDP port chẳng hạn. Bạn làm cái so sánh này nếu có nhiều hơn 1 kết quả mới so sánh chi tiết.
Như vậy một phép for (i = 0; i < 1000; i++) if (inx_value == idx[i]) {làm gì đó;} chắc chỉ chạy cỡ nano giây trên máy i5 hiện tại.

Uhm, có lý. Để mô phỏng bằng software thử.

Nhớ viết multithread để share tải giữa các CPU với nhau.

Thật ra, FPGA được nghĩ tới không phải để giải quyết vấn đề này. Đúng hơn, câu hỏi là có nên đem việc này từ CPU xuống FPGA hay không. FPGA luôn có sẵn để thực hiện các việc khác. Nói cách khác là có FPGA rồi, chỉ là có nên đem việc này xuống thực hiện ở FPGA ko.

Thường cổng 1G chẳng bao giờ full tải

Cái này không chắc, không 100% full nhưng chắc cũng cỡ đó. Ứng dụng này dùng trong hệ thống IPTV (Internet protocol TV), không phải mạng ở nhà. Trong mạng này, cần sử dụng tối đa băng thông.

[jefflieu]

Bạn tìm thử giải pháp ntop. Nó dùng PC thường capture được luồng 1G.
Mình nghĩ tốc độ PC bây giờ khả năng xử lý cực cao chỉ cần tối ưu code là việc này khả thi.

Dùng FPGA thứ nhất phải thực hiện Link Layer, sau đó nhận packet lưu lên RAM, và thực hiện tìm kiếm thực sự mà nói thì không biết có nhanh hơn là viết trên PC hay không vì bandwidth giữa RAM và FPGA không thể so với bandwidth giữa RAM và CPU của các máy bây giờ. Mình nghĩ một giải pháp ở tầng driver của PC tốt hơn.

Vấn đề không phải PC làm không nổi mà là:
- CPU xử lý rất nhiều thứ khác (decode mấy cái stream trong IP packets)
- FPGA thì luôn cần đề xử lý các việc khác trong hệ thống.
Câu hỏi đúng là: Có nên làm việc này ở Hardware ko?

[qmk]

Bạn có thể tính toán sơ năng lực hệ thống bằng cách stress test từng thuật toán xem "ăn" bao nhiêu CPU.

Bạn có thể gán một số process chỉ chạy ở vài CPU khác nhau trong hệ thống nhiều core (4 chẳng hạn), số còn lại để làm những cái khác.

[jefflieu]

Bạn có thể tính toán sơ năng lực hệ thống bằng cách stress test từng thuật toán xem "ăn" bao nhiêu CPU.

Bạn có thể gán một số process chỉ chạy ở vài CPU khác nhau trong hệ thống nhiều core (4 chẳng hạn), số còn lại để làm những cái khác.

Yup...search binary thì mất khoảng 20% CPU cho 300 streams.

[tonyvandinh]

Yup...search binary thì mất khoảng 20% CPU cho 300 streams.

Hồi xưa tôi có làm về "network security concentrator" thì việc tìm kiếm "source" hoặc "destination" address cần phải dùng "CAM" (Content Address Memory). Kết quả trúng hay sai chỉ trong một chu kỳ (1 clock). Dùng CPU cho networking applications thì không có hiệu nghiệm cho lắm. Dùng FPGA và CAM có hiệu quả hơn nhiều.

[jefflieu]

Hồi xưa tôi có làm về "network security concentrator" thì việc tìm kiếm "source" hoặc "destination" address cần phải dùng "CAM" (Content Address Memory). Kết quả trúng hay sai chỉ trong một chu kỳ (1 clock). Dùng CPU cho networking applications thì không có hiệu nghiệm cho lắm. Dùng FPGA và CAM có hiệu quả hơn nhiều.

Diễn đàn buồn quá, móc cái thread này lên chơi. Như đã nói ở trên, Jeff đã làm mẫu thử (prototype) và kết quả là việc tra cho 300 Luồng chiếm khoảng 20-30% của CPU (Duo Core, 2.6GHz, 64-bit system).
Sếp lớn ngồi trên muốn sản phẩm nhỏ gọn (Cỡ bằng 2 cuốn băng từ thời xưa), thế nên việc tra và lọc các gói IP được thực hiện trên FPGA. Nhưng dùng CAM thì không hiệu quả vì dữ liệu vào (key) lớn quá (khoảng 40 bytes) và số lượng các mục (entries) dự kiến thì quá nhiều (10000) ...
Nên đành phải theo một hướng giải quyết khác ... dùng FPGA tra dữ liệu ghi trong Static RAM. Việc này vừa tiết kiệm hơn RAM mà vừa nhanh hơn PC.

Tóm tắt thuật toán tìm/truy xuất:
- Cho mỗi kết nối giữa máy server và client, có nhiều gói IP được trao đổi. Nhưng địa chỉ (IP address) nguồn , đích và số cổng (Port) nguồn/đích sẽ không đổi trong quá trình kết nối. Như vậy mình sẽ dùng cặp địa chỉ và cặp cổng này đề xác định 1 kết nối. Và sẽ "đặt tên" cho kết nối này là 1 2 3 4 ... Để từ đó thực hiện các thống kê ví dụ nhưbăng thông của kết nối là bao nhiêu ... v.v


Đối với block tìm và truy xuất:
- Dữ liệu vào (Địa chỉ IP của nguồn/đích ... địa chỉ port của nguồn đích của một gói IP)
- Dữ liệu ra (Một số id đặc trưng cho kết nối)

Bảng dữ liệu trong bộ nhớ sẽ chứa một cặp Key (40 bytes) - ID (32/64 bit). Block truy xuất sẽ tra và trả ra ID cho mỗi Key. Một cặp key-id sẽ tạo thành 1 mục (entry) trong bộ nhớ. Để tiện việc tra cứu, các mục được xếp theo thứ tự lớn dần (Coi key là một số có 320 bit). Và thuật toán tra là thuật toán tìm nhị phân (binary search).

Cấu trúc của block là như thế này:


Bạn nào tò mò thì pm cho mình, mình gửi code viết bằng Verilog + testbench ... đọc rồi rảnh thì test dùm luôn .