Identifying snapshot membership for blocks based on snapid

Details Identifying snapshot membership for blocks based on snapid Identifying snapshot membership for blocks based on snapid

2007-03-30

2010-12-07

Jalil, Neveen Abel (Department: 2165)

Data processing: database and file management or data structures

File or database maintenance

Synchronization

C707S637000, C707S638000

Reexamination Certificate

active

07849057

ABSTRACT:
An on-disk structure of a file system has the capability to efficiently manage and organize data containers, such as snapshots, stored on a storage system. A multi-bit, monotonically increasing, snapshot identifier (“snapid”) is provided that represents a snapshot and that increases every time a snapshot is generated for a volume of the storage system. The snapid facilitates organization of snapshot metadata within, e.g., a data structure used to organize metadata associated with snapshot data. In the illustrative embodiment, the data structure is a balanced tree structure configured to index the copy-out snapshot data blocks. The snapid is also used to determine which blocks belong to which snapshots. To that end, every block that is used in a snapshot has an associated “valid-to” snapid denoting the newest snapshot for which the block is valid. The oldest snapshot for which the block is valid is one greater than the valid-to field of the next older block at the same file block number.

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: 5530855 (1996-06-01), Satoh et al.
patent: 5581724 (1996-12-01), Belsan et al.
patent: 5819292 (1998-10-01), Hitz et al.
patent: 6061770 (2000-05-01), Franklin
patent: 6081875 (2000-06-01), Clifton et al.
patent: 6341341 (2002-01-01), Grummon et al.
patent: 7076509 (2006-07-01), Chen et al.
patent: 7111021 (2006-09-01), Lewis et al.
patent: 7127577 (2006-10-01), Koning et al.
patent: 7409494 (2008-08-01), Edwards et al.
patent: 7454445 (2008-11-01), Lewis et al.
patent: 7587431 (2009-09-01), Rao et al.
patent: 2002/0083037 (2002-06-01), Lewis et al.
patent: 2005/0027748 (2005-02-01), Kisley
patent: 2005/0066095 (2005-03-01), Mullick et al.
patent: 2005/0138212 (2005-06-01), Yang
patent: 2005/0138312 (2005-06-01), Kubo et al.
patent: 2005/0193245 (2005-09-01), Hayden et al.
patent: 2005/0216535 (2005-09-01), Saika et al.
patent: 2005/0216788 (2005-09-01), Mani-Meitav et al.
patent: 2008/0059541 (2008-03-01), Fachan et al.
Corbett et al., “File System Capable of Generating Snapshots and Providing Fast Sequential Read Access”, U.S. Appl. No. 11/693,057, filed Mar. 29, 2007, 34 pages.
Corbett et al., “Maintaining Snapshot and Active File System Metadata in an On-Disk Structure of a File System”, U.S. Appl. No. 11/693,061, filed Mar. 29, 2007, 37 pages.
Hitz, Dave et al.,File System Design for an NFS File Server Appliance, Technical Report 3002, Rev. C395, presented Jan. 19, 1994.
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 14th VLDB Conference, LA, CA 1988.
Chaudhuri, Surajit, et al., Self-Tuning Technology in Microsoft SQL Server, Data Engineering Journal 22, 2 1999 pp. 20-27.
Chutani, Sailesh, et al., The Episode File System, In Proceedings of the USENIX Winter 1992.
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.
Gray, Jim, et al., The Recovery Manager of the System R Database Manager, ACM Computing Surveys, (13)2:223-242 1981.
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.
Howard, John, H. et al., Scale and Performance in a Distributed File System, Carnegie Mellon University, CMU-ITC-87-068, Aug. 1987.
Howard, John H., An Overview of the Andrew File System, Carnegie Mellon University, CMU-ITC-88-062 1988.
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 Leon, Synchronization and Caching Issues in the Andrew File System, Carnegie Mellon University, CMU-ITC-88-063.
Kazar, Michael L., et al., DEcorum File System Architectural Overview, USENIX Summer Conference, Anaheim, California, 1990.
Kemper, Alfons, et al., Performance Tuning for SAP R/3, Data Engineering Journal 22, 2 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 Syst., vol. 2, Mar. 1977, pp. 91-104.
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.
Patterson, D., et al., A Case for Redundant Arrays of Inexpensive Disks (RAID), Technical Report, CSD-87-391, Computer Science Division, Electrical Engineering and Computer Sciences, University of California at Berkeley 1987.
Patterson, D., et al., A Case for Redundant Arrays of Inexpensive Disks (RAID), SIGMOD International Conference on Management of Data, Chicago, IL, USA, Jun. 1-3, 1988, SIGMOD Record (17)3:109-16 Sep. 1988.
Peterson, Zachary Nathaniel Joseph, Data Placement for Copy-on-Write Using Virtual Contiguity, University of CA, Santa Cruz, Master's Thesis for the Department of Science in Computer Science, Sep. 2002.
Quinlan, Sean, A Cached WORM File System, Software-Practice and Experience, 21(12):1289-1299 1991.
Rosenblum, Mendel, et al., The LFS Storage Manager, Computer Science Division, Electrical Engineering and Computer Sciences, Univ. of CA, presented at Summer '90 USENIX Technical Conference, Anaheim, CA Jun. 1990.
Rosenblum, Mendel, et al. The Design and Implementation of a Log-Structured File System Jul. 24, 1991 pp. 1-15.
Rosenblum, Mendel, The Design and Implementation of a Log-Structured File System, 1992 pp. 1-93.
Rosenblum, Mendel, et al., The Design and Implementation of a Log-Structured File System, In Proceedings of ACM Transactions on Computer Systems, (10)1:26-52, Feb. 1992.
Schiefer, Berni, et al., DB2 Universal Database Performance Tuning, Data Engineering Journal 22, 2 1999 pp. 12-19.
Seltzer, Margo I., et al., Journaling Versus Soft Updates: Asynchronous Meta-Data Protection in File Systems, Proceedings of 200 USENIX Annual Technical Conference, Jun. 18-23, 2000.
Shasha, Dennis, Tuning Time Series Queries in Finance: Case Studies and Recommendations, Data Engineering Journal 22, 2 1999 pp. 41-47.
Sidebotham, Bob, Volumes: The Andrew File System Data Structuring Primitive, EEUG Conference Proceedings, Manchester, UK, Autumn 1986.
Subramanian, Muralidhar, et al., Performance Challenges in Object-Relational DBMSs, Data Engineering Journal 22, 2 1999 pp. 28-32.
Weikum, Gerhard, et al., Towards Self-Tuning Memory Management for Data Servers, Data Engineering Journal 22, 2 1999 pp. 3-11.
West, Michael, et al. The ITC Distributed File System: Prototype and Experience, Carnegie-Mellon University, Technical Report CMU-ITC-040, Mar. 1985.
Zayas, Edward R., AFS-3 Programmer's Reference: Architectural Overview, Transarc Corporation, Pittsburgh, PA, 1.0 edition 1991.
Non-Final Office Action, U.S. Appl. No. 11/693,061, mail date Aug. 27, 2009, 16 pages.
Final Office Action, U.S. Appl. No. 11/693,061, Mail Date Dec. 29, 2009, 23 pages.
Non-Final Office Action, U.S. Appl. No. 11/693,057, Mail Date Aug. 19, 2009, 16 pages.
Final Office Action, U.S. Appl. No. 11/693,057, Mail Date Dec. 16, 2009, 19 pages.

Affiliated with

Also associated with

Rating

Identifying snapshot membership for blocks based on snapid does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Identifying snapshot membership for blocks based on snapid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Identifying snapshot membership for blocks based on snapid will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4184017