公开(公告)号：US10936661B2

公开(公告)日：2021-03-02

申请号：US16232422

申请日：2018-12-26

Applicant: Micron Technology, Inc.

Inventor： David Burton ,  Greg A. Becker ,  Alexander Tomlinson

IPC: G06F7/00 ,  G06F16/901 ,  G06F16/903

Abstract: Aspects of the present disclosure provide for operations for a tree data structure that provides order-based node traversal. For some embodiments, the tree data structure stores one or more key-value pairs, implements at least one linked-list data structure, and enables traversal of nodes within the tree data structure based on a key order (e.g., forward or reverse key order).

公开(公告)号：US20200159727A1

公开(公告)日：2020-05-21

申请号：US16749523

申请日：2020-01-22

Applicant: Micron Technology, Inc.

Inventor： David Boles ,  John M. Groves ,  Steven Moyer ,  Alexander Tomlinson

IPC: G06F16/2458 ,  G06F16/901 ,  G06F16/2455

Abstract: Systems and techniques for reducing probabilistic filter query latency are described herein. A query for a probabilistic filter that is stored on a first media may be received from a caller. In response to receiving the query, cached segments of the probabilistic filter stored on a second media may be obtained. Here, the probabilistic filter provides a set membership determination that is conclusive in a determination that an element is not in a set. The query may be executed on the cached segments resulting in a partial query result. Retrieval of remaining data of the probabilistic filter from the first media to the second media may be initiated without intervention from the caller. Here, the remaining data corresponds to the query and data that is not in the cached segment. The partial query results may then be returned to the caller.

公开(公告)号：US10579633B2

公开(公告)日：2020-03-03

申请号：US15691998

申请日：2017-08-31

Applicant: Micron Technology, Inc.

Inventor： David Boles ,  John M. Groves ,  Steven Moyer ,  Alexander Tomlinson

IPC: G06F16/00 ,  G06F16/2458 ,  G06F16/901 ,  G06F16/2455

Abstract: Systems and techniques for reducing probabilistic filter query latency are described herein. A query for a probabilistic filter that is stored on a first media may be received from a caller. In response to receiving the query, cached segments of the probabilistic filter stored on a second media may be obtained. Here, the probabilistic filter provides a set membership determination that is conclusive in a determination that an element is not in a set. The query may be executed on the cached segments resulting in a partial query result. Retrieval of remaining data of the probabilistic filter from the first media to the second media may be initiated without intervention from the caller. Here, the remaining data corresponds to the query and data that is not in the cached segment. The partial query results may then be returned to the caller.

公开(公告)号：US20180225321A1

公开(公告)日：2018-08-09

申请号：US15428912

申请日：2017-02-09

Applicant: Micron Technology, Inc.

Inventor： David Boles ,  John M. Groves ,  Steven Moyer ,  Alexander Tomlinson

IPC: G06F17/30

Abstract: Systems and techniques for collecting and using merge tree garbage metrics are described herein. A kvset is created for a node in a KVS tree. Here, a set of kvset metrics for the kvset are computed as part of the node creation. The kvset is added to the node. The node is selected for a compaction operation based on a metric in the set of kvset metrics. The compaction operation is performed on the node.

公开(公告)号：US20180225316A1

公开(公告)日：2018-08-09

申请号：US15428976

申请日：2017-02-09

Applicant: Micron Technology, Inc.

Inventor： David Boles ,  John M. Groves ,  Steven Moyer ,  Alexander Tomlinson

IPC: G06F17/30

Abstract: Systems and techniques for stream selection from multi-stream storage devices. Notification of a KVS tree write request for a multi-stream storage device is received. The notification includes a KVS tree scope corresponding to data in the write request. A stream identifier (ID) is assigned to the write request based on the KVS tree scope and a stability value of the write request. The stream ID is returned to govern stream assignment to the write request, the stream assignment modifying a write operation of the multi-stream storage device.

公开(公告)号：US20230401155A1

公开(公告)日：2023-12-14

申请号：US18209850

申请日：2023-06-14

Applicant: MICRON TECHNOLOGY, INC.

Inventor： Alexander Tomlinson ,  Gaurav Sanjay Ramdasi ,  Gregory Alan Becker

IPC: G06F12/0875

CPC classification number: G06F12/0875 ,  G06F2212/1016 ,  G06F2212/163

Abstract: An event trigger to flush key-value data from a volatile memory device is detected. In response to detection of the event trigger, a determination is made whether the key-value data comprises uncommitted data for one or more active database transactions. If the key-value data comprises uncommitted data for one or more active database transactions, the uncommitted data is moved to a hold aside buffer in the volatile memory device, and committed data in the key-value data is stored on a non-volatile memory device.

公开(公告)号：US11599552B2

公开(公告)日：2023-03-07

申请号：US17146222

申请日：2021-01-11

Applicant: Micron Technology, Inc.

Inventor： Alexander Tomlinson

IPC: G06F16/00 ,  G06F16/25 ,  G06F7/14 ,  G06F16/22 ,  G06F16/23

Abstract: Aspects of the present disclosure provide for operations of a key-value tree data structure that merges key-value pair data of a node, in a key-value tree data structure using counter values.

公开(公告)号：US20220374148A1

公开(公告)日：2022-11-24

申请号：US17882862

申请日：2022-08-08

Applicant: Micron Technology, Inc.

Inventor： David Boles ,  John M. Groves ,  Steven Moyer ,  Alexander Tomlinson

IPC: G06F3/06 ,  G06F16/13 ,  G06F12/1009

Abstract: Systems and techniques for reducing probabilistic filter query latency are described herein. A query for a probabilistic filter that is stored on a first media may be received from a caller. In response to receiving the query, cached segments of the probabilistic filter stored on a second media may be obtained. Here, the probabilistic filter provides a set membership determination that is conclusive in a determination that an element is not in a set. The query may be executed on the cached segments resulting in a partial query result. Retrieval of remaining data of the probabilistic filter from the first media to the second media may be initiated without intervention from the caller. Here, the remaining data corresponds to the query and data that is not in the cached segment. The partial query results may then be returned to the caller.

公开(公告)号：US11238098B2

公开(公告)日：2022-02-01

申请号：US17017126

申请日：2020-09-10

Applicant: Micron Technology, Inc.

Inventor： David Boles ,  John M. Groves ,  Steven Moyer ,  Alexander Tomlinson

IPC: G06F16/00 ,  G06F16/901 ,  G06F16/23 ,  G06F16/22

Abstract: A KVS tree database and operations thereon are described herein. A KVS tree database is a multilevel tree that includes a base level and subsequent levels. The base level includes a heterogeneous kvset in a node, The heterogeneous kvset including entries for multiple KVS trees, such as a first entry for a first KVS tree and a second entry for a second KVS tree, The subsequent level includes a first node including a first homogeneous kvset for the first KVS tree and a second node including a second homogeneous kvset for the second KVS tree. Here, a homogeneous kvset includes nodes from only one KVS tree. The KVS tree database also includes a first determinative mapping of entries between the base level and the subsequent level and a second determinative mapping of entries between subsequent levels.

公开(公告)号：US20210133208A1

公开(公告)日：2021-05-06

申请号：US17146222

申请日：2021-01-11

Applicant: Micron Technology, Inc.

Inventor： Alexander Tomlinson

IPC: G06F16/25 ,  G06F7/14 ,  G06F16/22 ,  G06F16/23

Abstract: Aspects of the present disclosure provide for operations of a key-value tree data structure that merges key-value pair data of a node, in a key-value tree data structure using counter values.