appending_hash<row> ignores cells after first null

[pdziepak]

Scylla version (or git commit hash): d773e4b

appending_hash<row> is supposed to update the provided hasher with information form the selected columns. However, the loops that is supposed to do that ends early if a requested column doesn't not exist. As a result, a row hash will not include information about the cells after the first missing one.

        for (auto id : columns) {
            const cell_and_hash* cell_and_hash = cells.find_cell_and_hash(id);
            if (!cell_and_hash) {
                return; // <- should be continue
            }
            auto&& def = s.column_at(kind, id);
            // add current cell to the hasher

[slivne]

@pdziepak I need a bit more context about this - is this a bug in computing digests ? and potentially not identifying a case in which two rows are different and because of the return the hashes do match ?

since when do we have this ?

Example

Schema {PK PRIMARY KEY, A INT ,B INT ,C INT}

Node 1: PK=1,A=1,C=3
Node 2: PK=1,A=1,C=2

how did you find this bug - code inspection / unitests ?

[pdziepak]

d773e4b is the commit that introduced the bug (for the aficionados of archaeology, in the earlier versions of that patch there was a lambda and the return behaved like continue, later, lambda became a loop, but the return stayed being return).

The user-visible problem is exactly like you've shown in your example. If the queried columns are A, B, and C, then node 1 and 2 will produce the same digest since only column A will be taken into consideration.

I've spotted this by inspecting the code trying to find the source of an unrelated bug.

[gleb-cloudius]

We need to fix this asap. This is the root cause for #7116.

[eliransin]

@psarna this is a blocker for Jepsen. Please be advised there is a PR in place with requested changes on it (by pdziepak)

[avikivity]

Perhaps we can use a new hash function enum (with the same hash function) to describe the behavioral change.

[gleb-cloudius]

@avikivity this is a regression. All the problems you are trying to avoid by feature bits or new hash function would have present when the regression was introduced. It did not cause any mayhem so much so that we did not notice it. The same will be true for fixing the regression.

[avikivity]

@gleb-cloudius we don't know that it did not cause damage. Also, we have more users now, so there is more potential for problems.

[gleb-cloudius]

@avikivity we know because otherwise we would have notice the bug. "More users" argument is hard to dispute, but it is not like 2 years ago we had small amount either. Read repair for affected rows will not kill anyone and if repair uses the same hashing function it is likely read repair will happen anyway because data will be different after 2 years of been neglected. If schema digest may be different this is more serious problem, but may it?

[avikivity]

More users = more chances the problem will surface. I don't want to risk ruining someone's day during an upgrade, which is already stressful.

I think it can happen during schema digest. Why wouldn't it?

[gleb-cloudius]

Read repair will not ruin anyone's day. If it will they will have the bad day regardless because data is out of sync after we neglected to repair it for two years.

For the problem to happen a cell should not be present. Is it possible for schema tables? May be it is and we got lucky and nobody hit the problem when upgraded to broken version.

[tgrabiec]

Note that nodetool repair is not prone to this bug, it doesn't use this function.

[gleb-cloudius]

On Tue, Sep 08, 2020 at 05:43:49AM -0700, Tomasz Grabiec wrote: Note that nodetool repair is not prone to this bug, it doesn't use this function.

That's great. It means no data was lost due to it.

…

-- Gleb.

[tgrabiec]

Schema digest is also not prone.

[psarna]

I have a partially working work-in-progress series based on Paweł's commits (https://github.com/psarna/scylla/tree/fix_ignoring_cells_after_null_in_appending_hash) which adds a cluster feature for this, but it's quite tough to decide where to check for this feature bit...

The code in this branch is ugly and doesn't work well with our test suite, but I don't have any clear idea how to approach it, so suggestions are welcome. To sum up - the cluster feature check needs to be placed somewhere, and I don't see a good place for it. In my patch I placed the check inside mutation_partition.cc and used an awful global variable access to check if the cluster supports the new feature (which is terrible, but also common practice). It doesn't work, because in our test suite this global variable is not always initializes, so the code crashes. It would be better to pass a parameter up the callchain, but this will in turn spoil quite a few interfaces, starting with mutation_partition::query_compacted and going up through mutation::query. I don't see any other choice but to add this ugly parameter up the callchain, but I won't manage to do this today anyway, so I'm posting this cry for help in case somebody has a better idea.

/cc @avikivity

[avikivity]

I suggested before to model it as a hash function change: add digest_algorithm::xxHash_with_null_fix. Then specialize on the hasher.

I see there is also a digester class that type-erases the algorithm, so maybe not so easy to specialize.

[avikivity]

@psarna how does this interact with the cached hashes? I think it should not, since the cached hashes are on a cell level. My concern is that hashes generated with one hash function will be used with another hash function.

Are deleted cells and never-written cells treated the same way?

[psarna]

No idea, I'll browse the code and try to verify

[psarna]

From what I see here, deleted and never-written cells are not treated the same way. Hashes are cached for atomic_cell, which boils down to using atomic_cell_view, which have special cases for cells which are deleted (assuming that I'm reading our IMR code correctly, which is a very generous assumption:

template<>
struct appending_hash<atomic_cell_view> {
    template<typename Hasher>
    void operator()(Hasher& h, atomic_cell_view cell, const column_definition& cdef) const {
        feed_hash(h, cell.is_live());
        feed_hash(h, cell.timestamp());
        if (cell.is_live()) {
            if (cdef.is_counter()) {
                counter_cell_view::with_linearized(cell, [&] (counter_cell_view ccv) {
                    ::feed_hash(h, ccv);
                });
                return;
            }
            if (cell.is_live_and_has_ttl()) {
                feed_hash(h, cell.expiry());
                feed_hash(h, cell.ttl());
            }
            feed_hash(h, cell.value());
        } else {
            feed_hash(h, cell.deletion_time());
        }
    }
};

[avikivity]

template<typename Hasher>
void appending_hash<row>::operator()(Hasher& h, const row& cells, const schema& s, column_kind kind, const query::column_id_vector& columns, max_timestamp& max_ts) const {
    for (auto id : columns) {
        const cell_and_hash* cell_and_hash = cells.find_cell_and_hash(id);
        if (!cell_and_hash) {
            feed_hash(h, appending_hash<row>::null_hash_value);
            continue;
        }
        auto&& def = s.column_at(kind, id);
        if (def.is_atomic()) {
            max_ts.update(cell_and_hash->cell.as_atomic_cell(def).timestamp());
            if constexpr (query::using_hash_of_hash_v<Hasher>) {
                if (cell_and_hash->hash) {
                    feed_hash(h, *cell_and_hash->hash);
                } else {
                    query::default_hasher cellh;

Is it correct to use default_hasher here? Shouldn't we use Hasher?

Even more in this variant:

void appending_hash<row>::operator()<legacy_xx_hasher_without_null_digest>(legacy_xx_hasher_without_null_digest& h, const row& cells, const schema& s, column_kind kind, const query::column_id_vector& columns, max_timestamp& max_ts) const {

Although xxhash is compatible with legacy_xx_hasher_without_null_digest below the row level. So it's just a code wart, not a correctnesss problem.

[avikivity]

From what I see here, deleted and never-written cells are not treated the same way.

And that's correct, since we'd want deleted cells with different deletion times to trigger a read repair.

This can cause an unnecessary read repair if a tombstone is hashed in one replica and nothing in another, because the tombstone was expired and garbage collected. But I see nothing we can do about it.

[psarna]

template<typename Hasher>
void appending_hash<row>::operator()(Hasher& h, const row& cells, const schema& s, column_kind kind, const query::column_id_vector& columns, max_timestamp& max_ts) const {
    for (auto id : columns) {
        const cell_and_hash* cell_and_hash = cells.find_cell_and_hash(id);
        if (!cell_and_hash) {
            feed_hash(h, appending_hash<row>::null_hash_value);
            continue;
        }
        auto&& def = s.column_at(kind, id);
        if (def.is_atomic()) {
            max_ts.update(cell_and_hash->cell.as_atomic_cell(def).timestamp());
            if constexpr (query::using_hash_of_hash_v<Hasher>) {
                if (cell_and_hash->hash) {
                    feed_hash(h, *cell_and_hash->hash);
                } else {
                    query::default_hasher cellh;

Is it correct to use default_hasher here? Shouldn't we use Hasher?

Even more in this variant:

void appending_hash<row>::operator()<legacy_xx_hasher_without_null_digest>(legacy_xx_hasher_without_null_digest& h, const row& cells, const schema& s, column_kind kind, const query::column_id_vector& columns, max_timestamp& max_ts) const {

Although xxhash is compatible with legacy_xx_hasher_without_null_digest below the row level. So it's just a code wart, not a correctnesss problem.

Sounds right. I'll send a patch to remove the wart(s).

[avikivity]

@roydahan we need feedback on this fix, especially during upgrades.

[roydahan]

@avikivity I'll need more information about this.
What is your concern in terms of rolling upgrades?
(The current upgrade tests we have in master and 4.2.rc4 (AFAIU has the fix already) pass)

[avikivity]

Suppose you have a row pk ck c1 c2 c3
If there is a NULL in the middle (for example, c1=1, c3=3, but c2 has no value), then the patch changes the way such rows are compared when doing quorum reads (previously, we would treat (1, NULL, 2) the same as (1, NULL, 3).

The risk is that during the upgrade we'd see a spike in read repairs.

So we need a test that runs a QUORUM read workload before, during, and after the upgrade, and checks for read repair. There can be a few read repairs initiated after the upgrade, but there should not be any during the upgrade or a large number afterwards. The test should run on a few million rows, say reading 1000 rows/sec.

It can be manual, no need to repeat it.

[roydahan]

When looking on any read_repair metric we have, I don't see any that occurred - not before, during or after the upgrade.

Example of data in my table:

cassandra@cqlsh> SELECT * FROM  ks.targettable limit 10;

 pk                                   | ck       | c1                                   | c2   | c3  | c4   | c5   | c6
--------------------------------------+----------+--------------------------------------+------+-----+------+------+-----------
 093f8e10-1dde-11b2-da01-7977122bdf87 | 16382367 | 13ad0af0-1dd2-11b2-2a71-a5bc8c82f897 | null | 650 | null | null | 646.18738
 4b0dea10-1df9-11b2-da01-7977122bdf87 |    95964 | 13cfae20-1dd2-11b2-2a71-a5bc8c82f897 | null | 843 | null | null | 945.32086
 4b0dea10-1df9-11b2-da01-7977122bdf87 |  8391994 | 13f2c680-1dd2-11b2-2a71-a5bc8c82f897 | null | 470 | null | null | 768.49689
 4b0dea10-1df9-11b2-da01-7977122bdf87 | 13446650 | 141542a0-1dd2-11b2-2a71-a5bc8c82f897 | null | 936 | null | null | 233.95412
 4b0dea10-1df9-11b2-da01-7977122bdf87 | 18609679 | 14019390-1dd2-11b2-2a71-a5bc8c82f897 | null | 715 | null | null |   7.00867
 b6587d30-1dea-11b2-da01-7977122bdf87 |  3352719 | 13db1fd0-1dd2-11b2-2a71-a5bc8c82f897 | null | 797 | null | null | 697.15063
 b6587d30-1dea-11b2-da01-7977122bdf87 |  6253728 | 13c43c70-1dd2-11b2-2a71-a5bc8c82f897 | null | 732 | null | null | 390.12354
 b6587d30-1dea-11b2-da01-7977122bdf87 |  9661279 | 13b21400-1dd2-11b2-2a71-a5bc8c82f897 | null | 179 | null | null | 814.90497
 b6587d30-1dea-11b2-da01-7977122bdf87 | 10944590 | 13c4d8b0-1dd2-11b2-2a71-a5bc8c82f897 | null | 225 | null | null | 974.78217
 c5cb3980-1dde-11b2-da01-7977122bdf87 | 15431964 | 13ac95c0-1dd2-11b2-2a71-a5bc8c82f897 | null |  89 | null | null |  896.2901

I have around 15K op/ss during the insert part and 15K op/s during the reads.

The test scenarios is:

1. 4 nodes cluster of 4.1.7 (without the above fix).
2. Inserting 60M rows where (Pk, ck, C1, NULL, C3, NULL, NULL, C6).
3. Start reading using both:

   •  cql: select * from targettable where pk = ? and ck = ?
     

   •  cql: select * from targettable where pk = ?
     

4. During reads:
   a. upgrade node1 to master with the above fix.
   b. rollback node1 (just because it's already part of the scenario I have).
   c. Upgrade all nodes one by one node 1 - 4.
5. Continue read for a while.

[kostja]

Please backport to 4.2

[tgrabiec]

@roydahan Did you finish testing this?

[roydahan]

I've done the test Avi suggested, but I can't really verify that I had the case where the replicas differs from each other after the NULL.
In a later test I used CL=ONE and higher load during insert and saw some read_repairs after full cluster upgrade (not a lot).
But again, I can't really tell if it's row missing completely or caused by the issue above.

In any case, it looks like it doesn't break anything.

[slivne]

Backported to 4.2

Lets wait with additional backports till it matures in the field

[avikivity]

Backported to 4.1.