US20230017732A1 - Key packing for flash key value store operations - Google Patents

Abstract

A key value (KV) store, a method thereof, and a storage system are provided herein. The KV store may include a key logger; and a processor configured to receive a first command for storing a first KV in the KV store, write a first value of the first KV to a first NAND page, generate an extent map for identifying the first memory page including the first value, write the extent map to a second memory page, append an entry for storing the first KV to the key logger, and update a device hashmap of the KV store to include a first key of the first KV, upon a threshold being met within the key logger.

Description

PRIORITY
• This application is based on and claims priority under 35 U.S.C. § 119(e) to U.S. Provisional Patent Application Ser. No. 63/222,685, which was filed in the U.S. Patent and Trademark Office on Jul. 16, 2021, the entire content of which is incorporated herein by reference.
TECHNICAL AREA
• The present disclosure relates generally to key value (KV) store operations, and more particularly to improving KV store operations by storing multiple keys together in a single NAND page.
BACKGROUND
• A KV store or a KV database, is a data storage paradigm designed for storing, retrieving, and managing associative arrays, and a data structure more commonly known as a hash table. Hash tables contain a collection of objects, or records, which in turn have many different fields within them, each containing data. These records may be stored and retrieved using a key that uniquely identifies the record, and may be used to find the data within the database. KV stores often use less memory than a relational database.
• The above information is presented as background information only to assist with an understanding of the disclosure. No determination has been made, and no assertion is made, as to whether any of the above might be applicable as prior art with regard to the disclosure.
SUMMARY
• The present disclosure is made to address at least some of the disadvantages described above and to provide at least the advantages described below.
• An aspect of the present disclosure is to provide a system and method that allows packing of multiple keys inserted with no temporal locality, such that they may be grouped into a bunch of memory pages (e.g. NAND pages) with spatial locality. This provides a reduction in the number of NAND pages required to store all keys, and read amplification factor (RAF)/write amplification factor (WAF) reduction due to dense key packing. Further, NAND pages may limit garbage collection (GC) to when all keys in a page are invalidated.
• Accordingly, the present disclosure may significantly reduce GC overheads by a factor of packing density and reduce lengths of hash-map collision chains, which improves tail latency and lessens the number of NAND page reads that significantly decrease lookup latencies.
• According to one embodiment, a KV store may be provided, which includes a key logger;
• and a processor configured to receive a first command for storing a first KV in the KV store, write a first value of the first KV to a first memory page, generate an extent map for identifying the first memory page including the value, write the extent map to a second memory page, append an entry for storing the first KV to the key logger, and update a device hashmap of the KV store to include a first key of the first KV, upon a threshold being met within the key logger.
• According to one embodiment, a method of operating a KV store may be provided. The method includes receiving a first command for storing a first KV in the KV store; writing a first value of the first KV to a first memory page; generating an extent map for identifying the first memory page including the value; writing the extent map to a second NAND page; appending an entry for storing the first KV to a key logger of the KV store; and updating a device hashmap of the KV store to include a first key of the first KV, upon a threshold being met within the key logger.
• According to one embodiment, a storage system may be provided, which includes a KV store; and a processor configured to receive a first command for storing a first KV in the KV store, write a first value of the first KV to a first memory page, generate an extent map for identifying the first memory page including the value, write the extent map to a second memory page, append an entry for storing the first KV to a key logger of the KV store, and update a device hashmap of the KV store to include a first key of the first KV, upon a threshold being met within the key logger.
BRIEF DESCRIPTION OF THE DRAWINGS
• The above and other aspects, features, and advantages of certain embodiments of the present disclosure will be more apparent from the following detailed description, taken in conjunction with the accompanying drawings, in which:
• FIG.1 illustrates a hash implementation in a KV solid state device (SSD);
• FIG.2 illustrates a hash implementation in a KV SSD, according to an embodiment;
• FIG.3 illustrates a KV store, according to an embodiment;
• FIGS.4A and4B illustrate a deferred key packing operation in a KV store, according to an embodiment;
• FIG.5 is a flowchart illustrating a key packing operation of a KV store, according to an embodiment;
• FIG.6 is flowchart illustrating a Put operation of a KV store, according to an embodiment;
• FIG.7 is a flowchart illustrating a Delete operation of a KV store, according to an embodiment;
• FIG.8 is a flowchart illustrating a Get operation of a KV store, according to an embodiment;
• FIG.9 illustrates a block diagram of an electronic device in a network environment, according to an embodiment; and
• FIG.10 illustrates a diagram of a storage system, according to an embodiment.
DETAILED DESCRIPTION
• Hereinafter, embodiments of the present disclosure are described in detail with reference to the accompanying drawings. It should be noted that the same elements will be designated by the same reference numerals although they are shown in different drawings. In the following description, specific details such as detailed configurations and components are merely provided to assist with the overall understanding of the embodiments of the present disclosure. Therefore, it should be apparent to those skilled in the art that various changes and modifications of the embodiments described herein may be made without departing from the scope of the present disclosure. In addition, descriptions of well-known functions and constructions are omitted for clarity and conciseness. The terms described below are terms defined in consideration of the functions in the present disclosure, and may be different according to users, intentions of the users, or customs. Therefore, the definitions of the terms should be determined based on the contents throughout this specification.
• The present disclosure may have various modifications and various embodiments, among which embodiments are described below in detail with reference to the accompanying drawings. However, it should be understood that the present disclosure is not limited to the embodiments, but includes all modifications, equivalents, and alternatives within the scope of the present disclosure.
• Although the terms including an ordinal number such as first, second, etc. may be used for describing various elements, the structural elements are not restricted by the terms. The terms are only used to distinguish one element from another element. For example, without departing from the scope of the present disclosure, a first structural element may be referred to as a second structural element. Similarly, the second structural element may also be referred to as the first structural element. As used herein, the term “and/or” includes any and all combinations of one or more associated items.
• The terms used herein are merely used to describe various embodiments of the present disclosure but are not intended to limit the present disclosure. Singular forms are intended to include plural forms unless the context clearly indicates otherwise. In the present disclosure, it should be understood that the terms “include” or “have” indicate existence of a feature, a number, a step, an operation, a structural element, parts, or a combination thereof, and do not exclude the existence or probability of the addition of one or more other features, numerals, steps, operations, structural elements, parts, or combinations thereof.
• Unless defined differently, all terms used herein have the same meanings as those understood by a person skilled in the art to which the present disclosure belongs. Terms such as those defined in a generally used dictionary are to be interpreted to have the same meanings as the contextual meanings in the relevant field of art, and are not to be interpreted to have ideal or excessively formal meanings unless clearly defined in the present disclosure.
• An electronic device according to one embodiment may be one of various types of electronic devices. The electronic devices may include, for example, a portable communication device (e.g., a smart phone), a computer, a portable multimedia device, a portable medical device, a camera, a wearable device, or a home appliance. According to one embodiment of the disclosure, an electronic device is not limited to those described above.
• The terms used in the present disclosure are not intended to limit the present disclosure but are intended to include various changes, equivalents, or replacements for a corresponding embodiment. With regard to the descriptions of the accompanying drawings, similar reference numerals may be used to refer to similar or related elements. A singular form of a noun corresponding to an item may include one or more of the things, unless the relevant context clearly indicates otherwise. As used herein, each of such phrases as “A or B,” “at least one of A and B,” “at least one of A or B,” “A, B, or C,” “at least one of A, B, and C,” and “at least one of A, B, or C,” may include all possible combinations of the items enumerated together in a corresponding one of the phrases. As used herein, terms such as “1^st,” “2nd,” “first,” and “second” may be used to distinguish a corresponding component from another component, but are not intended to limit the components in other aspects (e.g., importance or order). It is intended that if an element (e.g., a first element) is referred to, with or without the term “operatively” or “communicatively”, as “coupled with,” “coupled to,” “connected with,” or “connected to” another element (e.g., a second element), it indicates that the element may be coupled with the other element directly (e.g., wired), wirelessly, or via a third element.
• As used herein, the term “module” may include a unit implemented in hardware, software, or firmware, and may interchangeably be used with other terms, for example, “logic,” “logic block,” “part,” and “circuitry.” A module may be a single integral component, or a minimum unit or part thereof, adapted to perform one or more functions. For example, according to one embodiment, a module may be implemented in a form of an application-specific integrated circuit (ASIC).
• Herein, any of the components or any combination of the components described (i.e., in the device diagrams) can be used to perform one or more of the operations of the flowcharts. The operations depicted in the flowcharts are exemplary operations and may involve various additional steps not explicitly provided in the flowcharts. The order of the operations depicted in the flowcharts is exemplary and not exclusive, as the order may vary depending on the implementation.
• An objective of a KV store may be to complete operations (e.g., Put/Get/Delete operations) in the fastest time possible, and in a typical KV store implementation, keys can be hashed and inserted into a hashmap.
• Reducing tail latency of KV operations may be beneficial for several workloads like artificial intelligence/machine learning (AI/ML), data sciences, etc. Further, it may be beneficial that KV technology will adapt to dense media with lower longevity.
• High performance computing (HPC) storage may be designed to be compatible with media having 50-500 write cycles. Consequently, reducing a WAF caused by application or device induced GC may also be beneficial. For example, reducing device WAF may also decrease an RAF in KV stores, possibly improving overall storage performance.
• A single NAND page can contain one key, which may result in higher device WAF when processing Delete operations and higher RAF when processing Put/Get/Exist operations.
• Additionally, worst case tail latency of a KV store may be proportional to a length of a longest collision chain in buckets of the hashmap. Increasing a number of buckets to reduce collision chains results in extra memory space required to host the buckets.
• Further, if buckets are themselves stored in NAND, when processing Put of a KV, device WAF increases, since for almost each KV insert, the NAND page hosting the bucket may need to be replaced.
• In accordance with this disclosure, systems and methods are provided, which allow for the packing of multiple keys together in a single NAND page, which may reduce worst case collision length in a device hashmap. Keys in the device hashmap may be grouped together to have spatial locality even though the keys themselves have no temporal locality.
• FIG.1 illustrates a hash implementation in a KV SSD.
• As illustrated inFIG.1, keys are hashed and inserted into a hashmap. However, a single NAND page can contain only one key. For example, bucket2f8 in the hashmap incudes a chain for Key1, Key34, and Key21. Each of Key1, Key34, and Key21 is stored on a separate NAND page. As described above, this may result in higher RAF during Puts/Gets/Exists, and higher device WAF during Deletes. Further, the worst case tail latency may be proportional to the length of longest collision chain in buckets of the hashmap, e.g.,bucket467 inFIG.1.
• In accordance with an embodiment of the disclosure, multiple keys may be packed together in a single NAND page to reduce the worst case collision length in a hashmap by a packing factor P (average number of keys packed per page).
• FIG.2 illustrates a hash implementation in a KV SSD, according to an embodiment
• Referring toFIG.2, multiple keys may be packed together in a single NAND page, wherein each key contains an extent pointer.
• A method according to an embodiment of the disclosure includes gathering related keys that have no temporal locality and grouping them together to have spatial locality. That is, keys that are indexed within contiguous buckets of the hashmap may be grouped into bucket groups.
• Additionally, the format of the KV entries may be modified such that a value may be written to NAND pages and may be tracked by an extent map. The extent map itself may be written to a NAND page, which may also contain part of the value, if space is available in the NAND page after writing the extent map. A key contains one extent pointer to the NAND page that contains the actual extent map, which in turn locates the pages containing the value for the key.
• This may significantly reduce device WAF/RAF when processing Get/Put/Delete operations by an entire factor of P. For example, if on an average, 4 keys can be packed into a page, the collision chain length reduces by 4 times along with a corresponding device WAF/RAF reduction by 4 times.
• Key packing, as described above, can be achieved with minimal additional resources consumed within the KV Store.
• FIG.3 illustrates a KV store, according to an embodiment.
• Referring toFIG.3, theKV store300 includes a key logger301 (e.g., an Auto Operation Logger (AOL)) that may be used to assist in key packing, aBloom filter303 to track keys inkey logger301, and a tail pointer table305 to create a back linked-list of keys in thekey logger301.
• key logger301 may be device wide and may only have append operations to it. Therefore, it may be implemented internally, like a Zoned namespace.
• ABloom filter303 tracks keys in thekey logger301 and therefore may be compact.
• For example, if thekey logger301 contains 10K entries, theBloom filter303 may include as few as 3 pages (each 4K RAM/SRAM/DRAM).
• Given that less than 0.01% of keys are logged in thekey logger301, compared to total keys in KV stores, most of the Get/Put/Delete operations will not include traversing the tail pointer table305 of entries in thekey logger301.
• A tail pointer table305 may be so constructed that if theBloom filter303 denotes a hit, the number of entries required to be traversed in thekey logger301 may be limited to one or two entries only. For example, ifkey logger301 has 10K entries, the tail pointer table305 may have 5K entries (each pointer being 16 bits only).
• AlthoughFIG.3 illustrates the components of theKV store300 as separate elements, the disclosure is not limited thereto. For example, at least two of the components may be combined into a single element, such as a processor, integrated circuit (IC), system on chip (SoC), etc., which pay perform the corresponding operations.
• FIGS.4A and4B illustrate a deferred key packing operation in a KV store, according to an embodiment. More specifically,FIG.4A illustrates an example before processing deferred key packing in KV stores, andFIG.4B illustrates an example after processing deferred packing of keys from a key logger. The deferred key packing operation may be based on Store (or Put) and Delete operations on KVs being first written only to the key logger. That is, instead of immediately performing the received Store and Delete operations, the entries may be written in the key logger until a certain threshold is reached and the operation may be performed. For example, the threshold may be a function of the percentage of entries in the key logger and/or a rate at which the key logger is filling up.
• Referring toFIG.4A, a bucket group includes 8 buckets B1 to B8 and points tological NAND pages6878 and6784 on which multiple keys are packed with extent pointers (ExtentP). In the example illustrated inFIG.4A, each logical NAND page may include a maximum of 6 keys, and includes a pointer to the next page containing keys of bucket group.
• Onlogical page6878, Key1 contains an extent pointer to an extent map stored onpage7. The extent map stored onpage7 identifies the page on which the value corresponding Key1 is stored. Similarly, Key12 contains an extent pointer to an extent map stored onpage480, Key2 contains an extent pointer to an extent map stored onpage21, KeyA contains an extent pointer to an extent map stored onpage78, and Key5 contains an extent pointer to an extent map stored onpage790. Each of the extent maps identifies the pages on which the values of the corresponding key are stored.
• Additionally,FIG.4A provides an example of a key logger with two chains of entries. Assuming that certain threshold is reached, the entries in the key logger may then be processed, i.e., deferred key packing may be performed.
• Referring toFIG.4B, among the entries of the chain being processed, there is a Store entry and a Delete entry for Key1/ExtentP480, which essentially cancel each other out.
• There is also Store entry for Key1/ExtentP250. Accordingly,logical page6878 receives a new entry for Key1 that contains an extent pointer topage250, on which an extent map is stored, which identifies the pages one which the value corresponding to Key1 are stored.
• Additionally, the old Key1 (as illustrated inFIG.4A) is removed fromlogical page6878, andpage7, which included the extent map for old Key1, and the pages identified by the extent map for old Key1 are queued for erase.
• Similarly, there is a Store entry for Key2/ExtentP310. Accordingly,logical page6878 receives a new entry for Key2 that contains an extent pointer topage310, on which an extent map is stored, which identifies the pages one which the value corresponding to Key2 are stored.
• Additionally, the old Key2 (as illustrated inFIG.4A) is removed fromlogical page6878, andpage21, which included the extent map for old Key2, and the pages identified by the extent map for old Key2 are queued for erase.
• There is also a Store entry for Key3/ExtentP560. Accordingly,logical page6878 receives a new entry for Key3 that contains an extent pointer topage560, on which an extent map is stored, which identifies the pages one which the value corresponding to Key3 are stored.
• There is also a Delete entry for Key12, which results in Key12 being removed fromlogical page6878, andpage480, which included the extent map for Key12, and the pages identified by the extent map for Key12 are queued for erase.
• Similarly, there is a Delete entry for Key5, which results in Key5 being removed fromlogical page6878, andpage790, which included the extent map for Key5, and the pages identified by the extent map for Key5 are queued for erase.
• Because two keys were removed from logical page6878 (Key12 and Key5) and one new key was added to logical page6878 (Key3), only 5 keys are left onlogical page6878. Therefore, KeyX is moved from logical page6784 (as illustrated inFIG.3) to logical page6878 (as illustrated inFIG.4B) so thatlogical page6878 includes the maximum of 6 keys.
• FIG.5 is a flowchart illustrating a key packing operation of a KV store, according to an embodiment.
• Referring toFIG.5, instep501, a key logger logs key entries for Store and Delete operations.
• After a certain threshold is met in the key logger instep503, e.g., the key logger is filled beyond a set threshold, key entries belonging to a group of adjacent buckets in a device hashmap are collated instep505.
• Instep507, existing keys in the device hashmap are merged with entries from the key logger to form new packed keys for each group of buckets.
• Instep509, the packed keys are written to at least one NAND page and the device hashmap is updated to point to pages containing the packed keys.
• Instep511, the key logger and its associated Bloom filter are cleared, such that the key logger can log new key entries.
• Grouping keys that correspond to a group of buckets may be an operation of O (1) complexity.
• Additionally, when adjacent buckets of a bucket group contain just one or two keys, they can end up sharing a packed key NAND page.
• For continuity of Put/Delete/Get operations when a key logger is being processed, a device according to an embodiment can implement two or more independent key loggers.
• FIG.6 is flowchart illustrating a Put operation of a KV store, according to an embodiment.
• Referring toFIG.6, instep601, upon receiving Put command for storing a KV, the KV store writes only the value of the KV to NAND pages.
• Instep603, the KV store creates an extent map page that tracks the location of the various NAND pages that contain the value of the KV.
• Instep605, the Bloom filter of the key logger is updated. For example, the Bloom filter may be updated such that a pre-determined number of known hash functions may be used to set bits in the Bloom filter bitmap.
• Instep607, a slot is selected in the tail pointer table based on the hash of the key of the KV. For example, the tail pointer table can contain K/2 entries, where K=total number of entries in the key logger.
• Instep609, the KV store notes the contents of the selected slot of the tail pointer table (i.e., the tail entry) and writes a current offset in the key logger to the same slot of the tail pointer table. Basically, the tail pointer table may be a hashmap of entries that are present in the key logger such that each bucket pointer of the hashmap points to the latest entry that mapped to the bucket. The tail pointer table may reduce the number of slots to be traversed in the key logger to find a particular key that may be indicated to be likely present in the key logger by an associated Bloom filter.
• Instep611, the KV store creates a four way tuple of the key, the NAND page containing the extent map, the opcode, and the tail entry pointer and appends the tuple to the key logger. AlthoughFIG.6 utilizes a four way tuple of the key, the disclosure is not limited thereto, and different sized tuples of the keys may be used.
• Instep613, the KV store updates a hashmap of the KVs, after sufficient number of keys are logged into key logger.
• FIG.7 is a flowchart illustrating a Delete operation of a KV store, according to an embodiment.
• Referring toFIG.7, instep701, upon receiving a Delete command for deleting a KV from the KV store, the KV store checks a Bloom filter tracking key entries in a key logger for the presence of the key to be deleted.
• When the Bloom filter for the key logger suggests a hit for the key instep703, the KV store traverses a hashmap for keys in the key logger in order to check for the presence of a matching keyname instep705. For example, if the received Delete command is for deleting a KV for Key33, the KV determines whether the key logger already includes an entry for Key33.
• When there is a matching keyname in the key logger instep707, the operation proceeds to step711.
• However, when the Bloom filter for the key logger does not suggest a hit for the key instep703 or when there is not a matching keyname in the key logger instep707, the KV store determines if the key is present in the device hashmap instep709.
• When the key is not present in the device hashmap instep709, the operation ends as there is no key available to delete.
• However, when the key is present in the device hashmap instep709, the operation proceeds to step711.
• Instep711, the KV store creates a Delete key entry and appends it to the key logger. For example, a Delete Key Entry tuple contains an indication of the key to be deleted, an address of the NAND page containing an extent map of the key (e.g., as read from the previous entry of the key in key logger), a delete opcode, and a current entry in tail pointer table.
• Instep713, the KV store updates the address of the key entry in tail pointer table to reflect the new Delete key entry.
• Instep715, the KV store defers the actual deletion of the key from the device hashmap. That is, the KV store waits to execute the delete operation until a certain threshold is reached within the key logger, as described above with reference toFIGS.4A and4B.
• FIG.8 is a flowchart illustrating a Get operation of a KV store, according to an embodiment.
• Referring toFIG.8, instep801, upon receiving a Get command for retrieving a stored KV, the KV store checks a Bloom filter tracking key entries in a key logger for the presence of the key to be retrieved.
• When the Bloom filter for the key logger suggests a hit for the key instep803, the KV store traverses a hashmap for keys in the key logger in order to check for the presence of a matching keyname instep805. For example, if the received Get command is for retrieving a KV for Key77, the KV determines whether the key logger already includes an entry for Key77.
• When there is a matching keyname in the key logger instep807, the KV stores determines whether the matching keyname in the key logger includes an opcode for delete instep815.
• When the matching keyname in the key logger includes an opcode for delete instep815, the Get operation fails instep817. For example, if the Get command is for retrieving a KV for Key88, but the key logger already includes an command entry to delete the KV for Key88, then the retrieve operation fails.
• However, when the matching keyname in the key logger does not include an opcode for delete instep815, e.g., the matching keyname includes an opcode for store, the operation proceeds to step811.
• When the Bloom filter for the key logger does not suggest a hit for the key instep803 or when there is not a matching keyname in the key logger instep807, the KV store determines if the key is present in the device hashmap instep809.
• When the key is not present in the device hashmap instep809, the Get operation fails instep813, as there is no key available to retrieve.
• However, when the key is present in the device hashmap instep809, the operation proceeds to step811.
• Instep811, the KV store reads a NAND page containing an extent map of the key and then reads the value of the key from the NAND page or pages identified by the extent map. As described above, because the device hashmap stores may store multiple keys and extent pointers, which point NAND pages containing extent maps for the keys, on a single NAND page, the KV may be able to quickly identify the NAND page containing an extent map of the key and then read the value of the key from the NAND page or pages identified by the extent map.
• FIG.9 illustrates a block diagram of anelectronic device901 in anetwork environment900, according to one embodiment.
• Referring toFIG.9, theelectronic device901 in thenetwork environment900 may communicate with anelectronic device902 via a first network998 (e.g., a short-range wireless communication network), or anelectronic device904 or a server908 via a second network999 (e.g., a long-range wireless communication network). Theelectronic device901 may communicate with theelectronic device904 via the server908. Theelectronic device901 may include aprocessor920, amemory930, aninput device950, asound output device955, adisplay device960, anaudio module970, asensor module976, aninterface977, ahaptic module979, acamera module980, apower management module988, a battery989, acommunication module990, a subscriber identification module (SIM)996, or anantenna module997. In one embodiment, at least one (e.g., thedisplay device960 or the camera module980) of the components may be omitted from theelectronic device901, or one or more other components may be added to theelectronic device901. In one embodiment, some of the components may be implemented as a single integrated circuit (IC). For example, the sensor module976 (e.g., a fingerprint sensor, an iris sensor, or an illuminance sensor) may be embedded in the display device960 (e.g., a display).
• Theprocessor920 may execute, for example, software (e.g., a program940) to control at least one other component (e.g., a hardware or a software component) of theelectronic device901 coupled with theprocessor920, and may perform various data processing or computations. As at least part of the data processing or computations, theprocessor920 may load a command or data received from another component (e.g., thesensor module976 or the communication module990) involatile memory932, process the command or the data stored in thevolatile memory932, and store resulting data innon-volatile memory934. Theprocessor920 may include a main processor921 (e.g., a central processing unit (CPU) or an application processor (AP)), and an auxiliary processor923 (e.g., a graphics processing unit (GPU), an image signal processor (ISP), a sensor hub processor, or a communication processor (CP)) that is operable independently from, or in conjunction with, themain processor921. Additionally or alternatively, theauxiliary processor923 may be adapted to consume less power than themain processor921, or execute a particular function. Theauxiliary processor923 may be implemented as being separate from, or a part of, themain processor921.
• Theauxiliary processor923 may control at least some of the functions or states related to at least one component (e.g., thedisplay device960, thesensor module976, or the communication module990) among the components of theelectronic device901, instead of themain processor921 while themain processor921 is in an inactive (e.g., sleep) state, or together with themain processor921 while themain processor921 is in an active state (e.g., executing an application). According to one embodiment, the auxiliary processor923 (e.g., an image signal processor or a communication processor) may be implemented as part of another component (e.g., thecamera module980 or the communication module990) functionally related to theauxiliary processor923.
• Thememory930 may store various data used by at least one component (e.g., theprocessor920 or the sensor module976) of theelectronic device901. The various data may include, for example, software (e.g., the program940) and input data or output data for a command related thereto. Thememory930 may include thevolatile memory932 or thenon-volatile memory934.
• Theprogram940 may be stored in thememory930 as software, and may include, for example, an operating system (OS)942,middleware944, or anapplication946.
• Theinput device950 may receive a command or data to be used by other component (e.g., the processor920) of theelectronic device901, from the outside (e.g., a user) of theelectronic device901. Theinput device950 may include, for example, a microphone, a mouse, or a keyboard.
• Thesound output device955 may output sound signals to the outside of theelectronic device901. Thesound output device955 may include, for example, a speaker or a receiver. The speaker may be used for general purposes, such as playing multimedia or recording, and the receiver may be used for receiving an incoming call. According to one embodiment, the receiver may be implemented as being separate from, or a part of, the speaker.
• Thedisplay device960 may visually provide information to the outside (e.g., a user) of theelectronic device901. Thedisplay device960 may include, for example, a display, a hologram device, or a projector and control circuitry to control a corresponding one of the display, hologram device, and projector. According to one embodiment, thedisplay device960 may include touch circuitry adapted to detect a touch, or sensor circuitry (e.g., a pressure sensor) adapted to measure the intensity of force incurred by the touch.
• Theaudio module970 may convert a sound into an electrical signal and vice versa. According to one embodiment, theaudio module970 may obtain the sound via theinput device950, or output the sound via thesound output device955 or a headphone of an externalelectronic device902 directly (e.g., wired) or wirelessly coupled with theelectronic device901.
• Thesensor module976 may detect an operational state (e.g., power or temperature) of theelectronic device901 or an environmental state (e.g., a state of a user) external to theelectronic device901, and then generate an electrical signal or data value corresponding to the detected state. Thesensor module976 may include, for example, a gesture sensor, a gyro sensor, an atmospheric pressure sensor, a magnetic sensor, an acceleration sensor, a grip sensor, a proximity sensor, a color sensor, an infrared (IR) sensor, a biometric sensor, a temperature sensor, a humidity sensor, or an illuminance sensor.
• Theinterface977 may support one or more specified protocols to be used for theelectronic device901 to be coupled with the externalelectronic device902 directly (e.g., wired) or wirelessly. According to one embodiment, theinterface977 may include, for example, a high definition multimedia interface (HDMI), a universal serial bus (USB) interface, a secure digital (SD) card interface, or an audio interface.
• A connectingterminal978 may include a connector via which theelectronic device901 may be physically connected with the externalelectronic device902. According to one embodiment, the connectingterminal978 may include, for example, an HDMI connector, a USB connector, an SD card connector, or an audio connector (e.g., a headphone connector).
• Thehaptic module979 may convert an electrical signal into a mechanical stimulus (e.g., a vibration or a movement) or an electrical stimulus which may be recognized by a user via tactile sensation or kinesthetic sensation. According to one embodiment, thehaptic module979 may include, for example, a motor, a piezoelectric element, or an electrical stimulator.
• Thecamera module980 may capture a still image or moving images. According to one embodiment, thecamera module980 may include one or more lenses, image sensors, image signal processors, or flashes.
• Thepower management module988 may manage power supplied to theelectronic device901. Thepower management module988 may be implemented as at least part of, for example, a power management integrated circuit (PMIC).
• The battery989 may supply power to at least one component of theelectronic device901. According to one embodiment, the battery989 may include, for example, a primary cell which is not rechargeable, a secondary cell which is rechargeable, or a fuel cell.
• Thecommunication module990 may support establishing a direct (e.g., wired) communication channel or a wireless communication channel between theelectronic device901 and the external electronic device (e.g., theelectronic device902, theelectronic device904, or the server908) and performing communication via the established communication channel. Thecommunication module990 may include one or more communication processors that are operable independently from the processor920 (e.g., the AP) and supports a direct (e.g., wired) communication or a wireless communication. According to one embodiment, thecommunication module990 may include a wireless communication module992 (e.g., a cellular communication module, a short-range wireless communication module, or a global navigation satellite system (GNSS) communication module) or a wired communication module994 (e.g., a local area network (LAN) communication module or a power line communication (PLC) module). A corresponding one of these communication modules may communicate with the external electronic device via the first network998 (e.g., a short-range communication network, such as Bluetooth™, wireless-fidelity (Wi-Fi) direct, or a standard of the Infrared Data Association (IrDA)) or the second network999 (e.g., a long-range communication network, such as a cellular network, the Internet, or a computer network (e.g., LAN or wide area network (WAN)). These various types of communication modules may be implemented as a single component (e.g., a single IC), or may be implemented as multiple components (e.g., multiple ICs) that are separate from each other. Thewireless communication module992 may identify and authenticate theelectronic device901 in a communication network, such as the first network998 or thesecond network999, using subscriber information (e.g., international mobile subscriber identity (IMSI)) stored in thesubscriber identification module996.
• Theantenna module997 may transmit or receive a signal or power to or from the outside (e.g., the external electronic device) of theelectronic device901. According to one embodiment, theantenna module997 may include one or more antennas, and, therefrom, at least one antenna appropriate for a communication scheme used in the communication network, such as the first network998 or thesecond network999, may be selected, for example, by the communication module990 (e.g., the wireless communication module992). The signal or the power may then be transmitted or received between thecommunication module990 and the external electronic device via the selected at least one antenna.
• At least some of the above-described components may be mutually coupled and communicate signals (e.g., commands or data) therebetween via an inter-peripheral communication scheme (e.g., a bus, a general purpose input and output (GPIO), a serial peripheral interface (SPI), or a mobile industry processor interface (MIPI)).
• According to one embodiment, commands or data may be transmitted or received between theelectronic device901 and the externalelectronic device904 via the server908 coupled with thesecond network999. Each of theelectronic devices902 and904 may be a device of a same type as, or a different type, from theelectronic device901. All or some of operations to be executed at theelectronic device901 may be executed at one or more of the externalelectronic devices902,904, or908. For example, if theelectronic device901 should perform a function or a service automatically, or in response to a request from a user or another device, theelectronic device901, instead of, or in addition to, executing the function or the service, may request the one or more external electronic devices to perform at least part of the function or the service. The one or more external electronic devices receiving the request may perform the at least part of the function or the service requested, or an additional function or an additional service related to the request, and transfer an outcome of the performing to theelectronic device901. Theelectronic device901 may provide the outcome, with or without further processing of the outcome, as at least part of a reply to the request. To that end, a cloud computing, distributed computing, or client-server computing technology may be used, for example.
• One embodiment may be implemented as software (e.g., the program940) including one or more instructions that are stored in a storage medium (e.g.,internal memory936 or external memory938) that is readable by a machine (e.g., the electronic device901). For example, a processor of theelectronic device901 may invoke at least one of the one or more instructions stored in the storage medium, and execute it, with or without using one or more other components under the control of the processor. Thus, a machine may be operated to perform at least one function according to the at least one instruction invoked. The one or more instructions may include code generated by a complier or code executable by an interpreter. A machine-readable storage medium may be provided in the form of a non-transitory storage medium. The term “non-transitory” indicates that the storage medium is a tangible device, and does not include a signal (e.g., an electromagnetic wave), but this term does not differentiate between where data is semi-permanently stored in the storage medium and where the data is temporarily stored in the storage medium.
• According to one embodiment, a method of the disclosure may be included and provided in a computer program product. The computer program product may be traded as a product between a seller and a buyer. The computer program product may be distributed in the form of a machine-readable storage medium (e.g., a compact disc read only memory (CD-ROM)), or be distributed (e.g., downloaded or uploaded) online via an application store (e.g., Play Store™), or between two user devices (e.g., smart phones) directly. If distributed online, at least part of the computer program product may be temporarily generated or at least temporarily stored in the machine-readable storage medium, such as memory of the manufacturer's server, a server of the application store, or a relay server.
• According to one embodiment, each component (e.g., a module or a program) of the above-described components may include a single entity or multiple entities. One or more of the above-described components may be omitted, or one or more other components may be added. Alternatively or additionally, a plurality of components (e.g., modules or programs) may be integrated into a single component. In this case, the integrated component may still perform one or more functions of each of the plurality of components in the same or similar manner as they are performed by a corresponding one of the plurality of components before the integration. Operations performed by the module, the program, or another component may be carried out sequentially, in parallel, repeatedly, or heuristically, or one or more of the operations may be executed in a different order or omitted, or one or more other operations may be added.
• FIG.10 illustrates a diagram of astorage system1000, according to an embodiment.
• Thestorage system1000 includes ahost1002 and astorage device1004. Although one host and one storage device is depicted, thestorage system1000 may include multiple hosts and/or multiple storage devices. Thestorage device1004 may be an SSD, a universal flash storage (UFS), etc. Thestorage device1004 includes acontroller1006 and a storage medium1008 connected to thecontroller1006. Thecontroller1006 may be an SSD controller, a UFS controller, etc. The storage medium1008 may include a volatile memory, a non-volatile memory, or both, and may include one or more flash memory chips (or other storage media). Thecontroller1006 may include one or more processors, one or more error correction circuits, one or more field programmable gate arrays (FPGAs), one or more host interfaces, one or more flash bus interfaces, etc., or a combination thereof. Thecontroller1006 may be configured to facilitate transfer of data/commands between thehost1002 and the storage medium1008. Thehost1002 sends data/commands to thestorage device1004 to be received by thecontroller1006 and processed in conjunction with the storage medium1008. As described herein, the methods, processes and algorithms may be implemented on a storage device controller, such ascontroller1006. The sources and destinations described herein may correspond to elements of the host1002 (i.e., processors or applications) and the storage medium1008.
• In accordance with the above-described embodiments, a system and method are provided, which allow for the packing of multiple keys together in a single NAND page in order to reduce the worst case collision length in a device hashmap by a packing factor P (i.e., the average number of keys packed per page).
• Further, related keys that have no temporal locality may be grouped together to have spatial locality. That is, keys that map to adjacent buckets in a device hashmap can be grouped together even though the keys themselves have no temporal locality.
• Accordingly, the number of NAND pages required to store all keys, and RAF/WAF reduction due to dense key packing may be reduced. Further, NAND pages may reduce GC to when all keys in a page are invalidated.
• Accordingly, the present disclosure may significantly reduce GC overheads by a factor of packing density and reduce lengths of hash-map collision chains, which may improve tail latency and lessen the number of NAND page reads that can significantly decrease lookup latencies.
• Although certain embodiments of the present disclosure have been described in the detailed description of the present disclosure, the present disclosure may be modified in various forms without departing from the scope of the present disclosure. Thus, the scope of the present disclosure shall not be determined merely based on the described embodiments, but rather determined based on the accompanying claims and equivalents thereto.

Claims (20)

1. A method for improving carrier to noise density ratio of a matched filter, the method comprising:

receiving a signal at a signal register of the matched filter;

receiving a local code at a local code register and a nulling register of the matched filter; and

correlating, at an adder tree of the matched filter, the signal register and the local code register with respect to the nulling register to obtain a correlation result, wherein the nulling register prevents high frequency samples of the signal register from affecting the correlation result.

2. The method ofclaim 1, wherein the matched filter corresponds to a narrowband receiver in a global navigation satellite system (GNSS).

3. The method ofclaim 2, wherein the signal is a time multiplexed binary offset carrier (TMBOC) transmission.

4. The method ofclaim 3, wherein the TMBOC transmission comprises an L1-C_pchannel having binary offset carrier (BOC)(1,1) and BOC (6,1) spreading symbols.

5. The method ofclaim 4, wherein the high frequency samples comprise the BOC (6,1) spreading symbols of the L1-C_pchannel.

6. The method ofclaim 1, wherein receiving the signal comprises:

receiving signal samples at a signal processor of the matched filter; and

processing the signal samples using frequencies from a carrier numerically-controlled oscillator (NCO) of the matched filter.

7. The method ofclaim 6, wherein receiving the signal further comprises:

digitizing the processed signal samples at a quantizer of the matched filter; and

providing the digitized processed signal samples to the signal register.

8. The method ofclaim 1, wherein receiving the local code comprises:

generating the local code at a local code generator of the matched filter.

9. The method ofclaim 8, wherein the local code is a 1-bit stream local code.

10. The method ofclaim 1, wherein the nulling register is aligned with timings of the high frequency samples of the signal register.

11. A matched filter for improving carrier to noise density ratio, the matched filter comprising:

a signal register receiving a signal;

a local code register receiving a local code;

a nulling register receiving the local code; and

an adder tree correlating the signal register and the local code register with respect to the nulling register to obtain a correlation result, wherein the nulling register prevents high frequency samples of the signal register from affecting the correlation result.

12. The matched filter ofclaim 11, wherein the matched filter corresponds to a narrowband receiver in a global navigation satellite system (GNSS).

13. The matched filter ofclaim 12, wherein the signal is a time multiplexed binary offset carrier (TMBOC) transmission.

14. The matched filter ofclaim 13, wherein the TMBOC transmission comprises an L1-C_pchannel having binary offset carrier (BOC)(1,1) and BOC (6,1) spreading symbols.

15. The matched filter ofclaim 14, wherein the high frequency samples comprise the BOC (6,1) spreading symbols of the L1-C_pchannel.

16. The matched ofclaim 11, further comprising:

a carrier numerically-controlled oscillator (NCO) outputting frequencies; and

a signal processor receiving signal samples and processing the signal samples using the frequencies from the carrier NCO.

17. The matched filter ofclaim 16, further comprising:

a quantizer digitizing the processed signal samples and providing the digitized processed signal samples to the signal register.

18. The matched filter ofclaim 11, further comprising:

a local code generator generating the local code and providing the local code to the local code register and the nulling register.

19. The matched filter ofclaim 18, wherein the local code is a 1-bit stream local code.

20. The matched filter ofclaim 11, wherein the nulling register is aligned with timings of the high frequency samples of the signal register.

Images