Patent ID: 12222866

DETAILED DESCRIPTION

Features of the inventive concept and methods of accomplishing the same may be understood more readily by reference to the detailed description of embodiments and the accompanying drawings. Hereinafter, embodiments will be described in more detail with reference to the accompanying drawings. The described embodiments, however, may be embodied in various different forms, and should not be construed as being limited to only the illustrated embodiments herein. Rather, these embodiments are provided as examples so that this disclosure will be thorough and complete, and will fully convey the aspects and features of the present inventive concept to those skilled in the art. Accordingly, processes, elements, and techniques that are not necessary to those having ordinary skill in the art for a complete understanding of the aspects and features of the present inventive concept may not be described. Unless otherwise noted, like reference numerals denote like elements throughout the attached drawings and the written description, and thus, descriptions thereof will not be repeated. Further, parts not related to the description of the embodiments might not be shown to make the description clear. In the drawings, the relative sizes of elements, layers, and regions may be exaggerated for clarity.

Various embodiments are described herein with reference to sectional illustrations that are schematic illustrations of embodiments and/or intermediate structures. As such, variations from the shapes of the illustrations as a result, for example, of manufacturing techniques and/or tolerances, are to be expected. Further, specific structural or functional descriptions disclosed herein are merely illustrative for the purpose of describing embodiments according to the concept of the present disclosure. Thus, embodiments disclosed herein should not be construed as limited to the particular illustrated shapes of regions, but are to include deviations in shapes that result from, for instance, manufacturing. For example, an implanted region illustrated as a rectangle will, typically, have rounded or curved features and/or a gradient of implant concentration at its edges rather than a binary change from implanted to non-implanted region. Likewise, a buried region formed by implantation may result in some implantation in the region between the buried region and the surface through which the implantation takes place. Thus, the regions illustrated in the drawings are schematic in nature and their shapes are not intended to illustrate the actual shape of a region of a device and are not intended to be limiting. Additionally, as those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the spirit or scope of the present disclosure.

As demonstrated above, performance of a scalable, distributed object store depends upon the performance associated with accessing the metadata representing the objects stored in the object store.

Scalable storage solutions employ a massive number of I/O threads to achieve performance. However, performance can only be achieved if the I/O threads can run as concurrently as possible, and with relatively little contention between them. Such concurrency is generally achieved by the Object Store I/O stack being performant in allowing the access of the object metadata.

Conventional solutions may achieve increased performance by simply caching frequently accessed metadata, as accessing the cache is generally significantly faster than accessing memory. However, as described above, the nature of the object store metadata for modern data scalability generally uses multiple accesses to different metadata, as well as multiple accesses to the same metadata, to access corresponding object data. That is, the object store will be massively multi-threaded due to parallelism. Because a large number of objects may be accessed by multiple clients, performance of the object store is limited by the concurrency of the cache operations as the cache introduces its own synchronization primitives to maintain the cache.

Conventionally, because the I/O threads concurrently have access to the cache, the different I/O threads may concurrently perform a respective lookup operation, cache entry insertion operation, or a cache entry eviction operation, lookup operations being the most common. To avoid contention between competing operations by respective I/O threads, one of the I/O threads (e.g., a first-in-time I/O thread) may acquire a “list lock” on a list of interest prior to beginning a cache lookup operation to allow the I/O thread to walk the list in search for the node that the I/O thread is looking up without the cache entry being changed (e.g., evicted or moved) by another I/O thread. However, because all other I/O threads are unable to perform an operation on the list that has the corresponding list lock, performance of the object store may suffer, as the other I/O threads may have to wait until the list lock is released.

Embodiments of the present disclosure provide an object store that is capable of high performance by enabling the caching of frequently accessed metadata, and also provide a method of operating the object store. Further, embodiments of the present disclosure enable a high-performing cache by supporting a contention-free lookup of the cache.

A method of contention-free lookup, according to embodiments of the present disclosure, enables a massive number of I/O threads to perform concurrent cache lookups. Metadata cache lookups may be performed more than once for each I/O in the object stack. Accordingly, eliminating contention from the cache lookup operation allows performance of the object store I/O stack to scale linearly with the number of I/O threads in the I/O path. A mechanism of achieving contention-free lookup according to embodiments of the present disclosure is described below.

FIG.2depicts a structure of a cache header of a cache entry that enables contention-free lookup, according to one or more embodiments of the present disclosure.

As described further below, cache entries are preallocated, and may be kept in a free pool, which may be separate from the cache. A cache entry may be removed from the free pool to be inserted into the cache when a new metadata object is cached. Similarly a cache entry in the cache may be removed from the cache and may be placed in the free pool when the cached metadata is evicted.

Referring toFIG.2, a cache entry includes two parts—a cache header200, and cached data.

The cached data generally includes the actual metadata that is cached in the cache entry. The metadata is what the individual I/O threads (e.g., the I/O threads130shown inFIG.1) seek in a cache operation (e.g., in a lookup operation).

The cache header200generally includes various fields for managing the cache entry, or the cached data, contained in the cache. The contents of the cache header200are owned and managed by a cache manager. The fields included in the cache header200are defined by an implementation chosen for the cache (e.g., whether the implementation corresponds to a hash table, to a search tree, etc.). In the present embodiment, the cache is implemented by using a hash table structure, which will be described further below to illustrate mechanisms of a contention-free lookup method according to one or more embodiments of the present disclosure.

The cache header200also includes the following set of information-signature information210, link fields for inserting the cache entry in the cache (e.g., link fields220), and link fields for tracking the cache entry in the free pool (e.g., link fields230).

The signature information210of the cache header200indicates the state of the cache, which specifies whether the cache entry is in the free pool or is in the cache. The signature information210is generally updated before a cache entry is inserted into the cache, and before a cache entry is evicted from the cache (e.g., to be placed in the free pool).

For example, the signature information210can include a bucket ID of the hash bucket in which the cache entry is currently located when the cache entry is inserted in a hash table, or can be a free pool ID if the cache entry is free. In other embodiments, the signature information210can be an ID of a search tree in which the cache entry is inserted.

The signature information210of the cache header200also indicates information about the data contained in the cache entry (e.g., the metadata). For example, the information can include a unique key associated with the data that is cached in the corresponding cache entry.

Aside from the signature information210of the cache header200, the cache header200also includes link fields for inserting the cache entry into the cache (e.g., link fields220).

These link fields220may be used as pointers that allow the cache entry to be part of the cache structure. For example, the link fields220for managing the cache entry when the cache entry is located in the cache can be raw pointers, indices, etc., which are used to link the cache entry into a hash table (or into a search tree, in other embodiments) based on the cache implementation chosen by the cache manager.

Further, these link fields220may generally always remain valid. For example, the link fields220for managing the cache entry when the cache entry is located in the cache are invalid prior to the creation of the cache entry, but remain valid once the cache entry is first used for cache metadata. Accordingly, even if the cache entry is removed from the cache as part of a process of evicting the cache entry from the cache, the pointers can continue to point to the values that are set when the cache entry was part of the cache.

Additionally, the cache header200includes link fields for tracking the cache entry when it is located in the free pool (e.g., link fields230). These link fields230operate as pointers that are used to keep track of the cache entry when it is located in the free pool (as opposed to being located in the cache).

FIG.3depicts an example in which a cache entry is located within the cache, according to one or more embodiments of the present disclosure.FIG.4depicts an example in which a cache entry is evicted from the cache and located in a free pool, according to one or more embodiments of the present disclosure.

Referring toFIGS.3and4, in the example of the present embodiment, the cache implementation uses a hash table340to manage cache entries (e.g., “CACHE ENTRY A”350inFIG.3, or “CACHE ENTRY B”450inFIG.4) in the cache.

In a highly scalable and performant object store, there may be several thousands, of I/O threads (e.g., the I/O threads130shown inFIG.1) that seek to perform concurrent lookups in the metadata cache (e.g., the object store110) at any point of time.

A contention-free lookup method, according to embodiments of the present disclosure, eliminates synchronization that is otherwise required when an I/O thread walks a dynamic list310. A dynamic list310is a list in which insertions and deletions of cache entries can occur concurrently with lookups of multiple respective I/O threads. The dynamic list310may be contained in a hash bucket330.

Conventionally, list locks on the list310may be acquired by an I/O thread to allow the I/O thread to walk the list310in search for the node320it is looking up without the cache entry located in the node being moved to a different hash bucket330or to the free pool410. However, acquiring a list lock during a lookup may cause contention between competing cache operations occurring on the hash bucket330(e.g., contention between unrelated lookup operations, cache insert operations, and/or cache eviction operations performed by respective I/O threads).

With a cache hit rate of over 90%, a lookup operation is frequently the only cache operation to be performed by an I/O thread. Thus, increasing performance of the I/O path includes scaling with the number of I/O threads. Accordingly, reducing contention in a cache lookup may be particularly useful, because a cache lookup is the most frequent operation in the cache.

FIG.5depicts a flowchart of a method of a contention-free lookup, according to one or more embodiments of the present disclosure.

Referring toFIGS.3,4, and5, for a lookup operation, an I/O thread may map a key360(e.g., KEY=K1) for an object (e.g., by using a hash function390) into a hash table ID370and a bucket ID380in the cache (S510).

The I/O thread may then walk the collision chain310in the hash bucket330corresponding to the hash table ID370and the bucket ID380by performing the following operations for each cache entry in the list310(S520).

Walking the collision chain310may include determining whether the signature information210in the cache entry matches that of the collision chain signature (e.g., matches the hash table ID370and the bucket ID380) (S522). If there is a mismatch with expected collision chain signature, the I/O thread may restart the walk of the collision chain310(e.g., go back to (S520)).

However, if there is a match between the signature information210in the cache entry and the collision chain signature information, the I/O thread may then determine whether the key260in the signature information210of the cache entry matches the key360of the lookup operation (S524). If there is no match, the I/O thread may continue to walk the collision chain310by moving on to the next node320in the collision chain310(S526). The I/O thread may again determine whether the key260in the signature information210matches the key360of the lookup operation for the subsequent node320(S524). If there is no subsequent node320in the collision chain310, the I/O thread may read a cache entry corresponding to the data lookup operation from a data storage/memory (e.g., CACHE ENTRY B450from the free pool410), and may repopulate the cache entry450into the hash bucket330corresponding to the hash table ID370and the bucket ID380determined by the hash function390(S527).

However, if it is determined that the key260in the signature information210of the cache entry (e.g., CACHE ENTRY A350ofFIG.3) matches the key360of the lookup operation, then the I/O thread may determine that a potential match exists (e.g., the I/O thread may determine that the data sought by the lookup operation is contained in the node320containing the cache entry350) (S528).

The I/O thread may then acquire a cache entry lock on the node320potentially containing the sought after data (S530). Unlike conventional methods, there is no global lock placed on the cache or on the list310as a result of the entry lock, which comparatively reduces performance. Instead, the entry lock holds a lock on the hash bucket level such that the list310is not modified. The entry lock only protects the contents in the entry, and the list310is not required to be locked. By performing signature checking, the I/O thread is able to know that it is walking the correct list at all times, such that the I/O thread does not need a lock to protect list310.

The entry lock is mainly to protect the data in the cache entry. This is the data that the IO thread is interested in.

The cache entry lock may be in the mode requested by the I/O operation (e.g., may be a shared entry lock or an exclusive entry lock). Accordingly, the cache manager can prevent other I/O threads from moving, evicting, or otherwise changing the cache entry350before the subject lookup operation has completed.

The I/O thread may then determine whether the key260in the signature information210still matches the key360of the lookup operation following the cache entry lock (S540). That is, the I/O thread may seek to ensure that, between the time the I/O thread determined that a potential match exists (S528) and the time that the I/O thread acquired an entry lock on the cache entry350containing the potential match (S530), the cache entry350has not been moved (e.g., evicted to the free pool410, or moved to a different hash bucket330in the cache, by another I/O thread performing a competing eviction operation on the cache entry350).

If the I/O thread determines that the key260in the signature information210no longer matches the key360of the lookup operation, then the I/O thread may release the cache entry lock (S550), and may restart the walk (e.g., go back to (S520)).

However, if the I/O thread determines that the key260in the signature information210still matches the key360of the lookup operation, then the I/O thread has found the sought after metadata object in the cache, and may access the metadata object (S560).

Then, the I/O thread may return the metadata object to a corresponding caller while holding the cache entry lock in the appropriate mode as requested by the I/O thread (S570).

Accordingly, the disclosed embodiments provide improvements to the field of data storage by providing a distributed object store capable of servicing a large number of I/O threads while providing a contention-free lookup mechanism.

In the description, for the purposes of explanation, numerous specific details provide a thorough understanding of various embodiments. It is apparent, however, that various embodiments may be practiced without these specific details or with one or more equivalent arrangements. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring various embodiments.

The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the present disclosure. As used herein, the singular forms “a” and “an” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises,” “comprising,” “have,” “having,” “includes,” and “including,” when used in this specification, specify the presence of the stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items.

When a certain embodiment may be implemented differently, a specific process order may be performed differently from the described order. For example, two consecutively described processes may be performed substantially at the same time or performed in an order opposite to the described order.

The electronic or electric devices and/or any other relevant devices or components according to embodiments of the present disclosure described herein may be implemented utilizing any suitable hardware, firmware (e.g., an application-specific integrated circuit), software, or a combination of software, firmware, and hardware. For example, the various components of these devices may be formed on one integrated circuit (IC) chip or on separate IC chips. Further, the various components of these devices may be implemented on a flexible printed circuit film, a tape carrier package (TCP), a printed circuit board (PCB), or formed on one substrate. Further, the various components of these devices may be a process or I/O thread, running on one or more processors, in one or more computing devices, executing computer program instructions and interacting with other system components for performing the various functionalities described herein. The computer program instructions are stored in a memory which may be implemented in a computing device using a standard memory device, such as, for example, a random access memory (RAM). The computer program instructions may also be stored in other non-transitory computer readable media such as, for example, a CD-ROM, flash drive, or the like. Also, a person of skill in the art should recognize that the functionality of various computing devices may be combined or integrated into a single computing device, or the functionality of a particular computing device may be distributed across one or more other computing devices without departing from the spirit and scope of the embodiments of the present disclosure.

Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the present inventive concept belongs. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and/or the present specification, and should not be interpreted in an idealized or overly formal sense, unless expressly so defined herein.

Embodiments have been disclosed herein, and although specific terms are employed, they are used and are to be interpreted in a generic and descriptive sense only and not for purpose of limitation. In some instances, as would be apparent to one of ordinary skill in the art as of the filing of the present application, features, characteristics, and/or elements described in connection with a particular embodiment may be used singly or in combination with features, characteristics, and/or elements described in connection with other embodiments unless otherwise for example indicated. Accordingly, it will be understood by those of skill in the art that various changes in form and details may be made without departing from the spirit and scope of the present disclosure as set forth in the following claims, with functional equivalents thereof to be included therein.