memberlist keeps resurrecting deleted store-gateways

[nicolai86]

Describe the bug
when performing a scale-up of store-gateway pods followed by a scale-down memberlist entries of deleted store-gateway pods sporadically re-appear after a few hours as unhealthy in the memberlist ring.
The system doesn't recover from the ghost entries and they appear and disappear at random.

In our case we scaled 12 to 80 and back to 12, but this happens with lower scale-up numbers as well.
we verified that each unhealthy entry as reported by the metrics references a no longer existing store-gateway pod.
This is indicated in the logs with messages like

msg=\"auto-forgetting instance from the ring because it is unhealthy for a long time\" instance=store-gateway-15 

To Reproduce
Steps to reproduce the behavior:

1. Start Cortex, using memberlist for store-gateway ring (efd1de4)
2. Scale up store-gateway deployment
3. Scale down store-gateway deployment
4. keep k8s cluster running for a few hours

relevant section of cortex configuration:

memberlist:
  bind_port: 7946

  join_members:
    - distributor-memberlist.cortex.svc.cluster.local:7946
    - compactor-memberlist.cortex.svc.cluster.local:7946
  abort_if_cluster_join_fails: false

  rejoin_interval: 10m

  left_ingesters_timeout: 20m

store_gateway:
  sharding_enabled: true
  sharding_strategy: default
  sharding_ring:
    kvstore:
      store: memberlist
      prefix: store-gateway-v1/
    heartbeat_timeout: 10m 
    zone_awareness_enabled: true

Expected behavior
Inspecting the cortex store-gateway ring status history for the lifetime of the cluster it shouldn't contain unhealthy store-gateways of deleted pods.

Environment:

• Infrastructure: Kubernetes
• Deployment tool: helm, custom chart

Storage Engine

• Blocks
• Chunks

Additional Context
#3603 was a PR to fix it, but it seems it doesn't cover some edge cases.

[tomwilkie]

Thoughts of what could be causing this:

• perhaps an old gossip is sitting in a queue somewhere? we could reject "stale" messages, if they exist
• this would be expected behaviour if a partitioned node rejoins after a few hours - is that happening here?
• we don't think this is due to ring converging too slowly, but just in case worth making sure that the gossip interval is <<< the tombstone timeout.
• is it possible that someone in the right never learnt about the tombstone? shouldn't be the case, as we periodically sync the ring state