Reducing data copy operations for writing data from a network to storage of a cached data storage system by organizing cache blocks as linked lists of data fragments

• US 6,889,288 B2
• Filed: 12/02/2002
• Issued: 05/03/2005
• Est. Priority Date: 12/02/2002
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Zheng, Jiannan, Jiang, Xiaoye, Bono, Jean-Pierre, Bixby, Peter C.
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US10/308,159
• Publication Number:
  US 20040107318A1
• Time in Patent Office: 883 Days
• Field of Search: 711/118, 711/129, 711/170, 711/173, 711/141, 711/143, 709/232, 709/238
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache

Abstract

In a network attached cached disk storage system, data is transmitted over the network in data packets having a data length that is much smaller than the logical block size for reading or writing to disk storage. To avoid copying of data from network port buffers to the cache memory, the cache blocks of the cache memory are organized as linked lists of list elements, which can be used as network port input or output buffers. For TCP data packets, for example, each list element has a data slot for storing up to 1,500 bytes, and a field indicating the number of bytes stored in the data slot.

Claims

1. A storage system comprising a storage controller, a cache memory, and data storage, wherein the storage controller is programmed to respond to a request to access a specified logical block of data in the data storage by accessing a logical block index to determine whether or not the specified logical block of data is in the cache memory, and when the logical block index indicates that the specified logical block of data is in the cache memory, to access the specified logical block of data in the cache memory, and when the logical block index indicates that the specified logical block of data is not in the cache memory, to access the specified logical block of data in the data storage, wherein the cache memory contains a multiplicity of logical blocks of data, and each of the multiplicity of logical blocks of data contained in the cache memory is organized as a respective linked list of list elements containing fragments of the data of said each of the multiplicity of logical blocks of data contained in the cache memory.

2. The storage system as claimed in claim 1, wherein the storage controller has a network port for attachment to a data network for receiving data packets from clients in the data network, and the storage controller is programmed to respond to a request for writing new data to the specified logical block of data in the data storage by storing the new data into a respective linked list for the specified logical block of data in the data storage, wherein the respective linked list for the specified logical block of data in the data storage includes multiple list elements in the cache memory, and the storing of the new data into the respective linked list for the specified logical block of data in the data storage includes storing data of each data packet into a corresponding one of multiple list elements of the respective linked list for the specified logical block of data in the data storage.

3. The storage system as claimed in claim 1, wherein the storage controller is programmed to respond to a request for writing new data to the specified logical block of data in the data storage by storing the new data into a first linked list of multiple list elements in the cache memory, accessing the logical block index to identify a second linked list of multiple list elements in the cache memory containing old data of the specified logical block of data in the data storage, and updating the logical block index to associate the first linked list of multiple list elements with the specified logical block of data in the data storage.

4. The storage system as claimed in claim 3, wherein the storage controller has a network port for attachment to a data network for receiving data packets from clients in the data network, and wherein the storing of the new data into the first linked list includes storing data of each data packet into a corresponding one of the multiple list elements in the first linked list.

5. The storage system as claimed in claim 1, wherein the storage controller is programmed to respond to a request for writing a packet of new data to the specified logical block of data in the data storage by storing the packet of new data into a first list element in the cache memory, accessing the logical block index to identify a respective list of multiple list elements in the cache memory containing data of the specified logical block of data in the data storage, inspecting the respective list of multiple list elements in the cache memory containing data of the specified logical block of data in the data storage to identify a second list element in the cache memory containing old data of the specified logical block of data in the data storage, removing said second list element from the respective list of multiple list elements in the cache memory containing data of the specified logical block of data in the data storage, and inserting said first list element into the respective list of multiple list elements in the cache memory containing data of the specified logical block of data in the data storage in order to replace said first list element with said second list element in the respective list of multiple list elements in the cache memory containing data of the specified logical block of data in the data storage.

6. The storage system as claimed in claim 1, wherein the storage controller has a network port for attachment to a data network for communication of data packets is with clients in the data network, and wherein the storage controller is programmed to respond to a request from one of the clients for reading data from the specified logical block of data in the data storage by accessing the logical block index to identify a respective linked list of multiple list elements in the cache memory containing data of the specified logical block of data in the data storage, and transmitting to said one of the clients a series of data packets, each data packet in the series of data packets being a respective one of the list elements in the respective linked list of multiple list elements in the cache memory containing data of the specified logical block of data in the data storage.

7. The storage system as claimed in claim 1, wherein each list element in the respective linked list of said each of the multiplicity of logical blocks of data contained in the cache memory includes a data slot containing a number of bytes of data of said each of the multiplicity of logical blocks of data contained in the cache memory, a field for a pointer to a next list element in the respective linked list of said each of the multiplicity of logical blocks of data contained in the cache memory, and a field for an indication of how many bytes of data of said each of the multiplicity of logical blocks of data contained in the cache memory are contained in the data slot.

8. The storage system as claimed in claim 7, wherein said each list element in the respective linked list of said each of the multiplicity of logical blocks of data contained in the cache memory further includes a field for indicating a size of the data slot.

9. The storage system as claimed in claim 7, wherein each logical block of data in the data storage has a length of eight kilobytes, and the data slot of said each list element has a length of 1,500 bytes.

10. The storage system as claimed in claim 7, wherein the storage system has an Internet Protocol port for linking the storage system to clients in an Internet Protocol data network, the storage controller is programmed for receiving Transmission Control Protocol data packets at the Internet Protocol port and writing data of each Transmission Control data packet to the data slot of a respective one of the list elements in the cache memory.

11. The storage system as claimed in claim 1, wherein the cache memory includes list elements associated with respective logical blocks of data storage and free list elements not associated respective logical blocks of data storage, and the storage controller is programmed to initialize the cache memory by linking the list elements into a list of free list elements.

12. The storage system as claimed in claim 11, wherein the storage controller is programmed to respond to a request for writing new data to the specified logical block of data in the data storage by storing the new data into a first linked list of the list elements, accessing the logical block index to identify a second linked list of the list elements containing old data of the specified logical block of data in the data storage, inserting the second linked list of the list elements into the list of free list elements, and updating the logical block index to associate the first linked list of the list elements with the specified logical block of data in the data storage.

13. The storage system as claimed in claim 12, wherein the storage controller has a network port for attachment to a data network for receiving data packets from clients in the data network, and wherein the storing of the new data into a first linked list of the list elements includes storing data of each data packet into a corresponding one of the list elements in the first linked list of the list elements.

14. The storage system as claimed in claim 1, wherein the storage controller has a network port for attachment to a data network for communicating data packets with clients in the data network, and wherein the storage controller is programmed to use the list elements as transmit and receive buffers for communicating the data packets with the clients in the data network.

15. The storage system as claimed in claim 14, wherein the storage controller is programmed to use the Transmission Control Protocol for communicating the data packets with the clients in the data network, and wherein each of the list elements has a data length of 1,500 bytes.

16. The storage system as claimed in claim 1, wherein the storage controller has network ports of different types for receiving data packets of different respective maximum data lengths, and the storage controller is programmed so that the different types of network ports use list elements of different lengths for receiving the data packets of different respective maximum data lengths.

17. The storage system as claimed in claim 1, wherein the storage controller has network ports of different types, and the storage controller is programmed so that each different type of network port uses list elements of a respective different length corresponding to a respective maximum data length of data packets received by said each different type of network port.

18. The storage system as claimed in claim 17, wherein the storage controller is programmed to maintain the list elements of each respective different length in a respective list element pool including free and allocated list elements.

19. The storage system as claimed in claim 18, wherein the storage controller is programmed to maintain the free list elements in each list element pool in a respective list of free list elements for said each list element pool.

20. The storage system as claimed in claim 1, wherein at least some of the list elements of at least some of the respective linked lists have data slots larger than the fragments of data stored in said at least some of the list elements, and the storage controller is programmed to perform a fragment merging process upon said at least some of the respective linked lists for merging the data fragments in at least some neighboring ones of the list elements in said at least some of the respective linked lists in order to reduce the number of list elements contained in said at least some of the respective linked lists.

21. The storage system as claimed in claim 20, wherein the storage controller is programmed to perform the fragment merging process as a background process relative to a process for responding to requests to access specified logical blocks of data in the data storage.

22. A storage system comprising a storage controller, a cache memory, and data storage, wherein the storage controller is programmed to respond to a request to access a specified logical block of data in the data storage by accessing a logical block index to determine whether or not the specified logical block of data is in the cache memory, and when the logical block index indicates that the specified logical block of data is in the cache memory, to access the specified logical block of data in the cache memory, and when the logical block index indicates that the specified logical block of data is not in the cache memory, to access the specified logical block of data in the data storage;

wherein the cache memory contains a list element pool of list elements, and at least some of the list elements in the list element pool are linked in respective lists for a multiplicity of logical blocks of data;

wherein each list element in the list element pool includes a data slot, a field for a pointer to a next list element in the list element pool, and a field for an indication of how many bytes of data are contained in the data slot; and

wherein the storage controller has a network port for attachment to a data network for communicating data packets with clients in the data network, and the storage controller is programmed to use the list elements as transmit and receive buffers for communicating the data packets with the clients in the data network.

23. The storage system as claimed in claim 22, wherein said each list element in the list element pool further includes a field for indicating a size of the data slot.

24. The storage system as claimed in claim 22, wherein the storage controller is programmed to communicate the data packets with the clients in the data network by storing data of each data packet received from the data network in a respective one of the list elements, and by reading data for each data packet transmitted to the data network from a respective one of the list elements.

25. The storage system as claimed in claim 22, wherein the storage controller is programmed to respond to a request for writing new data to the specified logical block of data in the data storage by storing the new data in a first linked list of a plurality of the list elements in the cache memory, accessing the logical block index to identify a second linked list of a plurality of the list elements in the cache memory containing old data of the specified logical block of data in the data storage, and updating the logical block index to associate the first linked list of a plurality of the list elements with the specified logical block of data in the data storage.

26. The storage system as claimed in claim 22, wherein the storage controller is programmed to respond to a request for writing a packet of new data to the specified logical block of data in the data storage by storing the packet of new data into a first list element in the cache memory, accessing the logical block index to identify a respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage, inspecting the respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage to identify a second list element in the cache memory containing old data of the specified logical block of data in the data storage, removing said second list element from the respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage, and inserting said first list element into the respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage in order to replace said first list element with said second list element in the respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage.

27. The storage system as claimed in claim 22, wherein the storage controller is programmed to communicate with the clients in the data network using the Transmission Control Protocol, each logical block of data in the data storage has a length of eight kilobytes, and the data slot of each of the list elements has a length of 1,500 bytes.

28. The storage system as claimed in claim 22, wherein the storage controller is programmed to initialize the cache memory by linking the list elements into a list of free list elements.

29. The storage system as claimed in claim 28, wherein the storage controller is programmed to respond to a request for writing new data to the specified logical block of data in the data storage by storing the new data into a first linked list of the list elements, accessing the logical block index to identify a second linked list of the list elements containing old data of the specified logical block of data in the data storage, inserting the second linked list of the list elements into the list of free list elements, and updating the logical block index to associate the first linked list of the list elements with the specified logical block of data in the data storage.

30. A method of operating a storage system having a storage controller, a cache memory, and data storage for storing logical blocks of data, the storage controller having a network port for attaching the storage controller to a data network for communicating data packets with clients in the data network, the storage controller being programmed to respond to a request to access a specified logical block of data in the data storage by accessing a logical block index to determine whether or not the specified logical block of data is in the cache memory, and when the logical block index indicates that the specified logical block of data is in the cache memory, to access the specified logical block of data in the cache memory, and when the logical block index indicates that the specified logical block of data is not in the cache memory, to access the specified logical block of data in the data storage;

wherein said method comprises;

said storage controller maintaining a pool of list elements in the cache memory, linking at least some of the list elements into respective linked lists for a multiplicity of the logical blocks of data stored in the data storage, and storing, in the list elements for each respective linked list for each of the multiplicity of the logical blocks of data stored in the data storage, the data of said each of the multiplicity of the logical blocks of data stored in the data storage; and

said storage controller using the list elements as transmit and receive buffers for communicating the data packets with the clients in the data network.

31. The method as claimed in claim 30, wherein each list element in the pool of list elements includes a data slot, a field for a pointer to a next list element in the list element pool, and a field for an indication of how many bytes of data are contained in the data slot;

and which includes storing, in the data slot, a portion of the data of at least one of the logical blocks of data in the data storage, and storing, in the field for an indication of how many bytes of data are contained in the data slot, a number indicating how many bytes of data are contained in the data slot.

32. The method as claimed in claim 30, which includes the storage controller communicating with the clients in the data network by storing data of each data packet received from the data network in a respective one of the list elements, and by reading data for each data packet transmitted to the data network from a respective one of the list elements.

33. The method as claimed in claim 30, which includes the storage controller responding to a request for writing new data to the specified logical block of data in the data storage by storing the new data in a first linked list of a plurality of the list elements in the cache memory, accessing the logical block index to identify a second linked list of a plurality of the list elements in the cache memory containing old data of the specified logical block of data in the data storage, and updating the logical block index to associate the first linked list of a plurality of the list elements with the specified logical block of data in the data storage.

34. The method as claimed in claim 30, which includes the storage controller responding to a request for writing a packet of new data to the specified logical block of data in the data storage by storing the packet of new data into a first list element in the cache memory, accessing the logical block index to identify a respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage, inspecting the respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage to identify a second list element in the cache memory containing old data of the specified logical block of data in the data storage, removing said second list element from the respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage, and inserting said first list element into the respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage in order to replace said first list element with said second list element in the respective list of a plurality of the list elements in the cache memory containing data of the specified logical block of data in the data storage.

35. The method as claimed in claim 30, which includes the storage controller communicating with the clients in the data network using the Transmission Control Protocol, and the data slot of each of the list elements has a length of 1,500 bytes.

36. The method as claimed in claim 30, which includes the storage controller initializing the cache memory by linking the list elements into a list of free list elements.

37. The method as claimed in claim 30, which includes the storage controller responding to a request for writing new data to the specified logical block of data in the data storage by storing the new data into a first linked list of the list elements, accessing the logical block index to identify a second linked list of the list elements containing old data of the specified logical block of data in the data storage, inserting the second linked list of the list elements into the list of free list elements, and updating the logical block index to associate the first linked list of the list elements with the specified logical block of data in the data storage.

38. The method as claimed in claim 30, wherein the storage controller has network ports of different types for receiving data packets of different respective maximum data lengths, and the storage controller is programmed so that the different types of network ports use list elements of different lengths for receiving the data packets of different respective maximum data lengths.

39. The method as claimed in claim 38, wherein the storage controller has network ports of different types, and each different type of network port uses list elements of a respective different length corresponding to a respective maximum data length of data packets received by said each different type of network port.

40. The method as claimed in claim 39, wherein the storage controller maintains the list elements of each respective different length in a respective list element pool including free and allocated list elements.

41. The method as claimed in claim 40, wherein the storage controller maintains the free list elements in each list element pool in a respective list of free list elements for said each list element pool.

42. The method as claimed in claim 30, wherein at least some of the list elements of at least some of the respective linked lists have data slots larger than the fragments of data stored in said at least some of the list elements, and the storage controller performs a fragment merging process upon said at least some of the respective linked lists for merging the data fragments in at least some neighboring ones of the list elements in said at least some of the respective linked lists in order to reduce the number of list elements contained in said at least some of the respective linked lists.

43. The method as claimed in claim 42, wherein the storage controller performs the fragment merging process as a background process relative to a process for responding to requests to access specified logical blocks of data in the data storage.