Load balancing by dynamically transferring memory range assignments

• US 10,235,069 B2
• Filed: 12/22/2016
• Issued: 03/19/2019
• Est. Priority Date: 12/22/2016
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Espeseth, Adam Michael, Jacobs, Brent William
• Primary Examiner(s): Krofcheck, Michael
• Application Number:
  US15/388,768
• Publication Number:
  US 20180181328A1
• Time in Patent Office: 817 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0284 Multiple user address space allocation, e.g. using different base addresses interprocessor communication G06F15/163
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/1048 Scalability
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/522 Barrier synchronisation

Abstract

A method and apparatus for accessing a storage device is disclosed. More specifically, for load balancing by dynamically transferring memory address range assignments. In one embodiment, a storage device receives, from a host apparatus, an access request directed at two or more storage addresses, assigns, based on a first storage address of the two or more storage addresses, the access request to a first processor of two or more processors of the storage device, obtains a local memory lock based on the first storage address, determines, based on a second storage address of the two or more storage addresses, that the second storage address is assigned to a second processor of the two or more processors, obtains a remote memory lock from the second processor based on the second storage address and processes the access request.

Claims

1. A method for accessing a storage device, comprising:

receiving, from a host apparatus, an access request directed at two or more storage addresses;

assigning, based on a first storage address of the two or more storage addresses, the access request to a first processor of two or more processors of the storage device;

obtaining a local memory lock based on the first storage address;

determining, based on a second storage address of the two or more storage addresses, that the second storage address is assigned to a second processor of the two or more processors;

obtaining a remote memory lock from the second processor based on the second storage address;

issuing a transition barrier command to each processor of the two or more processors;

receiving, from each processor of the two or more processors, a response to the transition barrier command;

issuing a transition barrier complete message to each processor of the two or more processors after receiving the response from all of the two or more processors; and

processing the access request.

2. The method of claim 1, further comprising:

determining to change from a first algorithm for assigning storage addresses to the two or more processors to a second algorithm.

3. The method of claim 2, wherein the transition barrier command includes the second algorithm.

4. The method of claim 2, further comprising:

determining, for a third storage address, a first assigned processor based on the first algorithm and a second assigned processor based on the second algorithm; and

obtaining memory locks based on both the first and second assigned processors.

5. The method of claim 4, wherein obtaining memory locks comprises:

determining the first or second assigned processor is different from a current processor; and

obtaining a remote memory lock from the first or second assigned processor based on the determination.

6. The method of claim 4, wherein obtaining memory locks comprises:

determining the first or second assigned processor is the same as a current processor; and

obtaining a local memory lock based on the determination.

7. The method of claim 2, wherein the response indicating each processor has finished processing access requests is sent by each processor after each processor has finished processing access requests received prior to the transition barrier command.

8. A computer system for storing and retrieving data, comprising:

a processor; and

a memory storing instructions that, when executed by the processor, cause the computer system to;

receive, from a host apparatus, an access request directed at two or more storage addresses;

assign, based on a first storage address of the two or more storage addresses, the access request to a first processor of two or more processors of the storage device;

obtain a local memory lock based on the first storage address;

determine, based on a second storage address of the two or more storage addresses, that the second storage address is assigned to a second processor of the two or more processors;

obtain a remote memory lock from the second processor based on the second storage address;

issue a transition barrier command to each processor of the two or more processors;

receive, from each processor of the two or more processors, a response to the transition barrier command;

issue a transition barrier complete message to each processor of the two or more processors after receiving the response from all of the two or more processors; and

process the access request.

9. The computer system of claim 8, wherein the instructions cause the computer system to:

determine to change from a first algorithm for assigning storage addresses to the two or more processors to a second algorithm.

10. The computer system of claim 9, wherein the transition barrier command includes the second algorithm.

11. The computer system of claim 9, wherein the instructions cause the computer system to:

determine, for a third storage address, a first assigned processor based on the first algorithm and a second assigned processor based on the second algorithm; and

obtain memory locks based on both the first and second assigned processors.

12. The computer system of claim 11, wherein obtain memory locks comprises:

determining the first or second assigned processor is different from a current processor; and

obtaining a remote memory lock from the first or second assigned processor based on the determination.

13. The computer system of claim 11, wherein obtain memory locks comprises:

determining the first or second assigned processor is the same as a current processor; and

obtaining a local memory lock based on the determination.

14. The computer system of claim 9, wherein the response indicating each processor has finished processing access requests is sent by each processor after each processor has finished processing access requests received prior to the transition barrier command.

15. A non-transitory computer readable storage medium containing instructions that, when executed by a processor, performs the following method:

receive, from a host apparatus, an access request directed at two or more storage addresses;

assign, based on a first storage address of the two or more storage addresses, the access request to a first processor of two or more processors of the storage device;

obtain a local memory lock based on the first storage address;

determine, based on a second storage address of the two or more storage addresses, that the second storage address is assigned to a second processor of the two or more processors;

obtain a remote memory lock from the second processor based on the second storage address;

issue a transition barrier command to each processor of the two or more processors;

receive, from each processor of the two or more processors, a response to the transition barrier command;

issue a transition barrier complete message to each processor of the two or more processors after receiving the response from all of the two or more processors; and

process the access request.

16. The non-transitory computer readable storage medium of claim 15, wherein the instructions cause the computer system to:

determine to change from a first algorithm for assigning storage addresses to the two or more processors to a second algorithm.

17. The non-transitory computer readable storage medium of claim 16, wherein the transition barrier command includes the second algorithm.

18. The non-transitory computer readable storage medium of claim 16, wherein the instructions cause the computer system to:

determine, for a third storage address, a first assigned processor based on the first algorithm and a second assigned processor based on the second algorithm; and

obtain memory locks based on both the first and second assigned processors.

19. The non-transitory computer readable storage medium of claim 18, wherein obtain memory locks comprises:

determining the first or second assigned processor is different from a current processor; and

obtaining a remote memory lock from the first or second assigned processor based on the determination.

20. The non-transitory computer readable storage medium of claim 18, wherein obtain memory locks comprises:

determining the first or second assigned processor is the same as a current processor; and

obtaining a local memory lock based on the determination.

21. The non-transitory computer readable storage medium of claim 16, wherein the response indicating each processor has finished processing access requests is sent by each processor after each processor has finished processing access requests received prior to the transition barrier command.

22. A device, comprising:

means for receiving, from a host apparatus, an access request directed at two or more storage addresses;

means for assigning, based on a first storage address of the two or more storage addresses, the access request to a first processor of two or more processors of the storage device;

first means for obtaining a local memory lock based on the first storage address;

means for determining, based on a second storage address of the two or more storage addresses, that the second storage address is assigned to a second processor of the two or more processors;

second means for obtaining a remote memory lock from the second processor based on the second storage address;

means for issuing a transition barrier command to each processor of the two or more processors;

means for receiving, from each processor of the two or more processors, a response to the transition barrier command;

means for issuing a transition barrier complete message to each processor of the two or more processors after receiving the response from all of the two or more processors; and

means for processing the access request.

23. The device of claim 22, wherein the first means for obtaining a local memory lock and the second means for obtaining a remote memory lock are the same means.

24. The device of claim 23, wherein the means for receiving, the means for assigning, the first means for obtaining a local memory lock, the means for determining and the second means for obtaining a remote memory lock are the same means.

25. The device of claim 22, wherein the means for processing comprises a plurality of means for processing.

26. The device of claim 25, further comprising means for indicating each means for processing has finished processing access requests.