Data processing: database and file management or data structures – Data integrity – Policy – rule-based management of records – files – and documents
Reexamination Certificate
2009-09-25
2010-11-16
Le, Debbie (Department: 2168)
Data processing: database and file management or data structures
Data integrity
Policy, rule-based management of records, files, and documents
C707S638000, C707S639000, C707S649000
Reexamination Certificate
active
07836029
ABSTRACT:
The invention relates to a method of determining if a block was modified in a file system by comparing the versions of the base snapshot, the delta snapshot, and the space map block entry (b, e). In another aspect, the invention relates to a method of searching for blocks modified in a tree structured file system. The invention relates to methods and systems of snapshot management of a file system in a data storage system. To represent the snapshots, the invention maintains pointers to the root block pointer of each snapshot. When the active file system is modified, this invention avoids overwriting any blocks used by previous snapshots by allocating new blocks for the modified blocks. When the invention needs to put an established block in a new location, it must update a parent block to point to the new location. The update to the parent block may then require allocating a new block for the new parent block and so forth. Parts of the file system not modified since a snapshot remain in place. The amount of space required to represent snapshots scales with the fraction of the file system that users modify. To maintain snapshot integrity, this invention keeps track of the first and last snapshots that use each block in space map blocks spread throughout the file system data space. When users delete snapshots, this invention may use a background process to find blocks no longer used by any snapshot and makes them available for future use.
REFERENCES:
patent: 5317731 (1994-05-01), Dias et al.
patent: 5664186 (1997-09-01), Bennett et al.
patent: 5819292 (1998-10-01), Hitz et al.
patent: 6038639 (2000-03-01), O'Brien et al.
patent: 6085298 (2000-07-01), Ohran
patent: 6205450 (2001-03-01), Kanome
patent: 6247099 (2001-06-01), Skazinski et al.
patent: 6289356 (2001-09-01), Hitz
patent: 6311193 (2001-10-01), Selkdo
patent: 6484186 (2002-11-01), Rungta
patent: 6490659 (2002-12-01), McKean et al.
patent: 6636878 (2003-10-01), Rudoff
patent: 6636879 (2003-10-01), Doucette et al.
patent: 6732125 (2004-05-01), Autrey et al.
patent: 6883074 (2005-04-01), Lee et al.
patent: 6938134 (2005-08-01), Madany
patent: 6959313 (2005-10-01), Kapoor et al.
patent: 6978353 (2005-12-01), Lee et al.
patent: 7072916 (2006-07-01), Lewis et al.
patent: 7111021 (2006-09-01), Lewis et al.
patent: 7237080 (2007-06-01), Green et al.
patent: 7257606 (2007-08-01), Kapoor et al.
patent: 7454445 (2008-11-01), Lewis et al.
patent: 7603391 (2009-10-01), Federwisch et al.
patent: 7631018 (2009-12-01), Lee et al.
patent: 2002/0019923 (2002-02-01), Reuter et al.
patent: 2002/0049718 (2002-04-01), Kleiman et al.
patent: 2002/0083037 (2002-06-01), Lewis et al.
patent: 2002/0091670 (2002-07-01), Hitz et al.
patent: 2002/0133735 (2002-09-01), McKean et al.
patent: 2003/0018878 (2003-01-01), Dorward et al.
patent: 2004/0133602 (2004-07-01), Kusters et al.
patent: WO 02/29573 (2002-04-01), None
You et al., Deep Store: An Archival Storage System Architecture, Proceedings of the 21st International Conference on Data Engineering, 2005, IEEE Computer Society.
Padala, A Log Structured File System with Snapshots, 2005, pp. 1-14, University of Michigan.
Peterson et al., Ext3cow: A Time-Shifting File System for Regulatory Compliance, 2005, pp. 1-21, vol. 5, No. N, MM 20YY, ACM Transactions on Storage.
Li et al., Secure Untrusted Data Repository (SUNDR), 2004, NYU Department of Computer Science, pp. 1-16.
Hong et al., Duplicate Data Elimination in a SAN File System, 2004, pp. 301-314.
Flouris et al., Clotho: Transparent Data Versioning at the Block I/O Level, 2004, pp. 101-114.
Cates, Robust and Efficient Data Management for a Distributed Hash Table, Masters of Engineering Thesis at MIT, 2003, pp. 1-64, US.
Schmuck et al., GPFS: A Shared-Disk File System for Large Computing Clusters, Proceedings of the Conference on File and Storage Tech., 2002, pp. 231-244, USENIX, Berkeley, CA.
Quinlan et al., Venti: A new Approach to Archival Storage, 2002, only partial copy readily available, Bell Labs, Lucent Technologies.
Chang et al., Myriad: Cost-effective Disaster Tolerance, Compaq Systems Research Center, 2002, pp. 1-13, Palo Alto, CA.
Muthitacharoen et al., Ivy: A Read/Write Peer-to-Peer File System, 5th Symposium on Operating Systems Design and Implementation, 2002, pp. 31-44, USENIX Association.
Santry et al., Deciding When to Forget in the Elephant File System, Operating Systems Review, 1999, pp. 110-123, 34(5): ACM, Kiawah Island, SC.
Samet, Spatial Data Structures, Modern Database Systems: The Object Model, Interoperability, and Beyond, 1995, pp. 361-385, Addison Wesley/ACM Press Reading, MA.
Kawaguchi et al., A Flash-Memory Based File System, 1995, Advanced Research Laboratory, Hitachi, Ltd.
Hartman et al., The Zebra Striped Network File System, Dissertation at UC Berkeley, 1994, pp. i-48, Berkeley, CA.
Hitz et al., File System Design for an NFS File Server Appliance, 1995, The USENIX Association, pp. 1-23, Mountain View, CA.
Jonge et al., The Logical Disk: A New Approach to Improving File Systems, 1994.
Seltzer et al., An Implementation of a Log-Structured File System for UNIX, 1993, Winter USENIX, pp. 201-220, San Diego, CA.
Quinlan, A Cached WORM File System, Software Practice and Experience, 1991, pp. 1289-1299, vol. 21(12), John Wiley & Sons, Ltd.
Nelson et al., Caching in the Sprite Network File System, 1988, pp. 134-154, vol. 6, No. 1, ACM Transactions on Computer Systems.
Sandberg et al., Design and Implementation of the Sun Network Filesystem, 1985, Sun Microsystems, Inc., Mountain View, CA.
Ousterhout et al., A Trace-Driven Analysis of the UNIX 4.2 BSD File System, 1985, pp. 15-24, Association for Computing Machinery (ACM).
U.S. Appl. No. 60/419,252, filed Jul. 8, 2004, Kusters et al.
McKusick, Joy, Leffler, and Fabry, A Fast File System for UNIX, ACM Transactions on Computer Systems, Aug. 1984, pp. 181-197, vol. 2, No. 3, US.
McKusick and Ganger, Soft Updates: A Technique for Eliminating Most Synchronous Writes in the Fast Filesystem, Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference, Jun. 6-11, 1999, pp. 1-18, Monterey, US.
Rosenblum and Ousterhout, The Design and Implementation of a Log-Structured File System, ACM Transactions on Computer Systems, Feb. 1992, pp. 26-52, vol. 10, No. 1, Berkeley, US.
Rosenberg, Dearle, Hulse, Lindstrom and Norris, Operating System Support for Persistant and Recoverable Computations, Communications of the ACM, Sep. 1996, pp. 62-69, vol. 38, No. 9, US.
Lee and Thekkath, Petal: Distributed Virtual Disks, copyrighted 1996, pp. 84-92, ACM, Inc. MA, US.
Thekkath, Mann, and Lee, Frangipani: A Scalable Distributed File System, copyrighted1997, pp. 224-237, ACM, Inc. Saint-Malo, France.
European Exam Report for European Patent Application No. EP 04756637, Dated Mar. 26, 2007.
Supplementary European Search Report for European Patent Application No. EP 04756637, Published Jan. 1, 2007.
PCT International Search Report for International Application No. PCT/US04/21476, Published May 10, 2005.
European Exam Report for European Patent Application No. EP 04756637, Dated Mar. 28, 2008.
Le Debbie
Moll Robert
Pillar Data Systems, Inc.
LandOfFree
Systems and methods of searching for and determining... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods of searching for and determining..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods of searching for and determining... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4186404