Tôi cần lưu trữ lượng lớn dữ liệu trên đĩa trong khoảng 1k khối. Tôi sẽ truy cập vào những vật thể này theo cách khó dự đoán, nhưng ở đâu có thể tồn tại các mẫu.Tối ưu hóa vị trí của dữ liệu trên đĩa để truy cập tuần tự
Có một thuật toán hoặc heuristic tôi có thể sử dụng sẽ sắp xếp lại các đối tượng trên đĩa dựa trên các mẫu truy cập của tôi để cố gắng tối đa hóa truy cập tuần tự, và do đó giảm thiểu thời gian tìm kiếm đĩa?
Tùy thuộc vào những gì bạn có nghĩa là bởi "khó dự đoán", tôi có thể nghĩ ra một vài lựa chọn:
Nếu bạn luôn tìm kiếm dựa trên cùng một lĩnh vực khối/tài sản, lưu trữ các hồ sơ trên đĩa được sắp xếp theo lĩnh vực mà . Điều này cho phép bạn sử dụng binary search cho hiệu suất O (log n).
Nếu bạn tìm kiếm trên các trường khối khác nhau, hãy xem xét lưu trữ chỉ mục bên ngoài cho từng trường. A b-tree mang lại cho bạn hiệu quả O (log n). Khi bạn tìm kiếm, lấy chỉ mục thích hợp, tìm kiếm nó cho địa chỉ tệp dữ liệu của khối của bạn và chuyển đến nó.
Tốt hơn, nếu các khối của bạn là đồng nhất, hãy xem xét chia nhỏ chúng thành các bản ghi cơ sở dữ liệu. Cơ sở dữ liệu cung cấp cho bạn khả năng lưu trữ, lập chỉ mục và khả năng thực hiện các truy vấn nâng cao miễn phí.
Cách đơn giản nhất để giải quyết vấn đề này là sử dụng một hệ điều hành giúp bạn giải quyết vấn đề đó, như Linux. Cung cấp cho nó đủ RAM để giữ 10% các đối tượng trong RAM và nó sẽ cố giữ càng nhiều bộ nhớ trong bộ nhớ cache càng tốt để giảm thời gian tải xuống 0. Máy chủ gần đây cũng có thể hoạt động (một số họ đã không cho tôi, đó là lý do tại sao tôi đề cập đến điều này).
Nếu đây là một đi không, hãy thử thuật toán này:
Tạo một tập tin rất lớn trên đĩa cứng. Điều rất quan trọng là bạn viết điều này trong một lần để hệ điều hành sẽ phân bổ một không gian liên tục trên đĩa.
Viết tất cả các đối tượng của bạn vào tệp đó. Đảm bảo rằng mỗi đối tượng có cùng kích thước (hoặc cung cấp cho mỗi không gian giống nhau trong tệp và lưu ý độ dài trong vài byte đầu tiên của mỗi đoạn). Sử dụng đĩa cứng trống hoặc đĩa vừa được phân mảnh.
Trong cấu trúc dữ liệu, hãy giữ khoảng cách của từng đoạn dữ liệu và tần suất truy cập dữ liệu đó như thế nào. Khi nó được truy cập rất thường xuyên, hoán đổi vị trí của nó trong tệp với một đoạn gần với phần đầu của tệp và có số truy cập thấp hơn.
[EDIT] Truy cập tệp này bằng API ánh xạ bộ nhớ của hệ điều hành để cho phép hệ điều hành lưu trữ bộ nhớ hiệu quả nhất để có hiệu suất tốt nhất cho đến khi bạn có thể tối ưu hóa bố cục tệp lần sau.
Theo thời gian, khối được truy cập nhiều sẽ phát ra từ đầu. Lưu ý rằng bạn có thể thu thập các mẫu truy cập trong một thời gian, phân tích chúng và thực hiện sắp xếp lại qua đêm khi có ít tải trên máy của bạn. Hoặc bạn có thể thực hiện sắp xếp lại trên một máy hoàn toàn khác và trao đổi tệp (và bảng bù trừ) khi thực hiện xong.
Điều đó nói rằng, bạn thực sự nên dựa vào một hệ điều hành hiện đại, nơi rất nhiều người thông minh đã suy nghĩ lâu và khó để giải quyết những vấn đề này cho bạn.
Sử dụng quyền truy cập tệp được ánh xạ bộ nhớ thay vì mẫu tìm kiếm/đọc mở thường lệ. Kỹ thuật này hoạt động trên nền tảng Windows và Unix.
Bằng cách này, hệ thống bộ nhớ ảo của hệ điều hành sẽ xử lý bộ nhớ đệm cho bạn. Truy cập các khối đã có trong bộ nhớ sẽ dẫn đến không có đĩa tìm kiếm hoặc đọc thời gian. Viết từ bộ nhớ trở lại đĩa được xử lý tự động và hiệu quả và không chặn ứng dụng của bạn.
Ghi chú của Aaron cũng tốt vì chúng sẽ ảnh hưởng đến thời gian tải ban đầu cho một đoạn không có trong bộ nhớ. Kết hợp với kỹ thuật ánh xạ bộ nhớ - sau khi tất cả sẽ dễ dàng hơn để sắp xếp lại các khối bằng cách sử dụng memcpy() hơn là đọc/ghi từ đĩa và cố gắng hoán đổi, v.v.
Cảm ơn, tôi hoàn toàn quên về mmap :) –
Tôi không tin rằng mmap sẽ làm cho việc truy cập đĩa thực tế nhanh hơn. Trong mọi trường hợp, IO được thực hiện trong các trang, vì vậy ngay cả khi bạn chỉ muốn một vài byte, toàn bộ một trang được đưa vào, và một trang khác cần phải được ném ra ngoài để nhường chỗ. Bí quyết là có được nhiều thứ hữu ích nhất có thể trong một trang. – MarkR
Đó là một thử thách thú vị. Thật không may, tôi không biết làm thế nào để giải quyết điều này ra khỏi hộp, một trong hai. Cách tiếp cận của Corbin nghe có vẻ hợp lý với tôi.
Dưới đây là một gợi ý tối ưu hóa ít nhất: Đặt các mục được truy cập nhiều nhất tại trung tâm của bạn (hoặc tệp không phân mảnh), chứ không phải ở đầu. Bằng cách đó, việc tìm kiếm dữ liệu ít được sử dụng sẽ gần bằng mức trung bình. Err, đó là khá rõ ràng, mặc dù.
Vui lòng cho chúng tôi biết nếu bạn tự tìm ra giải pháp.
Trên hệ điều hành hiện đại (Windows, Linux, v.v.), bạn hoàn toàn không thể làm gì để tối ưu hóa thời gian tìm kiếm! Đây là lý do:
Để diễn giải Raymond Chen, nếu bạn phải hỏi về giới hạn OS, có thể bạn đang làm điều gì đó sai. Đối xử với hệ thống tập tin của bạn như một hộp đen bất biến, nó chỉ là những gì nó được (tôi biết, bạn có thể sử dụng RAID và như vậy để giúp đỡ).
Bước đầu tiên bạn phải thực hiện (và phải được thực hiện bất cứ khi nào bạn tối ưu hóa) là để đo lường những gì bạn hiện có. Không bao giờ giả định bất cứ điều gì. Xác minh mọi thứ bằng dữ liệu cứng.
Từ bài đăng của bạn, có vẻ như bạn chưa thực sự viết bất kỳ mã nào, hoặc, nếu bạn có, hiện không có sự cố về hiệu suất.
Giải pháp thực sự duy nhất là nhìn vào bức tranh lớn hơn và phát triển các phương pháp để lấy dữ liệu khỏi đĩa mà không bị trì hoãn ứng dụng.Điều này thường sẽ thông qua truy cập không đồng bộ và tải đầu cơ. Nếu ứng dụng của bạn luôn truy cập vào đĩa và làm việc với các tập con nhỏ của dữ liệu, bạn có thể cân nhắc sắp xếp lại dữ liệu để đặt tất cả nội dung hữu ích vào một nơi và các dữ liệu khác ở nơi khác. Nếu không biết miền đầy đủ vấn đề thì không thể thực sự hữu ích.
Bạn có biết rằng bạn cần phải đi đến những độ dài này để tối ưu hóa mã của mình không? Điều này nghe có vẻ như tối ưu hóa sớm. Tại sao không viết một cái gì đó lành mạnh đầu tiên, và tốc độ nó lên sau khi bạn đã chứng minh bạn có một nút cổ chai? –