System architecture for integrated hierarchical query processing for key/value stores

• US 8,433,695 B2
• Filed: 04/29/2011
• Issued: 04/30/2013
• Est. Priority Date: 07/02/2010
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Wu, Jianming, Shi, Guangyu, Mortazavi, Masood, Kapuya, Avraham
• Primary Examiner(s): THAI, HANH B
• Application Number:
  US13/098,177
• Publication Number:
  US 20120005419A1
• Time in Patent Office: 732 Days
• Field of Search: 707/705, 707/747, 707/769, 707/762, 707/778
• US Class Current: 707/705
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951

Abstract

A key/value store comprising a first tier storage device configured to store information about a plurality of keys for a plurality of values without the values, and a second tier storage device coupled to the first tier storage device and configured to store the values associated with the keys without the keys, wherein the first tier storage device has lower latency and higher throughput than the second tier storage device, and wherein the second tier storage device has higher capacity than the first tier storage device. Also disclosed is a method comprising receiving a key/value operation request at a first tier storage device, mapping a key in the key/value operation request to a locator stored in a second tier storage device if the key/value operation request is valid, and mapping the locator to a value in a third tier storage device if the key has a corresponding locator.

Claims

1. A key/value store comprising:

a first tier storage device configured to store information about a plurality of keys for a plurality of values without the values; and

a second tier storage device coupled to the first tier storage device and configured to store the values associated with the keys without the keys,

wherein the first tier storage device has lower latency and higher throughput than the second tier storage device, and

wherein the second tier storage device has higher capacity than the first tier storage device.

2. The key/value store of claim 1 further comprising:

a third tier storage device coupled to the first tier storage device and the second tier storage device and configured to store a plurality of locators associated with the keys and the values,

wherein the third tier storage device has higher latency and lower throughput than the first tier storage device and lower latency and higher throughput than the second tier storage device, and

wherein the third tier storage device has higher capacity than the first tier storage device and lower capacity than the second tier storage device.

3. The key/value store of claim 2, wherein the first tier storage device is a Dynamic Random Access Memory (DRAM), the third tier storage device is a Solid State Drive (SSD), and the second tier storage device is a Hard Disk Drive (HDD).

4. The key/value store of claim 2, wherein the keys are represented in the first tier device using a bloom filter, wherein the locators are stored with the corresponding keys in a list of entries in the third tier storage device, and wherein the values are associated with the corresponding locators in the second tier storage device.

5. The key/value store of claim 2, wherein a plurality of hashed keys that correspond to the keys are stored in the first tier device, wherein the locators are stored with the corresponding keys in a list of entries in the third tier storage device, and wherein the values are associated with the corresponding locators in the second tier storage device.

6. The key/value store of claim 1, wherein the first tier storage device is a Dynamic Random Access Memory (DRAM) and the second tier storage device is a Solid State Drive (SSD).

7. The key/value store of claim 1, wherein the keys and a plurality of locators associated with the keys are stored in a list of entries in the first tier storage device, and wherein the values are associated with the corresponding locators in the second tier storage device.

8. A network component comprising:

a receiver configured to receive a plurality of hit queries and non-hit queries;

a first storage medium configured to store a plurality of keys for a plurality of values;

a second storage medium configured to store the values; and

a logic circuitry configured to process the hit queries at the first storage medium and the second storage medium and to process the non-hit queries only at the first storage medium without accessing the second storage medium.

9. The network component of claim 8, wherein the hit queries comprise a plurality of valid keys that have associated values in the second tier storage medium, and wherein the non-hit queries comprise a plurality of invalid keys, do not have associated values in the second storage medium, or correspond to denial-of-service (DoS)/distributed denial-of-service (DDoS) attacks.

10. The network component of claim 9, wherein the hit queries are processed by mapping the valid keys to a plurality of locators in the first storage medium and subsequently mapping the locators to the values in the second storage medium.

11. The network component of claim 9, wherein the non-hit queries are processed by discarding the invalid keys or mapping the non-hit queries to a plurality of locators in the first storage medium and subsequently discarding the non-hit queries that are not associated with values in the second storage medium.

12. The network component of claim 9, further comprising a third storage medium configured to store a plurality of locators associated with the keys and the values.

13. The network component of claim 12, wherein the first storage medium comprises a Dynamic Random Access Memory (DRAM), the third storage medium comprises a Solid State Drive (SSD), and the second storage medium comprises a Hard Disk Drive (HDD).

14. The network component of claim 12, wherein the keys are represented in the first storage medium using a bloom filter, wherein the locators are stored with the corresponding keys in a list of entries in the third storage medium, and wherein the values are associated with the corresponding locators in the second storage medium.

15. The network component of claim 12, wherein a plurality of hashed keys that correspond to the keys are stored in the first storage medium, wherein the locators are stored with the corresponding keys in a list of entries in the third storage medium, and wherein the values are associated with the corresponding locators in the second storage medium.

16. A method comprising:

receiving a key/value operation request at a first tier storage device;

mapping a key in the key/value operation request to a locator stored in a second tier storage device if the key/value operation request is valid;

mapping the locator to a value in a third tier storage device if the key has a corresponding locator,

discarding the key/value operation at the first query processing layer if the key/value operation request or the key is not valid; and

discarding the key/value operation request at the second query processing layer if the key does not have a corresponding locator,

wherein the key/value operation request is processed at a first query processing layer to obtain the key,

wherein the key is mapped to the locator at a second query processing layer, and

wherein the locator is mapped to the value at a third query processing layer.

17. The method of claim 16 further comprising mapping the key/value operation to the key using a bloom filter or a hash key in the key operation request at a third highest tier storage device.

18. The method of claim 16 further comprising caching some of the keys, some of the values, or both at a third highest tier storage device or at a part of the higher tier storage device and using the cached keys and values to process the key/value operation request.

19. The method of claim 16, wherein the third tier storage is configured to store the values associated with the keys without the keys.

20. The method of claim 16, wherein the first tier storage device has lower latency and higher throughput than the second and third tier storage devices, wherein the third tier storage device has higher capacity than the first and second tier storage devices, wherein the second storage device has a high capacity than the first storage device, and wherein the second storage device has a lower latency and a higher throughput than the third storage device.