List performance

1

I wanted to create a list with around 5K+ of append and remove(0) operation per minute. I want O(1) time complexity for both operations. Aerospike does have List data structure but it’s like ArrayList rather than LinkedList or circular array. So at a time either we will have append in O(1) but remove(0) will be O(N) or vice versa. Kindly, confirm if my understanding is correct. Any alternative approach with aerospike for this use case?

2

The List data type documentation includes the computational complexity of operations on the unordered, ordered, and K-ordered types of lists.

You’ll have to consider the cost and choose the appropriate list type - nothing’s free in life, or computer science :smile:

3

Thanks for the info @rbotzer. I was actually looking for an alternative to redis rpop & lpush which are both O(1). We right now are using redis and was looking to migrate to AS.

BTW, in our case, we are maintaining a list of max 10K size. If we always remove from the end remove_by_index(-1), wouldn’t it be in O(1) as intuitively, it seems no index rearrangement should happen in the existing list?

Also, I can see in AS doc ‘K-Ordered with Offset Index’ provides remove_by_index(i) in O(1) and add as logN. I can’t find any example to implement “'K-Ordered with Offset Index” with Java client. Any example of it would be really helpful.

4

For lists, remove_index(0) and append are both O(1) in terms of traversal.

There are also other considerations due to our database architecture. As mentioned in the docs, all ops have a +C time cost which is “for copy on write for allowing rollback on failure.” This does scale linearly with the size of the bin, but it is an order of magnitude faster than list traversal(because memcpy is really fast these days) that if your traversal order is not O(1) it would be hard to measure the +C.

Sorry, K-Ordered is a typo, I copied that table format from map and missed the K. It should just say Ordered. ORDERED lists will have an index if your storage model is data-in-memory. If it is disk only, index is not persisted.