Cache management system with multiple cache lists employing roving removal and priority-based addition of cache entries

A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations for managing contents of a cache, the operations comprising:

• establishing a multiple number of cache lists for storage of cache list entries each cache list entry naming a data item in the cache;
• designating a sequence and direction of progression through the cache lists;
• initially designating one of the cache lists as a current removal list;
• processing the cache lists by performing one of the following:
• a) performing demotion operations comprising responsive to each occurrence of a predetermined demotion-evaluation condition, selecting at least one entry from the current removal list, evaluating the selected entry, and if the selected entry satisfies predetermined demotion criteria, removing the selected entry from the current removal list and purging the cache of each data item represented by the removed entry;
• b) performing destaging operations comprising responsive to each occurrence of a predetermined destaging-evaluation condition, selecting at least one entry from the current removal list, evaluating the selected entry, and if the selected entry satisfies predetermined destaging criteria, removing the selected entry from the current removal list and destaging each data item represented by the selected entry, said destaging occurring from the cache to prescribed nonvolatile storage;
• designating a next list in the sequence from the current removal list whenever the current removal list becomes empty;
• responsive to predetermined types of activity of a data item in the cache, performing operations to add a cache list entry naming the data item into one of the cache lists, the operations comprising determining a priority ranking of the data item, adding a cache list entry naming the data item said addition being made into one of the lists spaced in the sequence of progression beyond the current removal list by a number representative of the priority ranking.

A logic circuit of multiple interconnected electrically conductive elements configured to perform operations to manage contents of a cache, the operations comprising:

• establishing a multiple number of cache lists for storage of cache list entries each cache list entry naming a data item in the cache;
• designating a sequence and direction of progression through the cache lists;
• initially designating one of the cache lists as a current removal list;
• processing the cache lists by performing one of the following:
• a) performing demotion operations comprising responsive to each occurrence of a predetermined demotion-evaluation condition, selecting at least one entry from the current removal list, evaluating the selected entry, and if the selected entry satisfies predetermined demotion criteria, removing the selected entry from the current removal list and purging the cache of each data item represented by the removed entry;
• b) performing destaging operations comprising responsive to each occurrence of a predetermined destaging-evaluation condition, selecting at least one entry from the current removal list, evaluating the selected entry, and if the selected entry satisfies predetermined destaging criteria, removing the selected entry from the current removal list and destaging each data item represented by the selected entry, said destaging occurring from the cache to prescribed nonvolatile storage;
• designating a next list in the sequence from the current removal list whenever the current removal list becomes empty;
• responsive to predetermined types of activity of a data item in the cache, performing operations to add a cache list entry naming the data item into one of the cache lists, the operations comprising determining a priority ranking of the data item, adding a cache list entry naming the data item said addition being made into one of the lists spaced in the sequence of progression beyond the current removal list by a number representative of the priority ranking.

A data storage system, comprising:

• a cache;
• nonvolatile data storage;
• metadata including a multiple number of cache lists for storage of cache list entries each cache list entry naming a data item in the cache, the lists having a designated sequence of progression there through, with one of the lists being initially designated as a current removal list;
• a storage manager, coupled to the cache, data storage, and metadata, the storage manager programmed to manage contents of the cache by performing operations comprising:
• establishing a multiple number of cache lists for storage of cache list entries each cache list entry naming a data item in the cache;
• designating a sequence and direction of progression through the cache lists;
• initially designating one of the cache lists as a current removal list;
• processing the cache lists by performing one of the following:
• a) performing demotion operations comprising responsive to each occurrence of a predetermined demotion-evaluation condition, selecting at least one entry from the current removal list, evaluating the selected entry, and if the selected entry satisfies predetermined demotion criteria, removing the selected entry from the current removal list and purging the cache of each data item represented by the removed entry;
• b) performing destaging operations comprising responsive to each occurrence of a predetermined destaging-evaluation condition, selecting at least one entry from the current removal list, evaluating the selected entry, and if the selected entry satisfies predetermined destaging criteria, removing the selected entry from the current removal list and destaging each data item represented by the selected entry, said destaging occurring from the cache to the nonvolatile data storage;
• designating a next list in the sequence from the current removal list whenever the current removal list becomes empty;
• responsive to predetermined types of activity of a data item in the cache, performing operations to add a cache list entry naming the data item into one of the cache lists, the operations comprising determining a priority ranking of the data item, adding a cache list entry naming the data item said addition being made into one of the lists spaced in the sequence of progression beyond the current removal list by a number representative of the priority ranking.

A data storage system, comprising:

• first means for caching data;
• second means for nonvolatile digital data storage;
• third means for storing metadata including a multiple number of cache lists for storage of cache list entries each cache list entry naming a data item in the cache, the lists having a designated sequence of progression therethrough, with one of the lists being initially designated as a current removal list;
• storage manager means, coupled to the first, second, and third means, for managing contents of the cache by:
• establishing a multiple number of cache lists for storage of cache list entries each cache list entry naming a data item in the first means;
• designating a sequence and direction of progression through the cache lists;
• initially designating one of the cache lists as a current removal list;
• processing the cache lists by performing one of the following:
• a) performing demotion operations comprising responsive to each occurrence of a predetermined demotion-evaluation condition, selecting at least one entry from the current removal list, evaluating the selected entry, and if the selected entry satisfies predetermined demotion criteria, removing the selected entry from the current removal list and purging the first means of each data item represented by the removed entry;
• b) performing destaging operations comprising responsive to each occurrence of a predetermined destaging-evaluation condition, selecting at least one entry from the current removal list, evaluating the selected entry, and if the selected entry satisfies predetermined destaging criteria, removing the selected entry from the current removal list and destaging each data item represented by the selected entry, said destaging occurring from the cache to the second means;
• designating a next list in the sequence from the current removal list whenever the current removal list becomes empty;
• responsive to predetermined types of activity of a data item in the first means, performing operations to add a cache list entry naming the data item into one of the cache lists, the operations comprising determining a priority ranking of the data item, adding a cache list entry naming the data item said addition being made into one of the lists spaced in the sequence of progression beyond the current removal list by a number representative of the priority ranking.