CN100505762C - Distributed multi-level cache system for object network storage - Google Patents

Abstract

The buffering system includes buffer in zero level in use for buffering metadata, buffer in first level in use for buffering data at client end, and buffer in second level in use for buffering data at object storage node. Management module of buffer in zero level is in charge for looking up, replacing metadata in buffer in zero level, and accessing metadata according to network access control protocol; Management module of buffer in first level is in charge for applying, assigning and recycling shared memory space as well as substituting buffer unit; Management module of buffer in second level is in charge for carrying unitive substitution in multiple queues for buffer in second level between object storage nodes. The invention possesses advantages of solving consistency of buffering metadata at client end, quickening speed fro accessing metadata, reducing response time for requesting service and average search time, raising I/O throughput, and data transmission rate.

Description

Distributed multi-level cache system for object network storage

technical field

The invention belongs to the technical field of computer storage, and in particular relates to a distributed multi-level cache system suitable for object network storage.

Background technique

The next-generation Internet is faster, larger, and has higher security and service quality, which requires the network storage system based on the next-generation Internet to have high efficiency, scalability, security and high service quality. Traditional storage systems built on the basis of blocks and files (such as NAS, SAN, etc.) can no longer meet the above requirements. Professor Paterson of the University of California, Berkeley, Carnegie Mellon University and other universities and research institutions have proposed an object-based (Object-Based) network storage interface protocol to facilitate the construction of efficient large-scale network storage systems.

The Chinese invention patent publication number is CN 1728665A, which discloses a method for building an object-based storage system. The object-based network storage system described in this invention includes 1 metadata server, N object storage nodes and M clients connected by computer network, and its object file system is based on the ext2 file system of standard Linux, with log File system properties.

A large-scale network storage system needs to design an efficient parallel file system to match it, in order to achieve high bandwidth, high scalability, high security, and intelligence of the storage system. As the I/O subsystem of the system, the file system will become a bottleneck for further improvement of system performance in many cases. Designing a high-performance parallel file system needs to be considered from two aspects: on the one hand, reduce the number of disk accesses as much as possible, and on the other hand, simplify the network access protocol as much as possible and reduce the network protocol overhead. File system caching technology is a mechanism to minimize the number of times the file system accesses the disk, and to improve the performance of the file system to make up for the lack of disk performance; at the same time, a good cache system design can also simplify network access protocols.

At present, the object-based storage file system has become a research hotspot for high-performance network storage file systems, such as Cluster File Systems' Lustre, Panasas' ActiveScale file system, and the object-oriented file system OBFS developed by the University of California, Santa Cruz, etc. . These file systems have their own characteristics, and they are also mentioned in the file system cache, but they mainly focus on the research of a certain aspect of the cache strategy. The cache system lacks integrity, resulting in complex access control protocols for the cache system and poor access request response time. Larger and other insufficient. Another way to implement caching is to run the cache as an independent device. This solution centrally manages the cache and facilitates the implementation of certain replacement and search strategies. However, independent devices increase the cost and are also a single point of failure for the system. .

Contents of the invention

The purpose of the present invention is to provide a distributed multi-level cache system suitable for object network storage. This system overcomes the shortcomings of the existing cache system, such as complex access control protocols and large delays in access requests. The three-level cache provides a complete cache system and its cache strategy, simplifies the network access protocol between nodes, reduces the load on the metadata server, reduces the response time of data access requests, improves the system I/O processing capacity, and reduces the system construction cost.

A distributed multi-level cache system suitable for object network storage provided by the present invention is characterized in that: the system includes a zero-level cache and a first-level cache located in the client, and a second-level cache located in the object storage node; The zero-level cache is used to cache metadata from the metadata server, the first-level cache is the data cache that directly serves the application process, and the second-level cache is the data cache that directly serves the client;

The zero-level cache management module is responsible for the search and replacement of metadata in the zero-level cache and the access to metadata in accordance with the network access control protocol;

The first-level cache management module is used to control the first-level cache, and is responsible for the application, allocation, recovery and replacement of cache units in shared memory space;

The second-level cache management module is responsible for performing multi-queue unified replacement of the second-level cache between object storage nodes.

The present invention has following characteristics:

(1) The zero-level metadata cache is set on the client side. In the case of a cache hit, the access to the metadata server is reduced once compared with the PVFS structure parallel file system, and the network traffic is reduced; a simplified metadata access protocol is designed. Solved the metadata cache consistency problem of multiple clients; accelerated the access speed of metadata and reduced the response time of service requests; improved the I/O throughput of the entire file system;

(2) The first-level data cache is implemented by shared memory, which reduces the number of memory copies during process communication and realizes data sharing between application processes; the first-level cache uses the hash-based LFU-DA algorithm, which retains the high hit rate of the LFU-DA algorithm characteristics, while greatly reducing the average lookup time of cached objects;

(3) The second-level cache in the object storage node can delay and reduce the direct access to the disk. According to the object access characteristics of the object storage node, the concept of access group is proposed, and the multi-queue unified replacement algorithm is designed at the same time, taking the access time into consideration and access frequency, so that the cache hit rate of each object storage node tends to be uniform, and the overall hit rate of the storage node cache is improved;

(4) The three-level cache together forms a distributed multi-level cache system suitable for object network storage, which greatly improves the efficiency of the storage system, reduces system delay, and improves the system data transmission rate.

Description of drawings

Fig. 1 is a schematic diagram of a distributed multi-level cache system suitable for object network storage according to the present invention;

Figure 2.1 is a schematic diagram of the file system reading process before improvement;

Figure 2.2 is a schematic diagram of the process of reading files after the client sets up the metadata cache in the present invention;

Figure 3.1 is a schematic diagram of the cache state before the allocation of cache blocks after the client sets up the first-level cache in the present invention;

Figure 3.2 is a schematic diagram of the cache state after the cache block is allocated after the client sets up the first-level cache in the present invention;

Figure 3.3 is a schematic diagram of the cache state before the cache block is released after the client sets up the first-level cache in the present invention;

Figure 3.4 is a schematic diagram of the cache state after the cache block is released after the client sets up the first-level cache in the present invention;

Fig. 4 is a flow chart of data access control in the present invention.

Detailed ways

As shown in FIG. 1 , in an object-based network storage system, a metadata server 1 , an object storage node 2 and a client 3 are connected together by a computer network. The data access process is as follows: the client 3 sends an access request to the metadata server 1; the metadata server 1 verifies the client’s identity, and queries the local metadata after confirmation. If it exists, the metadata server 1 sends an access request to the corresponding object storage node 2 Test package, after object storage node 2 confirms that the object is opened, it returns the authorization and the storage object mapping table requested by the client to metadata server 1; after receiving the information from metadata server 1, client 3 establishes a connection with the object storage node for data transmission .

The distributed multi-level cache system of the present invention includes a zero-level cache 6 in the client 3 , a first-level cache 8 and a second-level cache 4 in the object storage node 2 . The third-level cache is implemented in main memory. The zero-level cache 6 is set up in the client 3, and it caches the metadata from the metadata server 1. In the case of a cache hit, it can reduce the access to the metadata server 1 once, and the high hit rate of the metadata cache greatly reduces the Network traffic; Level 1 cache 8 is a data cache that directly serves the application process, and its hit directly eliminates the network consumption from the client 3 to the object storage node 2, improving system performance; Level 2 cache 4 is set up in the object storage node 2. Serve the client directly. 3. In the case of a cache hit, it can avoid accessing low-speed physical storage devices and speed up data access.

The three-level cache of the present invention is controlled by respective cache management modules. The zero-level cache management module 7 is responsible for searching and replacing metadata in the zero-level cache 6 and accessing the metadata server according to the network access control protocol in the case of a zero-level cache miss. Metadata search uses the cache hash table established by the global path name corresponding to the metadata item as the hash parameter to speed up the search; the metadata cache replacement strategy uses FIFO (First In First Out) queue; the metadata access control protocol first accesses zero Level 6 cache, if hit, send service request directly to metadata server 1, if miss, send metadata query request, and send service request after confirmation. The first-level cache management module 9 is responsible for the application, allocation, recovery and replacement of cache units of shared memory space. The first-level cache 8 is implemented in the form of shared memory. The system manages the application, allocation and recycling of cache space through the first-level cache management module 9; the cache unit replacement in the first-level cache 8 adopts the hash-based LFU-DA (LFU with Dynamic Aging) algorithm . The secondary cache management module 5 is responsible for the unified replacement of the secondary cache 4 between the object storage nodes 2, and adopts the multi-queue unified replacement algorithm—MQU (Multi-Queue United) algorithm.

The zero-level cache 6 is a metadata cache. In an object-based storage system, metadata includes mapping information between files and objects, object storage node information, and attribute information of storage objects. Although the object metadata (attributes) in the object-based storage system is very rich, only the user-related object attributes (such as file name and object ID mapping, object storage node location information) are saved on the metadata server 1. It does not take up much space, usually only one hundred to two hundred bytes. The zero-level cache is for the client to query whether the file exists, and only needs to keep the mapping between the file name and the object ID. Therefore, a zero-level cache space with a capacity of 1MB in the main memory can accommodate nearly ten thousand pieces of storage object metadata for query. This cost is worthwhile for the increasingly large main memory space, which ensures that the metadata The cache has a fairly high cache hit ratio. Such large-scale cached metadata makes metadata replacement infrequent. Therefore, the replacement algorithm uses a FIFO queue, which is characterized by simple implementation. However, more metadata makes searching more difficult, and the performance of the search algorithm determines the efficiency of the zero-level cache 6. The present invention adopts the hash table with the highest search efficiency, and uses the global path name corresponding to the metadata item as a hash parameter to establish a cache hash table to speed up lookups. The zero-level cache is empty when the client starts, and the zero-level cache obtains the backup of the required metadata from the metadata server when the client accesses the off-site data for the first time.

In the object-based network storage system, the client application process data access first checks the path of the file to be accessed (the data access form presented by the application program is still a file), and if it is a local file, call the local operation function to process the file; otherwise , convert the path of the file to be accessed into a unique path name of the global file system, and then establish a connection with the metadata server. In an object-based network storage system, data is stored centrally on object storage nodes, so the operations on metadata in the entire object file system are very frequent. The distributed file system used in the object network storage system involved in the present invention is designed with reference to PVFS. Its access process is clear and easy to implement. However, PVFS needs to visit the metadata server twice for each metadata operation, once to query and once to obtain real metadata. , will bring a large amount of network communication overhead, and cannot meet the requirements of the object file system. The data access protocol must be improved. The improved method is to set up a zero-level cache on the client.

Figure 2.1 shows the data access process of an object storage node without setting up a zero-level cache. From the perspective of the client, it is mainly divided into the following steps:

A1: The client converts the path of the file to be accessed into a unique path name of the global file system, establishes a connection with the metadata server, and sends a query request;

A2: The metadata server authenticates the client's access. If it is legal, it queries the metadata to confirm whether the accessed file exists, and sends a response message to the client; otherwise, the client's access is illegal and the process ends;

A3: The client receives the response information, if the data to be accessed exists, it sends a read object request to the metadata server, otherwise it reports an error to the application process, and the process ends;

A4: After the metadata server receives the client's request to read the object, it sends the object ID to the relevant object storage node;

A5: After the object storage node verifies the metadata server access request, it opens the object and sends a response message to the metadata server;

A6: After receiving the response, the metadata server responds to the client with the authorization to the client, the mapping table of file and storage object ID, and the location information of the storage object node;

A7: After receiving the response information from the metadata server, the client sends a read object request command packet to the object storage node corresponding to the received metadata, and establishes a connection with the corresponding object storage node;

A8: The object storage node verifies the user request, and sends the data object to the client after confirmation until the end of the data transmission.

It can be seen that the above data access control protocol involves a total of two network communications between the client and the metadata server, one network communication with each related object storage node, and one network communication between the metadata server and each storage node. The network communication overhead is very large, which seriously limits the improvement of system performance.

Analyzing the above protocol in detail, it is found that the protocol can be simplified. The present invention constructs a zero-level metadata cache on the client side is a method for simplifying the above-mentioned network access control protocol. The simplified network access control protocol is shown in Figure 2.2, which mainly consists of the following steps:

B1: The client converts the path of the file to be accessed into the unique path name of the global file system, and the application process queries the zero-level cache to determine whether the cache is hit, and the hit enters step B4;

B2: If the zero-level cache misses, the client establishes a connection with the metadata server and sends a metadata query request;

B3: The metadata server authenticates the client’s access. If it is legal, it queries the metadata, confirms whether the accessed file exists, sends a response message to the client, and proceeds to step B5;

B4: The client responds to the application process when the zero-level cache hits;

B5: After the client application process receives the response information, if the access object exists, it sends a read object request to the metadata server, otherwise an error is reported and the process ends;

B6: After the metadata server receives the client's request to read the object, it sends the object ID to the relevant object storage node;

B7: After the object storage node verifies the metadata server access request, it opens the object and sends a response message to the metadata server;

B8: After receiving the response, the metadata server responds to the client with the authorization to the client, the mapping table of file and storage object ID, and the location information of the storage object node, and updates the zero-level cache at the same time;

B9: After receiving the response information from the metadata server, the client sends a read object request command packet to the object storage node corresponding to the received metadata, and establishes a connection with the corresponding object storage node;

B10: The object storage node verifies the user request, and sends the data object to the client after confirmation, until the end of the data transmission.

From the above data network access control protocol, it can be seen that the zero-level cache can omit one visit to the metadata server in the case of a hit, and the extremely high zero-level cache hit rate greatly reduces the network overhead of metadata access.

Generally, after setting up a cache, there will be cache consistency problems, because each client has a zero-level cache, which will inevitably cause cache inconsistency. Failure to address cache coherence issues, especially metadata caching, will have catastrophic consequences for the system. The simplified network access control protocol of the present invention well solves the problem of metadata cache inconsistency. Metadata changes caused by any operation on data objects must be recorded in the metadata server or object storage node. The consistency of object metadata is guaranteed by the client's second metadata access B5-B8, because the real metadata of all operations is returned from the metadata server by operation B8, and is not directly read from the local zero-level cache . When the client opens an object or performs other metadata-related operations, it needs to visit the metadata server at least once. Any operation on the object by the user must notify the metadata server to ensure the correctness of the object metadata at all times; the object storage node only receives data from An open request from the metadata server. The above two guarantee the consistency of metadata, so even if there is inconsistency in metadata in multiple zero-level caches, it will not cause any problems. Assume that while a client is holding an object's metadata in the zero-level cache, the metadata is changed due to other client operations, resulting in inconsistencies in the metadata. The purpose of the first metadata access request B1-B4 is only to check whether the target file exists. The second metadata access request B5-B8 does not obtain metadata from the inconsistent zero-level cache. On the contrary, the second metadata access The metadata obtained by B5-B8 will also update the zero-level cache, thus avoiding the possible consequences of the zero-level cache inconsistency on the system.

The first-level cache in the client according to the present invention is implemented in a shared memory manner. The daemon process in the first-level cache management module is responsible for the application, allocation and recovery of the shared memory space, but is not responsible for handling the read and write requests of other processes. The application process maps the shared memory to its own virtual memory space. When it needs to read and write data, the application process can directly access the cache in the form of shared memory, thus avoiding a large amount of communication between processes and multiple copies of memory. The daemon process applies for a piece of shared memory space to the system at one time when the client starts, divides the space into many physically continuous small data blocks according to the size of the cache block, and manages it with a cache block array. The system also maintains an allocatable cache block array with the same size as the cache block array, indicating the currently allocatable cache block array items. The value of the allocatable cache block array item represents the subscript of the allocatable cache block array. When the value of the allocatable cache block array item is -1, it means that the block it represents has been allocated; when the value of the allocatable cache block array item is s, it means that the cache block s will be allocated. When the system is initialized, all cache blocks are free, and the value of the ith allocatable cache block array item is i. For the convenience of management, two values are used—the allocatable number and the free number to indicate the free items available for allocation in the allocatable cache block array: the allocatable number indicates the first data block available for allocation, and the free number indicates the last free item The data block also represents the position that will be inserted into the array of allocatable cache blocks when the block is reclaimed. If the allocatable number is equal to the free number, it means that there is no free cache space and it needs to be replaced to make room.

The first-level cache management module daemon process applies for, allocates, and reclaims cache space in the following steps:

(1) Apply for a cache space from the system, and divide the cache space into blocks according to the specified cache block size, and use a cache block array to represent the cache space, and the size of the array is the total number of blocks in the cache space requested;

(2) The daemon process maintains an array of allocatable cache blocks, the size of which is the same as the array of cache blocks, and indicates the head and tail of the free items in the allocatable cache block array with the allocatable number and the free number respectively;

(3) When the application process accesses the shared cache space, enter step (4); when the application process releases the cache space, enter step (5);

(4) When accessing the shared cache space, if it hits, then directly perform read and write operations; otherwise, first judge whether there is a free cache block available, the method is to judge whether the assignable number and the idle number are equal, if the assignable number and the idle number are equal, Go to step (4.1), otherwise go to step (4.2);

(4.1) If the allocatable number is equal to the free number, it means that there is no free block available, then the cache block is replaced, and then read and write operations are performed after the replacement, and the work is completed;

(4.2) The disequilibrium between the allocatable number and the free number indicates that there are still free blocks available, read the value of the array item of the allocatable cache block indicated by the allocatable number, and this value is the subscript of the first free block available for allocating cache , allocate the cache block indicated by the subscript to the application process, set the value of the array item of the allocatable cache block indicated by the allocatable number to -1, then add 1 to the allocatable number and take the remainder modulo the total number of cache blocks Operation, the remainder is the new assignable number, which indicates the next free block, and the work is completed;

(5) When the application process releases the cache block, first add 1 to the idle number and perform a remainder operation based on the total number of cache blocks to obtain a new idle number, and set the value of the array item of the allocatable cache block indicated by the idle number to the released cache Block number, the recovery of the cache block is completed, and the work is completed.

Figure 3.1-3.4 is a specific example of the first-level cache allocation and release process. Figure 3.1 is the state of the cache unit before its first allocation. Each value of the array of allocatable cache blocks is equal to the subscript. The allocatable number is 0, indicating that the first allocable data block is the zeroth item of the cache block array; the idle number is n, indicating that the last allocatable data block is the nth item of the cache block array. The state of the first block of the cache block array after being allocated is shown in Figure 3.2: the value of the zeroth item of the allocatable cache block array is -1, and the value of the allocatable number advances to 1, indicating that the next allocatable block is The first item of the cache block array. Figure 3.3 depicts the state of a data block before it is freed for the first time. Before this, the first 4 blocks have been allocated; Figure 3.4 describes the state after the data block is released: after the second block of the cache block array is released, according to the indication of the free number, the value of the zeroth item of the cache array will be allocated It is changed to 2, indicating that the last allocatable block is the second item of the cache block array, and the idle number cycle advances forward, and its value is 0.

The above is the realization of the first-level cache space application, allocation and reclaim of the present invention, which is completed by the daemon process, but it does not handle the specific process read and write requests, and the read and write requests are implemented by the hash-based LFU-DA ( LFU with Dynamic Aging) algorithm is completed.

LFU-DA is an improved algorithm of LFU. The LFU algorithm is a replacement algorithm based on frequency access priority, that is, it only considers that data blocks that have been accessed many times have a high chance of being re-visited in the near future, but ignores the latest access time of these data blocks. In fact, the system often turns to other tasks after processing one task. Those data blocks that were accessed very frequently in the previous task may never have the opportunity to be re-visited in the new task, but the number of accesses to these data blocks that occupy a large amount of cache space is very large. Using the LFU algorithm does not It is possible to replace these data blocks, which greatly reduces the utilization rate of the cache space. The LFU-DA algorithm adds the "age" attribute to the cached data blocks, and it is adjusted continuously during the access process, but the age of all blocks is not adjusted every time, but only dynamically adjusted during access. The "age" K _i of the data block is jointly obtained from the access times of the data block and the "age" of the last replaced block. The calculation formula of K _i is as follows:

K _i =CI*F _i +K (Formula 1)

Among them, F _i is the number of times the data block is accessed, and the value of the number of access times F ₁ of the data block added to the cache for the first time is 1; CI is the frequency factor, which is a variable parameter, usually the value is 1, but it can be Adjust its value according to different applications of the system to get the best value for the current application; K is a global variable with an initial value of 0. Whenever a data block is replaced, the value of K is adjusted to the "age" of the replaced block . The LFU-DA algorithm replaces the data block with the smallest "age" every time. Practice shows that the LFU-DA algorithm has a higher hit rate than the LRU algorithm. Since LFU-DA considers both "access time" and "access frequency", it can be used as a client cache replacement algorithm to obtain good performance, and it has a significantly higher hit rate than an algorithm that only considers access time. However, when the file system cache capacity is large, the LFU-DA algorithm has a disadvantage: it will cause the cache queue to be too long, causing the application to take too long to find data in the cache.

The present invention further improves the LFU-DA algorithm. The specific method is: divide the too long cache queue into m small queues according to the selected hash function, and use the block number of the cache data block and the ID of the object to which the data block belongs to find the hash value, and then insert the data block into the corresponding queue according to the requested hash value. Each hash queue is an LFU-DA queue. This speeds up cache lookups. The proof method is simple: assuming that the average search time of the LFU-DA algorithm is t, and the system cache queue is divided into m queues, then the average search time of the improved algorithm is about t/m.

In the cache structure of the shared memory mode, multiple processes may access the same cache block at the same time, and locks are required to achieve mutual exclusion between processes. The size of the lock granularity has a great impact on cache performance. If the granularity is too large, it will cause too much consistency and mutual exclusion overhead. If the granularity is too small, it will bring too much lock management overhead. The lock granularity of the cache in the present invention is at the queue level. The cache queue is divided into m small queues according to the hash function, and a read-write mutex is set up for each small queue. It is easy to manage using the queue-level lock granularity strategy. The daemon process is responsible for statically applying for a lock for each queue in advance when the file system is initially started, and then all locks are also managed and revoked by the daemon process. In this example, the lock is implemented using a semaphore.

The control flow of the first-level cache management module is as follows:

(1) The daemon process applies for shared memory space, maintains and manages the cache block array and the allocatable cache block array;

(2) Apply the process data access request, judge whether the first-level cache hits, hit and enter step (5);

(3) The first-level cache misses, access the object storage node according to the zero-level cache network access protocol, and obtain the required data object, the data object access frequency is 0, judge whether the cache queue is full, and if it is full, enter step (4), Otherwise, put the data object into an empty cache unit and enter step (5);

(4) cache queue is full, then find the cache unit with the smallest age in all cache units, replace the cache unit with the smallest age with the data object, make the global variable K equal to the replaced block age;

(5) Add 1 to the data block access frequency, calculate the new age according to (Formula 1), then calculate the hash value queue number, apply for a queue-level mutex, insert the cache unit into a new queue, and perform cache unit read and write operations.

The second-level cache management module is responsible for the unified replacement of the second-level cache between object storage nodes, and adopts the multi-queue unified replacement algorithm - MQU (Multi-Queue United) algorithm.

In large-scale object network storage systems, a file is often divided into multiple objects, which are stored on different object storage nodes to improve parallel bandwidth. In high-performance computing (such as matrix computing), it is often necessary to obtain data objects on all storage nodes at the same time before starting operations. If the access delay of a certain node is large, a single point of failure in the system will occur and the computing performance will be reduced. In order to solve the problem of a single point of failure, the present invention proposes the concept of an access group, that is, data objects with the same attribute distributed on different object storage nodes form the same access group. The MQU algorithm uniformly replaces the data objects belonging to the same access group, either all of them are retained or all of them are replaced, thus ensuring a high system hit rate.

The second-level cache on the object storage node is not like the first-level cache in the client. The access has a high degree of temporal and spatial locality, which makes the algorithm that considers access time priority have a higher hit rate in the first-level cache. . However, replacement algorithms based on access time considerations such as LRU and MRU lack consideration of data block access frequency; replacement algorithms based on access frequency considerations such as LFU lack consideration of access time and have cache pollution problems; algorithms such as LFU-DA and MQ Although the access time and access frequency are comprehensively considered, the unified replacement among multiple storage nodes in a distributed environment is not considered, and the cache hit rate and cache read and write response speed are not ideal in a distributed system with multiple storage nodes.

The MQU algorithm of the present invention is designed based on the MQ algorithm. During the replacement, the objects belonging to the same access group on different storage nodes are given overall consideration. Compared with the traditional data block replacement algorithm alone, the MQU algorithm reduces the number of storage nodes. The probability of a single node cache miss in the level cache, and the cache hit rate of each node tends to be more average. How to determine whether different objects belong to the same access group is realized by using the property of the set object, and the objects belonging to the same set are located in the same access group.

The MQU algorithm can be divided into three parts: the access of the cache unit, the dynamic adjustment of the cache queue and the selection of the replacement object. Among them, the access of the cache unit is the main body of the algorithm, which calls the other two parts of the algorithm. The algorithm is described as follows:

The MQU algorithm is designed on the basis of the MQ algorithm. The MQU algorithm uses the access frequency of objects in an access group as the basis for uniform replacement. When each object storage node uniformly replaces an access group, it needs to know the access frequency of objects in the same access group on other storage nodes. Storage nodes maintain all storage node cache information to achieve this. The MQU algorithm uses multiple queues to manage the cache information belonging to each storage node, that is, q LRU queues are used to manage the cache information belonging to each storage node. The value of q is determined by the specific application, ranging from 4 to 8 between. Which LRU queue to insert it into is determined according to the access frequency of the object. The cache information of each storage node is divided into q parts, and each part corresponds to one level, so that an object can be quickly found from the lowest level cache queue for replacement. In this way, p*q cache queues must be maintained on each storage node, where p is the number of object storage nodes.

The MQU algorithm dynamically adjusts the access frequency of the data object according to the time when the object is not accessed in the cache. For this purpose, a lifetime (lifeTime) is set for each object, and the lifetime (expireTime) of the object is set as the current time (currentTime ) plus lifetime. If the object has passed the lifetime, that is, the lifetime is less than the current time, the object will be adjusted to the lower-level queue (the time allowed for not being accessed is shorter), and the data objects in the lowest-level queue may be adjusted out of the cache .

The replacement of objects from the cache by the MQU algorithm is not simply discarded, but a FIFO queue is provided for the q cache information queues belonging to each storage node to record the historical access frequency and cache unit tag number of the discarded object. A discarded data object is revisited, from which its historical access frequency can be found. When implementing overall replacement for an access group, it is often necessary to find out the access frequencies of other data objects in the same access group. In order to reduce the lookup time, the MQU algorithm links all data objects in the same access group together.

The control flow of the secondary cache management module is as follows:

(1) Apply for cache space and monitor client access requests;

(2) The object storage node establishes a connection with the client, and the client requests to operate on a certain data object a;

(3) The object storage node accesses the second-level cache to determine whether the second-level cache hits. If it hits, move the object a from the current queue to the higher-level queue. If it is in the highest queue, it remains unchanged and enters step (6). Otherwise, L2 cache miss, enter step (4);

(4) Determine whether there are free blocks in the cache queue, if so, enter step (6), otherwise, the cache queue is full, and select the replaced object according to steps (4.1)-(4.5):

(4.1) Select the object to be replaced, and use the first object in the lowest-level non-empty queue of the object storage node as the object to be replaced;

(4.2) If the replaced object does not belong to any access group, discard it directly and proceed to step (5); otherwise, obtain the maximum access frequency of all objects in the access group where the replaced object is located;

(4.3) If the maximum access frequency of all objects in the access group is less than or equal to the access frequency of the replaced object, then discard all objects in this access group and enter step (4.5);

(4.4) Otherwise, adjust the access frequency of all objects in this access group to the maximum access frequency among all objects in this access group, insert the corresponding queue tail, adjust the replaced object to be the next object of the lowest non-empty queue, and enter the step (4.2);

(4.5) The FIFO queue records the access frequency of the replaced object and returns the replaced object;

(5) The cache queue is full and if the data object a is in the FIFO queue, obtain the access frequency of the data object a from the FIFO queue, otherwise the access frequency of the data object a is set to the initial value 0;

(6) Read object a from the storage device, add 1 to the access frequency of object a, calculate the new queue number, insert object a into the tail of the new queue, calculate the lifetime of object a, follow steps (6.1)-(6.3) Dynamically adjust the second-level cache queue of the object storage node;

(6.1) Add 1 to the current time;

(6.2) In the current object storage node, one of the q secondary cache queues is sequentially selected, and the first object of the current queue is selected. If the current queue is the last level queue, enter step (7);

(6.3) If the lifetime of the first object is less than the current time, adjust this object to the end of the next-level cache queue, the new lifetime of the object is the current time plus the lifetime, the current queue level plus 1, and enter step (6.2) ;

(7) The operation ends.

The distributed multi-level cache system of the present invention makes good use of existing main memory resources and achieves good performance with minimum cost. FIG. 4 is a flow chart of data access control after the distributed multi-level cache system is provided in the present invention.

Claims (5)

1. A distributed multi-level cache system suitable for object network storage, characterized in that: the system includes a zero-level cache and a first-level cache located in the client, and a second-level cache located in the object storage node; the zero-level cache The cache is used to cache metadata from the metadata server. The first-level cache is a data cache that directly serves the application process, and the second-level cache is a data cache that directly serves the client; The zero-level cache management module is responsible for the search and replacement of metadata in the zero-level cache and the access to metadata in accordance with the network access control protocol; The first-level cache management module is used to control the first-level cache, and is responsible for the application, allocation, recovery and replacement of cache units in shared memory space; The secondary cache management module uses a multi-queue unified replacement algorithm to perform multi-queue unified replacement of the secondary cache of the object storage node of the same access group. The same access group consists of objects with the same attribute and distributed on different object storage nodes. Data object composition. 2. The system according to claim 1, characterized in that: the network access control protocol in the zero-level cache management module is: (B1) The client converts the path of the file to be accessed into the unique path name of the global file system, and the application process queries the zero-level cache to determine whether the cache hits, and if it hits, enter step (B4); (B2) The client establishes a connection with the metadata server, and sends a metadata query request; (B3) metadata server carries out identity verification to client access, if legal then inquires metadata, confirms whether the file of access exists, sends response information to client, enters step (B5); (B4) responding to the application process; (B5) After the client application process receives the response information, if the access object exists, it sends a read object request to the metadata server, otherwise an error is reported, and the process ends; (B6) After the metadata server receives the client's request to read the object, it sends the object ID to the relevant object storage node; (B7) After the object storage node verifies the access request of the metadata server, it opens the object and sends a response message to the metadata server; (B8) After the metadata server receives the response, it responds to the client with the authorization to the client, the file and storage object ID mapping table, and the location information of the storage object node, and updates the zero-level cache at the same time; (B9) After receiving the response information from the metadata server, the client sends an object request command packet to the object storage node corresponding to the received metadata, and establishes a connection with the corresponding object storage node; (B10) The object storage node verifies the user request, and sends the data object to the client after confirmation, until the end of the data transmission. 3. The system according to claim 1 or 2, characterized in that: the daemon process of the first-level cache management module applies for, allocates and reclaims the first-level cache space according to the following steps: (C1) Apply for a cache space to the system, and divide the cache space into blocks according to the size of the specified cache block, and represent the cache space with an array of cache blocks, and the size of the array is the total number of blocks of the applied cache space; (C2) maintaining an array of allocatable cache blocks, the size of which is the same as the array of cache blocks, and indicating the head and tail of free items in the array of allocatable cache blocks with an allocatable number and a free number respectively; (C3) When the application process accesses the shared cache space, enter step (C4); when the application process releases the cache space, enter step (C5); (C4) When accessing the shared cache space, if it hits, then directly perform read and write operations; otherwise, first judge whether there is an idle cache block available, the method is to judge whether the assignable number and the idle number are equal, if the assignable number and the idle number are equal, Enter step (C41), otherwise enter step (C42); (C41) The distributable number and the free number are equal and represent that there is no free block available, then the cache block is replaced, and then read and write operations are performed after the replacement, and the work is completed; (C42) The disequilibrium between the allocatable number and the free number indicates that there are still free blocks available, read the value of the array item of the allocatable cache block indicated by the allocatable number, and this value is the subscript of the first free block available for allocating cache , allocate the cache block indicated by the subscript to the application process, set the value of the array item of the allocatable cache block indicated by the allocatable number to -1, then add 1 to the allocatable number and take the remainder as the modulo of the total number of cache blocks Operation, the remainder is the new assignable number, which indicates the next free block, and the work is completed; (C5) The application process releases the cache block. First, the idle number is increased by 1, and then the total block number of the cache is used as a modulo to do a remainder operation to obtain a new idle number, and the value of the array item of the allocated cache block indicated by the idle number is set to be released Cache the block number, complete the recovery of the cache block, and the work is completed. 4. The system according to claim 3, wherein the first-level cache management module replaces the cache unit according to the following steps: (D1) Apply for shared memory space, maintain and manage cache block arrays and allocatable cache block arrays; (D2) application process data access request, judging whether the first-level cache hits, hits and enters step (D5); (D3) Level-1 cache misses, access object storage node according to zero-level cache network access protocol, obtain required data object, data object access frequency is 0, judge whether cache queue is full, if full then enter step (D4), Otherwise, put the data object into an empty cache unit and go to step (D5); (D4) Find the cache unit with the smallest age in all cache units, replace the cache unit with the smallest age with the data object, make the global variable K equal to the age of the replaced block; (D5) Add 1 to the data block access frequency, calculate the new age Ki according to formula (1), then find the hash value queue number, apply for a queue-level mutex, insert the cache unit into a new queue, and perform cache unit read and write operations ; K _i ＝CI*F _i +K formula (1) Among them, F _i is the number of times the data block is accessed, and the value of the number of data block accesses F ₁ added to the cache for the first time is 1; CI is the frequency factor; the K value is adjusted to be replaced when a data block is replaced The "age" of the block. 5. The system according to claim 4, wherein the second-level cache management module uniformly replaces the second-level cache between object storage nodes according to the following steps: (E1) Apply for cache space and monitor client access requests; (E2) The object storage node establishes a connection with the client, and the client requests to operate on a certain data object a; (E3) The object storage node accesses the secondary cache, and judges whether the secondary cache hits. If it hits, move the above-mentioned object a from the current queue to the higher-level queue. If it is in the highest queue, it will not change, and enter step (E6), otherwise , the second-level cache miss, enter step (E4); (E4) Judging whether the cache queue has free blocks, if so, enter step (E6), otherwise, the cache queue is full, select the replaced object according to steps (E41)-(E45): (E41) Select the object to be replaced, and use the first object in the lowest-level non-empty queue of the object storage node as the object to be replaced; (E42) If the replaced object does not belong to any access group, directly discard it and enter step (E5); otherwise, obtain the maximum access frequency of all objects in the access group where the replaced object is located; (E43) If the maximum access frequency of all objects in the access group is less than or equal to the access frequency of the replaced object, then discard all objects of this access group and enter step (E45); (E44) Adjust the access frequency of all objects in this access group to the maximum access frequency among all objects in this access group, insert the tail of the corresponding queue, adjust the replaced object to be the next object of the lowest non-empty queue, and turn to the step (E42); (E45) The FIFO queue records the access frequency of the replaced object, and returns the replaced object; (E5) The cache queue is full and if the data object a is in the FIFO queue, obtain the access frequency of the data object a from the FIFO queue, otherwise the access frequency of the data object a is set to an initial value of 0; (E6) read object a from storage device, add 1 to the access frequency of object a, calculate new queue number, insert object a into the tail of new queue, calculate the lifetime of object a, according to steps (E61)-(E63) Dynamically adjust the second-level cache queue of the object storage node; (E61) Add 1 to the current time; (E62) Select one of the q second-level cache queues in the current object storage node, where q is the number of cache information belonging to each storage node, and the value of q is between 4 and 8; select the current queue If the first object of the current queue is the last level queue, enter step (E7); (E63) If the lifetime of the first object is less than the current time, adjust this object to the tail of the next level cache queue, the new lifetime of the object is the current time plus the lifetime, the current queue level plus 1, and enter the step (E62) ; (E7) The operation ends.

Images