Hybrid logical to physical address translation for non-volatile storage devices with integrated compute module

• US 10,565,123 B2
• Filed: 10/05/2017
• Issued: 02/18/2020
• Est. Priority Date: 04/10/2017
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Song, Seung-Hwan, De, Arup, Mehra, Pankaj, O'Krafka, Brian W.
• Primary Examiner(s): Yi, David
• Assistant Examiner(s): Otto, Alan
• Application Number:
  US15/726,313
• Publication Number:
  US 20180293174A1
• Time in Patent Office: 866 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

Abstract

A host compiles code to perform a set of one or more database operations on target and embeds an indication of whether the target data is randomly accessed data or sequentially accessed data. The compiled code is transmitted to the compute engine inside a memory system that maintains a first portion of memory for storing sequentially accessed data and a second portion of memory for storing randomly accessed data. The memory system (e.g. SSD) maintains reduced size L2P tables in volatile working memory by maintaining coarse L2P tables in the working memory for use with sequentially accessed data and maintaining fine L2P tables in the working memory for use with randomly accessed data. The compute engine uses the compiled code to perform the set of one or more database operations on the target data using the working memory.

Claims

1. An apparatus, comprising:

a memory system, comprising;

non-volatile memory;

working memory separate from the non-volatile memory, the working memory is configured to store a coarse logical address to physical address table for use with data stored in the non-volatile memory as sequentially accessed data and a fine logical address to physical address table for use with data stored in the non-volatile memory as randomly accessed data;

a controller in communication with the non-volatile memory and the working memory, the controller includes a processor, the controller is configured to create data for the coarse logical address to physical address table by reading fine logical address to physical address data and reducing the fine logical address to physical address data to coarse logical address to physical address data, the controller is configured to;

randomly access data stored in the non-volatile memory as randomly accessed data in response to a request from a host by translating a logical address from the host to a physical address in the non-volatile memory using the fine logical address to physical address table in the working memory,

sequentially access data stored in the non-volatile memory as sequentially accessed data in response to a request from the host by translating a logical address from the host to a physical address in the non-volatile memory using the coarse logical address to physical address table in the working memory, and

randomly access data stored in the non-volatile memory as sequentially accessed data in response to a request from the host by translating a logical address from the host to a physical address in the non-volatile memory using the coarse logical address to physical address table in the working memory; and

a compute engine positioned within the memory system, the compute engine is in communication with the controller and the working memory, the compute engine is different than the processor included in the controller, the compute engine is configured to receive code from the host and perform one or more database operations on target data in the non-volatile memory by executing the code and using the working memory.

2. The apparatus of claim 1, wherein:

the code received from the host is compiled code that includes an indication of whether the target data is sequentially accessed data or randomly accessed data.

3. The apparatus of claim 2, wherein:

the controller includes a host interface;

the compute engine is behind the host interface;

the host interface is configured to receive the compiled code from the host and forward the compiled code to the compute engine; and

the compute engine is further configured to use the controller to perform address translation between logical and physical addresses for the target data based on the coarse logical address to physical address table and the fine logical address to physical address table in the working memory.

4. The apparatus of claim 1, wherein:

the non-volatile memory includes a first portion of non-volatile memory configured to store sequentially accessed data comprising leaf node data for one or more database data structures and a second portion of non-volatile memory configured to store randomly accessed data comprising branch node data for one or more database data structures;

the controller is further configured to use the coarse logical address to physical address table to perform address translation between logical and physical addresses for sequentially accessed data stored in the first portion of non-volatile memory;

the controller is further configured to use the fine logical address to physical address table to perform address translation between logical and physical addresses for randomly accessed data stored in the second portion of non-volatile memory;

the coarse logical address to physical address table is separate from the leaf node data and the branch node data; and

the fine logical address to physical address table is separate from the leaf node data and the branch node data.

5. The apparatus of claim 1, wherein:

the non-volatile memory includes a first portion of non-volatile memory configured to store sequentially accessed data comprising leaf node data for one or more database data structures and a second portion of non-volatile memory configured to store randomly accessed data comprising branch node data for one or more database data structures;

the coarse logical address to physical address table is separate from the leaf node data and the branch node data;

the fine logical address to physical address table is separate from the leaf node data and the branch node data;

the compute engine is further configured to use the coarse logical address to physical address table to perform address translation between logical and physical addresses for sequentially accessed data stored in the first portion of non-volatile memory; and

the compute engine is further configured to use the fine logical address to physical address table to perform address translation between logical and physical addresses for randomly accessed data stored in the second portion of non-volatile memory.

6. The apparatus of claim 1, wherein:

the non-volatile memory includes a first portion of non-volatile memory configured to store leaf nodes of a database as sequentially accessed data and a second portion of non-volatile memory configured to store branch nodes of the database randomly accessed data;

the coarse logical address to physical address table is separate from the leaf nodes and the branch nodes;

the fine logical address to physical address table is separate from the leaf nodes and the branch nodes;

the compute engine is further configured to use the coarse logical address to physical address table to perform address translation between logical and physical addresses for the leaf nodes stored in the first portion of non-volatile memory; and

the compute engine is further configured to use the fine logical address to physical address table to perform address translation between logical and physical addresses for the branch nodes stored in the second portion of non-volatile memory.

7. The apparatus of claim 2, wherein:

wherein the indication of whether the target data is sequentially accessed data or random accessed data is inferred from a type of the one or more database operations specified by the code.

8. The apparatus of claim 1, wherein:

the working memory is volatile memory; and

the compute engine is further configured to use the volatile working memory to store working data for the compute engine while performing the one or more database operations.

9. The apparatus of claim 1, wherein:

the non-volatile memory includes a memory package that is separate from and connected to the controller; and

the memory package includes one or more non-volatile memory dies and the compute engine.

10. The apparatus of claim 9, wherein:

the compute engine is positioned on a first memory die of the one of the non-volatile memory dies;

the code received from the host is compiled code that is received by the compute engine on the first memory die; and

the compute engine is configured to execute the compiled code to access the target data on the first memory die based on

the coarse logical address to physical address table in the working memory for sequentially accessed data, and

the fine logical address to physical address table in the working memory for data randomly accessed data.

11. The apparatus of claim 1, wherein:

the memory system is a solid state drive; and

the controller includes a host interface, the compute engine is in the solid state drive and behind the host interface.

12. The apparatus of claim 1, wherein:

the controller includes a host interface, the compute engine is behind the host interface,

the compute engine is further configured to use the working memory to store working data for the compute engine while performing the one or more database operations;

the code received from the host is compiled code that includes an indication of whether the target data is sequentially accessed data or randomly accessed data;

the non-volatile memory includes a first portion of non-volatile memory configured to store sequentially accessed data and a second portion of non-volatile memory configured to store randomly accessed data;

the compute engine is further configured to use the coarse logical address to physical address table to perform address translation between logical and physical addresses for sequentially accessed data stored in the first portion of non-volatile memory; and

the compute engine is further configured to use the fine logical address to physical address table to perform address translation between logical and physical addresses for randomly accessed data stored in the second portion of non-volatile memory.

13. The apparatus of claim 1, wherein:

the non-volatile memory includes blocks of memory cells that are configured to be divided into pages;

entries in the coarse logical address to physical address table are at a block level; and

entries in the fine logical address to physical address table are at a page level.

14. The apparatus of claim 1, wherein:

the non-volatile memory is configured to store a set of address translation information;

the fine logical address to physical address table is a first cache of the set of address translation information in the non-volatile memory;

the coarse logical address to physical address table is a second cache of the set of address translation information in the non-volatile memory; and

the controller is further configured to create data for the second cache in the working memory by reading fine data of the set of address translation information in the non-volatile memory, reducing the fine data to coarse data, and storing the coarse data in the second cache in the working memory.

15. A method, comprising:

storing data written as sequentially accessed data in non-volatile memory of a memory system;

storing data written as randomly accessed data in the non-volatile memory of the memory system;

maintaining one or more logical to physical (L2P) tables in the non-volatile memory of the memory system for translating logical addresses to physical addresses for the stored data written as sequentially accessed data in the non-volatile memory of the memory system and for translating logical addresses to physical addresses for the stored data written as randomly accessed data in the non-volatile memory of the memory system;

maintaining a coarse L2P cache in a volatile working memory of the memory system to store a subset of entries in the one or more L2P tables for translating logical addresses to physical addresses for the stored data written as sequentially accessed data in the non-volatile memory of the memory system;

maintaining a fine L2P cache in the volatile working memory of the memory system to store a subset of entries in the one or more L2P tables for translating logical addresses to physical addresses for the stored data written as randomly accessed data in the non-volatile memory of the memory system;

creating data for the coarse L2P cache in the volatile working memory by reading fine L2P data from the one or more L2P tables, reducing the fine L2P data to coarse L2P data and storing the coarse L2P data in the coarse L2P cache;

receiving, by the memory system from a host, code that includes instructions for programming a compute engine within the memory system to perform a set of one or more database operations on target data in the non-volatile memory of the memory system;

executing, by the compute engine inside the memory system, the code to perform the set of one or more database operations on the target data using the volatile working memory; and

performing an address translation for a logical address associated with the one or more database operations using the coarse L2P cache or the fine L2P cache.

16. The method of claim 15, wherein:

the coarse L2P cache stores translation entries at a block level; and

the fine L2P cache stores translation entries at a page level.

17. The method of claim 16, wherein:

the storing data written as sequentially accessed data comprises storing leaf nodes of a database in the non-volatile memory of the memory system; and

the storing data written as randomly accessed data comprises storing branch nodes of the database in the non-volatile memory of the memory system, the branch nodes point to the leaf nodes, the branch nodes and the leaf nodes are separate from the coarse L2P cache and the fine L2P cache.

18. The method of claim 15, further comprising:

randomly accessing data written as sequentially accessed data in the non-volatile memory of the memory system in response to a host by translating a logical address to a physical address in the non-volatile memory using the coarse L2P cache in the volatile working memory.

19. A memory system, comprising:

non-volatile memory configured to store a database comprising leaf nodes and branch nodes pointing to the leaf nodes in blocks of memory cells, the blocks of memory cells are divided into pages, the non-volatile memory comprises a first set of memory cells configured to store the branch nodes of the database as randomly accessed data in pages and a second set of memory cells configured to store the leaf nodes of the database as sequentially accessed data in pages;

working memory separate from the non-volatile memory; and

a controller in communication with the non-volatile memory and the working memory, the controller including a host interface and a processor, the controller being configured to;

store a first logical address to physical address table in the working memory for accessing the branch nodes in the first set of memory cells and a second logical address to physical address table in the working memory for accessing the leaf nodes in the second set of memory cells, the first logical address to physical address table and the second logical address to physical address table are separate from the database,

create data for the second logical address to physical address table by reading fine logical address to physical address data and reducing the fine logical address to physical address data to coarse logical address to physical address data

receive a request from a host via the host interface, the request including an indication of target data of the database to be accessed,

access the target data from the first set of memory cells using the first logical address to physical address table in response to the request if the target data is randomly accessed data, and

access the target data from the second set of memory cells using the second logical address to physical address table in response to the request if the target data is sequentially accessed data; and

a compute engine that is behind the host interface and is in communication with the controller and the working memory, the compute engine is separate from the processor of the controller, the compute engine being configured to perform data manipulation operations on sequentially accessed data stored in the second set of memory cells using the working memory to store working data for the compute engine while performing the data manipulation operations.