Cách nhanh nhất để truy xuất/lưu trữ hàng triệu đối tượng nhị phân nhỏ

Question

Tôi đang tìm giải pháp nhanh (như hiệu suất lớn, không sửa nhanh) để lưu trữ và truy xuất hàng chục triệu đối tượng nhị phân nhỏ (khoảng 1k). Mỗi đối tượng phải có một ID duy nhất để truy xuất (tốt hơn là GUID hoặc SHA). Yêu cầu bổ sung là nó có thể sử dụng được từ .NET và không yêu cầu cài đặt phần mềm bổ sung.

Hiện tại, tôi đang sử dụng cơ sở dữ liệu SQLite với một bảng cho công việc này, nhưng tôi muốn loại bỏ chi phí xử lý các lệnh SQL đơn giản như SELECT data FROM store WHERE id = id.

Tôi cũng đã kiểm tra tính bền vững của hệ thống tệp trực tiếp dưới NTFS, nhưng hiệu suất giảm rất nhanh ngay khi nó đạt đến nửa triệu đối tượng.

P.S. Bằng cách này, các đối tượng không bao giờ cần phải bị xóa, và tỷ lệ chèn là rất, rất thấp. Trong thực tế, mỗi khi một đối tượng thay đổi một phiên bản mới được lưu trữ và phiên bản trước đó vẫn còn. Đây thực sự là một yêu cầu để hỗ trợ du hành thời gian.

Chỉ cần thêm một số thông tin bổ sung cho chủ đề này:

Để Blob hoặc Không Để BLOB: Lưu trữ đối tượng lớn trong một cơ sở dữ liệu hoặc một hệ thống tập tin http://arxiv.org/abs/cs.DB/0701168

Answer 1

Bạn có thể giảm bớt các vấn đề về hiệu suất của NTFS bằng cách phá vỡ mã định danh GUID của đối tượng thành nhiều phần và sử dụng chúng làm tên thư mục. Bằng cách đó, mỗi thư mục chỉ chứa một số lượng giới hạn các thư mục con hoặc tệp.

ví dụ: nếu số nhận dạng là aaaa-bb-cc-ddddeeee, đường dẫn đến mục sẽ là c:\store\aaaa\bbcc\dddd\eeee.dat, giới hạn mỗi thư mục không quá 64 nghìn phân mục con.

Answer 2

Tôi nghĩ rằng các truy vấn cơ sở dữ liệu là đặt cược tốt nhất của bạn.

Toàn bộ cấu trúc của cơ sở dữ liệu được điều chỉnh theo loại trường hợp này, và phân tích cú pháp và tối ưu hóa truy vấn đơn giản là không đáng kể.

Bạn có thể nấu một sơ đồ nơi bạn lưu trữ tất cả các đối tượng trong một blob lớn trực tiếp vào hệ thống tập tin, sau đó mở giao diện tệp ánh xạ bộ nhớ trên đó và lập chỉ mục ID đối tượng có bù đắp vào đốm , nhưng tôi nghi ngờ bạn sẽ thấy tuyệt vời hơn nhiều so với DB, vì đây thực chất là những gì nó làm.

Answer 3

Lưu trữ chỉ mục riêng biệt (tệp khác) của [Hướng dẫn -> số tệp + bù đắp trong tệp]. Sử dụng tìm kiếm nhị phân để truy xuất và chuyển đến tệp n + 1 bất kỳ khi nào tệp n đạt đến kích thước nhất định. Mỗi hàng trong tệp chỉ mục chỉ có 24 byte (kích thước cố định: số tệp guid + bù đắp, chia nhỏ tệp ở 4GB) và sắp xếp nhanh (chèn sắp xếp với tốc độ thấp.)

Edit: Bạn có các yêu cầu đơn giản, dễ hiểu để tối ưu hóa. Hệ thống được xây dựng cẩn thận này sẽ hoạt động tốt hơn cơ sở dữ liệu, đặc biệt nếu bạn cẩn thận về đọc khối dữ liệu và IO không đồng bộ. Các truy vấn cơ sở dữ liệu sẽ luôn có chi phí phân tích cú pháp.

Chỉnh sửa 2: Nếu bạn cần nó cũng an toàn (luôn luôn là một ý tưởng tốt), hãy xem ở đây để biết mô tả về cách khái niệm file system transactions có thể giúp bạn chống đạn.

Answer 4

Bạn cần gọi hàm prepare chỉ một lần cho mỗi câu lệnh, với tham số được biểu thị, ví dụ:bởi ? (vì vậy SELECT data FROM store WHERE id=? là tuyên bố bạn chuẩn bị); thì những gì bạn làm "hàng triệu lần" chỉ là bind tham số vào câu lệnh đã chuẩn bị và gọi sqlite_step - đây là những hoạt động nhanh. Đánh giá điểm đáng giá nếu blob open có thể không còn nhanh hơn nữa. IOW, tôi khuyên bạn nên gắn bó với SQLite và đào sâu vào giao diện cấp thấp của nó (từ quản lý C++ nếu bạn phải) để đạt hiệu suất tối đa - nó thực sự là một công cụ nhỏ tuyệt vời, và nó thường làm tôi ngạc nhiên với hiệu suất của nó!

Answer 5

Bạn đã xem xét thử cơ sở dữ liệu đối tượng, chẳng hạn như db4o? Nó có thể tồn tại bất kỳ CLR objekt, và truy cập chúng một cách nhanh chóng với ngôn ngữ truy vấn (hỗ trợ LINQ!). Tôi không có hàng triệu đối tượng, nhưng với vài nghìn truy cập khá nhanh, không có sự khác biệt lớn so với truy vấn SQL tương tự với trường id được lập chỉ mục.

Answer 6

Làm thế nào về một tập tin nhị phân với khối kích thước cố định khoảng 2k, có 4 byte đầu tiên là chiều dài của đối tượng ...

vị trí của đối tượng i là i * 2048 byte, sau đó đọc 2048 byte cho đối tượng, lấy độ dài của đối tượng thực tế từ 4 byte đầu tiên (không dấu).

Answer 7

Tôi thích giải pháp của Earwicker. Cách tôi đã xử lý với điều này là rất giống nhau.

Những gì tôi đã làm được điều này:

Hãy nói rằng guid của bạn là 3F2504E0-4F89-11D3-9A0C-0305E82C3301.

Đập hướng dẫn xuống dưới dạng băm ba chữ cái. aaa-zzz.

Giả sử, vì lý do tranh luận, hướng dẫn của bạn băm nhỏ thành "xap".

thông tin của bạn sẽ được tìm thấy trong các tập tin c: \ cửa hàng \ x \ xa \ XAP \ 3F2504E04F8911D39A0C0305E82C3301.dat

Đương nhiên, có rất nhiều biến thể của chiến lược này. Ví dụ, xap có thể là một tập tin với tất cả các đối tượng nhị phân nối với nhau, với một tiêu đề hoặc một tập tin bên ngoài có các guids và offset vào tập tin.

Answer 8

Bạn có thể kiểm tra xem HDF5 cấu trúc phù hợp với nhiệm vụ của bạn

• .Net interface

Answer 9

Tôi có xu hướng đồng ý w/Alex, nếu bạn viết giải pháp của riêng của bạn, bạn đang thiết kế lại những thứ đó là đã có khả năng trong SQLite, nhưng nếu bạn phải ...

Bạn có thể tạo BTree ở đây. Đó là cách làm việc của bất kỳ cơ sở dữ liệu nào và không gian vấn đề của bạn không phải là tất cả những điều xấu. 10 trong số hàng triệu đối tượng 1k vẫn chỉ là 10 trong số hàng tỷ byte, do đó hệ điều hành có thể quản lý tệp và có rất nhiều ví dụ về BTree để thử.

So với việc sử dụng cấu trúc thư mục hệ thống tệp để cơ bản tạo ra một tương tự BTree bằng cách sử dụng BTree thực sẽ nhanh hơn rất nhiều.

Một giải pháp khác có thể quan tâm là Mogilfs là hệ thống tệp dự phòng được phân phối.

Answer 10

Tôi không biết liệu chỉ mục hỗ trợ SQLite hay không, nhưng nếu có thì bạn có thể tăng tốc độ bằng cách tạo chỉ mục trên trường ID.

Nếu không, thì lựa chọn tốt nhất của bạn là cây B +. Cảm ơn