Build Cloud-Native apps with Apache Cassandra

GOT QUESTIONS from the Workshop? You're in the right place! Post a question here and we'll get you answers.

Click here for Week 7 Materials and Homework.

Registrations still open!


question

Shalini Ramachandra avatar image
Shalini Ramachandra asked ·

Why does a list collection incur read-before-write penalty but a set collection doesn't?

The "Cassandra Developer Workshop #5 - Advanced Data Type" has this note:

Sets and maps do not incur the read-before-write penalty, but some list operations do. Therefore, when possible, prefer sets to lists
  • Why do Lists incur read-before-write penalty?
  • And how do Sets not incur read-before-write penalty when we use UPDATE statements with + and - to update an existing set?
collections
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.

Erick Ramirez avatar image
Erick Ramirez answered ·

Collections

The difference between the two collection types lies in the fact that the elements in a list collection are stored in a particular order and thus allows for duplicate values. In contrast, a set collection consists of unordered unique values which only get sorted in natural order when queried.

Sets

To illustrate, let me use an example table that contains a set of friends and a set of numbers:

CREATE TABLE myset (
    name text PRIMARY KEY,
    friends set<text>,
    numbers set<int>
)

Inserting unordered groups of friends and numbers:

cqlsh> INSERT INTO myset (name, friends, numbers) \
  VALUES ( 'erick', \
    { 'tom', 'dick', 'harry', 'sally' }, \
    { 3, 1, 2, 4 } \
  );

When queried, we see that the friends' names are returned in alphabetical order and the numbers are returned in order:

cqlsh> SELECT * FROM myset ;

 name  | friends                           | numbers
-------+-----------------------------------+--------------
 erick | {'dick', 'harry', 'sally', 'tom'} | {1, 2, 3, 4}

Lists

Here's a similar table but this time has a list of friends and a list of numbers:

CREATE TABLE mylist (
    name text PRIMARY KEY,
    friends list<text>,
    numbers list<int>
)

Inserting a group of friends and numbers:

cqlsh> INSERT INTO mylist (name, friends, numbers) \
  VALUES ( 'erick', \
    [ 'tom', 'dick', 'harry', 'sally' ], \
    [ 3, 1, 2, 4 ] \
  );

When queried, we see that the order is preserved:

cqlsh> SELECT * FROM mylist ;

 name  | friends                           | numbers
-------+-----------------------------------+--------------
 erick | ['tom', 'dick', 'harry', 'sally'] | [3, 1, 2, 4]

This is an important point to understand because with a set, it doesn't matter whether we add or delete elements from the collection because the order does not matter.

With a list, prepending (adding an element to the start) or appending (adding an element to the end) does NOT involve a read-before-write because Cassandra does not need to know which position to add the new element -- it either goes at the start or the end of the list. But when inserting or deleting an element in a specific position, Cassandra needs to read the elements because it needs to rewrite it in the proper order.

Consider this diagram which shows the elements in order where Tom is in position 0, Dick is in position 1 and so on:

If we insert Alice in position 1, Cassandra needs to "walk" the list to get to position 1 and update its value:

cqlsh> UPDATE mylist SET friends[1] = 'alice' WHERE name = 'erick';

It can only do that by reading all the elements in the list. Similarly, to delete the element at position 2, C* needs to:

  1. iterate over the first 2 elements
  2. delete the value in position 2
  3. shift all the elements to the left
cqlsh> DELETE friends[2] FROM mylist WHERE name = 'erick';

To reiterate:

  • Cassandra does a read-before-write when updating or deleting the value of an element at a specific position because the order of elements matters in a list collection.
  • The elements are not in any particular order in a set collection so it does not incur this penalty.

Cheers!


4 comments Share
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.

Thanks so much for such a detailed answer @Erick Ramirez. Really appreciate it.

I see that the read-before-write is only applicable for add/delete at specific positions. But why can't this be handled in the read path instead of the write path? Aren't the multiple versions of data reconciled / coalesced across MemTables and SSTables during a read path - can't the list not be reconciled then, in the specific order?

[Follow up question posted as #6303]

0 Likes 0 · ·
But why can't this be handled in the read path instead of the write path?

Because the write path doesn't read. :)

Without reading the data beforehand, Cassandra doesn't know what to write.

Aren't the multiple versions of data reconciled / coalesced across MemTables and SSTables during a read path - can't the list not be reconciled then, in the specific order?

It feels like we're going around in circles and we're back to where we started. :)

You said it yourself -- it needs to read the data before it can write it in a specific order. Cheers!

0 Likes 0 · ·

I guess the "ordering" is the key here. Else it wouldn't have mattered to read-before-write. Thanks @Erick Ramirez. I think I am starting to get the hang of it

0 Likes 0 · ·
Show more comments
smadhavan avatar image
smadhavan answered ·

@Shalini Ramachandra, as you know,

The various collection choices and their uses are as listed below.

  • LIST
    • Element order is maintained (may not be the natural order of the elements)

    • It supports storing same value multiple times.

    • List values are returned according to their index value in the list.

  • SET
    • A set stores a group of elements that are returned in sorted order when queried.

    • It does not allow storing duplicate elements.

    • Values are returned in alphabetical order when queried, assuming the values are text.

  • MAP
    • It stores key-value pairs.

    • For each key, only one value may exist.

    • A map is a (sorted) set of key-value pairs, where keys are unique and the map is sorted by its keys.

LIST data type is implemented in such a way that it directly only works on the particular element when +/- operators. If you try to add an element at a particular position then, C* will have to read the entire collection to place the newly added element to assist the structure. For additional information, please refer to this documentation. Hope that helps!

Share
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.