lưu trữ tối ưu của cấu trúc dữ liệu cho tra cứu nhanh chóng và kiên trì

Question

Kịch bản

tôi có các phương pháp sau:

public void AddItemSecurity(int itemId, int[] userIds) 
public int[] GetValidItemIds(int userId) 

Ban đầu tôi nghĩ đến lưu trữ trên biểu mẫu:

itemId -> userId, userId, userId 

và

userId -> itemId, itemId, itemId 

AddItemSecurity dựa trên cách tôi nhận dữ liệu từ API của bên thứ ba, GetValidItemIds là cách tôi muốn sử dụng nó khi chạy.

Có khả năng 2000 người dùng và 10 triệu mục. Id mục có trên biểu mẫu: 2007123456, 20100(10 chữ số trong đó bốn chữ cái đầu tiên đại diện cho năm).

AddItemSecurity không phải thực hiện siêu nhanh, nhưng GetValidIds cần phải là giây. Ngoài ra, nếu có bản cập nhật trên itemId hiện có, tôi cần xóa mục đóId cho người dùng không còn trong danh sách.

Tôi đang cố gắng nghĩ về cách tôi nên lưu trữ điều này theo cách tối ưu. Tốt hơn trên đĩa (với bộ nhớ đệm), nhưng tôi muốn mã duy trì và sạch sẽ.

Nếu id mục đã bắt đầu ở mức 0, tôi đã nghĩ về việc tạo mảng byte có độ dài là MaxItemId/8 cho mỗi người dùng và đặt bit đúng/sai nếu mặt hàng đó có mặt hay không. Điều đó sẽ giới hạn độ dài mảng đến ít hơn 1mb cho mỗi người dùng và cung cấp tra cứu nhanh cũng như cách dễ dàng để cập nhật danh sách cho mỗi người dùng. Bởi sự bền bỉ này như là Memory Mapped Files với khuôn khổ .Net 4 Tôi nghĩ rằng tôi sẽ nhận được bộ nhớ đệm khá tốt (nếu máy có đủ RAM) mà không thực hiện bộ nhớ đệm logic bản thân mình. Phân tích cú pháp id, tước năm, và lưu trữ một mảng mỗi năm có thể là một giải pháp.

Danh sách ItemId -> UserId [] có thể được nối tiếp trực tiếp vào đĩa và đọc/ghi với thông số FileStream để duy trì danh sách và phân biệt nó khi có thay đổi.

Mỗi khi người dùng mới được thêm vào tất cả các danh sách đều phải cập nhật, nhưng điều này có thể được thực hiện hàng đêm.

Câu hỏi

Tôi có nên tiếp tục cố gắng ra cách tiếp cận này, hay có những con đường khác cần được khám phá không? Tôi đang nghĩ rằng máy chủ SQL sẽ không thực hiện đủ nhanh, và nó sẽ cung cấp cho một chi phí (ít nhất là nếu nó được lưu trữ trên một máy chủ khác nhau), nhưng giả định của tôi có thể sai. Bất kỳ suy nghĩ hoặc hiểu biết về vấn đề này được đánh giá cao. Và tôi muốn cố gắng giải quyết nó mà không cần thêm quá nhiều phần cứng :)

[Cập nhật 2010/03/31]

bây giờ tôi đã thử nghiệm với SQL server 2008 theo các điều kiện sau đây.

• Bảng với hai cột (userid, itemid) cả hai đều Int
• index Clustered trên hai cột
• thêm ~ 800.000 mục cho 180 người - Tổng số 144 triệu hàng
• phân bổ 4gb ram cho SQL server
• dual Core 2.66GHz laptop
• đĩa SSD
• Sử dụng một SqlDataReader để đọc tất cả itemid thành một Danh sách
• Vòng lặp qua tất cả người dùng

Nếu tôi chạy một chuỗi trung bình trên 0,2 giây. Khi tôi thêm một chuỗi thứ hai nó đi lên đến 0,4 giây, mà vẫn ok. Từ đó, kết quả giảm dần. Thêm một chủ đề thứ ba mang lại rất nhiều các truy vấn lên đến 2 seonds. Một chủ đề thứ tư, lên đến 4 giây, một lần thứ năm tăng một số truy vấn lên đến 50 giây.

CPU đang lợp mái trong khi điều này đang diễn ra, ngay cả trên một sợi. Ứng dụng thử nghiệm của tôi mất một số do vòng lặp nhanh chóng, và sql phần còn lại.

Điều này dẫn tôi đến kết luận rằng nó sẽ không mở rộng rất tốt. Ít nhất là không phải trên phần cứng thử nghiệm của tôi. Có cách nào để tối ưu hóa cơ sở dữ liệu, nói lưu trữ một mảng int cho mỗi người dùng thay vì một bản ghi cho mỗi mục. Nhưng điều này làm cho nó khó khăn hơn để loại bỏ các mục.

[Cập nhật 2010/03/31 # 2]

tôi đã làm một thử nghiệm nhanh với cùng một dữ liệu đặt nó như bit trong các tập tin bộ nhớ ánh xạ. Nó hoạt động tốt hơn nhiều. Sáu luồng tạo ra thời gian truy cập giữa 0,02 và 0,06. Bộ nhớ hoàn toàn bị ràng buộc. Các tệp ánh xạ được ánh xạ bởi một quá trình và được truy cập bởi sáu người khác cùng một lúc. Và khi cơ sở sql mất 4GB, các tập tin trên đĩa mất 23mb.

Answer 1

Sau nhiều lần thử nghiệm, tôi đã kết thúc bằng cách sử dụng các tệp Bộ nhớ ánh xạ, đánh dấu chúng bằng bit thưa (NTFS), sử dụng mã từ NTFS Sparse Files with C#.

Wikipedia có giải thích về những gì mà sparse file là.

Lợi ích của việc sử dụng tệp thưa thớt là tôi không phải quan tâm đến phạm vi ID của mình. Nếu tôi chỉ ghi id giữa 2006000000 và 2010999999, tệp sẽ chỉ phân bổ 625.000 byte từ 250.750.000 trong tập tin. Tất cả không gian lên đến bù đắp đó không được phân bổ trong hệ thống tệp. Mỗi id được lưu trữ như một bit thiết lập trong tập tin. Sắp xếp xử lý dưới dạng mảng bit. Và nếu chuỗi id đột nhiên thay đổi, thì nó sẽ phân bổ trong một phần khác của tệp.

Để truy xuất id nào được đặt, tôi có thể thực hiện cuộc gọi hệ điều hành để nhận các phần được phân bổ của tệp thưa thớt và sau đó tôi kiểm tra từng bit trong các chuỗi đó. Ngoài ra kiểm tra nếu một id cụ thể được thiết lập là rất nhanh. Nếu nó rơi bên ngoài các khối được phân bổ, thì nó không có ở đó, nếu nó nằm bên trong, nó chỉ là một byte đọc và kiểm tra một chút mặt nạ để xem nếu bit chính xác được thiết lập.

Vì vậy, đối với trường hợp cụ thể mà bạn có nhiều id mà bạn muốn kiểm tra với càng nhiều tốc độ càng tốt, đây là cách tối ưu nhất mà tôi đã tìm thấy cho đến nay.

Và phần tốt là các tệp ánh xạ bộ nhớ có thể được chia sẻ với Java (cũng hóa ra là một thứ cần thiết). Java cũng có hỗ trợ cho các tệp ánh xạ bộ nhớ trên Windows và việc triển khai logic đọc/ghi khá tầm thường.

Answer 2

Tôi thực sự nghĩ bạn nên thử một cơ sở dữ liệu tốt trước khi đưa ra quyết định. Một cái gì đó như thế này sẽ là một thách thức để duy trì trong thời gian dài. Cơ sở người dùng của bạn thực sự khá nhỏ. SQL Server sẽ có thể xử lý những gì bạn cần mà không có bất kỳ vấn đề gì.

Answer 3

2000 người dùng không quá tệ nhưng với 10 triệu mục có liên quan bạn thực sự nên xem xét việc đưa điều này vào cơ sở dữ liệu. DB làm tất cả lưu trữ, kiên trì, lập chỉ mục, lưu bộ nhớ cache, vv mà bạn cần và chúng hoạt động rất tốt.

Chúng cũng cho phép khả năng mở rộng tốt hơn trong tương lai. Nếu bạn đột nhiên cần phải đối phó với hai triệu người dùng và hàng tỷ cài đặt có một db tốt tại chỗ sẽ làm cho việc mở rộng không phải là vấn đề.