Bigtable: race condition in resuming ReadRows can lead to unintentional full table scan

[igorbernstein2]

This client seems to have a similar bug as:

googleapis/google-cloud-go@566ccf3
and
googleapis/python-bigtable#554

I believe the resumption code:

google-cloud-php/Bigtable/src/ChunkFormatter.php

Lines 211 to 222 in 6ece840

	if (count($rowSet->getRowRanges()) > 0) {
	$ranges = [];
	foreach ($rowSet->getRowRanges() as $range) {
	if (($range->getEndKeyOpen() && $prevRowKey > $range->getEndKeyOpen())
	|| ($range->getEndKeyClosed() && $prevRowKey >= $range->getEndKeyClosed())) {
	continue;
	} elseif ((!$range->getStartKeyOpen() || $prevRowKey > $range->getStartKeyOpen())
	&& (!$range->getStartKeyClosed() || $prevRowKey >= $range->getStartKeyClosed())) {
	$range->setStartKeyOpen($prevRowKey);
	}
	$ranges[] = $range;
	}

Is vulnerable to a race condition:

1. client sends a read request for range [a,c]
2. server sends back the data chunks row c
3. but before the OK trailers are received, the deadline expires
4. the retry logic will craft a retry request that will exclude ranges that can been consumed, leaving an empty RowSet
5. client will use the empty RowSet for the retry attempt
6. server will interpret the RPC as a full table scan

[bshaffer]

Thanks for reporting this @igorbernstein2!
No RPCs are made in the block you've linked to, so I'm not sure that is where a race condition would take place.

If I understand the solution implemented in python and go correctly, the solution is to validate that the ranges are valid before sending in the request. So in our case, it would be something like this:

if (count($ranges) < 1) {
    throw new RuntimeException('Invalid range');
}
$rowSet->setRowRanges($ranges);

I'm still not sure where the race condition would take place, but we could implement something like that to be safe. WDYT?

(cc @saranshdhingra as this looks to be an issue for your team!)

[bshaffer]

the retry logic will craft a retry request that will exclude ranges that can been consume

Maybe this is what I don't understand. If the values in $rowSet or $prevRowKey become invalid somehow, then I can see how the next chunk request would be invalid. But I don't understand why that would happen, or how to throw an error in the case it happens.

[igorbernstein2]

The entry point is ResumeableStream:

google-cloud-php/Bigtable/src/ChunkFormatter.php

Lines 127 to 144 in 91afd16

	$this->stream = new ResumableStream(
	$readRowsCall,
	function () {
	$prevRowKey = $this->prevRowKey;
	$this->reset();
	if ($prevRowKey) {
	$this->updateOptions($prevRowKey);
	}
	return [$this->tableName, $this->options];
	},
	function ($ex) {
	if ($ex && ResumableStream::isRetryable($ex->getCode())) {
	return true;
	}
	return false;
	},
	$this->pluck('retries', $this->options, false)
	);

for every retry attempt it will call updateOptions

In the case I described above, ResumeableStream will get the DeadlineExceeded code and invoke updateOptions before sending a retry attempt. UpdateOptions will then truncate the rowset and make it empty. Empty row set means a full table scan. So when ResumableStream sends the next attempt it will trigger a full table scan

[yash30201]

@igorbernstein2 So how should the library behave in this event? A straight up failure with an exception message or ignorance of deadline exceed error code and finish the operation? 🧐