Paper Accepted by the Distinguished International Journal ACM Transactions on Embedded Computing Systems

(First author: Min Dong-hyun; corresponding author: Professor Kim Young-jae)

▲ (Top row, from left) Min Dong-hyun (doctoral student), Kim Ki-hyun (combined master's–doctoral student)

(Bottom row, from left) Lee Seung-jin (master's student), Professor Kim Young-jae, Department of Computer Science & Engineering

A paper titled 'A Multi-Tenant Key-Value SSD with Secondary Index for Search Query Processing and Analysis', written by graduate students Min Dong-hyun (doctoral), Kim Ki-hyun (combined master's–doctoral) and Lee Seung-jin (master's) of the Department of Computer Science & Engineering under the supervision of Professor Kim Young-jae (corresponding author), has been accepted for publication in ACM Transactions on Embedded Computing Systems (ACM TECS).

The paper proposes a log-structured merge-tree based storage engine that not only supports multi-tenancy on existing key-value storage devices (KVSSD) but can also process user search queries at high speed. The research demonstrates that when multiple users execute a variety of search queries, execution depends on a single primary-key-based index implemented inside the storage engine, creating a performance bottleneck. To resolve this, Cerberus supports separate index structures per user, guaranteeing performance isolation. To speed up search query processing it also supports secondary-key-based index structures, alleviating the search bottleneck of the primary-key index. In particular, instead of the traditional way of implementing secondary indexes, the research constructs secondary indexes that allow direct access to the physical location where the key-value is stored, dramatically reducing primary-key index lookup time.

To measure search query processing speed in particular, a variety of search query scenarios were tested on real scientific and social data; compared with a KVSSD configured with only a primary-key index, the proposed Cerberus achieved up to 9.31 times faster performance.

Figure 1 depicts the conventional secondary-key index structure. Processing a search query through a conventional secondary-key index requires a double index lookup: first finding the primary key on the basis of the user's secondary key, and then finding the actual data through the primary-key index.

Figure 2, by contrast, depicts the proposed secondary-key index structure. Because the proposed secondary-key index maintains information about the actual storage location of the data within the index itself, the actual data can be found using the secondary key alone. Primary-key index lookup is therefore excluded from search query processing. On the basis of this core technique, Cerberus supports a variety of search query types at high speed.

ACM Transactions on Embedded Computing Systems (ACM TECS) is a globally prestigious international journal in embedded computing systems, covering both hardware and software fields including embedded systems, computing and algorithms.

----

References:

Journal: https://dl.acm.org/journal/tecs

Paper: https://discos.sogang.ac.kr/file/2023/intl_jour/ACM_TECS_2023_D_Min.pdf