Patent Description:
Generally, a cache is a structure that enables performance enhancing on objects, by holding them in a memory. However, the problem with caches is maintaining high performance when a memory allocated for a cache runs out (e.g., due to a need to access a very large number of objects), and swapping to disk has to take place. When the access pattern is random, the swapping to disk becomes a critical problem, since it has to be done in almost every access. For example, caching of data containers Metadata (MD), there is a very large number of containers (millions of them, 10KB of Metadata each). Moreover, during a deduplication process, these containers metadata structures need to be accessed in a random read pattern.

There are several conventional methods that help with the swapping problem as follows:.

For example, the actions may be operations on the objects, like adding references to the container MD, adding or deleting data from the container, and other operations that actually change the container or its MD. The transaction log is a list of all of these operations written according to the execution order. Moreover, the summaries can be information like the total used container size, is the container read-only, and other information that requires very small size and can be held in memory for all of the objects without taking too much of the memory.

For example, the double caching is a method of using two cache objects, one of them being active while certain operations are performed on the other cache in the background without delaying the active cache.

<CIT> discloses a method for recycling of cash content. In particular, a method is disclosed for operating a storage system. The method includes copying content of cache memory to a local storage device, and further marking the copied content of the cache memory. <CIT> discloses a system and a corresponding method for ensuring reliability of cache data. In particular, a reliability of cash data and metadata subsequent to a reboot process may be ensured.

<CIT> discloses a method for dumping data to a dump data storage device. Further, after the dumping of data, the data storage device manages that the dumping of data is updated. <CIT> discloses a method for secure handling of memory caches.

However, conventional devices and methods have the disadvantage that when holding in cache operations on objects for updates, and summaries of objects for reads, accessing the full object on disk is required to ensure consistency of the summary. Thus has a very high impact on performance, i.e. reduces the performance of the cache.

In view of the above-mentioned problems and disadvantages, embodiments of the present invention aim to improve the conventional devices and methods. An objective is to solve the consistency problem by assigning increasing identifiers (ID) to caches dumped (i.e., the transaction logs), and using the identifiers to prevent an inconsistent summary.

The objective is achieved by the embodiments provided in the enclosed independent claims.

Advantageous implementations of the embodiments are further defined in the dependent claims. The present invention is defined by a device according to independent claim <NUM>, a method according to independent claim <NUM>, a computer program according to independent claim <NUM>, and a non-transitory computer-readable recording medium according to independent claim <NUM>.

A first aspect of the invention provides a device comprising a memory comprising one or more caches configured to store information related to at least one object from a plurality of objects, and a summary structure configured to store at least one summary for at least one object from the plurality of objects; and a storage comprising a volume configured to store at least one merge file including the plurality of objects, and a set of dump-files, each dump-file being associated with a specific cache-dump operation of the one or more caches; wherein the device is further comprising a processor configured to assign, to a cache from the one or more caches, a first identifier; perform a cache-dump operation, wherein the cache-dump operation comprises generating a dump-file associated with the first identifier and storing the information related to the at least one object from the cache to the generated dump-file; and subsequently assign, to the cache from the one or more caches, a second identifier, wherein the second identifier is larger than the first identifier.

The device of the first aspect may retain the high-performance benefits of a conventional device in updating objects and summary queries, while at the same time advantageously ensuring the consistency of the summaries. This is achieved by assigning different identifiers (for example, by adding an ever-increasing identifier) to each cache dumped (also hereinafter referred to a cache-dump operation), and to the current active cache, and by using the identifiers to maintain summary consistency when applying the transactions to the objects.

For example, the device may comprise one or more caches. Moreover, the device may assign the first identifier to a cache, and may further perform a cache dump-operation. A cache-dump operation may be an operation performed by the device, in which the information of the cache is dumped (stored) in a file. For example, the device may generate a file that may be defined as dump-file, i.e., a file which is generated for a specific cache-dump operation. The device may assign the first identifier to the cache and may further perform the cache-dump operation, e.g., by storing the information of the cache in the generated dump-file and assigning the first identifier to the generated dump-file. Afterwards, the device may assign the second identifier to the cache. Moreover, the second identifier is larger from the first identifier. The device assigns identifiers that are constantly increased.

For example, in some embodiments, the identifiers may increase by adding an increment (e.g., adding <NUM> to previous identifier), a specific number, the system's time, any other number that is always increasing, etc..

Moreover, each object from the plurality of objects may have their own ID and may be identified, as it is generally known to skilled person. In the following, the identifiers for the objects are referred to as object ID.

In some embodiments, the device may use several performance-enhancing operations, for example, performing transaction logs in order to reduce cache size, holding all the object summaries in the caches (i.e., first memory), double-caching, swapping to disk and merging in the background, etc..

In an implementation form of the first aspect, the device is further configured to add the generated dump-file to the set of dump-files.

In a further implementation form of the first aspect, the device is further configured to merge the set of dump-files to the at least one merged file.

This is beneficial, since it may increase the performance of the caches.

In a further implementation form of the first aspect, the cache-dump operation is periodically performed at a time interval of N seconds; and/or the cache-dump operation is performed when the stored capacity of the cache reaches a predefined threshold.

In a further implementation form of the first aspect, the merging is periodically performed at time intervals of M seconds; wherein M is equal to or greater than N.

In a further implementation form of the first aspect, the device is further configured to, if a given dump-file storing information related to a determined object is merged from the set of dump-files to the at least one merge file, update the at least one summary for the determined object; and associate the updated at least one summary with the identifier of the given dump-file.

This is beneficial, since it may allow maintaining critical consistency of summaries (preventing data loss), while ensuring high performance of operations (both updates and summary queries).

In a further implementation form of the first aspect, the device is further configured to, if a given cache-dump operation assigned with a given identifier changes information related to a determined object, update the at least one summary for the determined object; and associate the at least one summary with the assigned identifier of the given cache-dump operation.

In a further implementation form of the first aspect, each summary for the at least one object comprises:.

In a further implementation form of the first aspect, the device is further configured to assign each summary in the summary structure to a regular summary group representing a type of summary resulting in a non-critical error in the case of an inconsistency in the summary; or a critical summary group representing a type of summary resulting in a critical error in the case of an inconsistency in the summary.

For example, in some embodiments, the device may divide the summaries into two types including a regular summary which may be a summary that effects the behavior of the user, but inconsistency will not result in critical errors, and a critical summary which may be a summary that can result in critical errors if being inconsistent. For example, ref-count of an object, where the summary query is whether the ref-count is <NUM> (whether the object can be deleted). In this example, a critical summary is when ref-count is <NUM>.

In a further implementation form of the first aspect, the device is further configured to compare, for a determined summary, the identifier indicated in ID-<NUM> with the identifier indicated in ID-<NUM>, and assign, when performing the merging operation, the determined summary to the critical summary group, when determining that the identifier indicated in ID-<NUM> is larger or equal to the identifier indicated in ID-<NUM>.

For example, in some embodiments, when an operation on an object changes the object in a way that prevents the summary from becoming a critical summary (such as the inc-ref-count), the device may mark the object's summary in the summaries structure (which is stored in memory) with the identifier of the dump-file identifier. Moreover, the merge operation (for example, on dump-files up to id=K) will only change the summary to critical after checking in the summaries structure for indication on operations done on the object with smaller identifiers (i.e., id<=K).

For instance, in some embodiments, when merging dump-files with identifiers up to K, the device may only change summaries in the summary structure of the memory for objects that have dump-file ID of up to or equal to K, and not larger.

In a further implementation form of the first aspect, the device is based on a double caching device.

A second aspect of the invention provides a method comprising storing, in one or more caches of a memory, information related to at least one object from a plurality of objects; storing, in a summary structure of the memory, at least one summary for at least one object from the plurality of objects; storing, in a volume of a storage, at least one merge file including the plurality of objects, and a set of dump-files, each dump-file being associated with a specific cache-dump operation of the one or more caches; wherein the method further comprises assigning, by a processor, to a cache from the one or more caches, a first identifier; performing, by the processor, a cache-dump operation based on generating a dump-file associated with the first identifier and storing the information related to the at least one object from the cache to the generated dump-file; and subsequently assigning, by the processor, to the cache from the one or more caches, a second identifier, wherein the second identifier is larger than the first identifier.

In an implementation form of the second aspect, the method further comprises adding the generated dump-file to the set of dump-files.

In a further implementation form of the second aspect, the method further comprises merging the set of dump-files to the at least one merged file.

In a further implementation form of the second aspect, the cache-dump operation is periodically performed at a time interval of N seconds; and/or the cache-dump operation is performed when the stored capacity of the cache reaches a predefined threshold.

In a further implementation form of the second aspect, the merging is periodically performed at time intervals of M seconds; wherein M is equal to or greater than N.

In a further implementation form of the second aspect, the method further comprises, if a given dump-file storing information related to a determined object is merged from the set of dump-files to the at least one merge file, updating the at least one summary for the determined object; and associating the updated at least one summary with the identifier of the given dump-file.

In a further implementation form of the second aspect, the method further comprises, if a given cache-dump operation assigned with a given identifier changes information related to a determined object, updating the at least one summary for the determined object; and associating the at least one summary with the assigned identifier of the given cache-dump operation.

In a further implementation form of the second aspect, each summary for the at least one object comprises:.

In a further implementation form of the second aspect, the method further comprises assigning each summary in the summary structure to a regular summary group representing a type of summary resulting in a non-critical error in the case of an inconsistency in the summary; or a critical summary group representing a type of summary resulting in a critical error in the case of an inconsistency in the summary.

In a further implementation form of the second aspect, the method further comprises comparing, for a determined summary, the identifier indicated in ID-<NUM> with the identifier indicated in ID-<NUM>, and assigning, when performing the merging operation, the determined summary to the critical summary group, when determining that the identifier indicated in ID-<NUM> is larger or equal to the identifier indicated in ID-<NUM>.

In a further implementation form of the second aspect, the method is for a double caching device.

The method of the second aspect and its implementation forms achieve all advantages and effects that are described above for the device of the first aspect and its respective implementation forms.

A third aspect of the invention provide a computer program product including computer program code, which, when executed by a processor, causes the method according to the second aspect or an implantation form of the second aspect to be performed.

A fourth aspect of the invention provide a non-transitory computer-readable recording medium that stores therein a computer program product which, when executed by a processor, causes the method according to the second aspect or an implantation form of the second aspect to be performed.

<FIG> is a schematic view of a device <NUM>, according to an embodiment of the present invention.

The device <NUM> comprises a memory <NUM> comprising one or more caches <NUM>, <NUM> configured to store information related to at least one object from a plurality of objects, and a summary structure <NUM> configured to store at least one summary for at least one object from the plurality of objects; and a storage <NUM> comprising a volume configured to store at least one merge file <NUM> including the plurality of objects, and a set of dump-files <NUM>, each dump-file being associated with a specific cache-dump operation of the one or more caches <NUM>, <NUM>.

The device <NUM> further comprises a processor <NUM> configured to assign, to a cache <NUM> from the one or more caches <NUM>, <NUM>, a first identifier K1; perform a cache-dump operation based on generating a dump-file <NUM> associated with the first identifier K1 and storing the information related to the at least one object from the cache <NUM> to the generated dump-file <NUM>; and subsequently assign, to the cache <NUM> from the one or more caches <NUM>, <NUM>, a second identifier K2, wherein the second identifier K2 is larger than the first identifier K1.

For example the first identifier K1 may be a number (e.g., K1=<NUM>) and the second identifier K2 may be a second number such as K2=K1+<NUM> (K2=<NUM>+<NUM>=<NUM>). Therefore, the first identifier K1 may be <NUM> and the second identifier K2 may be <NUM>, which is different than the first identifier. Hence, the different cache-dump operations and/or the dump-files may be identified based on their identifiers.

The device <NUM> may comprise a circuitry (not shown in <FIG>) which may comprise hardware and software. The hardware may comprise analog or digital circuitry, or both analog and digital circuitry. In some embodiments, the circuitry comprises one or more processors (e.g., the processor <NUM>) and a non-volatile memory (e.g., the memory <NUM>) connected to the one or more processors (e.g., the processor <NUM>). The non-volatile memory may carry executable program code which, when executed by the one or more processors, causes the device to perform the operations or methods described herein.

Reference is made to <FIG> which is another schematic view of the device <NUM> for maintaining summary consistency, according to an embodiment of the present invention.

The device <NUM> of <FIG> is based on a double cashing, i.e., it comprises two caches including an active cache <NUM> and a standby cache <NUM> which may be defined as two object caches in the memory <NUM>.

The device <NUM> further comprises summaries (e.g., summary structure <NUM>) of all of the objects in the memory <NUM>.

Furthermore, the device <NUM> comprises the storage <NUM> (disk) including a list of dump-files <NUM>, each representing a cache dump operation, and a single merge file <NUM> including the plurality of objects.

In the embodiment of <FIG>, the first unmerged cache dump identifier is assumed to be K+<NUM>, for example, K may be a number. Moreover, the second identifier is assumed to be K+<NUM>. As it can be derived from <FIG>, the device <NUM> constantly increases the identifiers by adding <NUM> to the previous identifiers, i.e., K+<NUM>, K+<NUM>, K+<NUM>, K+<NUM>, K+<NUM>, K+<NUM>, etc..

The device <NUM> can maintain summary consistency, for example, by using several performance-enhancing methods including one or more of:.

Moreover, the device <NUM> may divide the summaries into two types including:.

The device <NUM> may solve the consistency problem by assigning identifiers to caches dumped (transaction logs) and using this identifier to prevent inconsistent summary in memory. For example, each cache dump has a (unique) identifier (e.g., the IDs may constantly increase).

Moreover, the summary structure that is being held in the memory <NUM> for each object (the at least one summary for each object) may include three fields as follow:.

In addition, when merging a cache to the on-disk structures, the at least one summary will be updated to a critical-summary information, only if the last cache dump ID-<NUM> for this object is smaller or equal to the cache dump ID-<NUM>.

Reference is made to <FIG> which is a schematic view of a method <NUM> for performing a cache-dump operation on a double cache, according to an embodiment of the present invention.

The method <NUM> may be performed by the device <NUM>. The method <NUM> may be invoked every time period (e.g. n seconds) or when the cache is full. The device <NUM> may switch between the caches <NUM>, <NUM>, assign the new active cache a second identifier (e.g., the first identifier + <NUM>), and may further store the previous active cache to disk (while regular operations continue and use the new active cache). For example, the following operations may be performed.

At step <NUM>, the device <NUM> starts the method <NUM>.

At step <NUM>, the device <NUM> determines if the cache <NUM> is empty or not.

At step <NUM>, when it is determined "Yes", i.e., the cache <NUM> is empty, the device <NUM> sleeps N seconds.

At step <NUM>, when it is determined "No", i.e., the cache <NUM> is not empty, the device <NUM> switches the caches.

At step <NUM>, the device <NUM> increases the new active cache ID (i.e., assigning second identifier).

At step <NUM>, the device <NUM> dumps previously active <NUM> to the set of dump-files.

Reference is made to <FIG> which is a schematic view of a method <NUM> for merging the dump-files, according to an embodiment of the present invention.

The method <NUM> may be carried out by the device <NUM>, as it is described above. The method <NUM> may be invoked every time period (e.g., m seconds, m >>n), and if there are enough dump-files may merge them. The merge process (merging dump-files K to K+n) may be, merging all the dump-files <NUM> on the storage <NUM> into a single file <NUM> including all the objects and updating the summary of the object in memory <NUM>. For example, the following operations may be performed.

At step <NUM>, the device <NUM> determines if the caches were dumped X times (e.g., cache <NUM>) dumped or not. Moreover, when it is determined "Yes", i.e., there are X cache dump files, the device <NUM> goes to step <NUM>. However, when it is determined "No", i.e., the X caches are not dumped, the device <NUM> goes to step <NUM>.

At step <NUM>, the device <NUM> merges the dump-files <NUM> and goes to step <NUM>.

At step <NUM>, when it is determined "No", i.e., the X caches are not dumped, the device <NUM> determines if <NUM>*N seconds passes since last merge or not? Moreover, when it is determined "Yes", i.e., <NUM>*N seconds are passed since last merge, the device <NUM> goes to step <NUM>. However, when it is determined "No", i.e., <NUM>*N seconds are not passed since last merge, the device <NUM> goes to step <NUM>.

At step <NUM>, the device <NUM> sleeps M seconds and afterward goes to step <NUM>.

Reference is made to <FIG> which is a schematic view of a flowchart of a method for merging dump-files with IDs of K to K+n, according to an embodiment of the present invention.

The method <NUM> may be carried out by the device <NUM>, as it described above. For example, the following operations may be performed.

At step <NUM>, the device <NUM>, for each dump-file that is open, loads <NUM>st object. For example, each object may be identified by an identifier, e.g., the object ID.

At step <NUM>, the device <NUM> find object with minimal object ID (mini).

At step <NUM>, load another object from same dump-file as min1.

At step <NUM>, the device <NUM> determines if any object is remained. Moreover, when it is determined "Yes" the device <NUM> goes to step <NUM>, and when it is determined "No", the device <NUM> goes to step <NUM>.

At step <NUM>, the device <NUM> deletes all merged dump-files.

At step <NUM>, the device <NUM> finds object with minimal object ID (min2).

At step <NUM>, the device <NUM> loads another object from same dump-file as min2.

At step <NUM>, the device <NUM> determines if the "ID (min1) = ID (min2)". Moreover, when it is determined "Yes" the device <NUM> goes to step <NUM>, and when it is determined "No", the device <NUM> goes to step <NUM>.

At step <NUM>, the device <NUM> performs a merging based on "min1=merge (min1, min2)". Moreover, the device <NUM> goes to step <NUM>.

At step <NUM>, the device <NUM> saves mini to a new merge file.

At step <NUM>, the device <NUM> determines if the "Summary (min1) = critical summary". Moreover, when it is determined "Yes" the device <NUM> goes to step <NUM>, and when it is determined "No", the device <NUM> goes to step <NUM>.

At step <NUM>, the device <NUM> determines if the "last update ID of min1>K+n". Moreover, when it is determined "Yes" the device <NUM> goes to step <NUM>, and when it is determined "No", the device <NUM> goes to step <NUM>.

At step <NUM>, the device <NUM> updates the summary (mini).

At step <NUM>, it is determined that min1=min2.

<FIG> shows a method <NUM> according to an embodiment of the invention. The method <NUM> may be carried out by the device <NUM>, as it described above.

The method <NUM> comprises a step <NUM> of assigning, by a processor <NUM>, to a cache <NUM> from one or more caches <NUM>, <NUM> of a memory <NUM>, a first identifier K1.

The method <NUM> further comprises a step <NUM> of storing, in the one or more caches <NUM>, <NUM> of the memory <NUM>, information related to at least one object from a plurality of objects.

The method <NUM> further comprises a step <NUM> of storing, in a summary structure <NUM> of the memory <NUM>, at least one summary for at least one object from the plurality of objects.

The method <NUM> further comprises a step <NUM> of storing, in a volume of a storage <NUM>, at least one merge file <NUM> including the plurality of objects, and a set of dump-files <NUM>, each dump-file being associated with a specific cache-dump operation of the one or more caches <NUM>, <NUM>.

The method <NUM> further comprises a step <NUM> of performing <NUM>, by the processor <NUM>, a cache-dump operation based on generating a dump-file <NUM> associated with the first identifier K1 and storing the information related to the at least one object from the cache <NUM> to the generated dump-file <NUM>.

The method <NUM> further comprises a step <NUM> of subsequently assigning <NUM>, by the processor <NUM>, to the cache <NUM> from the one or more caches <NUM>, <NUM>, a second identifier K2, wherein the second identifier K2 is larger than the first identifier K1.

Claim 1:
A device (<NUM>) comprising:
a memory (<NUM>) comprising
one or more caches (<NUM>, <NUM>) configured to store information related to at least one object from a plurality of objects, and
a summary structure (<NUM>) configured to store at least one summary for at least one object from the plurality of objects;
a storage (<NUM>) comprising
a volume configured to store at least one merge file (<NUM>) including the plurality of objects, and a set of dump-files (<NUM>), each dump-file being associated with a specific cache-dump operation of the one or more caches (<NUM>, <NUM>); and
a processor (<NUM>) configured to
assign, to a cache (<NUM>) from the one or more caches (<NUM>, <NUM>), a first identifier (K1);
perform a cache-dump operation, wherein the cache-dump operation comprises generating a dump-file (<NUM>) associated with the first identifier (K1) and storing the information related to the at least one object from the cache (<NUM>) to the generated dump-file (<NUM>); and
subsequently assign, to the cache (<NUM>) from the one or more caches (<NUM>, <NUM>), a second identifier (K2), wherein the second identifier (K2) is larger than the first identifier (K1).