Methods and structure for automated determination and reconfiguration of the size of a cache memory in a storage system. Features and aspects hereof generate historical information regarding frequency of hits on cache lines in the cache memory. The history maintained is then analyzed to determine a desired cache memory size. The historical information regarding cache memory usage may be communicated to a user who may then direct the storage system to reconfigure its cache memory to a desired cache memory size. In other embodiments, the storage system may automatically determine the desired cache memory size and reconfigure its cache memory. The method may be performed automatically periodically, and/or in response to a user's request, and/or in response to detecting thrashing caused by least recently used (LRU) cache replacement algorithms in the storage system.