Browse Prior Art Database

OPTIMIZING ACCESS ON SCALED DATABASES

IP.com Disclosure Number: IPCOM000248861D
Publication Date: 2017-Jan-18
Document File: 12 page(s) / 2M

Publishing Venue

The IP.com Prior Art Database

Related People

Salvatore Valenza: AUTHOR [+5]

Abstract

Provided herein are techniques that allow for the optimization of weak Adelson-Velskii and Landis (WAVL)-based lookup time by implementing a new database entry management system based on a presence detection Bloom filter, a hash tables manager, WAVL trees, and actual central processing unit (CPU) parameters evaluated at run time.

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

Copyright 2017 Cisco Systems, Inc. 1

OPTIMIZING ACCESS ON SCALED DATABASES

AUTHORS: Salvatore Valenza Domenico Ficara

Davide Cuda Roberto Muccifora

Leo Caldarola

CISCO SYSTEMS, INC.

ABSTRACT

Provided herein are techniques that allow for the optimization of weak Adelson-

Velskii and Landis (WAVL)-based lookup time by implementing a new database entry

management system based on a presence detection Bloom filter, a hash tables manager,

WAVL trees, and actual central processing unit (CPU) parameters evaluated at run time.

DETAILED DESCRIPTION

Databases are ubiquitous in networking products. In particular, these databases are

required to manage a large number of entries due to an increasing number of Internet of

Things (IoT) devices in the access layer. Usually these databases are implemented in the

form of well-balanced trees (e.g., weak AVL (WAVL) trees) and provide a lookup time of

O(log(n)). However, as products manage larger and larger amounts of data, the

performance of the entire system suffers.

It is well known that WAVL trees can be built such that the same entry can be

shared among multiple trees (threads). This can be obtained with an entry structure as

illustrated in Figure 1 below.

Copyright 2017 Cisco Systems, Inc. 2

Figure 1

An entry is made by two main sections:

1. The data section that contains the database key, which is used for the search,

and the database data containing the data related to the key.

2. The WAVL section that contains an array of K left/right pointers. Each

left/right couple can identify a WAVL tree (thread). This section is normally

much smaller than the data section because it only contains K elements, and

K is typically very small.

Thus, each entry can be shared among K WAVL trees.

Copyright 2017 Cisco Systems, Inc. 3

In order to have a fast feedback regarding the presence of an entry inside the

database, a Bloom filter is used. The Bloom filter includes a bitmap and a set of hash

functions.

In the context of IoT or generically for any wireless access network database,

network products search for Media Access Control (MAC) and Internet Protocol (IP)

addresses. As such, the Bloom filter hash functions may be associated with simple bit

masks of those addresses. These operations are very fast for any processor.

In particular, an address has L bits. The hash functions may be selected so that they

filter a set of b bits with b = L/K, where K is the number of hash functions (note that L

needs to be divisible by K).

In this example, the hash functions are defined as follows:

hi(key) = MASK(b) & (key >> (i-1)*b)

where MASK(b) is a bitmask with the b less significant bits set to 1 and with all the others

set to 0.

If elements are present, the related entry should be searched for to obtain the data

related to them.

Although hash tables are a good technique for quickly accessing data, if the number

of entries is large with respect to the hashing memory available, collisions may occur. In

particular, more elements present...