Cách triển khai bộ nhớ cache được sử dụng gần đây nhất

Question

Cách tốt nhất để triển khai bộ nhớ cache các đối tượng được sử dụng gần đây nhất là gì?

Dưới đây là các yêu cầu và hạn chế ...

• Đối tượng được lưu trữ như cặp khóa/giá trị Object/Object, do đó giao diện sẽ là một chút như Hashtable nhận/đặt
• Một cuộc gọi đến ' nhận được 'sẽ đánh dấu đối tượng đó là đối tượng được sử dụng gần đây nhất.
• Bất cứ lúc nào, đối tượng ít được sử dụng gần đây nhất có thể bị xóa khỏi bộ nhớ cache.
• Tra cứu và thanh trừng phải nhanh (Như trong Hashtable nhanh)
• Số lượng đối tượng có thể lớn, do đó việc tra cứu danh sách không đủ tốt.
• Việc triển khai phải được thực hiện bằng cách sử dụng JavaME, do đó, có rất ít phạm vi để sử dụng mã của bên thứ ba hoặc các lớp thư viện gọn gàng từ các thư viện Java chuẩn. Vì lý do này tôi đang tìm kiếm nhiều hơn cho các câu trả lời thuật toán hơn là các khuyến nghị của các giải pháp off-the-peg.

Answer 1

Bộ sưu tập Java cung cấp LinkedHashMap ngoài hộp, rất phù hợp để xây dựng bộ nhớ cache. Bạn có lẽ không có điều này trong Java ME, nhưng bạn có thể lấy mã nguồn ở đây:

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

Nếu bạn không thể chỉ cần sao chép-dán nó, nhìn vào nó sẽ giúp bạn bắt đầu thực hiện một cho đưa vào ứng dụng dành cho thiết bị di động của bạn. Ý tưởng cơ bản là chỉ bao gồm một danh sách liên kết thông qua các yếu tố bản đồ. Nếu bạn giữ cập nhật này bất cứ khi nào ai đó đặt hoặc nhận được, bạn có thể theo dõi hiệu quả thứ tự truy cập và sử dụng thứ tự.

Tài liệu chứa hướng dẫn để tạo Bộ nhớ cache MRU bằng cách ghi đè phương thức .Tất cả các bạn thực sự phải làm là tạo một lớp mà kéo dài LinkedHashMap và ghi đè lên các phương pháp như vậy:

private static final int MAX_ENTRIES = 100; 

protected boolean removeEldestEntry(Map.Entry eldest) { 
    return size() > MAX_ENTRIES; 
} 

Ngoài ra còn có một constructor cho phép bạn xác định xem bạn muốn lớp để lưu trữ mọi thứ trong trật tự bằng cách chèn hoặc bằng cách sử dụng , vì vậy bạn đã có một sự linh hoạt chút cho chính sách đuổi của bạn, quá:

public LinkedHashMap(int initialCapacity, 
        float loadFactor, 
        boolean accessOrder) 

đèo đúng để sử dụng theo đơn đặt hàng và sai cho đơn đặt hàng chèn.

Answer 2

Tại sao triển khai một cái gì đó đã được triển khai? Sử dụng Ehcache.

Tuy nhiên, nếu thư viện của bên thứ ba là hoàn toàn ra câu hỏi, tôi đoán bạn đang tìm kiếm để thực hiện một cấu trúc dữ liệu mà trông giống như sau:

• Về cơ bản là một HashMap (mở rộng HashMap<Object, Object> nếu bạn sẽ)
• Mỗi giá trị trong Bản đồ trỏ đến một đối tượng trong danh sách được sắp xếp, dựa trên đó được sử dụng nhiều nhất.
• Đối tượng sử dụng gần đây được bổ sung vào người đứng đầu danh sách - O(1)
• tẩy phương gần đây ít sử dụng cắt bỏ phần cuối của danh sách - O(1)
• Tuy nhiên cung cấp cho bạn bản đồ tra cứu, nhưng vẫn giữ mục thời gian gần đây được sử dụng đầu tiên ...

Answer 3

Cách tiếp cận khác có thể là xem phần 5.6 trong Đồng thời Java trong thực tiễn bởi Brian Goetz: "Xây dựng bộ nhớ cache kết quả có thể mở rộng, hiệu quả". Hãy nhìn vào Memoizer, mặc dù bạn có thể phải tùy chỉnh nó cho các mục đích của bạn.

Là một sang một bên, những gì tôi không thể hiểu là lý do tại sao Java không có ConcurrentLinkedHashMap ra khỏi hộp. Cấu trúc dữ liệu này sẽ rất hữu ích để xây dựng bộ nhớ cache.

Answer 4

Một ConcurrentLinkedHashMap khó xây dựng, do các yêu cầu khóa. Bản đồ LinkedHashMap có khóa đơn giản nhưng không phải lúc nào cũng có hiệu suất. Một phiên bản đồng thời sẽ cố gắng giảm số lượng khóa, hoặc bằng cách tách khóa hoặc lý tưởng làm cho các hoạt động CAS để làm cho khóa rất rẻ. Nếu các hoạt động CAS bao giờ trở nên đắt đỏ, thì việc tách nhóm tương tự có thể hữu ích. Vì LRU yêu cầu viết cho mọi hoạt động truy cập và sử dụng danh sách được liên kết kép, điều này rất khó thực hiện với các hoạt động CAS thuần túy. Tôi đã thử nó, nhưng tôi cần phải tiếp tục trưởng thành thuật toán của mình. Nếu bạn tìm kiếm ConcurrentLinkedHashMap, bạn sẽ thấy trang dự án của tôi ...

Nếu Java ME không hỗ trợ các hoạt động CAS, điều tôi mong đợi là đúng, thì đồng bộ hóa cơ bản là tất cả những gì bạn có thể làm. Điều này có lẽ là đủ tốt với một LHM, cho rằng tôi đã chỉ nhìn thấy vấn đề hiệu suất ở số lượng thread cao trên phía máy chủ. Vì vậy, +1 cho câu trả lời ở trên.