Kịch bảnlư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ì
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.
Tôi biết bạn đang sử dụng C# và tôi không biết các tệp ánh xạ bộ nhớ được triển khai ở đó như thế nào, nhưng bạn có thể muốn xem xét điều này cho Java: 'http : //download.oracle.com/javase/6/docs/api/java/nio/channels/FileChannel.html#map (java.nio.channels.FileChannel.MapMode, dài, dài) ' – user183037
" Thay đổi được thực hiện cho bộ đệm kết quả cuối cùng sẽ được truyền cho tập tin; chúng có thể hoặc không được hiển thị cho các chương trình khác đã ánh xạ cùng một tệp. " - nếu bạn đang sử dụng nhiều chủ đề, bạn sẽ muốn cẩn thận về phần này. – user183037
Tôi không gặp vấn đề gì với đa luồng hoặc đa procs truy cập cùng một tệp. Nếu tôi không nhầm lẫn hai luồng/procs sẽ truy cập vào cùng một trang bộ nhớ trong hệ điều hành nếu truy cập cùng một dữ liệu và hệ điều hành sẽ chăm sóc lưu trữ/phân trang/xếp hàng các yêu cầu. Điều đó nói rằng, tôi không có chuyên gia và trong kịch bản của tôi tôi có một nhà văn và nhiều độc giả, và nhận được một lần bỏ lỡ là không có vấn đề lớn. Nếu bạn cần phải chắc chắn 100% trên chuỗi sự kiện, thì bạn có thể không muốn sử dụng mmf. Nhưng tôi sẽ tin tưởng điều này khá nhiều vì MMF là một trong những cách được khuyến nghị để chia sẻ dữ liệu giữa các ứng dụng. –