why do my cache entries all double up with a #cache_redirect item? I'm caching a piece of render array by adding cache keys to it. It's getting cached correctly, but I see two rows for every instance of it.

One looks normal -- contains the render array, with a cid that looks like:

CACHE_KEY:[languages:language_interface]=en:[languages:language_url]=en:[theme]=MYTHEME:[user.permissions]=HASH


The other one had data that starts like:

a:2:{s:15:"#cache_redirect";b:1;s:6:"#cache";a:5:{s:4:"keys";a:1 ...


and its CID is:

CACHE_KEY:[languages:language_interface]=en:[theme]=MYTHEME:[user.permissions]=HASH


It looks like this is something to do with language negotiation, but why, and is this normal? The page I am loading when I am testing this is using the language prefix, so I'm not getting redirected.
It's still a bit unclear what you are asking, but to be more precise about my comment. The bubbled up cache contexts depend initially on the content of the render array, but this content can be dependend on other things. For example a rendered link can depend on a configured language negiotiator which provides a path processors rendering links differently dependend on the language and so bubbles up the cache context you have identified.