Patent ID: 12248436

DETAILED DESCRIPTION

Embodiments of the present disclosure that are described herein provide improved methods and systems for managing a modification-time (“mTime”) value of a file. In the disclosed embodiments, a File System (FS) stores files in persistent, non-volatile storage. For a given file, the FS runs a software entity that “owns” the file, and enables multiple software entities, referred to as “mappers,” to access and modify the file concurrently. Among other tasks, the mappers and owner update the mTime value of the file in a manner that continually reflects the actual latest modification time, and is resilient to sudden power failures.

In some embodiments, each mapper maintains a local mTime value, which is indicative of the most recent time the file was modified by that particular mapper. In addition to the multiple local mTime values, the owner maintains a global mTime value that is indicative of the most recent time the file was modified by any of the mappers. The global mTime value is the value that is typically exposed to external applications and serves as the mTime value of the file.

When a certain mapper modifies the content of file, the mapper updates its local mTime value to reflect the modification time. The mapper writes the updated local mTime value together with the modified content to the non-volatile storage, e.g., using “piggyback journaling” or other suitable journaling scheme. In addition, the mapper sends a request to the owner to update the global mTime value. This local updating process is typically performed by the various mappers in parallel and without mutual coordination. The mapper typically updates the local mTime value after obtaining a lock on the relevant portion of the file. This lock, however, is local, and does not prevent other mappers from performing similar updates simultaneously in other portions of the file.

When the mappers operate in the above-described manner, the owner receives multiple uncoordinated requests from various mappers to update the global mTime value of the file. Upon receiving each request, the owner checks whether the local mTime value in the request is larger than the current global mTime value. If so, the owner replaces the global mTime value with the local mTime value indicated in the request.

Otherwise (i.e., if the local mTime value in the request is smaller than or equal to the current global mTime value), the owner increments the global mTime value by a predefined small increment denoted Δ, e.g., by a 1 nS tick. Incrementing of this sort maintains the global mTime value monotonically increasing, retains consistency, and mitigates scenarios in which multiple mappers request updates having the same local mTime values. The increment may cause some inaccuracy in the mTime value, but it is typically small enough to be tolerable in most applications.

In some embodiments, upon recovery from sudden power failure, the owner counts the number of write operations to the file that are currently open. The owner then sets the global mTime value to MAX+(N−1)·Δ, wherein N denotes the number of open write operations, MAX denotes the largest (i.e., the latest) of the local mTime values journaled in the open write operations before the power failure, and Δ denotes the predefined small increment.

When using the disclosed technique, the FS updates the mTime value of the file continually, even when the file is being modified by multiple uncoordinated writers, and practically without causing any centralized bottleneck that limits scalability or write performance. Since the disclosed technique does not require any kind of locking mechanism on the global mTime value, higher parallelism and higher performance and scalability are achieved. Resilience to sudden power failure is also maintained.

The disclosed technique is suitable for implementation in distributed, network-based FSs, as well as in centralized FSs that run on a single compute node. Generalizations to other file attributes, e.g., access-time (“aTime”), and to attributes of other objects, such as directories, are also described.

System Description

FIG.1is a block diagram that schematically illustrates a computing system20, in accordance with an embodiment of the present disclosure. System may include, for example, a data center, a cloud computing system or a computing system that performs any other suitable function.

System20includes multiple compute nodes24that communicate with one another over a computer communication network28Compute nodes24are referred to herein as nodes, for brevity, and may include, for example, servers, workstations or any other suitable type of compute node. Nodes24may communicate over network28in accordance with any suitable network communication protocol, such as Ethernet or Infiniband. System20may include any suitable number of compute nodes of any type. Nodes24may be collocated or located in multiple geographical locations. The collection of nodes24is also sometimes referred to as a cluster.

In the present example, each node24includes a Central Processing Unit (CPU)32, also referred to as a processor. Each node also includes a volatile memory36such as Random Access Memory (RAM), and non-volatile storage40such as one or more Solid State Drives (SSDs) or Hard Disk Drives (HDDs). Each node24further includes a network interface44such as a Network Interface Controller (NIC) for communicating over network28. CPU32of each node24runs one or more software applications52, e.g., user applications, Virtual Machines (VMs), operating system processes or containers, and/or any other suitable software.

In some embodiments, each CPU32runs a respective File System (FS) module48that carries out various file management functions. The plurality of modules48, running on CPUs32of nodes24, implement a distributed FS that manages the storage of files in the various non-volatile storage devices40. This distributed FS typically serves the various applications52using a suitable storage protocol such as Network File System (NFS) or Server Message Block (SMB).

The distributed FS formed by the collection of modules48uses the various storage devices40of the various nodes24(and/or storage devices40that do not belong to the nodes) as a system-wide pool of persistent, non-volatile storage. Certain aspects of distributed FS operation are addressed in U.S. Patent Application Publication 2016/0203219, entitled “Distributed File System for Virtualized Computing Clusters,” which is assigned to the assignee of the present patent application and whose disclosure is incorporated herein by reference.

The configurations of system20and nodes24shown inFIG.1are example configurations that are chosen purely for the sake of conceptual clarity. In alternative embodiments, any other suitable system and/or node configuration can be used. For example, one or more of storage devices40may be separate from nodes24, e.g., connected to network28individually or via some storage controller. As another example, some or even all of the functionality of modules48may be implemented on one or more processors that are separate from nodes24. The different elements of system20and nodes24may be implemented using suitable hardware, using software, or using a combination of hardware and software elements. In some embodiments, CPUs32include general-purpose processors, which are programmed in software to carry out the functions described herein. The software may be downloaded to the processors in electronic form, over a network, for example, or it may, alternatively or additionally, be provided and/or stored on non-transitory tangible media, such as magnetic, optical, or electronic memory.

Distributed Updating of File Modification Time by Multiple Mappers

For a given file, the distributed FS of system20runs a software entity that is responsible for managing the file. This software entity is referred to herein as the “owner” of the file. The distributed FS enables multiple entities, referred to as “mappers,” to access and modify the file concurrently. The owner typically permits each mapper to modify a respective portion of the file, and ensures that no two mappers are permitted to modify the same portion simultaneously.

The mappers may include, for example, different applications52that possibly run on different nodes24, different processes within a given application52, or any other suitable software module that modifies the content of files. The mappers usually operate without coordination with one another.

The owner of a file, the mappers that modify the file, and the distributed FS as a whole, all run on CPUs32of nodes24. For the sake of clarity, the description that follows refers mainly to “owner,” “mappers” and “distributed FS,” rather than to the underlying CPUs that run them. Nevertheless, the disclosed methods are ultimately carried out by one or more of CPUs32. Generally, the disclosed techniques may be carried out by any suitable number of processors, or even by a single processor.

Among other tasks, the distributed FS of system20maintains a modification-time (“mTime”) value for each file. The mTime value typically includes a numerical value that is indicative of the most recent time the file content was modified. The mTime value is also referred to as a “global” mTime value, in order to distinguish from local mTime values described below. The mTime value is typically stored in a suitable field in the file metadata. In the embodiments described herein, the mTime value is a 64-bit binary word that represents the most recent modification time with 1 nS resolution. Alternatively, however, any other suitable format, e.g., 32-bit format, can be used.

The global mTime value can be used by the FS, or by applications that use the file, for any suitable purpose. For example, when the file in question is part of a software project that includes multiple files, a build system tool may check the global mTime values of the various files in order to decide which files have changed and should be included in re-building. As another example, an operating system or other software may sort documents or files according to their latest update time using the global mTime values. A backup system may use the global mTime value to check whether a file was modified before archiving it. A security system may use the global mTime value to perform security auditing, e.g., detect whether and when a file was manipulated. Additionally or alternatively, the global mTime values can be used in any other suitable way for any other suitable purpose.

The description that follows refers to mTime value management of a single file, for the sake of clarity. Real-life file systems, however, typically manage a large number of files. In such embodiments, the disclosed techniques may be applied per file.

As noted above, at a given point in time, the owner typically assigns different portions (“mappings”) of the file to different mappers, and each mapper modifies the content in its respective assigned portion of the file. Each mapper maintains and updates a respective ‘local mTime value,” which is indicative of the most recent time the file was modified by that particular mapper. The owner consolidates the local mTime values reported by the mappers, so as to produce and continuously update the global mTime value for the entire file.

FIG.2is a flow chart that schematically illustrates a method of updating the local mTime value by a mapper, in accordance with an embodiment of the present disclosure. The method ofFIG.2is typically carried out by the various mappers, whenever a mapper writes to the file, possibly in parallel and without coordination with one another.FIG.3below describes the process of consolidating these local updates by the owner, for updating the global mTime value.

The method ofFIG.2begins with a mapper writing data to its assigned portion of the file, at a writing step60. The mapper sets its local mTime value to the time at which the write operation of step60took place, at a local updating step64. In some embodiments, the mapper stores the updated local mTime value together with the updated portion of the file in the non-volatile storage, in a dedicated journaling record. This sort of updating is referred to as “piggyback journaling.”

In these embodiments, the distributed FS occasionally (e.g., periodically) scans the dedicated journaling records of the file, combines the updates recorded in the records to produce an updated copy (“snapshot”) of the file, stores the snapshot in the non-volatile storage, and erases the (now obsolete) journaling records.

It should be noted, however, that the use of piggyback journaling is not mandatory. In alternative embodiments, the mapper may store the updated local mTime value in the non-volatile storage using any other suitable scheme.

At a global update requesting step68, the mapper initiates an update of the global mTime value by sending an update request to the owner. The request requests the owner to update the global mTime value to reflect the update of the local mTime value. Among other possible attributes, the request indicates the updated local mTime value.

FIG.3is a flow chart that schematically illustrates a method of updating the global mTime value by the owner of the file, in response to updates of the local mTime values by the mappers, in accordance with an embodiment of the present disclosure.

The method ofFIG.3begins with the owner receiving an update request from a certain mapper (e.g., the request sent at step68ofFIG.2above), at a request reception step70. At an mTime comparison step74, the owner checks whether the local mTime value in the request is larger than the current global mTime value. If so, the owner sets the global mTime value to the local mTime value specified in the request, at a global updating step78.

Otherwise (i.e., if the local mTime value in the request is smaller than or equal to the current global mTime value), the owner increments the global mTime value by a predefined small increment, at a global incrementing step82. Typically, the increment is chosen to be the finest-resolution step possible in the format used for representing the mTime values. In the present example, the predefined increment is 1 nS. Alternatively, however, any other suitable increment size can be used.

The method ofFIG.3is typically repeated by the owner upon receiving each update request from one of the mappers.

Incrementing the global mTime value in response to every update is important for maintaining the global mTime value monotonically increasing, for retaining consistency, and for mitigating scenarios in which multiple mappers request update their local mTime values simultaneously.

FIG.4is a flow chart that schematically illustrates a method for recovering the global mTime value following sudden power failure, in accordance with an embodiment of the present disclosure. When recovering from a sudden power failure, the owner counts the number of write operations to the file that are still open, i.e., the number of write operations to the file that were in progress at the time the power failure occurred, at a counting step90. This number is denoted N.

The owner then reads the last-recorded global mTime value from the non-volatile storage, and increments it depending on N and on the predefined increment α defined above, at a global recovery step94. In the present embodiment, Δ=1 nS, and the owner sets the global mTime value to be MAX+(N−1)·1 nS, wherein MAX denotes the largest (and thus the latest) among the local mTime values journaled in the open write operations before the power failure. In alternative embodiments, the owner may set the global mTime value to any other suitable function of N and/or Δ. The owner stores the new global mTime value to the non-volatile storage.

Although the embodiments described herein refer mainly to write operations and modification-time values of files, the disclosed techniques can also be used with other suitable storage operations, and for managing other suitable file attributes. For example, the distributed FS can use the disclosed techniques for updating the access time values (“aTime”) of files. The aTime value of a file is indicating of the most recent time the file was accessed (read or written, not necessarily written as the mTime value). In some embodiments, when using the disclosed techniques to manage aTime value, it is not mandatory to increment the global aTime value if the local aTime value in a request is not larger. In other words, steps74and82ofFIG.2can be omitted.

Although the embodiments described herein refer mainly to managing attributes of individual files, the disclosed techniques can alternatively be used for managing attributes (e.g., mTime or aTime) of other suitable objects, for example groups of files or entire directories.

It will thus be appreciated that the embodiments described above are cited by way of example, and that the present disclosure is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present disclosure includes both combinations and sub-combinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art. Documents incorporated by reference in the present patent application are to be considered an integral part of the application except that to the extent any terms are defined in these incorporated documents in a manner that conflicts with the definitions made explicitly or implicitly in the present specification, only the definitions in the present specification should be considered.