Data processing: database and file management or data structures – Data integrity – Data cleansing – data scrubbing – and deleting duplicates
Reexamination Certificate
2006-08-22
2010-06-29
Trujillo, James (Department: 2159)
Data processing: database and file management or data structures
Data integrity
Data cleansing, data scrubbing, and deleting duplicates
C707S747000, C711S112000, C711S118000, C711S162000
Reexamination Certificate
active
07747584
ABSTRACT:
A system and method enables de-duplication in a storage system architecture comprising one or more volumes distributed across a plurality of nodes interconnected as a cluster. De-duplication is enabled through the use of file offset indexing in combination with data content redirection. File offset indexing is illustratively embodied as a Locate by offset function, while data content redirection is embodied as a novel Locate by content function. In response to input of, inter alia, a data container (file) offset, the Locate by offset function returns a data container (file) index that is used to determine a storage server that is responsible for a particular region of the file. The Locate by content function is then invoked to determine the storage server that actually stores the requested data on disk. Notably, the content function ensures that data is stored on a volume of a storage server based on the content of that data rather than based on its offset within a file. This aspect of the invention ensures that all blocks having identical data content are served by the same storage server so that it may implement de-duplication to conserve storage space on disk and increase cache efficiency of memory.
REFERENCES:
patent: 4570217 (1986-02-01), Allen et al.
patent: 5124987 (1992-06-01), Milligan et al.
patent: 5163131 (1992-11-01), Row et al.
patent: 5202979 (1993-04-01), Hillis et al.
patent: 5278979 (1994-01-01), Foster et al.
patent: 5403667 (1995-04-01), Simoens
patent: 5519844 (1996-05-01), Stallmo
patent: 5581724 (1996-12-01), Belsan et al.
patent: 5732265 (1998-03-01), Dewitt et al.
patent: 5802366 (1998-09-01), Row et al.
patent: 5819292 (1998-10-01), Hitz et al.
patent: 5990810 (1999-11-01), Williams
patent: 6061770 (2000-05-01), Franklin
patent: 6081875 (2000-06-01), Clifton et al.
patent: 6212525 (2001-04-01), Guha
patent: 6289451 (2001-09-01), Dice
patent: 6341341 (2002-01-01), Grummon et al.
patent: 6671773 (2003-12-01), Kazar et al.
patent: 6868417 (2005-03-01), Kazar et al.
patent: 6889297 (2005-05-01), Krapp et al.
patent: 6892211 (2005-05-01), Hitz et al.
patent: 7010553 (2006-03-01), Chen et al.
patent: 7024527 (2006-04-01), Ohr
patent: 7076622 (2006-07-01), Hsu et al.
patent: 7079053 (2006-07-01), Kolavi
patent: 7124305 (2006-10-01), Margolus et al.
patent: 7127577 (2006-10-01), Koning et al.
patent: 7162662 (2007-01-01), Svarcas et al.
patent: 7269646 (2007-09-01), Yamamoto et al.
patent: 7289643 (2007-10-01), Brunk et al.
patent: 7289886 (2007-10-01), Brunk et al.
patent: 7472242 (2008-12-01), Deshmukh et al.
patent: 2002/0049883 (2002-04-01), Schneider et al.
patent: 2002/0059317 (2002-05-01), Black et al.
patent: 2002/0116593 (2002-08-01), Kazar et al.
patent: 2002/0194529 (2002-12-01), Doucette et al.
patent: 2003/0135514 (2003-07-01), Patel et al.
patent: 2003/0182301 (2003-09-01), Patterson et al.
patent: 2003/0182312 (2003-09-01), Chen et al.
patent: 2003/0182317 (2003-09-01), Kahn et al.
patent: 2003/0182322 (2003-09-01), Manley et al.
patent: 2004/0030668 (2004-02-01), Pawlowski et al.
patent: 2004/0083245 (2004-04-01), Beeler
patent: 2004/0153479 (2004-08-01), Mikesell et al.
patent: 2005/0097260 (2005-05-01), McGovern et al.
patent: 2005/0114289 (2005-05-01), Fair
patent: 2005/0120078 (2005-06-01), Kazar et al.
patent: 2005/0192932 (2005-09-01), Kazar et al.
patent: 2005/0235109 (2005-10-01), Ogihara et al.
patent: 2005/0246401 (2005-11-01), Edwards et al.
patent: 2006/0174063 (2006-08-01), Soules et al.
patent: 2006/0184587 (2006-08-01), Federwisch et al.
patent: 2007/0088702 (2007-04-01), Fridella et al.
patent: 1349 089 (2003-01-01), None
U.S. Appl. No. 11/105,895, entitledMethod and Apparatus for Identifying and Eliminating Duplicate Data Blocks and Sharing Data Blocks in a Storage System, by Zheng et al., filed Apr. 13, 2005, 46 pages.
U.S. Appl. No. 11/119,279, entitledSystem and Method for Implementing Atomic Cross-Stripe Write Operations in a Striped Volume Set, by Jernigan et al., filed Apr. 29, 2005, 60 pages.
Akyurek, Sedat, Placing Replicated Data to Reduce Seek Delays, Department of Computer Science, University of Maryland, UMIACS-TR-91-121, CS-TR-2746, Aug. 1991.
Bitton, Dina, Disk Shadowing, Proceedings of the 14.sup.th VLDB Conference, LA, CA (1988), 8 pages.
Business Wire, “SEPATON Announces Next Generation Data De-Duplication Software; Delivers Industry's Highest Level of De-Duplication without Affecting Backup Performance”, May 8, 2006, Jun. 7, 2008.
Chaudhuri, Surajit, et al., Self-Tuning Technology in Microsoft SQL Server, Data Engineering Journal 22, Feb. 1999 pp. 20-27.
Chutani, Sailesh, et al., The Episode File System, In Proceedings of the USENIX Winter 1992, 18 pages.
Coyne, Robert A., et al., Storage Systems for National Information Assets, Proc. Supercomputing 92, Minneapolis, Nov. 1992, pp. 626-633.
Finlayson, Ross S., et al., Log Files: An Extended File Service Exploiting Write-Once Storage Department of Computer Science, Stanford University, Report No. STAN-CS-87-1177, Sep. 1987, 14 pages.
Gray, Jim, et al., The Recovery Manager of the System R Database Manager, ACM Computing Surveys, (13)2:223-242 1981, 20 pages.
Hecht, Matthew S., et al. Shadowed Management of Free Disk Pages with a Linked List, ACM Transactions on Database Systems, 8/4, Dec. 1983, pp. 503-514.
Hitz, Dave et al., File System Design for an NFS File Server Appliance, Technical Report 3002, Rev. C395, presented Jan. 19, 1994, 23 pages.
Hong, Bo et al., “Duplicate Data Elimination in a SAN File System”, Proceedings of the 21st IEEE / 12th NASA Goddard Conference on Mass Storage Systems and Technologies (2004): 301-314. http://www.cse.ucsc.edu/˜darrell/papers/msst-hong-04.pdf.
Howard, John H., An Overview of the Andrew File System, Carnegie Mellon University, CMU-ITC-88-062 1988, 6 pages.
Howard, John H, et al., Scale and Performance in a Distributed File System, Carnegie Mellon University, CMU-ITC-87-068, Aug. 5, 1987, 33 pages.
Howard, John, H. et al., Scale and performance in a distributed file system, ACM Trans. Computer. System., 6(1), Feb. 1988 pp. 51-81.
Kazar, Michael L., et al., Decorum File System Architectural Overview, USENIX Summer Conference, Anaheim, California, 1990, 13 pages.
Kazar, Michael L., Synchronization and Caching Issues in the Andrew File System, Carnegie Mellon University, CMU-ITC-88-063, 12 pages.
Kemper, Alfons, et al., Performance Tuning for SAP R/3, Data Engineering Journal 22, Feb. 1999 pp. 33-40.
Kent, Jack et al., Optimizing Shadow Recovery Algorithms, IEEE Transactions on Software Engineering, 14(2): 155-168, Feb. 1988.
Kistler, et al., Disconnected Operation in the Coda File System, ACM Transactions on Computer Systems, vol. 10, No. 1, Feb. 1992, pp. 3-25.
Lorie, Raymond, A, Physical Integrity in a large segmented database, ACM Trans. Database Systems, 2(1): 91-104, Mar. 1977.
National Institute of Standards and Technology, “The Keyed-Hash Message Authentication Code (HMAC)”, Federal Information Processing Standards Publication, Mar. 6, 2002, 20 pages.
Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority and Declaration, International Filing Date: Jun. 25, 2007, International Application No. PCT/US2007/014664, Applicant: Network Applicance, Inc., Date of Mailing Apr. 9, 2008, 12 pages.
Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration, International Filing Date: Jun. 25, 2007, International Application No. PCT/US2007/014666, Applicant: Network Applicance, Inc., Date of Mailing: Feb. 22, 2008, pp. 1-18.
Ousterhout, John et al., Beating the I/O Bottleneck: A Case for Log-Structured File Systems, Technical Report, Computer Science Division, Electrical Engineering and Computer Sciences, University of California at Berkeley, Oct. 30, 1988, 18 pages.
Patterson, D., et al., A Case for Redundant Arrays of Inexpensive Disks (RAID), Technical Report, CSD-87-391, Computer Science Division, Electrical Engineerin
Casanova Jorge A
Cesari and McKenna LLP
NetApp, Inc.
Trujillo James
LandOfFree
System and method for enabling de-duplication in a storage... 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 enabling de-duplication in a storage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for enabling de-duplication in a storage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4244108