citusdata / citusdata/citus

CompareShardPlacements doesn't actually work - task assignment policies are broken

Open
#759 6 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
12.8k
Forks
794
Avg merge
2d 14h
Merged PRs (30d)
31

Description

I've notice that the code for CompareShardPlacements() isn't correct. It currently is:

```
const ShardPlacement *leftPlacement = *((const ShardPlacement **) leftElement);
const ShardPlacement *rightPlacement = *((const ShardPlacement **) rightElement);

Oid leftTupleOid = leftPlacement->tupleOid;
Oid rightTupleOid = rightPlacement->tupleOid;

/* tuples that are inserted earlier appear first */
int tupleOidDiff = leftTupleOid - rightTupleOid;
return tupleOidDiff;
```

but that's wrong, because the subtraction of two unsigned numbers will wrap around. I.e. `leftTupleOid - rightTupleOid` will never be negative (it can't, it's an unsigned integer!) here.

The only reason this sometimes gives halfway reasonable results is that we _afterwards_ _again_ cast the result to (signed) int. While that's not actually well defined behaviour:

> 6.3.1.3 Signed and unsigned integers
> 3) Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

On most 2's complement machines / compilers that'll kind of work:

```
5118 int tupleOidDiff = leftTupleOid - rightTupleOid;
(gdb) p leftTupleOid
$1 = 16580
(gdb) p rightTupleOid
$2 = 16581
(gdb) p leftTupleOid - rightTupleOid
$3 = 4294967295
(gdb) fin
Run till exit from #0 CompareShardPlacements (leftElement=0x289e958, rightElement=0x289e960)
at /home/andres/src/citusdb/src/backend/distributed/planner/multi_physical_planner.c:5118
Value returned is $4 = -1
```

(note the -1 returned)

This means that our comparator isn't actually guaranteed to be transitive afaics, and it means we're sometimes violating qsort's requirements, which are:

```
The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less
than, equal to, or greater than the second. If two members compare as equal, their order in the sorted array is undefined.
```

It's also very complicated to understand when / why this sometimes work. The only actually correct / sensible way to do this is

```
if (leftPlacementId < rightPlacementId)
{
return -1;
}
else if (leftPlacementId > rightPlacementId)
{
return 1;
}
else
{
return 0;
}
``
```

Contributor guide

Open the contributing guide

Research direction

Start in src/backend/distributed/planner/multi_physical_planner.c at CompareShardPlacements(), using the issue's qsort comparator discussion as context. Inspect the ShardPlacement fields used for ordering and verify the comparator's results across adjacent and wrapped Oid values. Done means task assignment policies receive a valid, transitive ordering without relying on implementation-defined signed conversion.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, postgresql
Domain
databases
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.