DynamoDB KVStore

[yonderblue]

This is a feature request and a question. Is there any reason it would be a bad idea to use Amazon's DynamoDB as a KVStore for bleve? Great library btw :D

[mschoch]

I don't know enough about DynamoDB to say. There are 2 properties that make many distributed databases not suitable:

1. Writes require a transaction. A single bleve operation mutates many rows in the underlying store, they have to either all succeed or not happen at all.
2. Reads require isolation. Searches create multiple iterators that independently read the database, but they must all see the same thing, and not see rows from concurrent write operations.

If DynamoDB can meet these needs, it may be suitable as a k/v store for bleve.

[lambdaupb]

You also need a causality preserving consistency model, most likely linearizability.

This is because records reference other records (e.g. token -> docid), and a reader should not observe a reference, without the referenced record also being visible to it.

Only few distributed databases provide this level of consistency, for example HBase and the new CockroachDB. While Cassandra, DynamoDB and many others do not.

[a-h]

I decided to see if any changes in DynamoDB, such as DynamoDB Transactions and Streams have had any impact on the ability to implement this. I used Bleve a couple of years ago in a project, but this is my first look at the code.

I've had it in mind to create a DynamoDB backed search for a while now, but I thought it would be better to start with Bleve if possible. I built a TF-IDF text indexing system a few years ago, so I'm familiar with that side of it, but I haven't looked into Bleve's database interactions in great depth.

Anyway, I thought I'd just have a go and see what it looks like, with a view to opening up a discussion about the practicality. You can see a comparison of the two forks here:

https://github.com/blevesearch/bleve/compare/master...a-h:master

Database design

I set up the DynamoDB table to have a partition key called "pk" and a sort key called "sk". In DynamoDB, you can have up to 10GB of data under a single partition key which I thought would be enough for a lot of purposes, but I'm sure there's a smarter way to distribute the data across multiple partitions. Based on what I've done so far, I think that a DynamoDB implementation would be better suited to operating at a higher level than a KV store, i.e. to store records rather than KV stores.

I'd be happy to get on a video chat with someone who knows a lot more about Bleve to design that out, because that would be a much better design.

Single partition in DynamoDB

It's not best practice to stick everything under a single partition in DynamoDB, because the read/write capacity is per partition, however, it's a simple way to get DynamoDB to be able to do range queries. DynamoDB lets you select a partition key to work under, then execute a query operation on data within it. So, I was able to create a range iterator with a simple #pk = :pk AND #sk BETWEEN :start and :end query, and table to create a prefix iterator with a #pk = :pk AND begins_with(#sk, :prefix) query.

A better design would potentially be to use ranges as partition keys, and then subfilter under there. However, I don't think the current K/V interface design allows for that.

DynamoDB Attributes

Although the unit tests use string keys, and I read the documentation about what the keys contain, I wasn't sure about the encoding of the keys, so I stuck with byte arrays for keys and values. Again, I'm sure that using more insight about the contents of the records being stored would allow for a better design of the database structure, and would allow more of DynamoDB's functionality to be used.

Merge operator

From reading the code, I could only find one implementation of the MergeOperator - it just adds 2 numbers together. It looks like the MergeOperator is a capability of Bolt to execute arbitrary functions on the data, that the other KV implementations were able to work around by leveraging their transaction capabilities to use a Go implementation on the data. DynamoDB doesn't have those capabilities, but it does have a number of operations it can carry out such as adding numbers, so I implement the Merge as a DynamoDB Update Add expression ADD #v :vv, this does an upsert on the record.

Reader

DynamoDB also has a MultiGet capability (BatchGetItem) which could be used instead of the relatively wasteful store.MultiGet operation I've left in place for now.

Reader isolation

Although DynamoDB doesn't have a start transaction / end transaction capability, it does have the capability to execute up to 25 operations in a single TransactWriteItems API call. I used this to implement batch functionality, but I have no idea if 25 operations in a transaction is enough for Bleve, probably not.

The fact that DynamoDB is so different to the other stores also affects the isolation behaviour - it's not possible to have readers that only see the data at a point in time. I was thinking about whether it would be a good idea to load key data, or the data of prefix / range iterators into RAM when they're requested (which would give the same effect, but may be costly), or whether it's possible to break write transactions into multiple smaller transactions that would make it not required to have isolation. It could also be possible to use a versioning scheme to provide read/write independence.

Summary

After a few hours of playing around, I was able to get all of the standard unit tests passing, except for the isolation tests. The tests use DynamoDB local and create (and dispose of) a local DynamoDB table for each test execution. So, the tests depend on having "DynamoDB local" running.

Based on what I've seen, to implement a DynamoDB store well would probably require a bit of a refactor of interfaces to enable DynamoDB.

Next steps

If there's wider interest in a DynamoDB implementation, I'd be happy to jump on a call to discuss it, or design it in more detail with someone that has more knowledge of the Bleve internals, e.g. @mschoch.

[mschoch]

We are deprecating the upsidedown index format, and all support for pluggable key/value stores.