US20170293442A1 - Media Aware Distributed Data Layout - Google Patents
Media Aware Distributed Data LayoutDownload PDFInfo
- Publication number
- US20170293442A1 US20170293442A1US15/630,575US201715630575AUS2017293442A1US 20170293442 A1US20170293442 A1US 20170293442A1US 201715630575 AUS201715630575 AUS 201715630575AUS 2017293442 A1US2017293442 A1US 2017293442A1
- Authority
- US
- United States
- Prior art keywords
- vdisk
- file
- directory
- inode
- segment
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Abandoned
Links
Images
Classifications
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/0614—Improving the reliability of storage systems
- G06F3/0619—Improving the reliability of storage systems in relation to data integrity, e.g. data losses, bit errors
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0662—Virtualisation aspects
- G06F3/0667—Virtualisation aspects at data level, e.g. file, record or object virtualisation
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/0604—Improving or facilitating administration, e.g. storage management
- G06F3/0605—Improving or facilitating administration, e.g. storage management by facilitating the interaction with a user or administrator
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/10—Address translation
- G06F12/1027—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
- G06F12/1036—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] for multiple virtual address spaces, e.g. segmentation
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
- G06F13/14—Handling requests for interconnection or transfer
- G06F13/36—Handling requests for interconnection or transfer for access to common bus or bus system
- G06F13/368—Handling requests for interconnection or transfer for access to common bus or bus system with decentralised access control
- G06F13/37—Handling requests for interconnection or transfer for access to common bus or bus system with decentralised access control using a physical-position-dependent priority, e.g. daisy chain, round robin or token passing
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/10—File systems; File servers
- G06F16/13—File access structures, e.g. distributed indices
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/10—File systems; File servers
- G06F16/17—Details of further file system functions
- G06F16/176—Support for shared access to files; File sharing support
- G06F16/1767—Concurrency control, e.g. optimistic or pessimistic approaches
- G06F16/1774—Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/10—File systems; File servers
- G06F16/18—File system types
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/061—Improving I/O performance
- G06F3/0611—Improving I/O performance in relation to response time
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0638—Organizing or formatting or addressing of data
- G06F3/0643—Management of files
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0638—Organizing or formatting or addressing of data
- G06F3/0644—Management of space entities, e.g. partitions, extents, pools
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0646—Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
- G06F3/065—Replication mechanisms
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0655—Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
- G06F3/0659—Command handling arrangements, e.g. command buffers, queues, command scheduling
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0662—Virtualisation aspects
- G06F3/0665—Virtualisation aspects at area level, e.g. provisioning of virtual or logical volumes
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
- G06F3/067—Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
- G06F3/0671—In-line storage system
- G06F3/0673—Single storage device
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
- G06F3/0671—In-line storage system
- G06F3/0683—Plurality of storage devices
- G06F3/0689—Disk arrays, e.g. RAID, JBOD
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/10—Address translation
- G06F12/109—Address translation for multiple virtual address spaces, e.g. segmentation
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/14—Protection against unauthorised use of memory or access to memory
- G06F12/1416—Protection against unauthorised use of memory or access to memory by checking the object accessibility, e.g. type of access defined by the memory independently of subject rights
- G06F12/145—Protection against unauthorised use of memory or access to memory by checking the object accessibility, e.g. type of access defined by the memory independently of subject rights the protection being virtual, e.g. for virtual blocks or segments before a translation mechanism
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/953—Organization of data
- Y10S707/956—Hierarchical
Definitions
- the present inventionis related to the storage of a file system on a plurality of segments, each of which has a different class of service.
- references to the present invention” or “invention”relate to exemplary embodiments and not necessarily to every embodiment encompassed by the appended claims.
- the present inventionconstructs said file system from multiple sub-file systems (vdisks), with operations involving multiple vdisks providing atomicity using a persistent operations table to record partial operation state.
- This inventiondivides a file system into a number of pools of inodes, otherwise called vdisks, and within each inode pool, data is stored in multiple segments, each potentially with a different class of service. Automated policies can choose the appropriate segment for different files, or even different portions of a file, chosen either statically or dynamically.
- Each inode poolcan be served by a separate processor in a multiprocessor system, limiting the amount of inter-processor communication within a file system to communication between inode pools. And each inode pool can be checked for consistently independently, greatly reducing the amount of computation and IO operations required to recover from even a severe system failure or software bug resulting in file system inconsistency, since only the inode pool with the detected inconsistency needs to be checked and repaired.
- the present inventionpertains to a storage system.
- the systemcomprises a memory having a first segment for storing data having a first class of service, and at least a second segment for storing data having a second class of service which is different than the first class of service of the first segment.
- the systemcomprises an interface which receives a file and stores a first portion of the file in the first segment and a second portion of the file on the second segment, and retrieves a file by reading the first portion and the second portion from the first and second segment, respectively.
- the present inventionpertains to a storage system.
- the systemcomprises a plurality of vdisks, with each vdisk containing a plurality of storage segments, and each segment providing a specific class of service (CoS).
- Each vdiskstores files with data and meta data distributed among its storage segments.
- the present inventionpertains to a storage system.
- the systemcomprises a memory having multiple classes of service.
- the systemcomprises an interface for storing a file as blocks of data associated with a class of service in the memory.
- the interfacechooses the class of service for a block on a block by block basis.
- the present inventionpertains to a file system for storing a file.
- the systemcomprises a plurality of vdisks, with each vdisk having a plurality of inodes.
- Each inode of each vdiskstores data on one or more segments, with each segment having a different class of service.
- the systemcomprises a controller which stores data of a file in an inode of a vdisk, in one or more segments of that vdisk
- the present inventionpertains to a file system for storing a file; the system comprises a plurality of vdisks, and each vdisk having a plurality of inodes.
- the systemcomprises a controller including a plurality of processors, with each processor serving one or more of the vdisks.
- the present inventionpertains to a file system for storing files.
- the systemcomprises a plurality of vdisks, with each vdisk having a plurality of inodes, a plurality of inodes of at least one vdisk storing data on a plurality of segments, each segment having a different class of service.
- the systemcomprises a controller which stores data of the file in one or more segments of one vdisk.
- the present inventionpertains to a method for storing a file.
- a methodcomprises the steps of receiving the file at an interface. There is the step of storing data of the file with a controller in one or more segments of one vdisk of a plurality of vdisks, each vdisk having a plurality of inodes.
- the plurality of inodes of at least one vdiskstore data in a plurality of segments, with each segment having a different class of service.
- the present inventionpertains to a method for storing a file.
- the methodcomprises the steps of receiving the file at an interface. There is the step of storing a first portion of the file in a first segment of a memory and a second portion of the file in a second segment of the memory. There is the step of retrieving the file by reading the first portion and the second portion from the first and second segment, respectively.
- FIG. 1shows two servers, each with multiple drives, with each drive holding multiple chunks. Some chunks hold file system data, while others store RAID parity information.
- FIG. 2shows the construction of vdisk block address spaces from one or more segments.
- FIG. 3shows an alternative construction of segments from individual disk drives instead of from chunks of disk drives.
- FIG. 4shows the distribution of files and directories in a file system between multiple vdisks.
- FIG. 5shows the modular decomposition of the invention, along with the binding of processors to vdisk module instances, and the binding of vdisk instances to the set of drives each vdisk controls.
- FIG. 6shows the message traffic involved in a file or directory delete operation, in the simple case where locks are all obtained without conflict.
- FIG. 7shows the message traffic involved in a file or directory delete operation, in the case where optimistic locking fails and locks have to be obtained again in a different order.
- FIG. 8shows the message traffic involved in a hard link operation (source locked first case).
- FIG. 9shows the message traffic involved in a hard link operation (target locked first case).
- FIG. 10shows the message traffic involved in a file create/directory create or symbolic link create operation.
- FIG. 11shows the message traffic involved in a rename operation.
- FIG. 12shows the fields stored in an inode for use by the simple policy mechanism.
- FIG. 13shows the modules present in a Unix operating system including the vdisk module instances of this invention.
- FIG. 14is a block diagram of the present invention.
- the system 10comprises a memory 12 having a first segment 14 for storing data having a first class of service, and at least a second segment 16 for storing data having a second class of service which is different than the first class of service of the first segment 14 .
- the system 10comprises an interface 18 which receives a file and stores a first portion of the file in the first segment 14 and a second portion of the file on the second segment 16 , and retrieves a file by reading the first portion and the second portion from the first and second segment 14 , 16 , respectively.
- the interface 18can store the file within one or more stripes of data in the first segment 14 and within one or more stripes of data in the second segment 16 .
- the system 10can include a plurality of disks 20 and wherein the interface 18 stores each segment as a plurality of data chunks distributed among several disks 20 .
- the segmentcan include a parity strip and the interface 18 stores the parity strip in the memory 12 according to RAID techniques so if any one strip is unavailable, the data blocks can still be retrieved from the other strips and the parity strip.
- the inode describing a fileincludes meta data which keeps track of the first portion and the second.
- the meta datais preferably a Unix-style indirect block tree.
- the present inventionpertains to a storage system 10 .
- the system 10comprises a plurality of vdisks 24 .
- Each vdisk 24contains a plurality of storage segments, with each segment 24 providing a specific class of service (CoS).
- CoSclass of service
- Each vdisk 24stores files with data and meta data distributed among its storage segments.
- a first portion of the file datacan be stored in a first segment 14
- a second portion of the filecan be stored in either the first segment 14 or a second segment 16 .
- the system 10can include a plurality of vdisks 24 , and where a vdisk 24 to hold a newly created file or directory is chosen from the plurality of vdisks 24 based on a predetermined mapping into the plurality of vdisks 24 in the storage system 10 .
- the predetermined mappingcan be a round-robin assignment algorithm.
- the predetermined mappingcan choose the vdisk 24 with a largest available space, or a largest percentage of available space.
- the system 10can include a plurality of processors 26 and wherein the predetermined mapping chooses the vdisk 24 served by a least loaded processor 26 .
- Each vdisk 24can be a random collection of directories and files, and at least one file is stored in at least two segments.
- Each vdisk 24can be a random collection of directories and files, and at least two vdisks 24 hold at least one file.
- the system 10can include an interface 18 to initiate a file system 10 consistency check on an individual vdisk 24 , triggered by an indication of an inconsistency in a specific vdisk 24 .
- the present inventionpertains to a storage system 10 .
- the system 10comprises a memory 12 having multiple classes of service.
- the system 10comprises an interface 18 for storing a file as blocks of data associated with a class of service in the memory 12 , with the interface 18 choosing the class of service for a block on a block by block basis.
- the present inventionpertains to a file system 10 for storing a file.
- the system 10comprises a plurality of vdisks 24 , with each vdisk 24 having a plurality of inodes. Each inode of each vdisk 24 stores data on one or more segments, with each segment having a different class of service.
- the system 10comprises a controller 28 which stores data of a file in an inode of a vdisk 24 , in one or more segments of that vdisk 24 .
- the system 10can include a plurality of processors 26 , with each processor 26 serving at least one of the vdisks 24 .
- Each segmentcan have a plurality of chunks.
- Each segmentcan have chunks added to it dynamically over time.
- Each vdisk 24can include an inode table 30 describing each file in the vdisk 24 .
- One of the vdisks 24is preferably a root vdisk 24 .
- One of the inodes in the root vdisk 24is preferably a root inode of the file system 10 .
- the system 10can include at least one directory storing mappings of file names to inode pointers. Each inode can have a back pointer to the directory entry pointing to the inode.
- the file system 10 described in this inventionis preferably a tree, with a single top-most directory, containing a mix of files and directories. Each other directory also contains a set of files and other directories. So, the root inode is the topmost inode in the file system 10 tree, and the only directory that doesn't have a parent directory.
- Directoriesincluding the root directory, are just normal files, marked with a special file type so that they can't just be read and written by users, but can instead only have directory operations like “create file in directory” performed on them. But, like normal files, they exist in a single vdisk and have their data blocks stored in one or more segments in that vdisk.
- the present inventionpertains to a file system 10 for storing a file.
- the system 10comprises a plurality of vdisks 24 , with each vdisk 24 having a plurality of inodes.
- the system 10comprises a controller 28 including a plurality of processors 26 , with each processor 26 serving one or more of the vnodes.
- the present inventionpertains to a file system 10 for storing a file.
- the system 10comprises a plurality of vdisks 24 , with each vdisk 24 having a plurality of inodes, a plurality of inodes of at least one vdisk 24 storing data on a plurality of segments, each segment having a different class of service.
- the system 10comprises a controller 28 which stores data of the file in multiple segments of one vdisk 24 .
- the present inventionpertains to a method for storing a file.
- a methodcomprises the steps of receiving the file at an interface 18 .
- Each vdisk 24stores a plurality of inodes.
- At least one inode of at least one vdisk 24stores data in a plurality of segments, each segment having a different class of service.
- the present inventionpertains to a method for storing a file.
- the methodcomprises the steps of receiving the file at an interface 18 .
- physical disks 20 and/or RAID arraysare divided into fixed sized chunks of storage with identical or very similar performance and reliability characteristics. These chunks may store data or parity (or checksum) information. These chunks are combined into variable sized segments, each segment providing a linear disk block address space, as well as a meta data description of the class of storage provided, including RAID class, average seek time, and read and write data transfer rates. Chunks may be combined into segments by simple concatenation, as shown by the diamond or horizontally marked segments in FIG. 1 , in which chunks are concatenated sequentially in the order of their tag.
- Chunksmay also be combined with RAID parity protection, as shown by the diagonally marked or shaded segments in the same figure, where, in these examples, every three chunks of data is stored with an additional parity chunk that stores the RAID 5 parity information for those three chunks.
- the parity datais not included in the segment's linear address space, so that the linear address is comprised of the concatenation of the data chunks only.
- the linear address space of the shaded segment in FIG. 1is comprised of the ordered set of chunks ⁇ 0, 1, 2, 3, 4, 5 ⁇ .
- a chunkis the smallest part of the disk that we *assign* to one segment or another.
- a blockis the smallest addressable part of a disk for the purposes of doing *I/O*. That is, we do disk space allocation in units of chunks, but we do individual reads and writes at a more granular level.
- Segmentsare a simple block storage concept, and are combined into sparse linear address spaces called vdisks 24 .
- Different segments within a vdisk 24may have varying storage types.
- a vdisk 24also includes an inode table 30 , with each entry identified by a 64 bit inode ID, specifying the inode within the vdisk 24 .
- any inode's data or meta data blocksmay be stored on any of the segments within the vdisk 24 . For example, a policy might specify that the first megabyte of every file is allocated from a segment with very low latency, with the remaining blocks allocated from segments stored on storage with higher latencies.
- a file system 10comprises multiple vdisks 24 .
- One vdisk 24is designated the root vdisk 24 , and a designated inode within that vdisk 24 represents the root of the entire file system 10 .
- the set of the inodes within the file system 10is then the union of all of the inodes in all of the file system's 10 vdisks 24 .
- Directoriesstore mappings from file names (represented as UTF-8 strings, without loss of generality) to (vdisk 24 , inode) pairs. Each inode has a back pointer (or a set of back pointers) to the directory entry or entries pointing to the inode, to help in validating the directory entry. These back pointers also allow directory reconstruction by scanning for inodes stored in the directory, and can also be used in generating path names from inodes.
- each small boxis a chunk of storage, allocated from a drive represented by a horizontal box.
- FIG. 1contains two logical servers, possibly residing within the same computer system, the first of which supports three drives, and the second of which supports four drives.
- Each logical serverprovides storage for the chunks making up one or two segments.
- Each segmentis striped among that server's drives: server 1 stores chunks from the dotted segment, and server 2 stores chunks from the shaded and white segments.
- Each segmentprovides storage with a different class of service: the dotted segment on sever 1 provides RAID 0 storage; the shaded segment on sever 2 provides RAID 5 storage, and the white segment on server 2 provides additional RAID 0 storage.
- RAIDis implemented in this figure across chunks stored on different drives, rather than across multiple drives in their entirety. This means that for RAID segments, some of the segment's chunks store parity information instead of file system data. For example, drive 7 's leftmost shaded chunk stores parity information for chunks 0 , 1 and 2 for the shaded segment, and drive 6 's rightmost shaded chunk stores parity information for the shaded segment's chunks 5 , 4 and 3 .
- FIG. 2shows the shaded, white and dotted chunks being combined into shaded, white and dotted segments.
- the dotted and white segmentsmake up the block address space for vdisk 1 , so that files whose inodes are stored on vdisk 1 can have blocks placed on either of the these segments, as the class of service policies for that file dictate.
- This invention's ability to aggregate multiple types of segments in a single vdisk 24allows the dynamic allocation of storage with a desired CoS to portions of a file.
- Vdisk 2consists of only the shaded segment.
- each vdisk 24would typically be comprised of sets of similarly typed segments.
- Each vdisk 24provides a separate inode space, and in this example, the two vdisks 24 are combined into a single file system name space.
- the rootis a specially designated inode in a designated vdisk 24 , and files are allocated out of each vdisk 24 on either a random, or a policy-driven, basis as new files and directories are created. It is not expected to move files between vdisks 24 frequently, or even transparently; changing the class of service of all or part of a file is accomplished not by changing a file's vdisk 24 , but by migrating a file's individual blocks to those segments within the file's original vdisk 24 providing the desired class of service. Overall load balancing can be accomplished by moving the responsibility for processing entire vdisks 24 between processors 26 or systems 10 .
- vdisk 1is actually comprised of storage (segments) controlled by both server 1 and server 2 .
- a file allocated on vdisk 1could have its blocks allocated half from the diagonally marked segment, and half from the shaded segment.
- vdisk 1 's ownerneeds to read or write data on another logical server, it does so by sending a request to that server to perform the read or write operation on its behalf. This flexibility allows one to build loosely coupled servers serving a single file system 10 .
- vdisks 24have owning processes that control the meta data operations for all segments within that vdisk 24 . Each segment has its own controlling process performing its basic read and write operations. In some cases, the process controlling a vdisk 24 is the same as the process controlling all of that vdisk's 24 segments, but this need not be the case in general.
- FIG. 3shows segments comprised of entire RAID groups, with each RAID group made from chunks comprised of entire disk drives.
- the segmentsare mapped into the vdisk 24 address space sparsely, to provide room for additional growth in an existing segment.
- FIG. 4shows the mapping between a file system directory structure and a collection of vdisks 24 .
- vdisk 1(the horizontal stripes) holds the root directory, and stores references to another set of directories, some of which are located on the same vdisk 24 and some of which are stored on vdisk 2 .
- Each of those directoriesin turn store references to some files (in this example), again, some of which are on the same vdisk 24 as the parent directory, and some of which are on a different vdisk 24 .
- each object within a directorymay be located on any vdisk 24 in the system 10 , whether or not it is the same vdisk 24 as holds the directory.
- Meta data operations that affect a single fileare typically done by a designated vdisk 24 owner, typically updating local or remote (preferentially local) segments containing the appropriate meta data.
- This architectureallows several different forms of striping.
- the files within a directorywill typically be striped among multiple vdisks 24 , allowing concurrent data and meta data operations on different files within even a single directory.
- a file's blockscan be allocated from multiple segments, each controlled by a different server, and allowing multiple processes to perform IO operations for different portions of even a single file.
- vdisk 24 operationsaffect multiple files, located in multiple vdisks 24 . All of these operations, either affecting one or affecting more than one vdisk 24 , are described below.
- the vdisk 24 interface 18plugs into a standard Unix operating system kernel just below the vnode layer, with a thin glue layer mapping incoming vnode calls from the kernel into the vdisk 24 operations described here. This glue layer is described in detail below, but every significant vnode operation has a corresponding vdisk 24 layer operation.
- FIG. 5a file create followed by a write of new data to the newly created file is described.
- the figureillustrates a system 10 with two processors 26 .
- Processor 1has software ownership of drives 1 and 2 (the horizontal boxes below the processor 26 ), containing two segments, A and B. Segments A and B provide storage to vdisk 1 , which stores a subset of the inodes in the single file system 10 exported in this example.
- processor 2has ownership of drives 3 and 4 , which collectively store segment C. Segment C is the sole segment providing storage for vdisk 2 , which stores the remainder of the inodes in this exported file system 10 . All operations on vdisk 1 , segments A and B, and drives 1 and 2 , are performed by processor 1 , while all operations on vdisk 2 , segment C and drives 3 and 4 are performed by processor 2 .
- a file create request from the protocol servers (NFSv3 and CIFS servers in FIG. 13 ), through a vnode shim layer, and finally into the top of the vdisk layer as a file create requestcontains a file handle identifying the directory in which to create the file, and also contains the name of the file to be created.
- the create operationreturns the file handle of the newly created file.
- FIG. 13shows how file system 10 requests enter the system 10 .
- the file create requestbegins by consulting a vdisk 24 location service, accessible from any processor 26 , to determine the current owner of the target vdisk 24 storing the directory in which the new file is to be created; the target vdisk 24 can be located in a subfield of the incoming directory file handle.
- the create requestis then forwarded to the processor 26 owning this vdisk 24 . If it is assumed the target directory resides on vdisk 1 , then the file create request begins execution on processor 1 .
- the vdisk 24 module for vdisk 1will choose the vdisk 24 to hold the file to be created, based upon policies such as load balancing or balancing the space used by the various vdisks 24 . In this example, it is assumed the policy module chooses vdisk 2 to hold the new file. Since the file create operation needs to atomically create a file by changing both the directory's vdisk 24 , and the new file's vdisk 24 , the create operation begins by creating a transaction entry in the directory vdisk's 24 (vdisk 1 's) persistent operations table (POT) 22 , storing the parameters of the operation tagged with a unique transaction ID.
- POTpersistent operations table
- this informationcan be used to restart the operation.
- the first vdisk 24then sends a perform-object-create operation to the second vdisk 24 , with this same transaction ID.
- the second vdisk 24now creates a file in its inode table 30 , updating storage in segment C.
- vdisk 2creates its own POT 22 entry in its own POT 22 , tagged by the same transaction ID, and giving the inode number of the created object.
- This object's file handle(derived from its inode number) is passed back in the perform-object-create's response to vdisk 1 .
- the create operation in vdisk 1running again on processor 1 , completes the new directory entry so that it stores both the new file name and the newly created file's inode number. It then marks the POT 22 entry for this operation as complete. Cleanup of the POT 22 entries is described below.
- vdisk 1needs to update the contents of the new file's parent directory. It does this by updating disk blocks on either segment A or segment B, depending upon the directory's associated storage policy.
- vdisk 2allocates an inode by writing to segment C.
- the invention's ability to create files on an arbitrary, policy specified, vdisk 24greatly simplifies load balancing in the system 10 , since no administrator defined volume boundaries between vdisks 24 exist.
- This descriptionalso illustrates how a storage policy associated with a directory can guide the vdisk's 24 write operation to choose a storage segment with the desired class of service, allowing a policy to specify a different class of service at as fine a level of granularity as an individual disk block.
- the write requestspecifies the file to update by file handle.
- the write requestwill be received by an arbitrary processor 26 , and since the file was created on vdisk 2 , the request will be forwarded to vdisk 2 's processor 26 , which is processor 2 . That processor 26 will call vdisk 2 's write operation, which will allocate a block from segment C (the policy module will not have much to do in this case, since there is only one segment to choose from), and then write the updated data to drive 3 or drive 4 , as required.
- the vdisk 24 operationsare divided into three classes. The first set consists of simple operations that affect a single file at a time. The second set consists of operations that read the contents of directories, either to lookup an individual object, or to read the contents of a directory, possibly returning file attributes simultaneously. Finally, a third set of operations consists of operations that modify directories, by creating, deleting or renaming file objects within the directory or directories.
- Increased concurrency compared with the state of the artcan be obtained for operations in the first set above easily by executing the operations for each vdisk 24 on a separate processor 26 . Since these operations require no shared state between different vdisks 24 , the operations can execute completely concurrently on separate vdisks 24 . Similarly, the second set of operations either operates on a single vdisk 24 as well (the readdir operation), or naturally decomposes into two separate operations which run first on one vdisk 24 and then on another (lookup, readdirplus), which can also run with high concurrency.
- One of the key innovations of this inventionis the implementation of directory modifying operations as multi-stage operations, where each stage affects a single vdisk 24 , and where the overall operation and its progress is recorded persistently so that the operation is performed atomically, and can complete successfully even if multiple processors 26 involved in the operation repeatedly restart during the operation; this is described further below.
- the vdisk 24 interface 18exports a set of simple operations affecting a single file or directory, which are very straightforward to implement in this invention. Each operation is performed on a single file, and reads or updates either the status of the file or its data blocks. Any vdisk 24 implementation that supports inode structures comparable to the FreeBSD operating system's UFS file system can use the inodes stored in a file system 10 as a vdisk 24 implementation for these operations.
- the vdisk 24 interface 18includes the following single file operations:
- the write operationties into the choice of segment for a file.
- the implementation of a write operationwill create dirty buffers in the memory 12 cache that are tagged by the inode identifying the file, and the offset within the file at which the data is located.
- a background “cleaner” thread within the vdisk 24 modulewill examine the inode for its link to a predetermined class of service policy. This policy might be, for example, that the first N megabytes of a file's data should be written to the segment in the vdisk 24 with the lowest read and write latency, and the remaining data should be written to the segment with the largest available free space; this would be an example of a static policy, since the parameters of the policy are defined once, and then followed for multiple files.
- the cleanerwould then allocate blocks of data for the dirty buffers from the vdisk's 24 segments according to the inode's policy and then write the dirty data to those newly allocated blocks.
- a more dynamic policymight write the most heavily accessed small files to a segment comprised of flash, or other low latency storage. In this case, some simple per-inode statistics would need to be gathered by the vdisk 24 manager so that the policies for heavily accessed files could be applied to the correct set of files.
- Two vdisk 24 operationslookup and readdirplus, interpret the contents of a directory, while also returning the attributes associated with one or more files in that directory.
- the lookup operationsearches the directory for an entry with a specific name, and returns the file's inode number (which, when qualified with the vdisk's 24 ID, gives the file's file handle), along with the file's attributes.
- the implementation of the vdisk lookup operationwill send a vdisk 24 getattr call to the vdisk 24 server, and return the attributes of the file along with the rest of the vnode lookup results. Making this call to the vdisk server 24 allows the lookup call to handle the case where the target file is located in another vdisk 24 .
- readdirplusreturns a set of file names, along with the attributes of each of the files.
- Each separate file's attributesmay, as in the lookup case, come from a different vdisk 24 , and, as with lookup, the attributes for these files come from vdisk 24 getattr cals made to the other vdisk(s) 24 .
- Directory modification operationsare considerably more complex, in that they involve modifying multiple vdisks 24 atomically. To implement these multi-stage operations atomically, they are implemented as transactions, and make use of a persistent operations table (the POT 22 ) in each vdisk 24 .
- the POT 22 entrystores the status of each complex operation, as well as any lock state involved in the operation.
- Each operationis implemented as a persistent state machine, recording the current state in the persistent operations table (POT 22 ). For a given operation, each vdisk 24 stores its own POT 22 entry for its portion of the transaction.
- Each operation in the POT 22is assigned a UUID when it first arrives at the first vdisk 24 receiving the vdisk 24 operation; this is called the primary POT 22 entry.
- the execution of the operationmay require sending requests to other vdisks 24 storing other objects modified by this vdisk 24 operation. These are called secondary requests, and their execution at a vdisk 24 may create secondary POT 22 entries in their local vdisk's persistent operations table.
- These secondary POT 22 entriesare tagged with the same request UUID, and are used to ensure that sub-components of atomic operations are executed exactly once, even in the case of multiple server crashes and restarts.
- Locks in this system 10are comprised of either a lock on an entire file handle, or a lock on a specific file name within a directory file handle. Locks on file handles conflict only if they specify the same file handle. Locks with names and file handles conflict only if both components match exactly. If one lock is a whole file handle lock and the other is a name lock, they conflict only if the file handle components match. Independent of the above, two read locks never conflict, even if the file handles would otherwise conflict.
- a vdisk delete or rmdir operationbegins at the parent directory's vdisk 24 server.
- the requestcreates a primary POT 22 entry with a new UUID, and the target file handle (including the target vdisk 24 ) is determined by doing a lookup operation on the directory.
- the requestestablishes a lock on the ⁇ parent-dir, name> mapping, and once the local lookup operation completes, the operation sends a perform-unlink-target request to the target vdisk 24 tagged with the POT 22 entry's UUID.
- the perform-unlink-target operationsets a write lock on the target file handle; a parameter to this operation tells the server whether the vdisk 24 server should wait for the lock or should instead fail the operation on a lock conflict, and for file delete, the caller sets the “wait” flag only if the target file handle follows the source directory lock in the global locking hierarchy. If, as is likely, there is no conflicting lock, the target object is locked, a secondary POT 22 entry is created with the request's UUID, the object is destroyed, the lock on the target object is released, and the perform-unlink-target operation is marked as complete.
- the requestWhile the object has been destroyed, and the operation is marked as complete, the request, tagged by UUID, stays in the persistent operation table until the operation is also completed at the primary server, to ensure that retransmissions of the perform-unlink-target operation are detected, and not re-executed.
- the primary vdisk 24removes the file name from the source directory, and drops all of its local locks. The primary removes the operation's POT 22 entry is removed from its POT 22 , and a response is sent to the originator of the request.
- the request's UUIDis batched up and sent eventually to the target object's vdisk 24 as part of a batch persistent-operation-complete request.
- the secondaryUpon receipt of this message, the secondary removes the operation from its persistent-operation-table as well, since at this point, it knows that the operation will never be retransmitted (as it has been removed from the primary server). Note that if a crash occurs before the persistent-operation-complete request has been processed, the secondary can iterate over all of its pending operations, checking with the primary vdisk 24 to see if the operation is still in progress; if the secondary finds any operations that are no longer present in the primary's POT 22 , the secondary can remove the operation from its table, as well.
- FIG. 6shows the message flow for this example.
- FIG. 6shows the behavior of the system 10 when the target succeeds at obtaining its lock, or if the target waits for its lock. It is also possible that the target failed to obtain its lock on the target file handle.
- the source vdisk 24releases its locks, and tries the operation in two phases, first locking the target, and then doing the actual work.
- the primary vdisk 24 serversends a slightly different request, prepare-unlink-target to the target.
- the prepare-unlink-targetspecifies that upon a conflict, the request should wait for the lock.
- the sourcelocks the source handle, and verifies that the name still matches the locked object.
- FIG. 7shows the behavior of the system 10 if the lock can't be obtained initially.
- the hard link operationworks fairly similarly to remove, but is simpler because all of the file handles are known at the start of the operation.
- the parameters to linkinclude a source directory and file name, and a target file handle that may be part of another vdisk 24 .
- the source vdisk 24determines the locking order between the target file and the source directory. The operation begins, as usual, by creating a request with a new UUID on the source vdisk 24 .
- the source vdisk 24locks the directory+name, and then sends a perform-link-target operation that does the locking for the link target, and updates the attributes as well (primarily the link count and ctime fields). Once the source receives the response, its local entry transitions to “complete” state and batches up a cleanup operation to the target vdisk 24 , upon receipt of which the target can remove the operation from its persistent operation table and release all of its locks.
- FIG. 8illustrates this message flow.
- the sourcethen sends it a prepare-link-target request, which locks the target file.
- the sourcethen locks the source directory+name, ensures the entry doesn't exist, and creates it.
- itsends the target a commit-link-target request.
- the targetexecutes the request, and keeps it in its POT 22 until the source contacts it, as part of a piggy-backed operation, indicating that the operation is complete and the request has been deleted. At this point, the target can remove the operation from its persistent operation table.
- FIG. 9illustrates the message flow in this case.
- the operationbegins at the directory's vdisk 24 (the primary vdisk 24 ), where the operation locks the file handle+name, and adds a new create request to the persistent operations table.
- the target vdisk 24is chosen either via a policy associated with the parent directory in which the object is being created, or via a global policy associated with the entire file system 10 . No matter what the policy's source, the policy can select a vdisk 24 on which to create the new object based on the load on the vdisk 24 , the operations/second capacity of the vdisk 24 , the space available on the segments comprising the vdisk 24 , or any other function of the state and configuration of the system's vdisks 24 .
- the target object's vdisk 24(the secondary vdisk 24 ) then receives a perform-object-create operation, telling it the type of object to create (empty directory, symbolic link, or file).
- the objectis created and the response is returned to the primary vdisk 24 , along with the identity of the newly created object.
- the primary vdisk 24then creates the directory entry with the new object name and file handle, and marks the operation as complete.
- the vdisk 24then batches up the completion notification to the secondary vdisk 24 , which removes the operation from its persistent operations table.
- FIG. 10illustrates the message flow
- vdisk 24to hold the new file, directory, or symbolic link.
- algorithmcan be chosen either as a policy associated with the parent directory, or by a more global policy, perhaps pertaining to the entire global file system 10 .
- One vdisk 24 choice functionmight be to create a new object on the vdisk 24 with the most free space, or the greatest percentage of free space; this would automatically keep space utilization balanced.
- Another vdisk 24 choice functionmight be to create a new object on the vdisk 24 with the lowest operation rate, i.e. on the vdisk 24 with the most spare capacity in operations/second.
- hybrid scoring approachesthat combine a “free space” store and a “available operations/second” score could also be used.
- the choice functioncould compute a linear combination of the two scores, and the invention could then create new objects on the vdisk 24 with the lowest hybrid score.
- Other hybrid functionsmight be include quadratic functions over the relevant scores, as well.
- vdisk 24 choice functionmight be a simple round-robin algorithm, where vdisks 24 are chosen in a repeated, circular pattern, but it is unlikely that such an approach would be optimal under any useful metric.
- the rename operationcan involve up to four separate objects: a source directory, a target directory, a source file or directory, and a target file or directory. All four, in the worst case, may be located on separate vdisks 24 . Semantically, the rename operation removes the directory entry in the source directory, and creates a new directory entry to the same object in the target directory. If an entry already exists at the target directory, it is first destroyed.
- the operationbegins at the source directory's vdisk 24 . If the source and target directories are identical, a simplified operation can be performed. The source (and thus target) directory is simply locked and the contents of the directory are updated directly. There are two cases, depending upon whether the target of the rename exists or not. If the target does not exist, then nothing changes except the directory storing the file/directory names. In this case, there is no message flow to illustrate, because all work is done by the source/target directory's vdisk 24 server.
- a renamewhere the source and target directories are the same, and where the target of the rename exists (and will be unlinked), works similarly to a file delete operation, except that the locking is a bit more complex, since there are two names to lock in the parent directory, as well as the target object's file handle.
- a locking hierarchyis chosen that orders locks by file handle first, and then by file name within the file handle (for locks that include a file name component). With this locking order, either both file names are locked in the directory before locking the target file, or both file names are locked in the directory after locking the target file.
- a rename in this casebegins by creating a POT 22 entry for the rename operation, and locking both the source and target file names within that directory. It then sends a perform-unlink-target operation to the target file's vdisk 24 (the secondary vdisk 24 ), setting the flag saying that the target should wait for the lock only if the target's file handle is ordered after the directory's file handle in the locking order. If the target succeeds at setting the lock, it creates a POT 22 entry for the rename operation, and unlinks the target. It then responds to the primary vdisk 24 , which completes the rename operation by removing the source directory entry and changing the target directory entry to point to the source file's file handle.
- the message flowis the same as for the simple file delete case illustrated in FIG. 6 . If the attempt at locking the target fails, the rename operation then drops all of its locks, and sends a prepare-unlink-target to the secondary vdisk 24 , and, upon receiving a response, then locks the parent directory's source and target file names. At this point, it verifies that the target file's identity is unchanged; if it has changed, the entire operation restarts. Otherwise, the primary vdisk 24 sends a commit-unlink-target operation to the secondary vdisk 24 , while updating the directory as in the first case.
- FIG. 7shows the message flow for this case, with the difference that the directory update is as is described above in this paragraph.
- the source directory's vdisk 24 serverbegins by creating a request that starts by sending a lookup operation to the target directory's vdisk 24 , looking up the target handle, while simultaneously locally looking up the source file handle. Once these operations complete, the identity of all objects involved in the rename operation is known, but no locks are held.
- the source vdisk 24 serverthen sends a prepare-rename-source message to the source object's vdisk 24 , locking that object; it sends a prepare-rename-target message to the target object's vdisk 24 ; and it sends a prepare-rename-tdir message to the target directory's vdisk 24 .
- Each of these operationslocks the entity in question, with the source directory's vdisk 24 locking the source directory, and sending these messages sequentially in the order required by the global locking hierarchy. Once all of the entities are locked, the source vdisk verifies that the results of the initial lookups remain unchanged; if not, the entire operation restarts.
- the prepare_rename_tdir operationperforms the target lookup verification step itself, to avoid requiring an additional message exchange.
- the sourcethen sends commit-source-object, commit-target-object and commit-target-directory operations to each of the source-object vdisk 24 , the target-object vdisk 24 , and the target-directory vdisks 24 , respectively. Once those operations have completed, the request enters the completed state at the source directory vdisk 24 , and batches up completion notifications to all of the other vdisks 24 , so they can free their state knowing that the source directory vdisk 24 will never again send operations associated with the completed request.
- FIG. 11shows the message flow in the most general version of the rename vdisk 24 operation.
- the persistent operations tableis utilized in the functioning of the above operations.
- POT 22is an example
- vdisk 1is the primary vdisk 24 , driving the distributed file system 10 operation in question.
- vdisk 1is the secondary vdisk 24 for a delete operation being driven from vdisk 30 .
- the first POT 22 entrydescribes a file create operation for a file name “foo” being created in the directory whose file handle is 1.100 (in the format ⁇ vdisk.inode>).
- the fileis being created in vdisk 2 , selected by policy rule associated with vdisk 1 .
- the operationhas run to completion, and when the response from the secondary vdisk was received, it included the actual allocated inode from vdisk 2 , specifically inode 121 , which was entered into this POT 22 entry as well.
- the operationis in “complete” state, meaning the operation completed at the secondary vdisk, and the primary vdisk has completed its work as well.
- the entryremains in the POT 22 only until the entry for this same UUID in vdisk 2 's POT 22 entry can be removed.
- the second entrydescribes a file delete operation, where the directory holding the file being deleted has file handle 1 . 102 .
- the file being deletedhas file handle 3 . 122 , which was obtained by looking up the file name “bar” in the primary directory; from its file handle we see that it is stored in vdisk 3 .
- the POT 22 entryis in “remote done” state, indicating that the secondary vdisk has freed the file, but the primary vdisk 24 has yet completed the removal of the directory entry from the primary directory itself.
- the third entry(UUID 5 ) describes a rename operation, where the source and target directories have file handles 1 . 110 and 3 . 211 , respectively.
- the file being renamedhas file handle 30 . 130 , which was determined by the primary vdisk 24 doing a lookup operation on “m”, the file's name.
- the new name for the fileis “p”, and that file already exists on vdisk 11 , with file handle 11 . 212 .
- the operationis in “remote sent” state, meaning that primary vdisk is waiting for responses from the secondary vdisks 24 before it can continue. Note that there are three remote vdisks 24 , 3 (holding the second, target directory), 30 (holding the file being renamed) and 11 (holding the file being deleted by virtue of being the target of the rename operation).
- the fourth entrydescribes a delete operation where the directory holding the file being deleted is stored on primary vdisk 30 , which is driving the delete operation for a file that happens to be stored on vdisk 1 (the secondary vdisk for this operation); the primary vdisk is requesting that this vdisk destroy that file, based on its file handle.
- the vdisk of the parent directoryis 30, and the secondary vdisk does not need to know the inode component of that file handle.
- the file being deletedhas file handle 1 . 132 , and once that file has been destroyed, a response is sent back to the primary, telling it that the operation requested by transaction ID 4 is complete.
- the entryis in “response sent” inode, meaning that the operation is complete at the secondary, and a response has been sent to the primary vdisk module.
- POT 22The primary use of the persistent operations table (POT 22 ) is in failure recovery, where a processor 26 handling one of the vdisks 24 involved in a multi-vdisk directory update fails. Essentially, a POT 22 entry acts as an intentions log entry, describing the operation to be performed, and whether that operation completed successfully or not.
- a primary vdiskwhich is the vdisk 24 at which the operation begins execution.
- the POT 22 entries created by the primary vdisk 24are called primary POT 22 entries.
- the vdisks 24 contacted by the primary vdisk 24 to perform part of a directory operationare called secondary vdisks 24 , and their POT 22 entries are called secondary POT 22 entries.
- these labelsapply to the role a vdisk 24 and its POT 22 entries play in a particular operation; thus, a vdisk 24 may be the primary vdisk 24 for a particular operation even while it is a secondary vdisk 24 for another concurrently executing operation.
- the primary POT 22 entry and its secondary POT 22 entriesare implicitly linked together by sharing the same unique transaction ID. In the example above, the first three entries are primary POT 22 entries, and the last entry is a secondary POT 22 entry.
- Each POT 22 entrymay be in one of two major states. It may be in the “executing” state, meaning that the request is currently executing, or it may be in the “complete” state, meaning that the request is finished, and has stored its results in the POT 22 entry.
- the processor 26 that created the primary POT 22fails, then upon restart, the processor 26 restarts the request, skipping the stages it has already executed, but resending any subsidiary requests to the secondary vdisks 24 . All of these retransmitted requests are resent with the original transaction ID, so that they can be matched with any already existing POT 22 entries, should the secondary vdisk 24 already have received the request before the primary's failure. If a secondary POT 22 entry indicates that the request is still in “executing” state, the secondary simply continues its execution. If there is no secondary POT 22 entry, indicating that the request has not yet executed, the new request begins execution. Finally, if the POT 22 entry is in “complete” state, the results of the operation, stored in the POT 22 entry, are sent back to the primary vdisk 24 , without re-executing the secondary request.
- a processor 26 processing a secondary POT 22 entryfails, then after recovering, if the secondary POT 22 entry is not in “complete” state, the operation is re-executed, skipping any portions that were already executed, and sending the response back to the primary vdisk 24 when the request completes. If the request is in “complete” state, the response is re-sent to the primary vdisk 24 without re-executing the request. If the primary vdisk 24 does not recognize the request's transaction ID, this means that the primary vdisk 24 had already received an earlier response from the secondary vdisk 24 , completed the primary request, and cleaned up its POT 22 entry. In this case, the secondary vdisk can delete its POT 22 entry.
- a basic disk block allocation policyis implemented by storing some descriptive tags with every segment in the system 10 . These tags are implemented as a bitmap of administrator-defined attributes. For example, an administrator might define a “low latency” attribute, a “write efficient RAID” attribute and an “archival” attribute for storage, and apply the “low latency” attribute to segments comprised of flash storage, the “write efficient RAID” attribute to segments stored in RAID 1 storage, and the “archival” attribute to segments stored in RAID 5 storage. Other, orthogonal properties could also be defined, such as “rotating media” for drive-based segments, or “slow” media for data rotating below 5400 RPM.
- each inodehas policy descriptors for three separate classes of storage used by the inode.
- One policy descriptordescribes the meta data associated with this file: in particular, the indirect blocks used for locating the file's data blocks.
- a second policy descriptorapplies to the first N blocks of the file, and the final policy descriptor describes the storage holding the remainder of the file.
- Each policy descriptormay be represented as a pair of bitmaps, a mask bitmap and a value bitmap. A segment matches one of these pairs if the segment's tag bitmap, ANDed with the policy descriptor's mask bitmap, matches the descriptor's value bitmap.
- the fields stored in each inode to represent these policiesare shows in FIG. 12 .
- the field “Initial part block count”gives the value of N above, while each of the remaining boxes hold the mask and value bitmaps describing the segments to be used for indirect block allocation, initial part data allocation, and the segment to be used for the rest of the file's data allocation.
- the policy descriptor shown in FIG. 12is inherited from the object's parent directory, and used to select storage for the data written to the newly created object.
- the inodeWhen the policy description in an inode is updated, the current data layout for the corresponding file may no longer match the updated policy. In this case, the inode is placed in a persistent queue for a background process to update the inode data's allocation to match the new policy. Similarly, when new storage is placed into service for a vdisk 24 , the existing policy descriptors may, upon re-examination, select some of the new storage to hold meta-data or normal data. In this case, all of the inodes need to be placed in a queue for a background task to verify that the inodes' block allocations still match the allocation policies.
- the administratormight add some new, very low latency storage to a vdisk's segment list, and then specify a new policy for one or more inodes to place the first 64 KB of data in that new segment.
- the system 10would do this by performing an “AddSegment” operation to add the storage to the vdisk 24 , adjusting the table describing which segments are part of the storage space for a vdisk 24 to include the new segment, possibly followed by a SetPolicy operation to specify where to use this new storage for a portion of the file system name space.
- the system 10would then internally perform a “readjust” operation on the inode or inodes in question, as the policies are updated, which would check that each block in each file whose policy is updated is allocated from a segment with the appropriate class of service. If a file fails this test, then the readjust operation would, for every block allocated from the wrong segment, allocate a block in the desired segment, copy the data from the old segment to the new segment, and adjust the indirect block pointing to the original block to point to the new block's location.
- the file's policyis consulted, and this policy specifies the desired class of service for the newly allocated blocks.
- the block allocatorthen chooses a segment with the desired CoS from among those within the file's vdisk 24 , and allocates space from that segment's block number subspace. Note that since all of the segments in a vdisk 24 reside at different locations within the same block number space, once blocks have been chosen to hold a file's newly added data blocks, the rest of the file allocation process proceeds in the same way as allocating space to files in the FreeBSD system.
- the blocks within a segmentare located via a very simple per-segment table that identifies the block number space for each segment within each vdisk 24 .
- the segment table shown belowmight specify that the dotted segment resides at vdisk 24 block offset 10000 for 5000 blocks, and that the white segment resides at vdisk 24 block offset 20000 for 3000 blocks.
- the file system 10determines the corresponding block number range for the segment, and then consults the UFS-like block allocation bitmap to determine which blocks are actually available in that segment. These block numbers are then stored in the UFS-like inodes and indirect blocks, just like the file system 10 stores any block number generated through any other block allocation algorithm used by the file system 10 .
- a global (per vdisk 24 )_policydescribes the class of service desired for the allocation of global file system meta data, such as inodes; typically, these would be allocated from relatively low latency storage.
- the internals of a system 10 designed to implement a file system 10 comprised of multiple vdisks 24is based upon implementing a set of vnode interface 18 calls on top of the vdisk 24 layer.
- Most vdisk 24 operationshave analogous vnode operations, so that the interface 18 function for those operations is very simple.
- FIG. 13shows the relationship between vnodes, vdisks 24 , and segments, in the context of a Unix operating system such as OpenSolaris running a file system 10 based on this invention.
- a Unix operating systemsuch as OpenSolaris running a file system 10 based on this invention.
- FIG. 13there is a VFS instance for each exported file system tree, and each such instance is composed of one or more vdisks 24 .
- FIG. 13it is shown how the vdisk 24 manager can fit into a standard Unix kernel.
- the figureshows three file systems 10 (and thus three name spaces).
- the first, VFS Ais comprised of files from vdisk 1 and vdisk 2 .
- the second, VFS Bis comprised of files allocated from vdisk 3 .
- the third, “Local UFS VFS”is a file system implemented from a normal Unix file system on its own local disks 20 .
- the VFS shim layerimplements a very thin layer mapping vnode operations to vdisk operations, and is described below in detail.
- VDisk ⁇ n> Secondaryrepresents the server for those internal vdisk operations, and the dashed arrows indicate that these internal vdisk operations are typically invoked by the primary vdisk implementation for some other vdisk within the same file system tree (and thus the same VFS).
- Each vdisk 24implements its own pool of inodes, and so needs to store data persistently.
- Each vdisk 24has a set of segments, accessed via the interface 18 described below, that it uses to store its persistent data. Different segments provide differing classes of service. For example, vdisk 1 has reasonably fast disk storage in a RAID 1 segment, and some extremely fast but expensive storage in a flash memory 12 segment.
- the vdisk 24may have, for example, an automatic allocation policy specifying that the first 256 KB of each file should be allocated from blocks in the flash segment, and any additional storage should be allocated from the slower disk segment. If this policy is followed, for example, sequential access to a randomly chosen set of files would be very fast, since the first 256 KB of data would be available nearly instantaneously, during which time the disk arms are positioned to transfer the remainder of the file.
- vdisks 2 and 3are compromised of a mix of relatively inexpensive RAID 5 storage, along with more expensive, but better performing RAID 1 storage.
- the vdisk interface 18consists of two sets of functions, a primary interface 18 called from the vnode layer on incoming file system calls, and a secondary interface 18 invoked by directory modifying primary vdisk operations that span multiple vdisks 24 .
- the calls in the vdisk 24 primary interface 18are typically called from the vnode layer. Many of the calls are applied to, or take, VDiskInode parameters describing the files themselves. The following describes the operations in the vdisk primary interface used by the vnode layer; some common operating system specific parameters, such as authentication credentials, have been omitted for clarity:
- VDiskInode:release( )—decrease the reference count on an inode.
- VDiskIndode:hold( )—increment the reference count on an inode.
- VDiskInode:getattr(VDiskInodeAttr *attrsp)—get attributes associated with an inode.
- VDiskInodeblockRead(uint64_t offset, uint32_t count, uint32_t flags, uint32_t *bufCount, buf **bufpp, VDiskInodeAttr *attrsp)—read data from inode starting at offset, for count bytes.
- the value *bufCount on inputspecifies the size of the bufpp array, and on output is set to the actual number of referenced buffers returned.
- the inode's attributes at the time of the readare returned in *attrsp. Note that a flag of 1 specifies that buffers should be obtained held for writing instead of reading, indicating that the operation is part of a write operation that will modify the buffers.
- VDiskInode:truncate(uint64_t offset, uint32_t count, VDiskInodeSetAttr *newAttrsp)—zero bytes from byte ‘offset’ for ‘count’ bytes. Any whole blocks that can be freed are freed.
- the newAttrsp parameteroptionally may specify updated mtime, ctime or atime values for the file.
- VDiskInode:readdir(uint64_t *cookiep, uint32_t *countp, char *resultsp, uint32_t *flagsp)—returns directory listing results, starting at an opaque value.
- *cookiepshould be 0.
- *countpgives the number of bytes available in the *resultsp buffer. Each entry consists of a 16 bit file name length, followed by a UTF-8 encoded file name, followed by a 64 bit “inode number”, followed by a 64 bit cookie value for the directory entry following this entry. An integral number of directory entries is always returned by readdir.
- the 1 bitis set in *flagsp if EOF is encountered, and no further entries will be returned. Note that *countp is updated to indicate the actual number of bytes returned, and *cookiep is updated to give the cookie value that, when passed into a new instance of this call, will return the next entry in the directory listing after those returned by this call.
- VDiskInode:readdirplus(uint64_t *cookiep, uint32_t *countp, uint32_t *entriesp, char *resultsp, VDiskInodeAttr *attrsp, uint32_t *flagsp)—This function acts like a combination of a readdir operation followed by getattr operations for each file entry returned. The parameters are the same as in readdir, with the following changes.
- the field *entriesp on entrygives the space available to hold returned attributes in the attrsp array, which points to an array of attribute structures. On exit, this field is set to the number of entries actually returned. The information returned in attrsp is ordered the same as the entries in the resultsp array.
- VDiskInodecreate(char *namep, VDisk *newVDiskp, VDiskInodeSetAttr *newAttrsp, VDiskInode **inodepp, VDiskInodeAttr *attrsp)—create a new file in the specified directory, using the new attributes specified by newAttrsp. The resulting attributes are returned in *attrsp, and a new inode is returned in *inodepp. Note that the file is created in a new vdisk specified by the newVDiskp parameter; if this parameter is null, the target vdisk is determined by consulting the policy choice module shown in FIG. 5 .
- VDiskInode:remove(char *namep, VDiskInode **inodepp, VDiskInodeAttr *attrsp)—remove a file or symbolic link from the specified directory.
- the updated object attributesare returned in *attrsp; this is meaningful for file's whose link count was decremented, but not to zero; in this case, *inodepp will also be set to a held reference to the inode in question.
- VDiskInode:mkdir(char *namep, VDisk *newVDiskp, VDiskInodeSetAttr *newAttrsp, VDiskInode **inodepp, VDiskInodeAttr *attrsp)—create a directory with the specified name, with the new attributes specified by *newAttrsp. A held reference to the newly created inode is returned in *inodepp, and the newly created file's attributes are returned in *attrsp. Note that the file is created in a new vdisk specified by the newVDiskp parameter; if this parameter is null, the target vdisk is determined by consulting the policy choice module shown in FIG. 5
- VDiskInode:symlink(char *namep, VDisk *newVDiskp, char *contentsp, VDiskInodeSetAttr *newAttrsp, VDiskInodeAttr *attrsp)—create a symbolic link named ‘namep’ with initial contents ‘contentsp’.
- the initial attributesare set from *newAttrsp, and the resulting full attributes are returned in *attrsp.
- the fileis created in a new vdisk specified by the newVDiskp parameter; if this parameter is null, the target vdisk is determined by consulting the policy choice module shown in FIG. 5 .
- VDiskInode:link(char *namep, VDiskInode *inodep, VDiskInodeAttr *attrsp)—create a hard link with name ‘namep’ in the specified directory, to the object specified by the inode *inodep. Updated attributes for the target object are returned in *attrsp, as of immediately after the operation's completion.
- VDiskInode:rename(char *snamep, VDiskInode *targetp, char *tnamep, VDiskInode **sinodep, VDiskInode **tinodep, VDiskInodeAttr *sattrp, VDiskInodeAttr *tattrp)—rename the file name ‘snamep’ in the source (applied) inode, changing its name to ‘tnamep’ in the target directory ‘targetp’.
- a read reference to the updated source inodeis returned in **sinodep
- a reference to the target inodeis returned in *tinodepp if the target object continues to exist after the unlink operation. Attributes immediately after the operation are returned in *sattrp and *tattrp for the source and target objects, respectively.
- bufsdisk buffers
- VDiskInodeAttrVDiskInodeSetAttr
- the buf structurerepresents a disk buffer. While there are many possible implementations of such a structure, the key fields that are typically present include the virtual and physical addresses of the data in the buffer, as well as a reference count, that, when zero, indicates that no processes are actively accessing the buffer.
- buf structureData char * Points to mapped in data buffer.
- VDiskInodeAttrThis gives information similar to the Unix “struct stat” structure:
- VdiskInodeAttr structureDevice uint64_t A unique value indicating the vdisk storing the file. Inode uint64_t A unique value indicating the inode with the vdisk/device corresponding to this file.
- UnixModeBitsuint16_t 16 bits of file mode as defined by POSIX file system specification (1003.1). This includes both the file type as well as the basic file protection bits.
- the VDiskInodeSetAttr structureincludes all of the fields of a VDiskInodeAttr structure, plus a single bit for each field, which is set to 1 if the value is valid in the structure, and should be set into the file's attributes, and 0 if the value should be ignored.
- This structureis passed to calls that set or change file attributes, and only the fields for which the corresponding bit is set are updated by the call.
- the POT 22 entryremains in the persistent operations table until a persistentOpComplete is received for the entry.
- the secondarymay also verify that the operation tagged with a POT 22 entry's request ID is still present at the primary; if it isn't, this means that the operation completed, the persistentOpComplete request got lost, and the secondary can and should remove the operation's entry from the POT 22 as well.
- the setAttrs parameterspecifies the type of object to be created, as well as its initial attributes.
- This operationis performed for the target directory inode, the source object inode and the target object inode for rename operations affecting two directories.
- the operationis performed on the source object inode, and, if it exists, the target object inode.
- Every operation in the vnode interface 18has a corresponding operation in the vdisk 24 interface 18 , having the same name. Most operations in the vdisk 24 interface 18 require a subset of the input parameters of the corresponding vnode operation with the same name, or return a superset of the output parameters required by the vnode operation, and so can trivially be implemented by calling the corresponding vdisk 24 operation with the underling VDiskInode object (which can even be embedded in the vnode structure used by the vnode interface 18 ).
- the segment interface 18provides operations for reading and writing file data, and reading and caching directory information. The following operations are provided:
- This callreturns a block of directory entries in a standard form from a physical offset within a directory.
- the data returnedis an integral number of records, each giving a file name (including the file name's length in bytes), and the 64 bit inode number within the vdisk 24 of the file.
- the inventionprovides two significant advantages over the state of the art today in file systems.
- First, the inventionprovides a much more flexible mechanism for changing the class of service of files, and even portions of files, than traditional file systems, both with directed attached storage and network attached storage systems.
- class of servicewe mean without restriction any property of the storage such as transfer rate, request latency, reliability or expense.
- Second, the inventionprovides a significantly simpler administrative model for file systems that can be serviced by multiple processes, for example, on a multiprocessor or on multiple systems in a clustered server. Because the invention divides a file system into an arbitrarily large number of independently servable and individually repairable components automatically, rather than by requiring the administrator to define a set of volumes, the administrative model is much simpler, and the resulting system is much easier to service.
- an administratorcould specify a policy where the first megabyte of every file would be located on segments having very low latency, perhaps comprised of very fast disks 20 or flash memory 12 .
- the remaining blockswould be allocated from normal storage vdisks 24 .
- this policywould reduce overall latency to the data in these files, since the first portion of the data would be accessible at very low latency, and during the transfer of this first portion of the data, the remaining data could be accessed from drives with a higher latency.
- this inventionprovides multiple classes of storage within the block address space used by a single pool of inodes (a vdisk 24 ), so that any file can be moved to storage with a new class of storage at any time, without changing where it resides in the file system name space.
- class of service policiesthat adjust the class of service for data stored in a file system, in this invention, can make adjustments on a block-by-block basis.
- the above systemswould all need to relocate an entire volume to make any class of service adjustments, and would furthermore be unable to make any adjustments at any granularity below that of an entire directory and its contents, while this invention can adjust data's class of service on a file by file, or even a block by block basis.
- this inventionhas the advantage that no volume boundaries have to be chosen at all—instead, data is randomly distributed among vdisks 24 .
- the class of service of the storageis associated not with the specific vdisk chosen, but with the type of segment storing the data within a particular vdisk 24 .
- disk consistency checksare run over individual vdisks 24 .
- Vdisks 24are not individually managed by administrators, so that having many vdisks 24 making up an individual file system does not add administrative complexity to the system management task.
- this inventionimproves on the state of the art for a global name space in a number of ways.
- a meta data synchronization serversuch as Red Hat's (originally Sistina's) GFS
- this systemperforms indirect block updates completely within an individual vdisk 24 , without any communication with other vdisks 24 .
- This systemalso performs directory updates on at most two vdisks 24 (except for the infrequently executed rename operation, which typically involves one vdisk 24 , but can in some complex cases involve up to four).
- this inventionAs compared with systems like IBM's AFS, the OSF's DCE/DFS and NetApp's Ontap/GX, which divide the global file system into a number of independent subtrees (volumes), this invention's scalability benefits come from its ability to divide the files within a given directory into a number of vdisks 24 , all of which can be processed independently (as opposed to the above systems, which require that all files within a single directory reside in a single volume, and thus be served by a single processor 26 system.)
- vdisk 24 creation and deletioncan be automated much more easily than volume creation and deletion (since the latter requires an administrator's choosing the volume boundaries in the global name space), this invention allows for the creation of many more vdisks 24 than the above systems, allowing automatic load balancing algorithms more flexibility to smoothly distribute vdisks 24 across processors.
- CoSclass of service management
- This inventionis believed to improve on the state of the art in a number of ways.
- the state of the art in CoS managementhas been to relocate volumes in designs such as AFS, DCE/DFS and Ontap/GX from underlying storage with one class of service to underlying storage having a different class of service.
- the weaknesses of this approachare that the granularity of the data whose CoS is changed is that of an entire volume, that all of the data within the volume are copied in order to change the CoS of any of the data, and that the volume boundaries are chosen initially to match the boundaries at which the administrator, sometime in the future, will require for CoS updates.
- volume boundaries after volume creationis both complicated and difficult to do while the data is being accessed by clients concurrently, since file handles held by client systems include a volume ID as part of that file handle. This means that operations changing volume boundaries will change client resident file handles, limiting the transparency of those operations.
- This inventiondetermines the CoS for an individual block of a file by choosing the appropriate segment from which to allocate the block, and thus operates at a lower level of abstraction than file handles. No administrative boundaries need to be determined or changed before changing a CoS policy. Furthermore, if new data with a different class of service becomes available, it can be divided into a number of segments, and each segment can be joined to existing vdisks 24 automatically, providing convenient access to the new type of storage for existing files.
- a new policycould then specify which blocks of which files should use the new storage, and that new storage could be automatically used for newly written files, while in the background, files conforming to the new policy could have their data migrated into the new.
- the ability to dynamically add new segments to a vdisk's block address spacecombined with invention's ability to allocate and reallocate file data from any of a vdisk's segments, allows a very inexpensive CoS management mechanism that can specify different classes of service at a very fine level of granularity (that of individual blocks in a file), and that can also change the class of service of an existing file continuously in the background, also on a block by block basis.
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Human Computer Interaction (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Computer Security & Cryptography (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Description
- This is a divisional of U.S. patent application Ser. No. 15/199,246 filed Jun. 30, 2016, now U.S. Pat. No. 9,696,944 which is a divisional of U.S. patent application Ser. No. 13/827,433 filed Mar. 14, 2013, now U.S. Pat. No. 9,389,806 issued on Jul. 12, 2016, which is a divisional of U.S. patent application Ser. No. 13/135,866 filed Jul. 16, 2011, now U.S. Pat. No. 8,412,742 issued on Apr. 2, 2013, which is a divisional of U.S. patent application Ser. No. 12/218,085 filed Jul. 11, 2008, now U.S. Pat. No. 8,214,404 issued on Jul. 3, 2012, all of which are incorporated by reference herein.
- The present invention is related to the storage of a file system on a plurality of segments, each of which has a different class of service. (As used herein, references to the present invention” or “invention” relate to exemplary embodiments and not necessarily to every embodiment encompassed by the appended claims.) Additionally, the present invention constructs said file system from multiple sub-file systems (vdisks), with operations involving multiple vdisks providing atomicity using a persistent operations table to record partial operation state.
- This section is intended to introduce the reader to various aspects of the art that may be related to various aspects of the present invention. The following discussion is intended to provide information to facilitate a better understanding of the present invention. Accordingly, it should be understood that statements in the following discussion are to be read in this light, and not as admissions of prior art.
- Most file systems today lack certain features useful for supporting mixed types of storage, as well as huge amounts of storage. In addition, most file systems today have meta data bottlenecks that limit their performance scaling in multi-core and distributed systems. The invention presented here is a novel file system implementation addressing these issues.
- This invention divides a file system into a number of pools of inodes, otherwise called vdisks, and within each inode pool, data is stored in multiple segments, each potentially with a different class of service. Automated policies can choose the appropriate segment for different files, or even different portions of a file, chosen either statically or dynamically.
- Each inode pool can be served by a separate processor in a multiprocessor system, limiting the amount of inter-processor communication within a file system to communication between inode pools. And each inode pool can be checked for consistently independently, greatly reducing the amount of computation and IO operations required to recover from even a severe system failure or software bug resulting in file system inconsistency, since only the inode pool with the detected inconsistency needs to be checked and repaired.
- The present invention pertains to a storage system. The system comprises a memory having a first segment for storing data having a first class of service, and at least a second segment for storing data having a second class of service which is different than the first class of service of the first segment. The system comprises an interface which receives a file and stores a first portion of the file in the first segment and a second portion of the file on the second segment, and retrieves a file by reading the first portion and the second portion from the first and second segment, respectively.
- The present invention pertains to a storage system. The system comprises a plurality of vdisks, with each vdisk containing a plurality of storage segments, and each segment providing a specific class of service (CoS). Each vdisk stores files with data and meta data distributed among its storage segments.
- The present invention pertains to a storage system. The system comprises a memory having multiple classes of service. The system comprises an interface for storing a file as blocks of data associated with a class of service in the memory. The interface chooses the class of service for a block on a block by block basis.
- The present invention pertains to a file system for storing a file. The system comprises a plurality of vdisks, with each vdisk having a plurality of inodes. Each inode of each vdisk stores data on one or more segments, with each segment having a different class of service. The system comprises a controller which stores data of a file in an inode of a vdisk, in one or more segments of that vdisk
- The present invention pertains to a file system for storing a file; the system comprises a plurality of vdisks, and each vdisk having a plurality of inodes. The system comprises a controller including a plurality of processors, with each processor serving one or more of the vdisks.
- The present invention pertains to a file system for storing files. The system comprises a plurality of vdisks, with each vdisk having a plurality of inodes, a plurality of inodes of at least one vdisk storing data on a plurality of segments, each segment having a different class of service. The system comprises a controller which stores data of the file in one or more segments of one vdisk.
- The present invention pertains to a method for storing a file. A method comprises the steps of receiving the file at an interface. There is the step of storing data of the file with a controller in one or more segments of one vdisk of a plurality of vdisks, each vdisk having a plurality of inodes. The plurality of inodes of at least one vdisk, store data in a plurality of segments, with each segment having a different class of service.
- The present invention pertains to a method for storing a file. The method comprises the steps of receiving the file at an interface. There is the step of storing a first portion of the file in a first segment of a memory and a second portion of the file in a second segment of the memory. There is the step of retrieving the file by reading the first portion and the second portion from the first and second segment, respectively.
- In the accompanying drawings, the preferred embodiment of the invention and preferred methods of practicing the invention are illustrated in which:
FIG. 1 shows two servers, each with multiple drives, with each drive holding multiple chunks. Some chunks hold file system data, while others store RAID parity information.FIG. 2 shows the construction of vdisk block address spaces from one or more segments.FIG. 3 shows an alternative construction of segments from individual disk drives instead of from chunks of disk drives.FIG. 4 shows the distribution of files and directories in a file system between multiple vdisks.FIG. 5 shows the modular decomposition of the invention, along with the binding of processors to vdisk module instances, and the binding of vdisk instances to the set of drives each vdisk controls.FIG. 6 shows the message traffic involved in a file or directory delete operation, in the simple case where locks are all obtained without conflict.FIG. 7 shows the message traffic involved in a file or directory delete operation, in the case where optimistic locking fails and locks have to be obtained again in a different order.FIG. 8 shows the message traffic involved in a hard link operation (source locked first case).FIG. 9 shows the message traffic involved in a hard link operation (target locked first case).FIG. 10 shows the message traffic involved in a file create/directory create or symbolic link create operation.FIG. 11 shows the message traffic involved in a rename operation.FIG. 12 shows the fields stored in an inode for use by the simple policy mechanism.FIG. 13 shows the modules present in a Unix operating system including the vdisk module instances of this invention.FIG. 14 is a block diagram of the present invention.- Referring now to the drawings wherein like reference numerals refer to similar or identical parts throughout the several views, and more specifically to
FIGS. 5 and 14 thereof, there is shown astorage system 10. Thesystem 10 comprises amemory 12 having afirst segment 14 for storing data having a first class of service, and at least asecond segment 16 for storing data having a second class of service which is different than the first class of service of thefirst segment 14. Thesystem 10 comprises aninterface 18 which receives a file and stores a first portion of the file in thefirst segment 14 and a second portion of the file on thesecond segment 16, and retrieves a file by reading the first portion and the second portion from the first andsecond segment - The
interface 18 can store the file within one or more stripes of data in thefirst segment 14 and within one or more stripes of data in thesecond segment 16. Thesystem 10 can include a plurality of disks20 and wherein theinterface 18 stores each segment as a plurality of data chunks distributed among several disks20. The segment can include a parity strip and theinterface 18 stores the parity strip in thememory 12 according to RAID techniques so if any one strip is unavailable, the data blocks can still be retrieved from the other strips and the parity strip. The inode describing a file includes meta data which keeps track of the first portion and the second. The meta data is preferably a Unix-style indirect block tree. - The present invention pertains to a
storage system 10. Thesystem 10 comprises a plurality ofvdisks 24. Eachvdisk 24 contains a plurality of storage segments, with eachsegment 24 providing a specific class of service (CoS). Eachvdisk 24 stores files with data and meta data distributed among its storage segments. - A first portion of the file data can be stored in a
first segment 14, and a second portion of the file can be stored in either thefirst segment 14 or asecond segment 16. Thesystem 10 can include a plurality ofvdisks 24, and where avdisk 24 to hold a newly created file or directory is chosen from the plurality ofvdisks 24 based on a predetermined mapping into the plurality ofvdisks 24 in thestorage system 10. The predetermined mapping can be a round-robin assignment algorithm. The predetermined mapping can choose thevdisk 24 with a largest available space, or a largest percentage of available space. - The
system 10 can include a plurality ofprocessors 26 and wherein the predetermined mapping chooses thevdisk 24 served by a least loadedprocessor 26. Eachvdisk 24 can be a random collection of directories and files, and at least one file is stored in at least two segments. Eachvdisk 24 can be a random collection of directories and files, and at least twovdisks 24 hold at least one file. Thesystem 10 can include aninterface 18 to initiate afile system 10 consistency check on anindividual vdisk 24, triggered by an indication of an inconsistency in aspecific vdisk 24. - The present invention pertains to a
storage system 10. Thesystem 10 comprises amemory 12 having multiple classes of service. Thesystem 10 comprises aninterface 18 for storing a file as blocks of data associated with a class of service in thememory 12, with theinterface 18 choosing the class of service for a block on a block by block basis. - The present invention pertains to a
file system 10 for storing a file. Thesystem 10 comprises a plurality ofvdisks 24, with each vdisk24 having a plurality of inodes. Each inode of each vdisk24 stores data on one or more segments, with each segment having a different class of service. Thesystem 10 comprises acontroller 28 which stores data of a file in an inode of avdisk 24, in one or more segments of thatvdisk 24. - The
system 10 can include a plurality ofprocessors 26, with eachprocessor 26 serving at least one of thevdisks 24. Each segment can have a plurality of chunks. Each segment can have chunks added to it dynamically over time. Eachvdisk 24 can include an inode table30 describing each file in thevdisk 24. One of thevdisks 24 is preferably aroot vdisk 24. One of the inodes in theroot vdisk 24 is preferably a root inode of thefile system 10. Thesystem 10 can include at least one directory storing mappings of file names to inode pointers. Each inode can have a back pointer to the directory entry pointing to the inode. - The
file system 10 described in this invention is preferably a tree, with a single top-most directory, containing a mix of files and directories. Each other directory also contains a set of files and other directories. So, the root inode is the topmost inode in thefile system 10 tree, and the only directory that doesn't have a parent directory. - Directories, including the root directory, are just normal files, marked with a special file type so that they can't just be read and written by users, but can instead only have directory operations like “create file in directory” performed on them. But, like normal files, they exist in a single vdisk and have their data blocks stored in one or more segments in that vdisk.
- The present invention pertains to a
file system 10 for storing a file. Thesystem 10 comprises a plurality ofvdisks 24, with each vdisk24 having a plurality of inodes. Thesystem 10 comprises acontroller 28 including a plurality ofprocessors 26, with eachprocessor 26 serving one or more of the vnodes. - The present invention pertains to a
file system 10 for storing a file. Thesystem 10 comprises a plurality ofvdisks 24, with each vdisk24 having a plurality of inodes, a plurality of inodes of at least onevdisk 24 storing data on a plurality of segments, each segment having a different class of service. Thesystem 10 comprises acontroller 28 which stores data of the file in multiple segments of onevdisk 24. - The present invention pertains to a method for storing a file. A method comprises the steps of receiving the file at an
interface 18. There is the step of storing data of the file with acontroller 28 in multiple segments of onevdisk 24 of a plurality ofvdisks 24. Eachvdisk 24 stores a plurality of inodes. At least one inode of at least one vdisk24 stores data in a plurality of segments, each segment having a different class of service. - The present invention pertains to a method for storing a file. The method comprises the steps of receiving the file at an
interface 18. There is the step of storing a first portion of the file in afirst segment 14 of amemory 12 and storing a second portion of the file in asecond segment 16 of thememory 12. There is the step of retrieving the file by reading the first portion and the second portion from the first andsecond segment - In the operation of the invention, physical disks20 and/or RAID arrays are divided into fixed sized chunks of storage with identical or very similar performance and reliability characteristics. These chunks may store data or parity (or checksum) information. These chunks are combined into variable sized segments, each segment providing a linear disk block address space, as well as a meta data description of the class of storage provided, including RAID class, average seek time, and read and write data transfer rates. Chunks may be combined into segments by simple concatenation, as shown by the diamond or horizontally marked segments in
FIG. 1 , in which chunks are concatenated sequentially in the order of their tag. Chunks may also be combined with RAID parity protection, as shown by the diagonally marked or shaded segments in the same figure, where, in these examples, every three chunks of data is stored with an additional parity chunk that stores theRAID 5 parity information for those three chunks. In the case of segments with parity chunks, the parity data is not included in the segment's linear address space, so that the linear address is comprised of the concatenation of the data chunks only. For example, the linear address space of the shaded segment inFIG. 1 is comprised of the ordered set of chunks {0, 1, 2, 3, 4, 5}. - A chunk is the smallest part of the disk that we *assign* to one segment or another. A block, on the other hand, is the smallest addressable part of a disk for the purposes of doing *I/O*. That is, we do disk space allocation in units of chunks, but we do individual reads and writes at a more granular level.
- Segments are a simple block storage concept, and are combined into sparse linear address spaces called
vdisks 24. Different segments within avdisk 24 may have varying storage types. Avdisk 24 also includes an inode table30, with each entry identified by a 64 bit inode ID, specifying the inode within thevdisk 24. Within avdisk 24, any inode's data or meta data blocks may be stored on any of the segments within thevdisk 24. For example, a policy might specify that the first megabyte of every file is allocated from a segment with very low latency, with the remaining blocks allocated from segments stored on storage with higher latencies. - A
file system 10 comprisesmultiple vdisks 24. Onevdisk 24 is designated theroot vdisk 24, and a designated inode within thatvdisk 24 represents the root of theentire file system 10. The set of the inodes within thefile system 10 is then the union of all of the inodes in all of the file system's10vdisks 24. - Directories store mappings from file names (represented as UTF-8 strings, without loss of generality) to (
vdisk 24, inode) pairs. Each inode has a back pointer (or a set of back pointers) to the directory entry or entries pointing to the inode, to help in validating the directory entry. These back pointers also allow directory reconstruction by scanning for inodes stored in the directory, and can also be used in generating path names from inodes. - In
FIG. 1 , each small box is a chunk of storage, allocated from a drive represented by a horizontal box.FIG. 1 contains two logical servers, possibly residing within the same computer system, the first of which supports three drives, and the second of which supports four drives. Each logical server provides storage for the chunks making up one or two segments. Each segment is striped among that server's drives:server 1 stores chunks from the dotted segment, andserver 2 stores chunks from the shaded and white segments. Each segment provides storage with a different class of service: the dotted segment on sever1 providesRAID 0 storage; the shaded segment on sever2 providesRAID 5 storage, and the white segment onserver 2 providesadditional RAID 0 storage. - Note that RAID is implemented in this figure across chunks stored on different drives, rather than across multiple drives in their entirety. This means that for RAID segments, some of the segment's chunks store parity information instead of file system data. For example, drive7's leftmost shaded chunk stores parity information for
chunks chunks FIG. 2 shows the shaded, white and dotted chunks being combined into shaded, white and dotted segments. The dotted and white segments make up the block address space forvdisk 1, so that files whose inodes are stored onvdisk 1 can have blocks placed on either of the these segments, as the class of service policies for that file dictate. This invention's ability to aggregate multiple types of segments in asingle vdisk 24 allows the dynamic allocation of storage with a desired CoS to portions of a file.Vdisk 2 consists of only the shaded segment. In common practice, when creatingseparate vdisks 24 for scalability and fault isolation reasons, eachvdisk 24 would typically be comprised of sets of similarly typed segments.- Each
vdisk 24 provides a separate inode space, and in this example, the twovdisks 24 are combined into a single file system name space. The root is a specially designated inode in a designatedvdisk 24, and files are allocated out of each vdisk24 on either a random, or a policy-driven, basis as new files and directories are created. It is not expected to move files betweenvdisks 24 frequently, or even transparently; changing the class of service of all or part of a file is accomplished not by changing a file'svdisk 24, but by migrating a file's individual blocks to those segments within the file'soriginal vdisk 24 providing the desired class of service. Overall load balancing can be accomplished by moving the responsibility for processingentire vdisks 24 betweenprocessors 26 orsystems 10. - Note that
vdisk 1 is actually comprised of storage (segments) controlled by bothserver 1 andserver 2. A file allocated onvdisk 1 could have its blocks allocated half from the diagonally marked segment, and half from the shaded segment. When vdisk1's owner needs to read or write data on another logical server, it does so by sending a request to that server to perform the read or write operation on its behalf. This flexibility allows one to build loosely coupled servers serving asingle file system 10. - In other words, vdisks24 have owning processes that control the meta data operations for all segments within that
vdisk 24. Each segment has its own controlling process performing its basic read and write operations. In some cases, the process controlling avdisk 24 is the same as the process controlling all of that vdisk's24 segments, but this need not be the case in general. - Note that alternative mechanisms for creating segments from disk storage are also possible. For example,
FIG. 3 shows segments comprised of entire RAID groups, with each RAID group made from chunks comprised of entire disk drives. As in the previous example, the segments are mapped into thevdisk 24 address space sparsely, to provide room for additional growth in an existing segment. FIG. 4 shows the mapping between a file system directory structure and a collection ofvdisks 24. In this example, vdisk1 (the horizontal stripes) holds the root directory, and stores references to another set of directories, some of which are located on thesame vdisk 24 and some of which are stored onvdisk 2. Each of those directories in turn store references to some files (in this example), again, some of which are on thesame vdisk 24 as the parent directory, and some of which are on adifferent vdisk 24. In this invention, each object within a directory may be located on anyvdisk 24 in thesystem 10, whether or not it is thesame vdisk 24 as holds the directory.- Meta data operations that affect a single file are typically done by a designated
vdisk 24 owner, typically updating local or remote (preferentially local) segments containing the appropriate meta data. - This architecture allows several different forms of striping. The files within a directory will typically be striped among
multiple vdisks 24, allowing concurrent data and meta data operations on different files within even a single directory. In addition, a file's blocks can be allocated from multiple segments, each controlled by a different server, and allowing multiple processes to perform IO operations for different portions of even a single file. - Aside from meta data operations that affect a single file, some
vdisk 24 operations affect multiple files, located inmultiple vdisks 24. All of these operations, either affecting one or affecting more than one vdisk24, are described below. - The implementation of a device to implement the
vdisk 24interface 18 is now described. Thevdisk 24interface 18 plugs into a standard Unix operating system kernel just below the vnode layer, with a thin glue layer mapping incoming vnode calls from the kernel into thevdisk 24 operations described here. This glue layer is described in detail below, but every significant vnode operation has acorresponding vdisk 24 layer operation. - Referring to
FIG. 5 , a file create followed by a write of new data to the newly created file is described. The figure illustrates asystem 10 with twoprocessors 26.Processor 1 has software ownership ofdrives 1 and2 (the horizontal boxes below the processor26), containing two segments, A and B. Segments A and B provide storage tovdisk 1, which stores a subset of the inodes in thesingle file system 10 exported in this example. Similarly,processor 2 has ownership ofdrives vdisk 2, which stores the remainder of the inodes in this exportedfile system 10. All operations onvdisk 1, segments A and B, and drives1 and2, are performed byprocessor 1, while all operations onvdisk 2, segment C and drives3 and4 are performed byprocessor 2. - A file create request from the protocol servers (NFSv3 and CIFS servers in
FIG. 13 ), through a vnode shim layer, and finally into the top of the vdisk layer as a file create request contains a file handle identifying the directory in which to create the file, and also contains the name of the file to be created. The create operation returns the file handle of the newly created file.FIG. 13 shows howfile system 10 requests enter thesystem 10. - The file create request begins by consulting a vdisk24 location service, accessible from any
processor 26, to determine the current owner of thetarget vdisk 24 storing the directory in which the new file is to be created; thetarget vdisk 24 can be located in a subfield of the incoming directory file handle. The create request is then forwarded to theprocessor 26 owning thisvdisk 24. If it is assumed the target directory resides onvdisk 1, then the file create request begins execution onprocessor 1. - The
vdisk 24 module forvdisk 1 will choose thevdisk 24 to hold the file to be created, based upon policies such as load balancing or balancing the space used by thevarious vdisks 24. In this example, it is assumed the policy module choosesvdisk 2 to hold the new file. Since the file create operation needs to atomically create a file by changing both the directory'svdisk 24, and the new file'svdisk 24, the create operation begins by creating a transaction entry in the directory vdisk's24 (vdisk1's) persistent operations table (POT)22, storing the parameters of the operation tagged with a unique transaction ID. In the event of a system failure, this information can be used to restart the operation. Thefirst vdisk 24 then sends a perform-object-create operation to thesecond vdisk 24, with this same transaction ID. Thesecond vdisk 24 now creates a file in its inode table30, updating storage in segment C. As part of this operation,vdisk 2 creates itsown POT 22 entry in itsown POT 22, tagged by the same transaction ID, and giving the inode number of the created object. This object's file handle (derived from its inode number) is passed back in the perform-object-create's response tovdisk 1. The create operation invdisk 1, running again onprocessor 1, completes the new directory entry so that it stores both the new file name and the newly created file's inode number. It then marks thePOT 22 entry for this operation as complete. Cleanup of thePOT 22 entries is described below. - As part of creating the directory entry,
vdisk 1 needs to update the contents of the new file's parent directory. It does this by updating disk blocks on either segment A or segment B, depending upon the directory's associated storage policy. Similarly, as part of allocating a new object (inode),vdisk 2 allocates an inode by writing to segment C. - This illustrates several key features of this invention. First, the invention's ability to create files on an arbitrary, policy specified,
vdisk 24, greatly simplifies load balancing in thesystem 10, since no administrator defined volume boundaries betweenvdisks 24 exist. This description also illustrates how a storage policy associated with a directory can guide the vdisk's24 write operation to choose a storage segment with the desired class of service, allowing a policy to specify a different class of service at as fine a level of granularity as an individual disk block. - Next is described the writing of a block of data to the newly created file. The write request specifies the file to update by file handle. In the example, the write request will be received by an
arbitrary processor 26, and since the file was created onvdisk 2, the request will be forwarded tovdisk 2'sprocessor 26, which isprocessor 2. Thatprocessor 26 will callvdisk 2's write operation, which will allocate a block from segment C (the policy module will not have much to do in this case, since there is only one segment to choose from), and then write the updated data to drive3 or drive4, as required. - Next, the details of the
various vdisk 24 operations provided are examined. - The vdisk24 operations are divided into three classes. The first set consists of simple operations that affect a single file at a time. The second set consists of operations that read the contents of directories, either to lookup an individual object, or to read the contents of a directory, possibly returning file attributes simultaneously. Finally, a third set of operations consists of operations that modify directories, by creating, deleting or renaming file objects within the directory or directories.
- Increased concurrency compared with the state of the art can be obtained for operations in the first set above easily by executing the operations for each vdisk24 on a
separate processor 26. Since these operations require no shared state betweendifferent vdisks 24, the operations can execute completely concurrently onseparate vdisks 24. Similarly, the second set of operations either operates on asingle vdisk 24 as well (the readdir operation), or naturally decomposes into two separate operations which run first on onevdisk 24 and then on another (lookup, readdirplus), which can also run with high concurrency. Even the third set of operations, those that modify one or more directory entries, only affect a small number of vdisks24 (typically two, but occasionally three or four), meaning that in asystem 10 with dozens ofvdisks 24, many such operations can run concurrently without creating a bottleneck on asingle vdisk 24. Again, this allows considerably improved levels of concurrency, as compared with more centralized file system architectures. - One of the key innovations of this invention is the implementation of directory modifying operations as multi-stage operations, where each stage affects a
single vdisk 24, and where the overall operation and its progress is recorded persistently so that the operation is performed atomically, and can complete successfully even ifmultiple processors 26 involved in the operation repeatedly restart during the operation; this is described further below. - Details of the implementation of these operations are provided below.
- The
vdisk 24interface 18 exports a set of simple operations affecting a single file or directory, which are very straightforward to implement in this invention. Each operation is performed on a single file, and reads or updates either the status of the file or its data blocks. Anyvdisk 24 implementation that supports inode structures comparable to the FreeBSD operating system's UFS file system can use the inodes stored in afile system 10 as avdisk 24 implementation for these operations. - The
vdisk 24interface 18 includes the following single file operations: - getattr—get the attributes of a file
- setattr—change the attributes or file length of a file
- read—read data from a file
- write—update the contents of a file, and update the inode change time (POSIX file system ctime) and data modification time (POSIX file system mtime) fields simultaneously.
- readdir—read the contents of a directory in a standard format.
- The write operation ties into the choice of segment for a file. Specifically, the implementation of a write operation will create dirty buffers in the
memory 12 cache that are tagged by the inode identifying the file, and the offset within the file at which the data is located. A background “cleaner” thread within thevdisk 24 module will examine the inode for its link to a predetermined class of service policy. This policy might be, for example, that the first N megabytes of a file's data should be written to the segment in thevdisk 24 with the lowest read and write latency, and the remaining data should be written to the segment with the largest available free space; this would be an example of a static policy, since the parameters of the policy are defined once, and then followed for multiple files. The cleaner would then allocate blocks of data for the dirty buffers from the vdisk's24 segments according to the inode's policy and then write the dirty data to those newly allocated blocks. - A more dynamic policy might write the most heavily accessed small files to a segment comprised of flash, or other low latency storage. In this case, some simple per-inode statistics would need to be gathered by the
vdisk 24 manager so that the policies for heavily accessed files could be applied to the correct set of files. - Two vdisk24 operations, lookup and readdirplus, interpret the contents of a directory, while also returning the attributes associated with one or more files in that directory.
- The lookup operation searches the directory for an entry with a specific name, and returns the file's inode number (which, when qualified with the vdisk's24 ID, gives the file's file handle), along with the file's attributes. To obtain the file attributes, the implementation of the vdisk lookup operation will send a
vdisk 24 getattr call to thevdisk 24 server, and return the attributes of the file along with the rest of the vnode lookup results. Making this call to thevdisk server 24 allows the lookup call to handle the case where the target file is located in anothervdisk 24. - Similarly, readdirplus returns a set of file names, along with the attributes of each of the files. Each separate file's attributes may, as in the lookup case, come from a
different vdisk 24, and, as with lookup, the attributes for these files come fromvdisk 24 getattr cals made to the other vdisk(s)24. - Neither lookup nor readdirplus make any guarantees about reading the directory and obtaining the file attributes atomically, so the implementation can straightforwardly be done in two steps, first reading the directory's contents, and then obtaining the target file's attributes.
- Directory modification operations are considerably more complex, in that they involve modifying
multiple vdisks 24 atomically. To implement these multi-stage operations atomically, they are implemented as transactions, and make use of a persistent operations table (the POT22) in eachvdisk 24. ThePOT 22 entry stores the status of each complex operation, as well as any lock state involved in the operation. Each operation is implemented as a persistent state machine, recording the current state in the persistent operations table (POT22). For a given operation, each vdisk24 stores itsown POT 22 entry for its portion of the transaction. - Each operation in the
POT 22 is assigned a UUID when it first arrives at thefirst vdisk 24 receiving thevdisk 24 operation; this is called theprimary POT 22 entry. The execution of the operation may require sending requests toother vdisks 24 storing other objects modified by thisvdisk 24 operation. These are called secondary requests, and their execution at avdisk 24 may createsecondary POT 22 entries in their local vdisk's persistent operations table. Thesesecondary POT 22 entries are tagged with the same request UUID, and are used to ensure that sub-components of atomic operations are executed exactly once, even in the case of multiple server crashes and restarts. - Some secondary operations set locks on files, directories, or portions of directories. Locks in this
system 10 are comprised of either a lock on an entire file handle, or a lock on a specific file name within a directory file handle. Locks on file handles conflict only if they specify the same file handle. Locks with names and file handles conflict only if both components match exactly. If one lock is a whole file handle lock and the other is a name lock, they conflict only if the file handle components match. Independent of the above, two read locks never conflict, even if the file handles would otherwise conflict. - Each class of directory modification operation in turn is now examined.
- A vdisk delete or rmdir operation begins at the parent directory's
vdisk 24 server. The request creates aprimary POT 22 entry with a new UUID, and the target file handle (including the target vdisk24) is determined by doing a lookup operation on the directory. Before doing the lookup operation, the request establishes a lock on the <parent-dir, name> mapping, and once the local lookup operation completes, the operation sends a perform-unlink-target request to thetarget vdisk 24 tagged with thePOT 22 entry's UUID. The perform-unlink-target operation sets a write lock on the target file handle; a parameter to this operation tells the server whether thevdisk 24 server should wait for the lock or should instead fail the operation on a lock conflict, and for file delete, the caller sets the “wait” flag only if the target file handle follows the source directory lock in the global locking hierarchy. If, as is likely, there is no conflicting lock, the target object is locked, asecondary POT 22 entry is created with the request's UUID, the object is destroyed, the lock on the target object is released, and the perform-unlink-target operation is marked as complete. While the object has been destroyed, and the operation is marked as complete, the request, tagged by UUID, stays in the persistent operation table until the operation is also completed at the primary server, to ensure that retransmissions of the perform-unlink-target operation are detected, and not re-executed. Once the perform-unlink-target call has completed, theprimary vdisk 24 removes the file name from the source directory, and drops all of its local locks. The primary removes the operation'sPOT 22 entry is removed from itsPOT 22, and a response is sent to the originator of the request. In addition, the request's UUID is batched up and sent eventually to the target object'svdisk 24 as part of a batch persistent-operation-complete request. Upon receipt of this message, the secondary removes the operation from its persistent-operation-table as well, since at this point, it knows that the operation will never be retransmitted (as it has been removed from the primary server). Note that if a crash occurs before the persistent-operation-complete request has been processed, the secondary can iterate over all of its pending operations, checking with theprimary vdisk 24 to see if the operation is still in progress; if the secondary finds any operations that are no longer present in the primary'sPOT 22, the secondary can remove the operation from its table, as well. FIG. 6 shows the message flow for this example.FIG. 6 shows the behavior of thesystem 10 when the target succeeds at obtaining its lock, or if the target waits for its lock. It is also possible that the target failed to obtain its lock on the target file handle. In this case, the source vdisk24 releases its locks, and tries the operation in two phases, first locking the target, and then doing the actual work. In this case, theprimary vdisk 24 server sends a slightly different request, prepare-unlink-target to the target. The prepare-unlink-target specifies that upon a conflict, the request should wait for the lock. After the primary gets the response, the source locks the source handle, and verifies that the name still matches the locked object. If it doesn't, the entire operation is restarted; otherwise the source server marks the operation as committed, and removes the entry from the directory, while concurrently telling theprepared target vdisk 24 to remove the target object, by sending it a commit-unlink-target operation. Once the removal is complete, the source vdisk24 completes the operation and removes the operation from the persistent operation table.FIG. 7 shows the behavior of thesystem 10 if the lock can't be obtained initially.- The hard link operation works fairly similarly to remove, but is simpler because all of the file handles are known at the start of the operation. The parameters to link include a source directory and file name, and a target file handle that may be part of another
vdisk 24. The source vdisk24 determines the locking order between the target file and the source directory. The operation begins, as usual, by creating a request with a new UUID on thesource vdisk 24. - If the source needs to be locked first, the source vdisk24 locks the directory+name, and then sends a perform-link-target operation that does the locking for the link target, and updates the attributes as well (primarily the link count and ctime fields). Once the source receives the response, its local entry transitions to “complete” state and batches up a cleanup operation to the
target vdisk 24, upon receipt of which the target can remove the operation from its persistent operation table and release all of its locks.FIG. 8 illustrates this message flow. - If the target needs to be locked first, the source then sends it a prepare-link-target request, which locks the target file. The source then locks the source directory+name, ensures the entry doesn't exist, and creates it. Finally, it sends the target a commit-link-target request. The target executes the request, and keeps it in its
POT 22 until the source contacts it, as part of a piggy-backed operation, indicating that the operation is complete and the request has been deleted. At this point, the target can remove the operation from its persistent operation table.FIG. 9 illustrates the message flow in this case. - Create and mkdir function similarly to each other. Because both operations create new entities, rather than dealing with existing entities that might be active, they are simpler than remove/rmdir to implement.
- The operation begins at the directory's vdisk24 (the primary vdisk24), where the operation locks the file handle+name, and adds a new create request to the persistent operations table.
- The
target vdisk 24 is chosen either via a policy associated with the parent directory in which the object is being created, or via a global policy associated with theentire file system 10. No matter what the policy's source, the policy can select avdisk 24 on which to create the new object based on the load on thevdisk 24, the operations/second capacity of thevdisk 24, the space available on the segments comprising thevdisk 24, or any other function of the state and configuration of the system'svdisks 24. - The target object's vdisk24 (the secondary vdisk24) then receives a perform-object-create operation, telling it the type of object to create (empty directory, symbolic link, or file). The object is created and the response is returned to the
primary vdisk 24, along with the identity of the newly created object. Theprimary vdisk 24 then creates the directory entry with the new object name and file handle, and marks the operation as complete. Thevdisk 24 then batches up the completion notification to thesecondary vdisk 24, which removes the operation from its persistent operations table. FIG. 10 illustrates the message flow.- Since these operations actually create new objects, one of the most important functions they perform is choosing a
vdisk 24 to hold the new file, directory, or symbolic link. There are many potential algorithms to follow here, and the specific algorithm can be chosen either as a policy associated with the parent directory, or by a more global policy, perhaps pertaining to the entireglobal file system 10. - One
vdisk 24 choice function might be to create a new object on thevdisk 24 with the most free space, or the greatest percentage of free space; this would automatically keep space utilization balanced. Anothervdisk 24 choice function might be to create a new object on thevdisk 24 with the lowest operation rate, i.e. on thevdisk 24 with the most spare capacity in operations/second. Obviously hybrid scoring approaches that combine a “free space” store and a “available operations/second” score could also be used. For example, the choice function could compute a linear combination of the two scores, and the invention could then create new objects on thevdisk 24 with the lowest hybrid score. Other hybrid functions might be include quadratic functions over the relevant scores, as well. - Of course, a very
simple vdisk 24 choice function might be a simple round-robin algorithm, where vdisks24 are chosen in a repeated, circular pattern, but it is unlikely that such an approach would be optimal under any useful metric. - The rename operation can involve up to four separate objects: a source directory, a target directory, a source file or directory, and a target file or directory. All four, in the worst case, may be located on
separate vdisks 24. Semantically, the rename operation removes the directory entry in the source directory, and creates a new directory entry to the same object in the target directory. If an entry already exists at the target directory, it is first destroyed. - The operation begins at the source directory's
vdisk 24. If the source and target directories are identical, a simplified operation can be performed. The source (and thus target) directory is simply locked and the contents of the directory are updated directly. There are two cases, depending upon whether the target of the rename exists or not. If the target does not exist, then nothing changes except the directory storing the file/directory names. In this case, there is no message flow to illustrate, because all work is done by the source/target directory'svdisk 24 server. - If the target file or directory does exist, there is a somewhat more complex operation, similar to a file delete. Specifically, a rename where the source and target directories are the same, and where the target of the rename exists (and will be unlinked), works similarly to a file delete operation, except that the locking is a bit more complex, since there are two names to lock in the parent directory, as well as the target object's file handle. A locking hierarchy is chosen that orders locks by file handle first, and then by file name within the file handle (for locks that include a file name component). With this locking order, either both file names are locked in the directory before locking the target file, or both file names are locked in the directory after locking the target file. A rename in this case begins by creating a
POT 22 entry for the rename operation, and locking both the source and target file names within that directory. It then sends a perform-unlink-target operation to the target file's vdisk24 (the secondary vdisk24), setting the flag saying that the target should wait for the lock only if the target's file handle is ordered after the directory's file handle in the locking order. If the target succeeds at setting the lock, it creates aPOT 22 entry for the rename operation, and unlinks the target. It then responds to theprimary vdisk 24, which completes the rename operation by removing the source directory entry and changing the target directory entry to point to the source file's file handle. The message flow is the same as for the simple file delete case illustrated inFIG. 6 . If the attempt at locking the target fails, the rename operation then drops all of its locks, and sends a prepare-unlink-target to thesecondary vdisk 24, and, upon receiving a response, then locks the parent directory's source and target file names. At this point, it verifies that the target file's identity is unchanged; if it has changed, the entire operation restarts. Otherwise, theprimary vdisk 24 sends a commit-unlink-target operation to thesecondary vdisk 24, while updating the directory as in the first case. Finally, theprimary vdisk 24 sends a response back to the caller, and batches a persistent-op-complete operation to clean up the state on thesecondary vdisk 24.FIG. 7 shows the message flow for this case, with the difference that the directory update is as is described above in this paragraph. - In the most complex rename case, when the source and target directories differ, the operation is significantly more complex and expensive. The source directory's
vdisk 24 server begins by creating a request that starts by sending a lookup operation to the target directory'svdisk 24, looking up the target handle, while simultaneously locally looking up the source file handle. Once these operations complete, the identity of all objects involved in the rename operation is known, but no locks are held. - The source vdisk24 server then sends a prepare-rename-source message to the source object's
vdisk 24, locking that object; it sends a prepare-rename-target message to the target object'svdisk 24; and it sends a prepare-rename-tdir message to the target directory'svdisk 24. Each of these operations locks the entity in question, with the source directory'svdisk 24 locking the source directory, and sending these messages sequentially in the order required by the global locking hierarchy. Once all of the entities are locked, the source vdisk verifies that the results of the initial lookups remain unchanged; if not, the entire operation restarts. Note that the prepare_rename_tdir operation performs the target lookup verification step itself, to avoid requiring an additional message exchange. Once all entities are prepared, locked and verified, the source then sends commit-source-object, commit-target-object and commit-target-directory operations to each of the source-object vdisk 24, the target-object vdisk 24, and the target-directory vdisks 24, respectively. Once those operations have completed, the request enters the completed state at thesource directory vdisk 24, and batches up completion notifications to all of theother vdisks 24, so they can free their state knowing that thesource directory vdisk 24 will never again send operations associated with the completed request. FIG. 11 shows the message flow in the most general version of therename vdisk 24 operation.- The persistent operations table is utilized in the functioning of the above operations. Here is an example POT22:
Primary Secondary Rename2 Rename2 UUID OpCode Dir FH FH/Name Dir FH FH/ Name Status 1 Create VDisk = 1 VDisk = 2 NA NA Complete Inode = 100 Inode = 121 Name = “foo” 2 Delete VDisk = 1 VDisk = 3 NA NA Remote Inode = 102 Inode = 122 Done Name = “bar” 5 Rename VDisk = 1 VDisk = 30 VDisk = 3 VDisk = 11 Remote Inode = 110 Inode = 130 Inode = 211 Inode = 212 Sent Name = “m” Name = “p” 4 Perform VDisk = 30 VDisk = 1 NA NA Response Unlink Inode = NA Inode = 132 Sent Target Name = NA - In the table above, a set of
POT 22 entries forvdisk 1 is shown. For the first four entries,vdisk 1 is theprimary vdisk 24, driving the distributedfile system 10 operation in question. In the last entry,vdisk 1 is thesecondary vdisk 24 for a delete operation being driven fromvdisk 30. - In more detail, the
first POT 22 entry describes a file create operation for a file name “foo” being created in the directory whose file handle is 1.100 (in the format <vdisk.inode>). The file is being created invdisk 2, selected by policy rule associated withvdisk 1. The operation has run to completion, and when the response from the secondary vdisk was received, it included the actual allocated inode fromvdisk 2, specifically inode121, which was entered into thisPOT 22 entry as well. The operation is in “complete” state, meaning the operation completed at the secondary vdisk, and the primary vdisk has completed its work as well. The entry remains in thePOT 22 only until the entry for this same UUID invdisk 2'sPOT 22 entry can be removed. - The second entry describes a file delete operation, where the directory holding the file being deleted has file handle1.102. The file being deleted has file handle3.122, which was obtained by looking up the file name “bar” in the primary directory; from its file handle we see that it is stored in
vdisk 3. ThePOT 22 entry is in “remote done” state, indicating that the secondary vdisk has freed the file, but theprimary vdisk 24 has yet completed the removal of the directory entry from the primary directory itself. - The third entry (UUID5) describes a rename operation, where the source and target directories have file handles1.110 and3.211, respectively. The file being renamed has file handle30.130, which was determined by the
primary vdisk 24 doing a lookup operation on “m”, the file's name. The new name for the file is “p”, and that file already exists onvdisk 11, with file handle11.212. The operation is in “remote sent” state, meaning that primary vdisk is waiting for responses from thesecondary vdisks 24 before it can continue. Note that there are threeremote vdisks 24,3 (holding the second, target directory),30 (holding the file being renamed) and11 (holding the file being deleted by virtue of being the target of the rename operation). - Finally, the fourth entry describes a delete operation where the directory holding the file being deleted is stored on
primary vdisk 30, which is driving the delete operation for a file that happens to be stored on vdisk1 (the secondary vdisk for this operation); the primary vdisk is requesting that this vdisk destroy that file, based on its file handle. The vdisk of the parent directory is 30, and the secondary vdisk does not need to know the inode component of that file handle. The file being deleted has file handle1.132, and once that file has been destroyed, a response is sent back to the primary, telling it that the operation requested bytransaction ID 4 is complete. Note that the entry is in “response sent” inode, meaning that the operation is complete at the secondary, and a response has been sent to the primary vdisk module. - The primary use of the persistent operations table (POT22) is in failure recovery, where a
processor 26 handling one of thevdisks 24 involved in a multi-vdisk directory update fails. Essentially, aPOT 22 entry acts as an intentions log entry, describing the operation to be performed, and whether that operation completed successfully or not. - In all of the directory modifying operations described above in this section, there is a primary vdisk, which is the
vdisk 24 at which the operation begins execution. For any given operation, thePOT 22 entries created by theprimary vdisk 24 are calledprimary POT 22 entries. Similarly, thevdisks 24 contacted by theprimary vdisk 24 to perform part of a directory operation are calledsecondary vdisks 24, and theirPOT 22 entries are calledsecondary POT 22 entries. Note that these labels apply to the role avdisk 24 and itsPOT 22 entries play in a particular operation; thus, avdisk 24 may be theprimary vdisk 24 for a particular operation even while it is asecondary vdisk 24 for another concurrently executing operation. For a given operation, theprimary POT 22 entry and itssecondary POT 22 entries are implicitly linked together by sharing the same unique transaction ID. In the example above, the first three entries areprimary POT 22 entries, and the last entry is asecondary POT 22 entry. - Each
POT 22 entry may be in one of two major states. It may be in the “executing” state, meaning that the request is currently executing, or it may be in the “complete” state, meaning that the request is finished, and has stored its results in thePOT 22 entry. - If the
processor 26 that created theprimary POT 22 fails, then upon restart, theprocessor 26 restarts the request, skipping the stages it has already executed, but resending any subsidiary requests to thesecondary vdisks 24. All of these retransmitted requests are resent with the original transaction ID, so that they can be matched with any already existingPOT 22 entries, should thesecondary vdisk 24 already have received the request before the primary's failure. If asecondary POT 22 entry indicates that the request is still in “executing” state, the secondary simply continues its execution. If there is nosecondary POT 22 entry, indicating that the request has not yet executed, the new request begins execution. Finally, if thePOT 22 entry is in “complete” state, the results of the operation, stored in thePOT 22 entry, are sent back to theprimary vdisk 24, without re-executing the secondary request. - Similarly, if a
processor 26 processing asecondary POT 22 entry fails, then after recovering, if thesecondary POT 22 entry is not in “complete” state, the operation is re-executed, skipping any portions that were already executed, and sending the response back to theprimary vdisk 24 when the request completes. If the request is in “complete” state, the response is re-sent to theprimary vdisk 24 without re-executing the request. If theprimary vdisk 24 does not recognize the request's transaction ID, this means that theprimary vdisk 24 had already received an earlier response from thesecondary vdisk 24, completed the primary request, and cleaned up itsPOT 22 entry. In this case, the secondary vdisk can delete itsPOT 22 entry. - A basic disk block allocation policy is implemented by storing some descriptive tags with every segment in the
system 10. These tags are implemented as a bitmap of administrator-defined attributes. For example, an administrator might define a “low latency” attribute, a “write efficient RAID” attribute and an “archival” attribute for storage, and apply the “low latency” attribute to segments comprised of flash storage, the “write efficient RAID” attribute to segments stored inRAID 1 storage, and the “archival” attribute to segments stored inRAID 5 storage. Other, orthogonal properties could also be defined, such as “rotating media” for drive-based segments, or “slow” media for data rotating below 5400 RPM. - In this basic policy implementation, each inode has policy descriptors for three separate classes of storage used by the inode. One policy descriptor describes the meta data associated with this file: in particular, the indirect blocks used for locating the file's data blocks. A second policy descriptor applies to the first N blocks of the file, and the final policy descriptor describes the storage holding the remainder of the file. Each policy descriptor may be represented as a pair of bitmaps, a mask bitmap and a value bitmap. A segment matches one of these pairs if the segment's tag bitmap, ANDed with the policy descriptor's mask bitmap, matches the descriptor's value bitmap. The fields stored in each inode to represent these policies are shows in
FIG. 12 . In this structure, the field “Initial part block count” gives the value of N above, while each of the remaining boxes hold the mask and value bitmaps describing the segments to be used for indirect block allocation, initial part data allocation, and the segment to be used for the rest of the file's data allocation. Thus, for example, when a data block for an offset less than N needs to be allocated by a cleaner, one of the vdisk's segments is chosen from the set of segments whose descriptive tag matches the inode's second policy descriptor. - When a new file or directory is created, the policy descriptor shown in
FIG. 12 is inherited from the object's parent directory, and used to select storage for the data written to the newly created object. - There are a number of operations used for managing policies and the files using policies.
- GetPolicy—returns the policy object associated with a file or directory.
- SetPolicy—sets the policy object associated with a file or directory.
- Recursive apply—sets the policy object for a directory, and all of its descendent directories and files.
- Note that this is an exemplary policy description, and that many others are possible, including policy descriptors that are only applied if a file's attributes (size, owner, etc) have certain values, or the file's name matches a regular expression. One might, for example, define a policy that says all files whose name match the regular expression “.*\.o” and whose size is greater than 1 MB should be stored on “archival” class storage.
- When the policy description in an inode is updated, the current data layout for the corresponding file may no longer match the updated policy. In this case, the inode is placed in a persistent queue for a background process to update the inode data's allocation to match the new policy. Similarly, when new storage is placed into service for a
vdisk 24, the existing policy descriptors may, upon re-examination, select some of the new storage to hold meta-data or normal data. In this case, all of the inodes need to be placed in a queue for a background task to verify that the inodes' block allocations still match the allocation policies. - For example, the administrator might add some new, very low latency storage to a vdisk's segment list, and then specify a new policy for one or more inodes to place the first 64 KB of data in that new segment. The
system 10 would do this by performing an “AddSegment” operation to add the storage to thevdisk 24, adjusting the table describing which segments are part of the storage space for avdisk 24 to include the new segment, possibly followed by a SetPolicy operation to specify where to use this new storage for a portion of the file system name space. Thesystem 10 would then internally perform a “readjust” operation on the inode or inodes in question, as the policies are updated, which would check that each block in each file whose policy is updated is allocated from a segment with the appropriate class of service. If a file fails this test, then the readjust operation would, for every block allocated from the wrong segment, allocate a block in the desired segment, copy the data from the old segment to the new segment, and adjust the indirect block pointing to the original block to point to the new block's location. - The preceding described the operation of the
system 10 in terms of operations on individual inodes. These inodes are implemented in a manner similar to that in which Unix systems like FreeBSD implement inodes in their UFS file system, with the exception that in this invention, a policy-based block allocator is invoked to choose the segments from which to obtain blocks to add to a file. This allocator is invoked any time that any of the operations discussed in this section need to allocate more disk blocks to an existing or new file, directory, or symbolic link. - It is assumed that when a file or directory is created, it inherits a reference to a policy object from its parent directory. This policy specifies in some manner which blocks within the file should be allocated with which CoS from among the segments making up the file's
vdisk 24. For example, one such policy might be the disk block allocator described above. - When disk blocks are later allocated to such a file, the file's policy is consulted, and this policy specifies the desired class of service for the newly allocated blocks. The block allocator then chooses a segment with the desired CoS from among those within the file's
vdisk 24, and allocates space from that segment's block number subspace. Note that since all of the segments in avdisk 24 reside at different locations within the same block number space, once blocks have been chosen to hold a file's newly added data blocks, the rest of the file allocation process proceeds in the same way as allocating space to files in the FreeBSD system. - The blocks within a segment are located via a very simple per-segment table that identifies the block number space for each segment within each
vdisk 24. For example, the segment table shown below might specify that the dotted segment resides atvdisk 24 block offset 10000 for 5000 blocks, and that the white segment resides atvdisk 24 block offset 20000 for 3000 blocks. Once a segment has been chosen for block allocation, thefile system 10 determines the corresponding block number range for the segment, and then consults the UFS-like block allocation bitmap to determine which blocks are actually available in that segment. These block numbers are then stored in the UFS-like inodes and indirect blocks, just like thefile system 10 stores any block number generated through any other block allocation algorithm used by thefile system 10. A global (per vdisk24)_policy describes the class of service desired for the allocation of global file system meta data, such as inodes; typically, these would be allocated from relatively low latency storage. - The internals of a
system 10 designed to implement afile system 10 comprised ofmultiple vdisks 24 is based upon implementing a set ofvnode interface 18 calls on top of thevdisk 24 layer. Most vdisk24 operations have analogous vnode operations, so that theinterface 18 function for those operations is very simple. FIG. 13 shows the relationship between vnodes, vdisks24, and segments, in the context of a Unix operating system such as OpenSolaris running afile system 10 based on this invention. InFIG. 13 , there is a VFS instance for each exported file system tree, and each such instance is composed of one ormore vdisks 24.- In
FIG. 13 , it is shown how thevdisk 24 manager can fit into a standard Unix kernel. The figure shows three file systems10 (and thus three name spaces). The first, VFS A, is comprised of files fromvdisk 1 andvdisk 2. The second, VFS B, is comprised of files allocated fromvdisk 3. The third, “Local UFS VFS” is a file system implemented from a normal Unix file system on its own local disks20. - The VFS shim layer implements a very thin layer mapping vnode operations to vdisk operations, and is described below in detail.
- Once a
vdisk 24 operation is invoked, somevdisk 24 operations, especially the directory modification operations described above, require performinginternal vdisk 24 operations atother vdisks 24 implementing the same VFS. For example, a file create performed on a directory within VFS A that happens to be located onvdisk 1 might create its file onvdisk 2, and thus might invoke the perform-create-target function onvdisk 2. The block labeled “VDisk <n> Secondary” represents the server for those internal vdisk operations, and the dashed arrows indicate that these internal vdisk operations are typically invoked by the primary vdisk implementation for some other vdisk within the same file system tree (and thus the same VFS). - Each
vdisk 24 implements its own pool of inodes, and so needs to store data persistently. Eachvdisk 24 has a set of segments, accessed via theinterface 18 described below, that it uses to store its persistent data. Different segments provide differing classes of service. For example,vdisk 1 has reasonably fast disk storage in aRAID 1 segment, and some extremely fast but expensive storage in aflash memory 12 segment. Thevdisk 24 may have, for example, an automatic allocation policy specifying that the first 256 KB of each file should be allocated from blocks in the flash segment, and any additional storage should be allocated from the slower disk segment. If this policy is followed, for example, sequential access to a randomly chosen set of files would be very fast, since the first 256 KB of data would be available nearly instantaneously, during which time the disk arms are positioned to transfer the remainder of the file. - Similarly,
vdisks inexpensive RAID 5 storage, along with more expensive, but better performingRAID 1 storage. - The
vdisk interface 18 consists of two sets of functions, aprimary interface 18 called from the vnode layer on incoming file system calls, and asecondary interface 18 invoked by directory modifying primary vdisk operations that spanmultiple vdisks 24. - The calls in the
vdisk 24primary interface 18 are typically called from the vnode layer. Many of the calls are applied to, or take, VDiskInode parameters describing the files themselves. The following describes the operations in the vdisk primary interface used by the vnode layer; some common operating system specific parameters, such as authentication credentials, have been omitted for clarity: - VDiskInode::release( )—decrease the reference count on an inode.
- VDiskIndode::hold( )—increment the reference count on an inode.
- VDiskInode::getattr(VDiskInodeAttr *attrsp)—get attributes associated with an inode.
- VDiskInode::setattr(VDiskInodeSetAttr *newAttrsp, VDiskInodeAttr *updatedAttrsp)—update attributes as described by newAttrsp, returning the updated attributed in *updatedAttrsp.
- VDiskInode::blockRead(uint64_t offset, uint32_t count, uint32_t flags, uint32_t *bufCount, buf **bufpp, VDiskInodeAttr *attrsp)—read data from inode starting at offset, for count bytes. The value *bufCount on input specifies the size of the bufpp array, and on output is set to the actual number of referenced buffers returned. The inode's attributes at the time of the read are returned in *attrsp. Note that a flag of 1 specifies that buffers should be obtained held for writing instead of reading, indicating that the operation is part of a write operation that will modify the buffers.
- VDiskInode::truncate(uint64_t offset, uint32_t count, VDiskInodeSetAttr *newAttrsp)—zero bytes from byte ‘offset’ for ‘count’ bytes. Any whole blocks that can be freed are freed. The newAttrsp parameter optionally may specify updated mtime, ctime or atime values for the file.
- VDiskInode::readdir(uint64_t *cookiep, uint32_t *countp, char *resultsp, uint32_t *flagsp)—returns directory listing results, starting at an opaque value. In the initial call to readdir, *cookiep should be 0. *countp gives the number of bytes available in the *resultsp buffer. Each entry consists of a 16 bit file name length, followed by a UTF-8 encoded file name, followed by a 64 bit “inode number”, followed by a 64 bit cookie value for the directory entry following this entry. An integral number of directory entries is always returned by readdir. The 1 bit is set in *flagsp if EOF is encountered, and no further entries will be returned. Note that *countp is updated to indicate the actual number of bytes returned, and *cookiep is updated to give the cookie value that, when passed into a new instance of this call, will return the next entry in the directory listing after those returned by this call.
- VDiskInode::lookup(char *namep, VDiskInode **newInodepp)—lookup the name ‘namep’ in the specified directory, returning a held reference to the target inode in *newInodepp. If the entry can't be located, a non-zero error code is returned. A return code of ENOENT is reserved for an indication that no temporary error occurred, and the file name definitely does not exist in the directory.
- VDiskInode::readdirplus(uint64_t *cookiep, uint32_t *countp, uint32_t *entriesp, char *resultsp, VDiskInodeAttr *attrsp, uint32_t *flagsp)—This function acts like a combination of a readdir operation followed by getattr operations for each file entry returned. The parameters are the same as in readdir, with the following changes. The field *entriesp on entry gives the space available to hold returned attributes in the attrsp array, which points to an array of attribute structures. On exit, this field is set to the number of entries actually returned. The information returned in attrsp is ordered the same as the entries in the resultsp array.
- VDiskInode::create(char *namep, VDisk *newVDiskp, VDiskInodeSetAttr *newAttrsp, VDiskInode **inodepp, VDiskInodeAttr *attrsp)—create a new file in the specified directory, using the new attributes specified by newAttrsp. The resulting attributes are returned in *attrsp, and a new inode is returned in *inodepp. Note that the file is created in a new vdisk specified by the newVDiskp parameter; if this parameter is null, the target vdisk is determined by consulting the policy choice module shown in
FIG. 5 . - VDiskInode::remove(char *namep, VDiskInode **inodepp, VDiskInodeAttr *attrsp)—remove a file or symbolic link from the specified directory. The updated object attributes are returned in *attrsp; this is meaningful for file's whose link count was decremented, but not to zero; in this case, *inodepp will also be set to a held reference to the inode in question.
- VDiskInode::mkdir(char *namep, VDisk *newVDiskp, VDiskInodeSetAttr *newAttrsp, VDiskInode **inodepp, VDiskInodeAttr *attrsp)—create a directory with the specified name, with the new attributes specified by *newAttrsp. A held reference to the newly created inode is returned in *inodepp, and the newly created file's attributes are returned in *attrsp. Note that the file is created in a new vdisk specified by the newVDiskp parameter; if this parameter is null, the target vdisk is determined by consulting the policy choice module shown in
FIG. 5 - VDiskInode::rmdir(char *namep)—remove the directory named ‘namep’ from the directory to which this operation is applied.
- VDiskInode::symlink(char *namep, VDisk *newVDiskp, char *contentsp, VDiskInodeSetAttr *newAttrsp, VDiskInodeAttr *attrsp)—create a symbolic link named ‘namep’ with initial contents ‘contentsp’. The initial attributes are set from *newAttrsp, and the resulting full attributes are returned in *attrsp. Note that the file is created in a new vdisk specified by the newVDiskp parameter; if this parameter is null, the target vdisk is determined by consulting the policy choice module shown in
FIG. 5 . - VDiskInode::link(char *namep, VDiskInode *inodep, VDiskInodeAttr *attrsp)—create a hard link with name ‘namep’ in the specified directory, to the object specified by the inode *inodep. Updated attributes for the target object are returned in *attrsp, as of immediately after the operation's completion.
- VDiskInode::rename(char *snamep, VDiskInode *targetp, char *tnamep, VDiskInode **sinodep, VDiskInode **tinodep, VDiskInodeAttr *sattrp, VDiskInodeAttr *tattrp)—rename the file name ‘snamep’ in the source (applied) inode, changing its name to ‘tnamep’ in the target directory ‘targetp’. A read reference to the updated source inode is returned in **sinodep, and a reference to the target inode is returned in *tinodepp if the target object continues to exist after the unlink operation. Attributes immediately after the operation are returned in *sattrp and *tattrp for the source and target objects, respectively.
- The operations above refer to the following non-opaque structures: bufs (disk buffers), VDiskInodeAttr and VDiskInodeSetAttr structures. The following tables show the contents of each of these structures:
- The buf structure represents a disk buffer. While there are many possible implementations of such a structure, the key fields that are typically present include the virtual and physical addresses of the data in the buffer, as well as a reference count, that, when zero, indicates that no processes are actively accessing the buffer.
buf structure Data char * Points to mapped in data buffer. PhysAddr char * Points to phyocation of buffer. RefCount uint32_t Reference count for buffer. - Next, the VDiskInodeAttr structure is described; this gives information similar to the Unix “struct stat” structure:
VdiskInodeAttr structure Device uint64_t A unique value indicating the vdisk storing the file. Inode uint64_t A unique value indicating the inode with the vdisk/device corresponding to this file. UnixModeBits uint16_t 16 bits of file mode as defined by POSIX file system specification (1003.1). This includes both the file type as well as the basic file protection bits. Owner uint32_t File owner's ID. Group uint32_t File's group owner. Length uint64_t File length in bytes. Access time 2 x Time file data last accessed, in uint32_t seconds and microseconds since midnight, Jan. 1, 1970 GMT. Modification time 2 x Time file data last modified, in same uint32_t format. Change time 2 x Time file attributes last changed, in uint32_t same format. Space uint64_t Space allocated for file, in bytes. - The VDiskInodeSetAttr structure includes all of the fields of a VDiskInodeAttr structure, plus a single bit for each field, which is set to 1 if the value is valid in the structure, and should be set into the file's attributes, and 0 if the value should be ignored. This structure is passed to calls that set or change file attributes, and only the fields for which the corresponding bit is set are updated by the call.
- Note that in all cases except for persistentOpComplete, the
POT 22 entry remains in the persistent operations table until a persistentOpComplete is received for the entry. At any time, the secondary may also verify that the operation tagged with aPOT 22 entry's request ID is still present at the primary; if it isn't, this means that the operation completed, the persistentOpComplete request got lost, and the secondary can and should remove the operation's entry from thePOT 22 as well. - VDisk::performUnlinkTarget(UUID requestId, VDiskInode *targetp)—
Create POT 22 entry with ID requested, then lock the file handle for inode targetp, decrement the target object's link count, and drop the file handle lock, leaving thePOT 22 entry to catch duplicate operations. - VDisk::prepareUnlinkTarget(UUID requestId, VDiskInode *targetp)—
Create POT 22 entry with ID requested, and lock the file handle for inode targetp, leaving locks set andPOT 22 entry to catch duplicate operations. - VDisk::commitUnlinkTarget(UUID requestId)—Unlink the locked object referenced from the exiting
POT 22 entry, drop the lock and return. This call expects to be applied to a requestId specifying an operation that has already performed a prepareUnlinkTarget operation, which specified the inode to be unlinked. - VDisk::performLinkTarget(UUID requestId, VDiskInode *targetp)—Create a
POT 22 entry with the specified requestId, lock the specified object, increment object's link count, drop locks and return. The entry remains in thePOT 22 until the receipt of a persistentOpComplete request with the same transaction UUID. - VDisk::prepareLinkTarget(UUID requestId, VDiskInode *targetp)—Create a
POT 22 entry with ID from requestId, lock the specified object *targetp and return. - VDisk::commitLinkTarget(UUID requestId)—Increment the link count on the object locked by the request and stored in the
POT 22 entry, update its attributes, drop the lock on the target and return. This call expected to be performed on aPOT 22 entry for which a prepareLinkTarget operation has already been successfully performed. - VDisk::performCreateTarget(UUID requestId, VDiskInode **targetpp, VDiskInodeSetAttrs setAttrs)—Create a
POT 22 entry for the request ID, allocate the target file inode (storing it in thePOT 22 entry) and return the new object's file handle to the caller. On a retransmission of this request, resend the already allocated object's file handle. The setAttrs parameter specifies the type of object to be created, as well as its initial attributes. - VDiskInode::lookup—This is the same function as present in the
primary interface 18; it can also be invoked via thesecondary interface 18. - VDisk::prepareRenameOperand(UUID requestId, VDiskInode *targetp)—
Create POT 22 entry, lock file handle of target inode, and return. This operation is performed for the target directory inode, the source object inode and the target object inode for rename operations affecting two directories. For single directory renames, the operation is performed on the source object inode, and, if it exists, the target object inode. - VDisk::commitRenameTargetDir(UUID requestId, char *namep, VDiskInode *inodep)—Update the target directory's entry for the target ‘namep’ to point to the file handle for the inode specified by inodep. Then drop all locks on inodep's file handle, and return. This call requires that a prepareRenameOperand call have been previously made with this requestId to this server.
- VDisk::commitRenameTargetFile(UUID requestId)—Update the target inode associated with the request's
POT 22 entry by decrementing its link count, then drop its locks and return. This call requires that a prepareRenameOperand call have been previously made with this requestId to this server. - VDisk::commitRenameSourceFile(UUID requestId, VDiskInode *targetDirp)—If we're renaming a directory, update the “..” pointer in the directory associated with the locked file handle (obtained via the
POT 22 entry), drop the locks and return. This call requires that a prepareRenameOperand call have been previously made with this requestId to this server. - VDisk::persistentOpComplete(UUID requestId)—This operation removes the
POT 22 entry tagged with requestId from the persistent operations table. To guard against this message being lost due to a poorly timed system crash, the secondary also periodically verifies thatold POT 22 entries are still valid by contacting the primary vdisk with the VDisk::checkOperationStatus call to determine whether thePOT 22 entry's request ID is still active. - VDisk::checkOperationStatus(UUID requestId, int *statusp)—This operation checks on the status of the transaction tagged with requestId. The value of *statusp is set, on return, to the status of the operation, that is, one of remoteSent, remoteDone, complete, or unknown. The first three are normal states recorded in a
POT 22 entry, while the last indicates that there is noPOT 22 entry with the specified transaction UUID. - Every operation in the
vnode interface 18 has a corresponding operation in thevdisk 24interface 18, having the same name. Most operations in thevdisk 24interface 18 require a subset of the input parameters of the corresponding vnode operation with the same name, or return a superset of the output parameters required by the vnode operation, and so can trivially be implemented by calling the correspondingvdisk 24 operation with the underling VDiskInode object (which can even be embedded in the vnode structure used by the vnode interface18). - The
segment interface 18 provides operations for reading and writing file data, and reading and caching directory information. The following operations are provided: - Segment::read(uint64_t offset, uint32_t count, buf *datap). This call reads the data located at the specified offset, returning it in the provided buffer. Only count bytes are transferred.
- Segment::write(uint64_t offset, uint32_t count, buf *datap). This call works like read, only the data is written from the start of the provided buffer.
- Segment::readdir(uint64_t offset, uin32_t count, buf *datap). This call returns a block of directory entries in a standard form from a physical offset within a directory. The data returned is an integral number of records, each giving a file name (including the file name's length in bytes), and the 64 bit inode number within the
vdisk 24 of the file. - Note that these calls can be executed as local calls to access drives connected to the same computer system as the caller, or as remote procedure calls to access drives connected to other computer systems.
- This invention provides two significant advantages over the state of the art today in file systems. First, the invention provides a much more flexible mechanism for changing the class of service of files, and even portions of files, than traditional file systems, both with directed attached storage and network attached storage systems. By class of service, we mean without restriction any property of the storage such as transfer rate, request latency, reliability or expense. Second, the invention provides a significantly simpler administrative model for file systems that can be serviced by multiple processes, for example, on a multiprocessor or on multiple systems in a clustered server. Because the invention divides a file system into an arbitrarily large number of independently servable and individually repairable components automatically, rather than by requiring the administrator to define a set of volumes, the administrative model is much simpler, and the resulting system is much easier to service.
- For example, with this invention, an administrator could specify a policy where the first megabyte of every file would be located on segments having very low latency, perhaps comprised of very fast disks20 or
flash memory 12. The remaining blocks would be allocated fromnormal storage vdisks 24. With an operations mix that chooses files at random and then reads each chosen file sequentially, this policy would reduce overall latency to the data in these files, since the first portion of the data would be accessible at very low latency, and during the transfer of this first portion of the data, the remaining data could be accessed from drives with a higher latency. - In many of today's storage systems, there are several options for changing the class of service of stored data. Systems like IBM's AFS, the Open Software Foundation's DCE/DFS, NetApp's Ontap GX, and Sun's ZFS provide a mechanism for moving volumes, representing subtrees of the file system name space, from one storage area to another. When the two storage areas provide different classes of storage, the administrator effectively changes the class of storage for the relevant subtree when moving the volume from one area to another. This invention improves upon this art in several ways. First, volume boundaries are administratively difficult to adjust after the creation of the volumes, while this invention does not have a comparable volume concept whose boundaries might need adjustment to match the desired class of service boundaries. Instead, this invention provides multiple classes of storage within the block address space used by a single pool of inodes (a vdisk24), so that any file can be moved to storage with a new class of storage at any time, without changing where it resides in the file system name space. Second, class of service policies that adjust the class of service for data stored in a file system, in this invention, can make adjustments on a block-by-block basis. The above systems would all need to relocate an entire volume to make any class of service adjustments, and would furthermore be unable to make any adjustments at any granularity below that of an entire directory and its contents, while this invention can adjust data's class of service on a file by file, or even a block by block basis.
- In terms of administrative model simplicity, again, comparing this invention with volume-based data architectures, this invention has the advantage that no volume boundaries have to be chosen at all—instead, data is randomly distributed among
vdisks 24. The class of service of the storage is associated not with the specific vdisk chosen, but with the type of segment storing the data within aparticular vdisk 24. - In the realm of serviceability, instead of having to run disk consistency checks over the entire file system, or over a single volume, both administratively visible concepts, in the invention, disk consistency checks are run over
individual vdisks 24.Vdisks 24 are not individually managed by administrators, so that havingmany vdisks 24 making up an individual file system does not add administrative complexity to the system management task. - In terms of meta data scalability, this invention improves on the state of the art for a global name space in a number of ways. As compared with a name space with a meta data synchronization server, such as Red Hat's (originally Sistina's) GFS, this system performs indirect block updates completely within an
individual vdisk 24, without any communication withother vdisks 24. This system also performs directory updates on at most two vdisks24 (except for the infrequently executed rename operation, which typically involves onevdisk 24, but can in some complex cases involve up to four). Whenmultiple vdisks 24 collaborate on a single directory operation, they do so by exchanging a small number of messages among themselves (as described above), where each individual operation actually executes on asingle vdisk 24. Since operations on eachvdisk 24 can be performed byseparate processors 26 without any references to data structures controlled byother vdisks 24, this architecture allows significant global file system scaling without requiring a meta data server acting as a synchronization point, via the splitting of an active file system into a moderately large number ofvdisks 24. Thus, because files are distributed amongvdisks 24 automatically, a single name space can be distributed amongmultiple processors 26 without any manual administrative intervention. - As compared with systems like IBM's AFS, the OSF's DCE/DFS and NetApp's Ontap/GX, which divide the global file system into a number of independent subtrees (volumes), this invention's scalability benefits come from its ability to divide the files within a given directory into a number of
vdisks 24, all of which can be processed independently (as opposed to the above systems, which require that all files within a single directory reside in a single volume, and thus be served by asingle processor 26 system.) In addition, becausevdisk 24 creation and deletion can be automated much more easily than volume creation and deletion (since the latter requires an administrator's choosing the volume boundaries in the global name space), this invention allows for the creation of many more vdisks24 than the above systems, allowing automatic load balancing algorithms more flexibility to smoothly distributevdisks 24 across processors. - In terms of class of service management (CoS), this invention is believed to improve on the state of the art in a number of ways. The state of the art in CoS management has been to relocate volumes in designs such as AFS, DCE/DFS and Ontap/GX from underlying storage with one class of service to underlying storage having a different class of service. The weaknesses of this approach are that the granularity of the data whose CoS is changed is that of an entire volume, that all of the data within the volume are copied in order to change the CoS of any of the data, and that the volume boundaries are chosen initially to match the boundaries at which the administrator, sometime in the future, will require for CoS updates. Changing volume boundaries after volume creation is both complicated and difficult to do while the data is being accessed by clients concurrently, since file handles held by client systems include a volume ID as part of that file handle. This means that operations changing volume boundaries will change client resident file handles, limiting the transparency of those operations. This invention, on the other hand, determines the CoS for an individual block of a file by choosing the appropriate segment from which to allocate the block, and thus operates at a lower level of abstraction than file handles. No administrative boundaries need to be determined or changed before changing a CoS policy. Furthermore, if new data with a different class of service becomes available, it can be divided into a number of segments, and each segment can be joined to existing
vdisks 24 automatically, providing convenient access to the new type of storage for existing files. A new policy could then specify which blocks of which files should use the new storage, and that new storage could be automatically used for newly written files, while in the background, files conforming to the new policy could have their data migrated into the new. In this case, in other words, the ability to dynamically add new segments to a vdisk's block address space, combined with invention's ability to allocate and reallocate file data from any of a vdisk's segments, allows a very inexpensive CoS management mechanism that can specify different classes of service at a very fine level of granularity (that of individual blocks in a file), and that can also change the class of service of an existing file continuously in the background, also on a block by block basis. - A glossary of various terms used here follows.
- Chunk—A fixed sized, contiguous portion of a single disk. Chunks may store data or checksum/parity information. Multiple chunks sharing the same class of service, or basic attributes, are concatenated into segments, a variable sized piece of storage.
- File attributes—Meta data information describing the properties of a file, including the file's length in bytes, the user ID of the owner of the file, the file's last accessed time, last modified time and last “attributes modified” time.
- Persistent Operations Table (POT22)—A per-vdisk table tracking the progress of atomic file system operations that affect a single VFS, but one or
more vdisks 24. For example, a file create or delete may affect a directory stored within onevdisk 24, and a file stored within anothervdisk 24 in the same virtual file system. The persistent operations table on eachvdisk 24 keeps track of the progress of each such file system operation. All entries describing the progress of a single atomic operation are tagged with the same operation UUID. - RAID array—An array of physical disks grouped together with some form of RAID parity scheme, and storing a number of fixed sized chunks.
- Segment—A variable length collection of a number of chunks, all sharing the same type of storage, for example,
RAID 1 storage comprised of 15K RPM disk drives. A segment can be addressed internally by a virtual 64 bit block pointer; these addresses only map to the data chunks of a segment, not the parity chunks. The virtual addresses are all contiguous within a single segment, but the underlying physical addresses of the individual chunks of which the segment is made may be scattered throughout the disks20 attached to a computing system. - Segment Interface—A simple interface providing operations to read and write data stored in a segment.
- UUID—Universal Unique IDentifier, a 128 bit, easy to construct identifier that is unique over all systems and all time. Typically, these are constructed using the IEEE 48 bit hardware address of some card in the computing system, combined with a very fine granularity clock value, and a process ID and/or boot counter.
- VDisk—An arbitrary collection of inodes, not connected as a single file system tree, storing its data and meta data in a dedicated collection of segments. The different segments within a
vdisk 24 may have different properties, e.g. RAID levels, transfer rates, etc, and individual files may be allocated entirely from one segment within avdisk 24, or from multiple segments, depending upon externally provided policies. For example, one possible policy might be to place all meta data in aRAID 1 vdisk, and put all user data in aRAID 5 vdisk. Another possible policy might be to to store the first megabyte of every file in a segment having very low latency (perhaps comprising flash memory12), with the remaining blocks allocated fromnormal RAID 5 storage, so that reading random medium-sized files in their entirety could be done with very low overall latency. One or more vdisks are combined to create a VFS, or file system. - VDisk Interface—An interface used in this invention to perform file system modifying operations on files stored in
vdisks 24 making up a single VFS. The key new functionality in the vdisk interface allows directory operations to change objects in more than one vdisk, by beginning execution at one of thevdisks 24, which then forwards subsidiary requests to the other vdisk(s) involved in the operation on asecondary interface 18. - VDisk Primary Interface—The primary interface used by components such as the local NFS server to access files stored in the
vdisks 24 making up a VFS. For each VFS operation, there is a corresponding vdisk operation, with slightly different parameters, as described in the section above on the VDisk interface. - VDisk Secondary Interface—The interface invoked by those vdisk primary interface operations that update objects on more than one vdisk, to effect changes to those objects on the
other vdisks 24. For example, the secondary vdisk interface includes an operation to allocate an inode, which is invoked by the primary vdisk file create operation. Most operations in the secondary interface createPOT 22 entries to ensure that their changes occur atomically with respect to the invoking primary interface operation. - VFS or Virtual File System. A collection of files and directories stored in one or more vdisks24, and making up together a connected file system tree, with a root directory and a collection of subdirectories, each containing other files and subdirectories. A VFS contains a number of
vdisks 24, and each vdisk is a member of exactly one VFS. - VFS Interface—A reasonably standard interface to virtual file systems, first introduced in the 1980s by Sun Microsystems in the SunOS 3.X operating system, and today present in some form in many Unix and Linux-based kernels, including Sun's OpenSolaris operating system. Typical operations including reading and writing blocks within files, reading and changing file attributes, and creating and deleting files within a directory.
- Although the invention has been described in detail in the foregoing embodiments for the purpose of illustration, it is to be understood that such detail is solely for that purpose and that variations can be made therein by those skilled in the art without departing from the spirit and scope of the invention except as it may be described by the following claims.
Claims (12)
1. A file system for storing a file comprising:
a plurality of vdisks, each vdisk having a plurality of non-transient storage segments, each segment providing a specific class of service (CoS) for storage, each vdisk having a plurality of inodes stored in an inode table, each inode describing a file in the vdisk, each inode of each vdisk storing data on one or more of a plurality of segments, each segment having a different class of service for storage; and
a controller having a plurality of physical processors which store data of a file in an inode of a vdisk, in one or more segments of that vdisk, each processor serving one or more of the vdisks.
2. A system as described inclaim 1 including at least one directory storing mappings of file names to (vdisk, inode) pairs.
3. A system as described inclaim 2 wherein each inode has one or more back pointers to all of the directory entries pointing to the inode.
4. A system as described inclaim 3 wherein one of the vdisks is a root vdisk.
5. A system as described inclaim 4 wherein one of the inodes in the root vdisk is a root inode of the file system.
6. A system as described inclaim 5 wherein each segment has a plurality of chunks.
7. A system as described inclaim 6 , including an interface to initiate a file system consistency check on an individual vdisk, triggered by an indication of an inconsistency in a specific vdisk.
8. A system as described inclaim 1 wherein each segment has a plurality of chunks.
9. A system as described inclaim 8 wherein each segment has chunks added to it dynamically over time.
10. A method for storing a file comprising the steps of:
receiving the file at an interface; and
storing data of the file with a controller in multiple segments of one vdisk of a plurality of vdisks, each vdisk having a plurality of inodes, at least two of the Inodes of one vdisk storing data in different segments, each segment having a different class of service for storage.
11. A method for updating a directory comprising the steps of:
receiving a request to delete a file, directory or symbolic link at an interface;
creating a first POT entry at a first vdisk server;
sending an operation to a second vdisk server;
creating a second POT entry at the second vdisk server;
sending a response from the second vdisk server to the first vdisk server; and
freeing the first and second POT entries after the completion of the operation.
12. A method for updating a directory comprising the steps of:
receiving an object to create a normal file, directory or symbolic link at an interface;
creating a first POT entry at the first vdisk server;
selecting a second vdisk for a new object based upon a predetermined policy;
sending an operation to a second vdisk server;
creating a second POT entry at the second server;
sending a response from the second vdisk server to the first vdisk server; and
freeing the first and second POT entries sometime after the completion of the operation.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US15/630,575US20170293442A1 (en) | 2008-07-11 | 2017-06-22 | Media Aware Distributed Data Layout |
Applications Claiming Priority (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US12/218,085US8214404B2 (en) | 2008-07-11 | 2008-07-11 | Media aware distributed data layout |
| US13/135,866US8412742B2 (en) | 2008-07-11 | 2011-07-16 | Media aware distributed data layout |
| US13/827,433US9389806B2 (en) | 2008-07-11 | 2013-03-14 | Media aware distributed data layout |
| US15/199,246US9696944B2 (en) | 2008-07-11 | 2016-06-30 | Media aware distributed data layout |
| US15/630,575US20170293442A1 (en) | 2008-07-11 | 2017-06-22 | Media Aware Distributed Data Layout |
Related Parent Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| US15/199,246DivisionUS9696944B2 (en) | 2008-07-11 | 2016-06-30 | Media aware distributed data layout |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| US20170293442A1true US20170293442A1 (en) | 2017-10-12 |
Family
ID=41506087
Family Applications (9)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| US12/218,085Expired - Fee RelatedUS8214404B2 (en) | 2008-07-11 | 2008-07-11 | Media aware distributed data layout |
| US13/135,866Expired - Fee RelatedUS8412742B2 (en) | 2008-07-11 | 2011-07-16 | Media aware distributed data layout |
| US13/493,701ActiveUS8655931B2 (en) | 2008-07-11 | 2012-06-11 | Media aware distributed data layout |
| US13/827,433Active2029-07-22US9389806B2 (en) | 2008-07-11 | 2013-03-14 | Media aware distributed data layout |
| US14/175,801Active2029-01-11US9405487B2 (en) | 2008-07-11 | 2014-02-07 | Media aware distributed data layout |
| US15/199,246ActiveUS9696944B2 (en) | 2008-07-11 | 2016-06-30 | Media aware distributed data layout |
| US15/222,449ActiveUS9710195B2 (en) | 2008-07-11 | 2016-07-28 | Media aware distributed data layout |
| US15/630,575AbandonedUS20170293442A1 (en) | 2008-07-11 | 2017-06-22 | Media Aware Distributed Data Layout |
| US15/649,260ActiveUS10338853B2 (en) | 2008-07-11 | 2017-07-13 | Media aware distributed data layout |
Family Applications Before (7)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| US12/218,085Expired - Fee RelatedUS8214404B2 (en) | 2008-07-11 | 2008-07-11 | Media aware distributed data layout |
| US13/135,866Expired - Fee RelatedUS8412742B2 (en) | 2008-07-11 | 2011-07-16 | Media aware distributed data layout |
| US13/493,701ActiveUS8655931B2 (en) | 2008-07-11 | 2012-06-11 | Media aware distributed data layout |
| US13/827,433Active2029-07-22US9389806B2 (en) | 2008-07-11 | 2013-03-14 | Media aware distributed data layout |
| US14/175,801Active2029-01-11US9405487B2 (en) | 2008-07-11 | 2014-02-07 | Media aware distributed data layout |
| US15/199,246ActiveUS9696944B2 (en) | 2008-07-11 | 2016-06-30 | Media aware distributed data layout |
| US15/222,449ActiveUS9710195B2 (en) | 2008-07-11 | 2016-07-28 | Media aware distributed data layout |
Family Applications After (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| US15/649,260ActiveUS10338853B2 (en) | 2008-07-11 | 2017-07-13 | Media aware distributed data layout |
Country Status (2)
| Country | Link |
|---|---|
| US (9) | US8214404B2 (en) |
| WO (1) | WO2010005460A1 (en) |
Families Citing this family (56)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9342528B2 (en) | 2010-04-01 | 2016-05-17 | Avere Systems, Inc. | Method and apparatus for tiered storage |
| US8015343B2 (en)* | 2008-08-08 | 2011-09-06 | Amazon Technologies, Inc. | Providing executing programs with reliable access to non-local block data storage |
| US8346735B1 (en)* | 2008-09-30 | 2013-01-01 | Emc Corporation | Controlling multi-step storage management operations |
| US20100088296A1 (en)* | 2008-10-03 | 2010-04-08 | Netapp, Inc. | System and method for organizing data to facilitate data deduplication |
| US8819208B2 (en) | 2010-03-05 | 2014-08-26 | Solidfire, Inc. | Data deletion in a distributed data storage system |
| US20120066223A1 (en)* | 2010-09-13 | 2012-03-15 | Openpeak Inc. | Method and computing device for creating distinct user spaces |
| US8650658B2 (en) | 2010-10-25 | 2014-02-11 | Openpeak Inc. | Creating distinct user spaces through user identifiers |
| US9646013B2 (en)* | 2011-02-16 | 2017-05-09 | Docbert Llc | System and method for file management |
| US8849880B2 (en)* | 2011-05-18 | 2014-09-30 | Hewlett-Packard Development Company, L.P. | Providing a shadow directory and virtual files to store metadata |
| US8832035B2 (en)* | 2011-08-30 | 2014-09-09 | Netapp, Inc. | System and method for retaining deduplication in a storage object after a clone split operation |
| EP2581704A1 (en)* | 2011-10-14 | 2013-04-17 | Harman Becker Automotive Systems GmbH | Method for compressing navigation map data |
| WO2013080243A2 (en)* | 2011-11-28 | 2013-06-06 | Hitachi, Ltd. | Storage system controller, storage system, and access control method |
| US9838269B2 (en) | 2011-12-27 | 2017-12-05 | Netapp, Inc. | Proportional quality of service based on client usage and system metrics |
| US9054992B2 (en) | 2011-12-27 | 2015-06-09 | Solidfire, Inc. | Quality of service policy sets |
| FR2989801B1 (en)* | 2012-04-18 | 2014-11-21 | Schneider Electric Ind Sas | METHOD FOR SECURE MANAGEMENT OF MEMORY SPACE FOR MICROCONTROLLER |
| CN103581229B (en)* | 2012-07-26 | 2018-06-15 | 腾讯科技（深圳）有限公司 | Distributed file system, file access method and client |
| JP6222227B2 (en)* | 2013-05-20 | 2017-11-01 | 日本電気株式会社 | Storage node, storage node management apparatus, storage node logical capacity setting method, program, recording medium, and distributed data storage system |
| US10754825B2 (en)* | 2013-08-28 | 2020-08-25 | Red Hat, Inc. | Path resolver for client access to distributed file systems |
| US9170746B2 (en)* | 2014-01-07 | 2015-10-27 | Netapp, Inc. | Clustered raid assimilation management |
| US20150244795A1 (en) | 2014-02-21 | 2015-08-27 | Solidfire, Inc. | Data syncing in a distributed system |
| US10264071B2 (en) | 2014-03-31 | 2019-04-16 | Amazon Technologies, Inc. | Session management in distributed storage systems |
| US9772787B2 (en)* | 2014-03-31 | 2017-09-26 | Amazon Technologies, Inc. | File storage using variable stripe sizes |
| US10372685B2 (en) | 2014-03-31 | 2019-08-06 | Amazon Technologies, Inc. | Scalable file storage service |
| US9798728B2 (en) | 2014-07-24 | 2017-10-24 | Netapp, Inc. | System performing data deduplication using a dense tree data structure |
| US9671960B2 (en) | 2014-09-12 | 2017-06-06 | Netapp, Inc. | Rate matching technique for balancing segment cleaning and I/O workload |
| US10133511B2 (en) | 2014-09-12 | 2018-11-20 | Netapp, Inc | Optimized segment cleaning technique |
| US9720626B2 (en)* | 2014-09-19 | 2017-08-01 | Netapp Inc. | Cluster configuration information replication |
| US9836229B2 (en) | 2014-11-18 | 2017-12-05 | Netapp, Inc. | N-way merge technique for updating volume metadata in a storage I/O stack |
| US9720601B2 (en) | 2015-02-11 | 2017-08-01 | Netapp, Inc. | Load balancing technique for a storage array |
| US9762460B2 (en) | 2015-03-24 | 2017-09-12 | Netapp, Inc. | Providing continuous context for operational information of a storage system |
| US9710317B2 (en) | 2015-03-30 | 2017-07-18 | Netapp, Inc. | Methods to identify, handle and recover from suspect SSDS in a clustered flash array |
| US9740566B2 (en) | 2015-07-31 | 2017-08-22 | Netapp, Inc. | Snapshot creation workflow |
| US10043027B1 (en)* | 2015-11-19 | 2018-08-07 | Xilinx, Inc. | Generation of mask-value pairs for managing access to memory segments |
| US10810168B2 (en) | 2015-11-24 | 2020-10-20 | Red Hat, Inc. | Allocating file system metadata to storage nodes of distributed file system |
| US10545927B2 (en) | 2016-03-25 | 2020-01-28 | Amazon Technologies, Inc. | File system mode switching in a distributed storage service |
| US10140312B2 (en) | 2016-03-25 | 2018-11-27 | Amazon Technologies, Inc. | Low latency distributed storage service |
| US10474636B2 (en) | 2016-03-25 | 2019-11-12 | Amazon Technologies, Inc. | Block allocation for low latency file systems |
| US10929022B2 (en) | 2016-04-25 | 2021-02-23 | Netapp. Inc. | Space savings reporting for storage system supporting snapshot and clones |
| US10642763B2 (en) | 2016-09-20 | 2020-05-05 | Netapp, Inc. | Quality of service policy sets |
| US10740288B2 (en)* | 2016-12-02 | 2020-08-11 | International Business Machines Corporation | Accessing objects in an erasure code supported object storage environment |
| US10579598B2 (en) | 2017-01-03 | 2020-03-03 | International Business Machines Corporation | Global namespace for a hierarchical set of file systems |
| US10592479B2 (en) | 2017-01-03 | 2020-03-17 | International Business Machines Corporation | Space management for a hierarchical set of file systems |
| US10657102B2 (en) | 2017-01-03 | 2020-05-19 | International Business Machines Corporation | Storage space management in union mounted file systems |
| US10649955B2 (en) | 2017-01-03 | 2020-05-12 | International Business Machines Corporation | Providing unique inodes across multiple file system namespaces |
| US10579587B2 (en) | 2017-01-03 | 2020-03-03 | International Business Machines Corporation | Space management for a hierarchical set of file systems |
| US10585860B2 (en) | 2017-01-03 | 2020-03-10 | International Business Machines Corporation | Global namespace for a hierarchical set of file systems |
| US10599611B1 (en)* | 2017-04-24 | 2020-03-24 | EMC IP Holding Company LLC | Base object selection and creation in data storage system management |
| US10496318B1 (en)* | 2017-04-28 | 2019-12-03 | EMC IP Holding Company LLC | System and method for capacity management in multi-tiered storage |
| US10768844B2 (en)* | 2018-05-15 | 2020-09-08 | International Business Machines Corporation | Internal striping inside a single device |
| CN109407970B (en)* | 2018-09-12 | 2022-02-11 | 新华三技术有限公司成都分公司 | Read-write request processing method and device and electronic equipment |
| US11500817B2 (en)* | 2020-05-11 | 2022-11-15 | Cohesity, Inc. | Asynchronous deletion of large directories |
| CN111617469B (en)* | 2020-06-04 | 2023-09-26 | 广州西山居网络科技有限公司 | Game data processing method and device |
| CN114442962B (en)* | 2022-02-15 | 2024-07-02 | 北京百度网讯科技有限公司 | Data reading method, device, equipment and storage medium |
| US12287738B2 (en)* | 2022-06-16 | 2025-04-29 | Samsung Electronics Co., Ltd. | System and method for caching in storage devices |
| US12153600B2 (en)* | 2022-09-28 | 2024-11-26 | Rubrik, Inc. | Techniques for upgrading and accessing metadata |
| US12260105B1 (en)* | 2023-09-21 | 2025-03-25 | VMware LLC | Converting the format of a distributed object storage with reduced write operations |
Citations (32)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4286325A (en)* | 1979-08-27 | 1981-08-25 | Pitney Bowes Inc. | System and method for computing domestic and international postage |
| US5537400A (en)* | 1994-04-15 | 1996-07-16 | Dsc Communications Corporation | Buffered crosspoint matrix for an asynchronous transfer mode switch and method of operation |
| US5682477A (en)* | 1993-05-27 | 1997-10-28 | Fujitsu Limited | System for selecting an implementing class having corresponding prescribed resources matching the availed resources and calculating compensating data to be stored in a management table |
| US20020129123A1 (en)* | 2000-03-03 | 2002-09-12 | Johnson Scott C | Systems and methods for intelligent information retrieval and delivery in an information management environment |
| US20020133491A1 (en)* | 2000-10-26 | 2002-09-19 | Prismedia Networks, Inc. | Method and system for managing distributed content and related metadata |
| US6665740B1 (en)* | 1999-11-12 | 2003-12-16 | Emc Corporation | Logical volume selection in a probability-based job scheduler |
| US20030233494A1 (en)* | 2002-05-06 | 2003-12-18 | Sukha Ghosh | Application program interface-access to hardware services for storage management applications |
| US20040141494A1 (en)* | 1999-02-04 | 2004-07-22 | Beshai Maged E. | Rate-controlled multi-class high-capacity packet switch |
| US20040177220A1 (en)* | 1990-02-26 | 2004-09-09 | Hitachi, Ltd. | Distribution of I/O requests across multiple disk units |
| US20040236798A1 (en)* | 2001-09-11 | 2004-11-25 | Sudhir Srinivasan | Migration of control in a distributed segmented file system |
| US20050102383A1 (en)* | 2003-01-23 | 2005-05-12 | Computer Associates Think, Inc. | Method and apparatus for remote discovery of software applications in a networked environment |
| US6904470B1 (en)* | 2003-03-26 | 2005-06-07 | Emc Corporation | Device selection by a disk adapter scheduler |
| US20050192932A1 (en)* | 2003-12-02 | 2005-09-01 | Michael Kazar | Storage system architecture for striping data container content across volumes of a cluster |
| US20050246438A1 (en)* | 2002-08-14 | 2005-11-03 | Michael Menth | Access control for packet-oriented networks |
| US20050256914A1 (en)* | 2004-05-13 | 2005-11-17 | International Business Machines Corporation | Symbolic links with a plurality of addresses |
| US20050289296A1 (en)* | 2004-06-23 | 2005-12-29 | Sridhar Balasubramanian | SAN based application recognition (SBAR) for RAID controller |
| US20060236061A1 (en)* | 2005-04-18 | 2006-10-19 | Creek Path Systems | Systems and methods for adaptively deriving storage policy and configuration rules |
| US20060248088A1 (en)* | 2005-04-29 | 2006-11-02 | Michael Kazar | System and method for multi-tiered meta-data caching and distribution in a clustered computer environment |
| US20060253678A1 (en)* | 2005-05-05 | 2006-11-09 | Gusler Carl P | Autonomic storage provisioning to enhance storage virtualization infrastructure availability |
| US20070033540A1 (en)* | 2005-08-05 | 2007-02-08 | Lexmark International, Inc. | Systems and methods for directory and file manipulation using a multifunction device |
| US20070073781A1 (en)* | 2005-09-27 | 2007-03-29 | Adkins Janet E | Method and apparatus to capture and transmit dense diagnostic data of a file system |
| US20070300013A1 (en)* | 2006-06-21 | 2007-12-27 | Manabu Kitamura | Storage system having transaction monitoring capability |
| US20080052329A1 (en)* | 2006-08-25 | 2008-02-28 | Dan Dodge | File system having variable logical storage block size |
| US20080082525A1 (en)* | 2006-09-29 | 2008-04-03 | Cha Myung Hoon | File storage system, file storing method and file searching method therein |
| US20080189343A1 (en)* | 2006-12-29 | 2008-08-07 | Robert Wyckoff Hyer | System and method for performing distributed consistency verification of a clustered file system |
| US7415591B1 (en)* | 2003-04-23 | 2008-08-19 | Emc Corporation | Method and apparatus for migrating data and automatically provisioning a target for the migration |
| US7447854B1 (en)* | 2005-12-30 | 2008-11-04 | Vmware, Inc. | Tracking and replicating changes to a virtual disk |
| US20090024814A1 (en)* | 2007-06-01 | 2009-01-22 | Michael Eisler | Providing an administrative path for accessing a writeable master storage volume in a mirrored storage environment |
| US7509329B1 (en)* | 2004-06-01 | 2009-03-24 | Network Appliance, Inc. | Technique for accelerating file deletion by preloading indirect blocks |
| US7849057B1 (en)* | 2007-03-30 | 2010-12-07 | Netapp, Inc. | Identifying snapshot membership for blocks based on snapid |
| US20110153697A1 (en)* | 2005-09-15 | 2011-06-23 | Computer Assoicates Think, Inc. | Automated Filer Technique for Use in Virtualized Appliances and Applications |
| US8190588B1 (en)* | 2005-09-19 | 2012-05-29 | Amazon Technologies, Inc. | Providing a distributed transaction information storage service |
Family Cites Families (73)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5689706A (en) | 1993-06-18 | 1997-11-18 | Lucent Technologies Inc. | Distributed systems with replicated files |
| US5634122A (en) | 1994-12-30 | 1997-05-27 | International Business Machines Corporation | System and method for multi-level token management for distributed file systems |
| US5729734A (en) | 1995-11-03 | 1998-03-17 | Apple Computer, Inc. | File privilege administration apparatus and methods |
| US6335927B1 (en) | 1996-11-18 | 2002-01-01 | Mci Communications Corporation | System and method for providing requested quality of service in a hybrid network |
| US5960446A (en) | 1997-07-11 | 1999-09-28 | International Business Machines Corporation | Parallel file system and method with allocation map |
| US7536524B2 (en) | 1998-07-31 | 2009-05-19 | Kom Networks Inc. | Method and system for providing restricted access to a storage medium |
| US6330621B1 (en)* | 1999-01-15 | 2001-12-11 | Storage Technology Corporation | Intelligent data storage manager |
| US6339793B1 (en) | 1999-04-06 | 2002-01-15 | International Business Machines Corporation | Read/write data sharing of DASD data, including byte file system data, in a cluster of multiple data processing systems |
| US6385701B1 (en) | 1999-11-19 | 2002-05-07 | International Business Machines Corporation | Method, system and program products for sharing data between varied clients using token management |
| US6708269B1 (en) | 1999-12-30 | 2004-03-16 | Intel Corporation | Method and apparatus for multi-mode fencing in a microprocessor system |
| US7023802B2 (en)* | 2000-02-14 | 2006-04-04 | Fujitsu Limited | Network system priority control method |
| US7660902B2 (en) | 2000-11-20 | 2010-02-09 | Rsa Security, Inc. | Dynamic file access control and management |
| US7707149B2 (en) | 2001-04-04 | 2010-04-27 | Alorica, Inc | Method, system, and program for customer service and support management |
| US6950833B2 (en) | 2001-06-05 | 2005-09-27 | Silicon Graphics, Inc. | Clustered filesystem |
| US20030028514A1 (en) | 2001-06-05 | 2003-02-06 | Lord Stephen Philip | Extended attribute caching in clustered filesystem |
| US7765329B2 (en) | 2002-06-05 | 2010-07-27 | Silicon Graphics International | Messaging between heterogeneous clients of a storage area network |
| US7617292B2 (en) | 2001-06-05 | 2009-11-10 | Silicon Graphics International | Multi-class heterogeneous clients in a clustered filesystem |
| US7593968B2 (en) | 2001-06-05 | 2009-09-22 | Silicon Graphics, Inc. | Recovery and relocation of a distributed name service in a cluster filesystem |
| US8010558B2 (en) | 2001-06-05 | 2011-08-30 | Silicon Graphics International | Relocation of metadata server with outstanding DMAPI requests |
| US20040139125A1 (en) | 2001-06-05 | 2004-07-15 | Roger Strassburg | Snapshot copy of data volume during data access |
| US7640582B2 (en) | 2003-04-16 | 2009-12-29 | Silicon Graphics International | Clustered filesystem for mix of trusted and untrusted nodes |
| US20030018606A1 (en) | 2001-07-17 | 2003-01-23 | International Business Machines Corporation | Revocation of tokens without communication between the token holders and the token server |
| US7325064B2 (en) | 2001-07-17 | 2008-01-29 | International Business Machines Corporation | Distributed locking protocol with asynchronous token prefetch and relinquish |
| US7085815B2 (en) | 2001-07-17 | 2006-08-01 | International Business Machines Corporation | Scalable memory management of token state for distributed lock managers |
| US20030028664A1 (en) | 2001-08-02 | 2003-02-06 | Kaijun Tan | Method and system for secure distribution and utilization of data over a network |
| US7418500B1 (en) | 2002-03-25 | 2008-08-26 | Network Appliance, Inc. | Mechanism for controlled sharing of files in a clustered application environment |
| US7017037B2 (en) | 2002-06-27 | 2006-03-21 | Microsoft Corporation | Apparatus and method to decrease boot time and hibernate awaken time of a computer system utilizing disk spin-up-time |
| US7107385B2 (en)* | 2002-08-09 | 2006-09-12 | Network Appliance, Inc. | Storage virtualization by layering virtual disk objects on a file system |
| US8041735B1 (en) | 2002-11-01 | 2011-10-18 | Bluearc Uk Limited | Distributed file system and method |
| US20040153841A1 (en) | 2003-01-16 | 2004-08-05 | Silicon Graphics, Inc. | Failure hierarchy in a cluster filesystem |
| JP4271967B2 (en) | 2003-03-10 | 2009-06-03 | 株式会社日立製作所 | Distributed file system and distributed file system operation method |
| US20040210656A1 (en) | 2003-04-16 | 2004-10-21 | Silicon Graphics, Inc. | Failsafe operation of storage area network |
| US7291878B2 (en) | 2003-06-03 | 2007-11-06 | Hitachi Global Storage Technologies Netherlands B.V. | Ultra low-cost solid-state memory |
| US7716323B2 (en)* | 2003-07-18 | 2010-05-11 | Netapp, Inc. | System and method for reliable peer communication in a clustered storage system |
| US7305520B2 (en)* | 2004-01-30 | 2007-12-04 | Hewlett-Packard Development Company, L.P. | Storage system with capability to allocate virtual storage segments among a plurality of controllers |
| JP2005250938A (en) | 2004-03-05 | 2005-09-15 | Hitachi Ltd | Storage control system and method |
| US7441096B2 (en)* | 2004-07-07 | 2008-10-21 | Hitachi, Ltd. | Hierarchical storage management system |
| WO2006015182A2 (en) | 2004-07-29 | 2006-02-09 | Infoassure, Inc. | Object access level |
| EP1650646A3 (en) | 2004-10-22 | 2008-11-19 | Quantum Corporation | Data storage system for storing data in different types of data storage media |
| JP4956922B2 (en) | 2004-10-27 | 2012-06-20 | ソニー株式会社 | Storage device |
| US20140108049A1 (en) | 2005-02-24 | 2014-04-17 | Epic Systems Corporation | System and method for facilitating cross enterprise data sharing in a health care setting |
| US20090307755A1 (en) | 2005-02-24 | 2009-12-10 | Dvorak Carl D | System and method for facilitating cross enterprises data sharing in a healthcare setting |
| US7962689B1 (en)* | 2005-04-29 | 2011-06-14 | Netapp, Inc. | System and method for performing transactional processing in a striped volume set |
| US7739318B2 (en)* | 2005-06-20 | 2010-06-15 | Netapp, Inc. | System and method for maintaining mappings from data containers to their parent directories |
| US7640279B2 (en) | 2005-11-30 | 2009-12-29 | International Business Machines Corporation | Apparatus and method for file-level replication between two or more non-symmetric storage sites |
| US20070143344A1 (en) | 2005-12-15 | 2007-06-21 | International Business Machines Corporation | Cache maintenance in a distributed environment with functional mismatches between the cache and cache maintenance |
| US20070214497A1 (en) | 2006-03-10 | 2007-09-13 | Axalto Inc. | System and method for providing a hierarchical role-based access control |
| US20070220271A1 (en) | 2006-03-15 | 2007-09-20 | Law Eric C W | Online creation and delivery of cryptographically verifiable one-time password tokens |
| US20070233868A1 (en)* | 2006-03-31 | 2007-10-04 | Tyrrell John C | System and method for intelligent provisioning of storage across a plurality of storage systems |
| US8260831B2 (en)* | 2006-03-31 | 2012-09-04 | Netapp, Inc. | System and method for implementing a flexible storage manager with threshold control |
| US7769723B2 (en)* | 2006-04-28 | 2010-08-03 | Netapp, Inc. | System and method for providing continuous data protection |
| JP2007323284A (en) | 2006-05-31 | 2007-12-13 | Hitachi Ltd | Computer system, storage system, and bandwidth management method |
| JP4943081B2 (en) | 2006-07-27 | 2012-05-30 | 株式会社日立製作所 | File storage control device and method |
| US8566503B2 (en) | 2006-08-25 | 2013-10-22 | Qnx Software Systems Limited | Multimedia filesystem having unified representation of content on diverse multimedia devices |
| US8019938B2 (en) | 2006-12-06 | 2011-09-13 | Fusion-I0, Inc. | Apparatus, system, and method for solid-state storage as cache for high-capacity, non-volatile storage |
| DE502008001996D1 (en) | 2007-04-16 | 2011-01-20 | Tixel Gmbh | METHOD AND DEVICE FOR ACCESS CONTROL OF SEVERAL APPLICATIONS |
| US20080271130A1 (en) | 2007-04-30 | 2008-10-30 | Shankar Ramamoorthy | Minimizing client-side inconsistencies in a distributed virtual file system |
| IES20080508A2 (en) | 2007-06-22 | 2008-12-10 | Tenoware R & D Ltd | Network distributed file system |
| US20090012817A1 (en) | 2007-07-06 | 2009-01-08 | Squires Charles S | System and method for facilitating cross enterprise data sharing in a healthcare setting |
| US7890555B2 (en) | 2007-07-10 | 2011-02-15 | International Business Machines Corporation | File system mounting in a clustered file system |
| US8156164B2 (en) | 2007-07-11 | 2012-04-10 | International Business Machines Corporation | Concurrent directory update in a cluster file system |
| US8392702B2 (en) | 2007-07-27 | 2013-03-05 | General Instrument Corporation | Token-based management system for PKI personalization process |
| US7958200B2 (en) | 2007-08-14 | 2011-06-07 | International Business Machines Corporation | Methods, computer program products, and apparatuses for providing remote client access to exported file systems |
| US7843825B2 (en)* | 2007-10-02 | 2010-11-30 | Broadcom Corporation | Method and system for packet rate shaping |
| US20090113543A1 (en) | 2007-10-25 | 2009-04-30 | Research In Motion Limited | Authentication certificate management for access to a wireless communication device |
| JP5124238B2 (en) | 2007-11-09 | 2013-01-23 | 株式会社日立製作所 | Backup execution determination system |
| US20090310028A1 (en) | 2008-06-11 | 2009-12-17 | Reza Sadri | System for Controlling a Group of Picture Frames |
| US9323681B2 (en) | 2008-09-18 | 2016-04-26 | Avere Systems, Inc. | File storage system, cache appliance, and method |
| US8266684B2 (en) | 2008-09-30 | 2012-09-11 | General Instrument Corporation | Tokenized resource access |
| US8103764B2 (en) | 2008-10-14 | 2012-01-24 | CacheIQ, Inc. | Method and apparatus for matching trigger pattern |
| JP4550933B1 (en) | 2009-03-09 | 2010-09-22 | 株式会社東芝 | Broadcast receiving apparatus and broadcast receiving method |
| US8903773B2 (en) | 2010-03-31 | 2014-12-02 | Novastor Corporation | Computer file storage, backup, restore and retrieval |
| US20120331518A1 (en) | 2011-06-23 | 2012-12-27 | Salesforce.Com, Inc. | Flexible security token framework |
- 2008
- 2008-07-11USUS12/218,085patent/US8214404B2/ennot_activeExpired - Fee Related
- 2009
- 2009-05-29WOPCT/US2009/003264patent/WO2010005460A1/enactiveApplication Filing
- 2011
- 2011-07-16USUS13/135,866patent/US8412742B2/ennot_activeExpired - Fee Related
- 2012
- 2012-06-11USUS13/493,701patent/US8655931B2/enactiveActive
- 2013
- 2013-03-14USUS13/827,433patent/US9389806B2/enactiveActive
- 2014
- 2014-02-07USUS14/175,801patent/US9405487B2/enactiveActive
- 2016
- 2016-06-30USUS15/199,246patent/US9696944B2/enactiveActive
- 2016-07-28USUS15/222,449patent/US9710195B2/enactiveActive
- 2017
- 2017-06-22USUS15/630,575patent/US20170293442A1/ennot_activeAbandoned
- 2017-07-13USUS15/649,260patent/US10338853B2/enactiveActive
Patent Citations (33)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4286325A (en)* | 1979-08-27 | 1981-08-25 | Pitney Bowes Inc. | System and method for computing domestic and international postage |
| US20040177220A1 (en)* | 1990-02-26 | 2004-09-09 | Hitachi, Ltd. | Distribution of I/O requests across multiple disk units |
| US5682477A (en)* | 1993-05-27 | 1997-10-28 | Fujitsu Limited | System for selecting an implementing class having corresponding prescribed resources matching the availed resources and calculating compensating data to be stored in a management table |
| US5537400A (en)* | 1994-04-15 | 1996-07-16 | Dsc Communications Corporation | Buffered crosspoint matrix for an asynchronous transfer mode switch and method of operation |
| US20040141494A1 (en)* | 1999-02-04 | 2004-07-22 | Beshai Maged E. | Rate-controlled multi-class high-capacity packet switch |
| US6665740B1 (en)* | 1999-11-12 | 2003-12-16 | Emc Corporation | Logical volume selection in a probability-based job scheduler |
| US20020129123A1 (en)* | 2000-03-03 | 2002-09-12 | Johnson Scott C | Systems and methods for intelligent information retrieval and delivery in an information management environment |
| US20020133491A1 (en)* | 2000-10-26 | 2002-09-19 | Prismedia Networks, Inc. | Method and system for managing distributed content and related metadata |
| US20040236798A1 (en)* | 2001-09-11 | 2004-11-25 | Sudhir Srinivasan | Migration of control in a distributed segmented file system |
| US7093038B2 (en)* | 2002-05-06 | 2006-08-15 | Ivivity, Inc. | Application program interface-access to hardware services for storage management applications |
| US20030233494A1 (en)* | 2002-05-06 | 2003-12-18 | Sukha Ghosh | Application program interface-access to hardware services for storage management applications |
| US20050246438A1 (en)* | 2002-08-14 | 2005-11-03 | Michael Menth | Access control for packet-oriented networks |
| US20050102383A1 (en)* | 2003-01-23 | 2005-05-12 | Computer Associates Think, Inc. | Method and apparatus for remote discovery of software applications in a networked environment |
| US6904470B1 (en)* | 2003-03-26 | 2005-06-07 | Emc Corporation | Device selection by a disk adapter scheduler |
| US7415591B1 (en)* | 2003-04-23 | 2008-08-19 | Emc Corporation | Method and apparatus for migrating data and automatically provisioning a target for the migration |
| US20050192932A1 (en)* | 2003-12-02 | 2005-09-01 | Michael Kazar | Storage system architecture for striping data container content across volumes of a cluster |
| US20050256914A1 (en)* | 2004-05-13 | 2005-11-17 | International Business Machines Corporation | Symbolic links with a plurality of addresses |
| US7509329B1 (en)* | 2004-06-01 | 2009-03-24 | Network Appliance, Inc. | Technique for accelerating file deletion by preloading indirect blocks |
| US20050289296A1 (en)* | 2004-06-23 | 2005-12-29 | Sridhar Balasubramanian | SAN based application recognition (SBAR) for RAID controller |
| US20060236061A1 (en)* | 2005-04-18 | 2006-10-19 | Creek Path Systems | Systems and methods for adaptively deriving storage policy and configuration rules |
| US20060248088A1 (en)* | 2005-04-29 | 2006-11-02 | Michael Kazar | System and method for multi-tiered meta-data caching and distribution in a clustered computer environment |
| US20060253678A1 (en)* | 2005-05-05 | 2006-11-09 | Gusler Carl P | Autonomic storage provisioning to enhance storage virtualization infrastructure availability |
| US20070033540A1 (en)* | 2005-08-05 | 2007-02-08 | Lexmark International, Inc. | Systems and methods for directory and file manipulation using a multifunction device |
| US20110153697A1 (en)* | 2005-09-15 | 2011-06-23 | Computer Assoicates Think, Inc. | Automated Filer Technique for Use in Virtualized Appliances and Applications |
| US8190588B1 (en)* | 2005-09-19 | 2012-05-29 | Amazon Technologies, Inc. | Providing a distributed transaction information storage service |
| US20070073781A1 (en)* | 2005-09-27 | 2007-03-29 | Adkins Janet E | Method and apparatus to capture and transmit dense diagnostic data of a file system |
| US7447854B1 (en)* | 2005-12-30 | 2008-11-04 | Vmware, Inc. | Tracking and replicating changes to a virtual disk |
| US20070300013A1 (en)* | 2006-06-21 | 2007-12-27 | Manabu Kitamura | Storage system having transaction monitoring capability |
| US20080052329A1 (en)* | 2006-08-25 | 2008-02-28 | Dan Dodge | File system having variable logical storage block size |
| US20080082525A1 (en)* | 2006-09-29 | 2008-04-03 | Cha Myung Hoon | File storage system, file storing method and file searching method therein |
| US20080189343A1 (en)* | 2006-12-29 | 2008-08-07 | Robert Wyckoff Hyer | System and method for performing distributed consistency verification of a clustered file system |
| US7849057B1 (en)* | 2007-03-30 | 2010-12-07 | Netapp, Inc. | Identifying snapshot membership for blocks based on snapid |
| US20090024814A1 (en)* | 2007-06-01 | 2009-01-22 | Michael Eisler | Providing an administrative path for accessing a writeable master storage volume in a mirrored storage environment |
Also Published As
| Publication number | Publication date |
|---|---|
| US10338853B2 (en) | 2019-07-02 |
| US8214404B2 (en) | 2012-07-03 |
| US20100011037A1 (en) | 2010-01-14 |
| US20160313948A1 (en) | 2016-10-27 |
| WO2010005460A1 (en) | 2010-01-14 |
| US20110282922A1 (en) | 2011-11-17 |
| US20140156928A1 (en) | 2014-06-05 |
| US20140115015A1 (en) | 2014-04-24 |
| US9696944B2 (en) | 2017-07-04 |
| US20170308331A1 (en) | 2017-10-26 |
| US20160335015A1 (en) | 2016-11-17 |
| US9389806B2 (en) | 2016-07-12 |
| US8655931B2 (en) | 2014-02-18 |
| US20120271858A1 (en) | 2012-10-25 |
| US9710195B2 (en) | 2017-07-18 |
| US9405487B2 (en) | 2016-08-02 |
| US8412742B2 (en) | 2013-04-02 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10338853B2 (en) | Media aware distributed data layout | |
| US11797498B2 (en) | Systems and methods of database tenant migration | |
| US10515192B2 (en) | Consistent snapshots and clones in an asymmetric virtual distributed file system | |
| US10437721B2 (en) | Efficient garbage collection for a log-structured data store | |
| US10534768B2 (en) | Optimized log storage for asynchronous log updates | |
| US8977659B2 (en) | Distributing files across multiple, permissibly heterogeneous, storage devices | |
| US9235479B1 (en) | Distributed file system having separate data and metadata and providing a consistent snapshot thereof | |
| US10430392B2 (en) | Computer file system with path lookup tables | |
| US8533295B2 (en) | Shared file system | |
| US9582213B2 (en) | Object store architecture for distributed data processing system | |
| US8650168B2 (en) | Methods of processing files in a multiple quality of service system | |
| US7676628B1 (en) | Methods, systems, and computer program products for providing access to shared storage by computing grids and clusters with large numbers of nodes | |
| US10885023B1 (en) | Asynchronous processing for synchronous requests in a database | |
| US11741144B2 (en) | Direct storage loading for adding data to a database | |
| US11914571B1 (en) | Optimistic concurrency for a multi-writer database |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| AS | Assignment | Owner name:ARRIAD, INC., PENNSYLVANIA Free format text:ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:KAZAR, MICHAEL L.;REEL/FRAME:045089/0339 Effective date:20080917 Owner name:AVERE SYSTEMS, INC., PENNSYLVANIA Free format text:CHANGE OF NAME;ASSIGNOR:ARRIAD, INC.;REEL/FRAME:045490/0302 Effective date:20080930 | |
| STPP | Information on status: patent application and granting procedure in general | Free format text:DOCKETED NEW CASE - READY FOR EXAMINATION | |
| STPP | Information on status: patent application and granting procedure in general | Free format text:NON FINAL ACTION MAILED | |
| STPP | Information on status: patent application and granting procedure in general | Free format text:RESPONSE TO NON-FINAL OFFICE ACTION ENTERED AND FORWARDED TO EXAMINER | |
| STPP | Information on status: patent application and granting procedure in general | Free format text:DOCKETED NEW CASE - READY FOR EXAMINATION | |
| STPP | Information on status: patent application and granting procedure in general | Free format text:NON FINAL ACTION MAILED | |
| AS | Assignment | Owner name:MICROSOFT TECHNOLOGY LICENSING, LLC, WASHINGTON Free format text:ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:AVERE SYSTEMS, INC.;REEL/FRAME:053373/0574 Effective date:20200303 | |
| STCB | Information on status: application discontinuation | Free format text:ABANDONED -- FAILURE TO RESPOND TO AN OFFICE ACTION |