SYSTEM AND METHOD FOR I/O COMMAND MANAGEMENT

• US 20120110291A1
• Filed: 03/06/2010
• Published: 05/03/2012
• Est. Priority Date: 04/06/2009
• Status: Abandoned Application

• Current Assignee: Kaminario Limited
• Original Assignee: Kaminario Limited
• Inventors: Keren, Guy, Zilber, Erez, Koren, Benny
• Application Number:
  US13/262,867
• Publication Number:
  US 20120110291A1
• Time in Patent Office: Days
• US Class Current: 711/163
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0676 Magnetic disk device

Abstract

Systems and methods for input/output command management. In embodiments of the invention an input/output command fully executes after a lock has been obtained for the command on all storage segments relating to the command, in a predetermined order. Some embodiments of the invention allow overlapping access to storage and/or to individual storage segments by a plurality of input/output commands. In some embodiments of the invention, prioritization of commands is facilitated through the usage of a sharing policy and/or wakeup policy.

Claims

1. A method of managing input/output commands comprising:

in a predetermined order, attempting to obtain a lock for a received input/output command on all of a plurality of storage segments relating to said command;

if during said attempting a lock cannot be obtained on a storage segment in said plurality because of an already existing lock which will not be shared with said command, then waiting until a lock can be obtained for said command and after obtaining said lock, attempting to obtain a lock on a next storage segment in said predetermined order;

wherein said command is performed only after a lock has been obtained for said command on all of said plurality of storage segments.

2. The method of claim 1, wherein said predetermined order is according to ascending addresses of said plurality of storage segments.

3. The method of claim 1, further comprising:

unlocking at least one of said plurality of storage segments.

4. The method of claim 1, wherein more than one command is waiting for said lock, and said command obtains said lock because of a longer wait time than any other waiting command.

5. The method of claim 1, wherein said input/output command and another command are non-content changing commands, said attempting including:

sharing a lock on a storage segment in said plurality with said other command.

6. The method of claim 5, further comprising:

checking if a number of content changing commands waiting for a lock on said storage segment is less than a predetermined ceiling, and sharing a lock on said storage segment only if said number is less than said ceiling.

7. The method of claim 6, wherein said ceiling is one.

8. The method of claim 6, further comprising:

incrementing a counter when a command begins sharing a lock on a storage segment and decrementing a counter when a command stops sharing a lock on said storage segment .

9. The method of claim 1, wherein for at least one storage segment in said plurality, said attempting includes:

hashing an identifier of said storage segment in order to determine an associated entry in a hash table;

checking if said associated entry includes a pointer corresponding to said storage segment;

if said associated entry does not include a pointer corresponding to said storage segment, generating a pointer associated with said storage segment, wherein said pointer is located in said entry.

10. The method of claim 9, wherein said identifier includes at least part of an address of said storage segment.

11. The method of claim 9, further comprising:

if said associated entry does include a pointer corresponding to said storage segment, queuing said input/output command in a queue pointed to by said pointer.

12. The method of claim 9, further comprising:

after performing said input/output command, discarding an empty queue associated with a storage segment in said plurality which is not currently locked by one or more other commands.

13. The method of claim 1, wherein for at least one storage segment in said plurality, said attempting includes:

searching a search tree to determine if said tree includes a node associated with an identifier of said storage segment ;

if no such node exists, adding a leaf node to said search tree and generating a pointer associated with said storage segment, wherein said pointer is located in said leaf node.

14. The method of claim 13, wherein said identifier includes at least part of an address of said storage segment.

15. The method of claim 13, further comprising:

if such a node exists, queuing said input/output command in a queue pointed to by a pointer located in said node.

16. The method of claim 13, further comprising:

after performing said input/output command, discarding an empty queue and a node associated with a storage segment in said plurality which is not currently locked by one or more other commands.

17. The method of claim 1, wherein at least one of said plurality of storage segments collectively stores or will store a data element subject to said input/output command.

18. The method of claim 1, wherein at least one of said plurality of storage segments collectively stores or will store recovery enabling data relating to a data element which is subject to said input/output command.

19. The method of claim 1, wherein at least one of said plurality of storage segments is associated with at least one solid state storage entity.

20. The method of claim 1, wherein at least one of said plurality of said storage segments is associated with a non-volatile memory non-solid state storage entity.

21. The method of claim 1, wherein said plurality of storage segments directly relate to said command.

22. The method of claim 1, wherein at least one of said plurality of storage segments indirectly relates to said command.

23. A system for managing input/output commands comprising:

at least one storage comprising storage segments; and

at least one controller configured to receive input/output commands generated by at least one command generator, and for each input/output command configured to attempt to obtain a lock on all of a plurality of storage segments related to said command in a predetermined order, and if during said attempting a lock cannot be obtained on a storage segment in said plurality because of an already existing lock which will not be shared with said command, then further configured to wait until a lock can be obtained for said command and after obtaining said lock, to attempt to obtain a lock on a next storage segment in said predetermined order;

said at least one controller further configured to perform said command after a lock has been obtained on all storage segments related to said command.

24. The system of claim 23, wherein said system includes a counter, configured to keep count of a number of commands sharing a lock on a storage segment in said at least one storage.

25. The system of claim 23, wherein said system includes a table or search tree, configured to hold at least one pointer to at least one queue associated with at least one storage segment in said at least one storage.

26. The system of claim 23, wherein said system is configured to generate a hash function of an identifier of a storage segment in said storage in order to identify an entry in a hash table, and to generate a pointer associated with said storage segment if not yet existing, wherein said pointer is located in said entry.

27. The system of claim 23, wherein said system is configured to search a search tree for an identifier of a storage segment in said storage and to generate a node associated with said storage segment, if not yet existing, on said tree,

28. The system of claim 23, wherein said at least one storage is divided among at least first and second solid state storage entities and a non volatile memory non-solid state storage entity.

29. The system of claim 28, wherein

said first solid state storage entity is configured to store data thereon and responsive to a write command related to a data element for storing a first copy of said data element;

said second solid state storage entity is configured to store data thereon and responsive to said write command related to said data element for temporarily storing recovery-enabling data corresponding to said respective data element;

said non-volatile memory non-solid state storage entity is configured to store data thereon and operatively connected to at least said second solid state storage entity,

and wherein a controller among said at least one controller which is associated with said second solid state storage entity is further configured to issue a write command for causing said non-volatile memory non-solid state storage entity to store a copy of recovery-enabling data thereon, and

wherein said controller which is associated with said second solid state storage entity is further configured to initiate the write command substantially immediately upon storage of the recovery-enabling data on said second solid state storage entity.

30. The system of claim 28, wherein at least one of said second solid state storage entity and said non-volatile memory non-solid state storage entity is on a different server than said first solid state storage entity, so that said data element is stored on a separate server than at least one of said recovery-enabling data and said copy of said recovery-enabling data.

31. The system of claim 28, wherein said system is configured to obtain a lock on a segment in first solid state storage entity, effectively locking a segment on said second solid state storage entity or on said non-volatile memory non-solid state storage entity.

32. The system of claim 30, wherein if said first solid state storage entity fails, then said system is configured to independently obtain a lock on said segment in said second solid state storage entity or non-volatile memory non-solid state storage entity.

33. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method of managing input/output commands comprising:

in a predetermined order, attempting to obtain a lock for a received input/output command on all of a plurality of storage segments relating to said command;

if during said attempting a lock cannot be obtained on a storage segment in said plurality because of an already existing lock which will not be shared with said command, then waiting until a lock can be obtained for said command and after obtaining said lock, attempting to obtain a lock on a next storage segment in said predetermined order;

wherein said command is performed only after a lock has been obtained for said command on all of said plurality of storage segments.

34. A computer program product comprising a computer useable medium having computer readable program code embodied therein of managing input/output commands the computer program product comprising:

computer readable program code for causing the computer to in a predetermined order, attempting to obtain a lock for a received input/output command on all of a plurality of storage segments relating to said command;

computer readable program code for causing the computer to if during said attempting a lock cannot be obtained on a storage segment in said plurality because of an already existing lock which will not be shared with said command, then waiting until a lock can be obtained for said command and after obtaining said lock, attempting to obtain a lock on a next storage segment in said predetermined order;

computer readable program code for causing the computer to wherein said command is performed only after a lock has been obtained for said command on all of said plurality of storage segments.