What are some of the popular caching algorithms?
Some of the most popular and theoretically important algorithms are FIFO, LRU, LFU, LRU2, 2Q and time-based expiration. Most of the titles are based on the strategies used to eject items from cache when the cache gets full, except the time-based expiration algorithms. FIFO (First In First Out): Items are added to the cache as they are accessed, putting them in a queue or buffer and not changing their location in the buffer; when the cache is full, items are ejected in the order they were added. Cache access overhead is constant time regardless of the size of the cache. The advantage of this algorithm is that it’s simple and fast; it can be implemented using just an array and an index. The disadvantage is that it’s not very smart; it doesn’t make any effort to keep more commonly used items in cache. Summary for FIFO: fast, not adaptive, not scan resistant LRU – (Least Recently Used): Items are added to the cache as they are accessed; when the cache is full, the least recently used item
