Reducing read starvation
View Patent ↗Apparatus, methods, and other embodiments associated with reducing read starvation that is supported by a multi-purpose buffer managed by a least recently used (LRU) data structure are described. One example method includes changing how certain retired pages are added back into the LRU. The dual-purpose buffer may be used in data de-duplication to support satisfying ingest requests and to support satisfying read requests. The method may also include controlling the LRU to allocate active ingest pages and active read pages from the head of the LRU. The method may also include controlling the LRU to cause the active ingest page and the active read page to re-enter the LRU at the tail of the LRU. Unlike conventional approaches, the method may also include controlling the LRU to cause a retired ingest page to re-enter the LRU at a location other than the tail (e.g., head) of the LRU.
1. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:
accessing a least-recently-used (LRU) data structure associated with a dual-purpose buffer to support satisfying ingest requests and to support satisfying read requests, the LRU data structure having a head and a tail;
controlling the LRU data structure to allocate an active ingest page from the head of the LRU data structure to support satisfying a particular ingest request;
controlling the LRU data structure to allocate an active read page from the head of the LRU data structure to support satisfying a particular read request;
controlling the LRU data structure to cause the active ingest page to re-enter the LRU data structure at the tail of the LRU data structure;
controlling the LRU data structure to cause the active read page to re-enter the LRU data structure at the tail of the LRU data structure; and
controlling the LRU data structure to cause a retired ingest page to re-enter the LRU data structure at the head of the LRU data structure, where the active ingest page becomes the retired ingest page upon completing support of satisfying the particular ingest request.
2. The non-transitory computer-readable medium of claim 1 , the method comprising controlling the LRU data structure to cause a retired read page to re-enter the LRU data structure at the head of the LRU data structure, where the active read page becomes the retired read page upon completing support of satisfying the particular read request.
3. The non-transitory computer-readable medium of claim 1 , the method comprising manipulating a tracking data that tracks a number of active read pages that cross a boundary in the LRU data structure.
4. The non-transitory computer-readable medium of claim 3 , the method comprising selectively altering a priority between satisfying ingest requests and satisfying read requests based, at least in part, on the tracking data.
5. The non-transitory computer-readable medium of claim 4 , the method comprising selectively increasing a priority of satisfying ingest requests over satisfying read requests based, at least in part, on the tracking data.
6. The non-transitory computer-readable medium of claim 4 , the method comprising selectively decreasing a priority of satisfying ingest requests over satisfying read requests based, at least in part, on the tracking data.
7. The non-transitory computer-readable medium of claim 2 , the method comprising manipulating a tracking data that tracks a number of active read pages that that cross a boundary in the LRU data structure.
8. The non-transitory computer-readable medium of claim 7 , the method comprising selectively altering a priority between satisfying ingest requests and satisfying read requests based, at least in part, on the tracking data.
9. The non-transitory computer-readable medium of claim 8 , the method comprising selectively increasing a priority of satisfying ingest requests over satisfying read requests based, at least in part, on the tracking data.
10. The non-transitory computer-readable medium of claim 8 , the method comprising selectively decreasing a priority of satisfying ingest requests over satisfying read requests based, at least in part, on the tracking data.
11. The non-transitory computer-readable medium of claim 1 , where the least-recently-used (LRU) data structure is associated with a dual-purpose buffer to support satisfying ingest requests and to support satisfying read requests for a data de-duplication process.
12. An apparatus, comprising:
a processor;
a memory configured with a least recently used (LRU) data structure to manage buffer pages in a multi-purpose buffer used to support data de-duplication;
a set of logics; and
an interface to connect the processor, the memory, and the set of logics, the set of logics comprising:
a first logic that supports a first data de-duplication action;
a second logic that supports a second data de-duplication action; and
a third logic that supports both the first data de-duplication action and the second data de-duplication action by controlling an allocation of a particular buffer page via the LRU data structure and by selectively controlling the particular buffer page to re-enter the LRU data structure at one of, a tail of the LRU data structure, a head of the LRU data structure, and at a selected location in the LRU data structure.
13. The apparatus of claim 12 , the first de-duplication action being an ingest action.
14. The apparatus of claim 13 , the second de-duplication action being a read request action.
15. The apparatus of claim 14 , where the third logic controls a retired ingest page to re-enter the LRU data structure at the head of the LRU data structure.
16. The apparatus of claim 15 , where the third logic acquires data concerning a position of a tracked buffer page in the LRU data structure.
17. The apparatus of claim 16 , where the third selectively controls allocation of a resource between the first data de-duplication action and the second data de-duplication action based, at least in part, on the data concerning the position of the tracked buffer page.
18. The apparatus of claim 14 , where the third logic controls a retired read page to re-enter the LRU data structure at the head of the LRU data structure.
19. A system, comprising:
means for controlling an ingest process;
means for controlling a read process; and
means for selectively controlling a re-entry point of a buffer page into a least recently used (LRU) data structure associated with a dual-purpose buffer that supports the ingest process and the read process, where the re-entry point is determined as a function of a status of the buffer page, where the means for selectively controlling a re-entry point include hardware, the means for controlling a read process include hardware, and the means for controlling an ingest process include hardware.
20. The system of claim 19 , comprising means for selectively controlling a priority between the ingest process and the read process in response to detecting an advancement of an active read page beyond a location in the LRU data structure, where the means for selectively controlling a priority include hardware.
21. The system of claim 19 , the ingest process being a data de-duplication ingest process, the read process being a data de-duplication read process.