Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Consistent Hashing Algorithm Improvement with Flash Storage

IP.com Disclosure Number: IPCOM000245571D
Publication Date: 2016-Mar-18

Publishing Venue

The IP.com Prior Art Database

Abstract

This article shows an improved method for consistent hashing algorithm in flash storage system. Actually, all objects are eventually saved in at least one storage media underneath. But consistent hashing algorithm has no sense of the media type in storage subsystem. This invention is to have a better performance of object read by leveraging the advantages of flash technology. And meanwhile, it also keeps the properties and advantages of consistent hashing algorithms.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 01 of 11

Consistent Hashing Algorithm Improvement with Flash Storage

Consistent hashing is a special kind of hashing such that when a hash table is resized and consistent hashing is used , only K/n objects need to be remapped on average, where K is the number of objects, and n is the number of array slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all objects to be remapped.

Consistent hashing algorithm has lots of properties to make it very useful for distributed caching protocols on the Internet :
1. Spread

2. Load

3. Balance

4. Monotonicity

The problem:

Actually, all objects are eventually saved in storage media underneath. But consistent hashing has no sense of the media type in storage subsystem. This invention is to have a better performance of object read by leveraging the advantages of FLASH technology. And meanwhile, it also keeps the properties of consistent hashing algorithms.

Core idea of this article:

1. Setup hashing ring with SSD section and HDD section. Need to make sure that each type of storage has continuous space on hashing ring. 2. Define two different hash functions to let the objects go different paths.

3. Calculate hot object and cold object. Fetch the hot object in FLASH and cold object in HDD.

4. Relocate object in background based on the temperature of that object.

5. Leverage the current properties of consistent hashing algorithms.

The advantage of using this method is to have a better performance of object read by use of FLASH technology.

Consistent hashing ring

Assume that there are lots of array slots (or virtual nodes) and objects. And all of them are organized into a hashing ring in order to have a better view here. Each object is mapped to a point of the circle. The system also maps each available machine to many distributed virtual node on the edge of the same circle.

To find where an object should be placed, the system finds the location of that object's key on the edge of the circle; then walks around the circle until falling into the first virtual node it encounters. The result is that each virtual node contains all the resources located between it and the previous one.

1



Page 02 of 11

2



Page 0...