Airphant:�Cloud-oriented Document Indexing

Supawit Chockchowwat, Chaitanya Sood, and Yongjoo Park

University of Illinois at Urbana-Champaign

April 25, 2022

Data systems are moving to cloud

Traditionally, owners maintain their own servers on premise.

Data systems are moving to cloud (e.g. AWS, Azure, GCP)

Traditional

Cloud native

Traditional on cloud

PostgreSQL

[1,2,3,4,5,6,7,8]

Elastic computing reduces cost

Elasticity: ability to scale up (or down) with the workload

Lower cost by matching resource demand & supply

e.g. stream systems [10], Starling [11], LogStore [12]

[9]

There are many ways to achieve elasticity

Function as a service: execute short-lived code on demand

Partition / Sharding: add/remove nodes with a data migration

Vertical Scaling: bigger/smaller nodes depending on the past usage

Disaggregate

For example, disaggregation works in data analytics

AWS EC2

(computing node)

[13,14,15,16]

Latency is relatively tolerable in analytical DBs compared to document stores

Disaggregation is challenging for document stores

Traditional indexes are slow under disaggregation.

Basic operations are latency sensitive.

If they are slow, upper operations become much slower.

Large volume of data and random queries require auxiliary index structures.

Can we design an index for document stores under disaggregation?

We focus on document store and exact matching

Document store: maintain collections of documents for retrieval

Set retrieval: given a query, retrieve relevant documents

Exact matching: given a word, retrieve documents containing the word

• Naturally generalize to boolean queries
• Accelerate regex retrievals by n-gram [18,19]

How can we perform exact matching under disaggregation?

Common approach uses inverted index

Inverted index: quickly maps a word to its list of document IDs (postings list)

are: Doc_1�fox: Doc₂ Doc_3�quick: Doc₂ Doc₃ Doc_4�the: Doc₂ Doc₃ Doc₄ Doc₅

…

…

Common approach uses inverted index

Inverted index: quickly maps a word to its list of document IDs (postings list)

d₁: w_1�d₂: w₂w₃w_4�d₃: w₂w₃w_4�d₄: w₃w_4�d₅: w₄

w₁: d_1�w₂: d₂d_3�w₃: d₂d₃d_4�w₄: d₂d₃d₄d₅

Index traversal

Index 1

…

Index L

Doc IDs

Documents

Postings list retrieval

Common approach requires many round trips

Inverted index: quickly maps a word to its list of document IDs (postings list)

w₁: d_1�w₂: d₂d_3�w₃: d₂d₃d_4�w₄: d₂d₃d₄d₅

Require multiple round trips

Typically cached

Alternative: extremely shallow structures

One-layer index where each entry points to the postings list location.

w₁: d₁

w₂: d₂d₃

w₃: d₂d₃d₄

w₄: d₂d₃d₄d₅

One-layer Index

w₁

w₂

w₃

w₄

One-layer Index

Doc IDs

Documents

Consumes more memory as number of words grows…

Airphant properties

Minimize round trip�to retrieve list of document IDs

Bounded memory consumption�configurable, irrespective of data size

How Airphant breaks the limit

Airphant relaxes lookup steps

Small One-layer Index

Candidate Doc IDs

Candidate Documents

Documents

• Configurable size
• Remove round trips
• Faster

• Increase data volume
• Slightly slower

• Fast local filtering

Faster overall

Index 1

…

Index L

Doc IDs

Documents

Airphant

Grouping reduces number of ”words”

d₂d₃d₄

d₂₀₂d₃₀₃d₄₀₄

d₁₀₁d₂₀₂

d₂₀₂d₆₀₆d₇₀₇d₈₀₈

d₂d₃d₄ d₁₀₁d₂₀₂

d₂₀₂d₃₀₃d₄₀₄d₆₀₆d₇₀₇d₈₀₈

w₁

w₂

w₃

w₄

v₁

v₂

4 words

2 words�(superposts)

But introduces false positives

d₂d₃d₄

d₂₀₂d₃₀₃d₄₀₄

d₁₀₁d₂₀₂

d₂₀₂d₆₀₆d₇₀₇d₈₀₈

d₂d₃d₄ d₁₀₁d₂₀₂

d₂₀₂d₃₀₃d₄₀₄d₆₀₆d₇₀₇d₈₀₈

w₁

w₂

w₃

w₄

d₂d₃d₄

v₁

v₂

False-positive Doc IDs

More grouping & intersection reduce FPs

d₂d₃d₄

d₂₀₂d₃₀₃d₄₀₄

d₁₀₁d₂₀₂

d₂₀₂d₆₀₆d₇₀₇d₈₀₈

d₂d₃d₄ d₁₀₁d₂₀₂

w₁

w₂

w₃

w₄

d₂d₃d₄

v_1,1

d₂d₃d₄

d₂₀₂d₆₀₆d₇₀₇d₈₀₈

d₂d₃d₄

d₂₀₂d₃₀₃d₄₀₄

d₂d₃d₄

d₂₀₂

Intersect

v_2,1

v_3,1

Grouping by multi-layer hash table (MHT)

d₂d₃d₄

d₂d₃d₄ d₁₀₁d₂₀₂

w₁

d₂d₃d₄

v_1,h1(w1)

d₂d₃d₄

d₂₀₂d₆₀₆d₇₀₇d₈₀₈

d₂d₃d₄

d₂₀₂d₃₀₃d₄₀₄

d₂d₃d₄

d₂₀₂

Intersect

v_2,h2(w1)

v_3,h3(w1)

MHT with 3 hash functions

We call the data structure, IoU Sketch

IoU Sketch: a statistical inverted index consisting of two parts

1. Multi-layer hash table (MHT): lightweight lookup structure
2. Superposts: lists of candidate document IDs

Memory bounded by number of superposts (B) to store pointers

MHT (in memory)

Superposts (on cloud)

.

.

.

d₂d₃d₄

d₂₀₂

Candidate Doc IDs

We call the data structure, IoU Sketch

IoU Sketch: a statistical inverted index consisting of two parts

1. Multi-layer hash table (MHT): lightweight lookup structure
2. Superposts: lists of candidate document IDs

How to select number of layers (L)?

MHT (in memory)

Superposts (on cloud)

.

.

.

d₂d₃d₄

d₂₀₂

Candidate Doc IDs

Number of layers controls the accuracy

Given size( ) = memory budget

…

.

.

.

Small L

• Insufficient intersection
• Many false positives

Large L

• Few bins in each layer
• Insufficient shuffling
• Many false positives

L = 1

L = 2

L = 3

L = B

IoU Sketch problem formulation

Given size( ) = memory budget

…

d₁: w_1�d₂: w₂w₃w_4�d₃: w₂w₃w_4�d₄: w₃w_4�d₅: w₄

Corpus Distribution

Query Distribution

Error budget per query

Expected error ≤ error budget

L^*

.

.

.

IoU Sketch problem formulation

MHT size = O(B), for B number of bins

e.g. B = 10⁵ in experiments

Target number of false positives per query F₀

p_w probability that word w appears in query

W_i words in i-th document, W vocabulary

q_i false positive rate on irrelevant document

e.g. F₀ = 1 in experiments

IoU Sketch core properties

MHT size = O(B), for B number of bins

Log mean FPs

number of layers L

e.g. B = 10⁵ in experiments

The number of layers L affects the expected false positive and superpost sizes

Target number of false positives F₀

e.g. F₀ = 1 in experiments

IoU Sketch optimization

1. Check whether (B, F₀) is potentially feasible with the lower bound
2. Binary search in the fast region
3. Otherwise, iteratively search in the slow region

Log mean FPs

number of layers L

In summary, Airphant has two workflows

Query

MHT

Candidate Doc IDs

Candidate Documents

Documents

Intersect superposts

Filter false positives

Build

Optimize L

(B, F₀)

Corpus

Keyword

Build IoU Sketch

MHT

Superposts

Experiments

Experiments

Setup: GCP e2-small (2 vCPUs, 2 GB memory) + Cloud Storage via gcsfuse [17]

Datasets: 3 synthetic + 1 small text + 3 large loghub datasets

Baselines: Lucene [21], Elasticsearch [20], SQLite [3], HashTable (L=1)

Speedup up to 9x over existing solutions

More speedup over cross-region storage

Windows dataset

1.9x

4.0x

9.4x

1.5x

1.4x

2.0x

1.9x

1.9x

1.7x

Less wait on network communication

Wait time: time intervals with low data transfer (less than 10 KB/s)

Download time: time intervals with high data transfer (more than 10 KB/s)

Cost Comparison

Elasticsearch:

e2-medium and local disk, ideal sharding and load balancing for peak workload

​

Cost = 100 units

Suppose total data size is 4 TB and trough workload is 20 times smaller

Airphant:

Cheaper

Conclusion

We designed an inverted index for the cloud.

1. Minimizes round trips (one for document IDs, one for documents)
2. Retrieves superposts and documents in parallel to maximize bandwidth.
3. Automatically tunes IoU Sketch with respect to memory constraint.

Cloud = disaggregated compute and storage

Thank you

References

[1] PostgreSQL. PostgreSQL: The world’s most advanced open source relational database. https://www.postgresql.org. [Online; accessed February-19-2022].

[2] MySQL. MySQL. https://www.mysql.com. [Online; accessed February-19-2022].

[3] SQLite. SQLite. https://www.sqlite.org. [Online; accessed April-24-2021].

[4] Google Cloud. Cloud SQL for postgresql, mysql, sql server. https://cloud.google.com/sql. [Online; accessed February-19-2022].

[5] Elastic. Elastic Cloud hosted elasticsearch, hosted search. https://www.elastic.co/cloud. [Online; accessed February-19-2022].

[6] Amazon Web Services. Amazon Redshift: Cloud data warehouse. https://aws.amazon.com/redshift. [Online; accessed April-14-2021].

[7] Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, Allison W. Lee, Ashish Motivala, Abdul Q. Munir, Steven Pelley, Peter Povinec, Greg Rahn, Spyridon Triantafyllis, and Philipp Unter- brunner. The snowflake elastic data warehouse. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, page 215–226, New York, NY, USA, 2016. Association for Computing Machinery.

[8] Google Cloud. BigQuery: Cloud data warehouse. https://cloud.google.com/bigquery. [Online; accessed April-14-2021].

[9] Nikolas Roman Herbst, Samuel Kounev, and Ralf Reussner. Elasticity in cloud computing: What it is, and what it is not. In 10th International Conference on Autonomic Computing (ICAC 13), pages 23–27, San Jose, CA, June 2013. USENIX Association.

[10] Henriette Ro ̈ger and Ruben Mayer. A comprehensive survey on parallelization and elasticity in stream processing. ACM Comput. Surv., 52(2), apr 2019.

References

[11] Matthew Perron, Raul Castro Fernandez, David DeWitt, and Samuel Madden. Starling: A scalable query engine on cloud functions. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD ’20, page 131–141, New York, NY, USA, 2020. Association for Computing Machinery.

[12] Wei Cao, Xiaojie Feng, Boyuan Liang, Tianyu Zhang, Yusong Gao, Yunyang Zhang, and Feifei Li. LogStore: A Cloud-Native and Multi-Tenant Log Database, page 2464–2476. Association for Computing Machinery, New York, NY, USA, 2021.

[13] Amazon Web Services. Amazon EC2. https://aws.amazon.com/pm/ec2. [Online; accessed February- 19-2022].

[14] PrestoDB. Distributed sql query engine for big data. https://prestodb.io/. [Online; accessed April-14-2021].

[15] PrestoDB. Hive connector – presto 0.270 documentation. https://prestodb.io/docs/current/ connector/hive.html. [Online; accessed February-19-2022].

[16] Amazon Web Services. Cloud object storage. https://aws.amazon.com/s3/. [Online; accessed April- 14-2021].

[17] Google Cloud. Cloud storage. https://cloud.google.com/storage. [Online; accessed April-14-2021].

[18] Tao Qiu, Xiaochun Yang, Bin Wang, and Wei Wang. Efficient regular expression matching based on positional inverted index. IEEE Transactions on Knowledge and Data Engineering, pages 1–1, 2020.

[19] Junghoo Cho and S. Rajagopalan. A fast regular expression indexing engine. In Proceedings 18^th International Conference on Data Engineering, pages 419–430, 2002.

[20] Elastic. Free and open search: The creators of elasticsearch, elk & kibana. https://www.elastic.co/. [Online; accessed April-14-2021].

[21] Apache Lucene. Apache lucene. https://lucene.apache.org. [Online; accessed April-24-2021].