The intent of sorting dependencies (done in loadelement.pyx) was that the staging order would be independent of the declaration order of dependencies in .bst files. As part of the investigation into #1988, it has become clear that the comparison function is broken as it does not impose a total ordering. Besides resulting in different sort orders with different Python versions (addressed in #1993), this also means that reordering dependencies in .bst files sometimes results in a change in staging order, which in turn results in a change in cache key.
BuildStream should implement a better sorting algorithm that is independent of the declaration order. As this would change staging order and cache keys of existing projects, this should be opt-in per project.