System and method for managing large filesystem-based caches

Details System and method for managing large filesystem-based caches System and method for managing large filesystem-based caches

2008-09-09

2011-10-18

Doan, Duc (Department: 2185)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

Reexamination Certificate

active

08041893

ABSTRACT:
Embodiments disclosed herein utilize statistical approximations to manage large filesystem-based caches based on imperfect information. When removing entries from a large cache, which may have a million or more entries, the cache manager does not need to find the absolutely oldest entry that has been accessed the least recently. Instead, it suffices to find an entry that is older than most. In embodiments disclosed herein, statistical sampling of the cache is performed to produce models of different properties of the cache, including the number of entries, distribution of access times, distribution of entry sizes, etc. The models are then used to guide decisions that involve those properties. The size of the samples can be adjusted to balance the cost of acquiring the samples against the confidence level of the models produced by the samples. To achieve randomness, entries are stored using prefixes of addresses generated via a message-digest function.

REFERENCES:
patent: 5202982 (1993-04-01), Gramlich et al.
patent: 5473772 (1995-12-01), Halliwell et al.
patent: 5504879 (1996-04-01), Eisenberg et al.
patent: 5740430 (1998-04-01), Rosenberg et al.
patent: 5946697 (1999-08-01), Shen
patent: 6029175 (2000-02-01), Chow et al.
patent: 6151624 (2000-11-01), Teare et al.
patent: 6178461 (2001-01-01), Chan et al.
patent: 6192415 (2001-02-01), Haverstock et al.
patent: 6198824 (2001-03-01), Shambroom
patent: 6272492 (2001-08-01), Kay et al.
patent: 6408360 (2002-06-01), Chamberlain et al.
patent: 6571246 (2003-05-01), Anderson et al.
patent: 6591266 (2003-07-01), Li et al.
patent: 6651217 (2003-11-01), Kennedy et al.
patent: 6697844 (2004-02-01), Chan et al.
patent: 6701428 (2004-03-01), Harvey, III et al.
patent: 6754621 (2004-06-01), Cunningham et al.
patent: 6760813 (2004-07-01), Wu
patent: 6772203 (2004-08-01), Feiertag et al.
patent: 6785769 (2004-08-01), Jacobs et al.
patent: 6850941 (2005-02-01), White et al.
patent: 7024452 (2006-04-01), O'Connell et al.
patent: 7137009 (2006-11-01), Gordon et al.
patent: 7188216 (2007-03-01), Rajkumar et al.
patent: 7360025 (2008-04-01), O'Connell et al.
patent: 7398304 (2008-07-01), Smith et al.
patent: 7752394 (2010-07-01), Rajkumar et al.
patent: 7818506 (2010-10-01), Shepstone
patent: 2001/0032254 (2001-10-01), Hawkins
patent: 2001/0034771 (2001-10-01), Hutsch et al.
patent: 2001/0037407 (2001-11-01), Dragulev et al.
patent: 2002/0065912 (2002-05-01), Catchpole et al.
patent: 2002/0165877 (2002-11-01), Malcolm et al.
patent: 2002/0178187 (2002-11-01), Rasmussen et al.
patent: 2002/0194219 (2002-12-01), Bradley et al.
patent: 2003/0078964 (2003-04-01), Parrella et al.
patent: 2003/0217117 (2003-11-01), Dan et al.
patent: 2004/0030697 (2004-02-01), Cochran et al.
patent: 2004/0030746 (2004-02-01), Kavacheri et al.
patent: 2004/0107319 (2004-06-01), D'Orto et al.
patent: 2004/0205165 (2004-10-01), Melamed et al.
patent: 2004/0205452 (2004-10-01), Fitzsimmons et al.
patent: 2006/0136472 (2006-06-01), Jujjuri et al.
patent: 2006/0184572 (2006-08-01), Meek et al.
patent: 2010/0262785 (2010-10-01), Rajkumar
Office Action issued in U.S. Appl. No. 11/825,909 mailed Sep. 29, 2009, 9 pgs.
Office Action issued in U.S. Appl. No. 11/701,193, mailed Oct. 22, 2009, 10 pgs.
Office Action issued in U.S. Appl. No. 12/819,985 mailed Aug. 2, 2010, 9 pgs.
Office Action issued in U.S. Appl. No. 11/701,193 dated Mar. 31, 2009, Rajkumar, 9 pages.
Office Action issued in U.S. Appl. No. 11/825,909 mailed Mar. 5, 2010,11 pgs.
Notice of Allowance issued in U.S. Appl. No. 12/819,985 mailed Dec. 15, 2010, 10 pgs.
Office Action for U.S. Appl. No. 12/904,937, mailed Jan. 5, 2011, 12 pgs.
Chen et al., “Wormhole Caching with HTTP PUSH Method for Satellite-Based Web Content Multicast and Replication System” Workshop 99, pp. 1-14, 1999.
Fielding et al. “13 Caching in HTTP” part of Hypertext Transfer Protocol—HTTP/1.1, The Internet Society, 20 pgs, 1999.
Dias et al., A Smart Internet Caching System by University of Moratuwa, Sri Lanka, 13 pgs, 1996.
Office Action issued in U.S. Appl. No. 10/733,798, dated May 31, 2006, 14 pgs.
Office Action issued in U.S. Appl. No. 10/733,798, dated Jan. 3, 2006, 9 pgs.
Office Action issued in U.S. Appl. No. 10/733,742, dated Aug. 22, 2007, 14 pgs.
Office Action issued in U.S. Appl. No. 10/733,742, dated Feb. 7, 2007, 12 pgs.
Office Action issued in U.S. Appl. No. 10/733,742, dated Sep. 15, 2006, 8 pgs.
Office Action issued in U.S. Appl. No. 10/733,742, dated Jun. 6, 2006, 15 pgs.
Office Action issued in U.S. Appl. No. 10/733,742, dated Jan. 17, 2006, 10 pgs.
Office Action issued in U.S. Appl. No. 11/701,193, dated Oct. 2, 2008, 9 pgs.
Office Action for U.S. Appl. No. 12/212,414, mailed May 10, 2011, 24 pgs.
Office Action for U.S. Appl. No. 12/208,934, mailed May 10, 2011, 25 pgs.
Office Action for U.S. Appl. No. 12/904,937, mailed May 25, 2011, 11 pgs.
Office Action for U.S. Appl. No. 12/904,937, mailed Sep. 2, 2011, 13 pgs.

Affiliated with

Also associated with

Rating

System and method for managing large filesystem-based caches does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for managing large filesystem-based caches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for managing large filesystem-based caches will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4284874