Enable increasing the number of containers

[tkaitchuck]

Problem description
Right now we are mapping segments to containers by simple consistent hashing. We should modify this so that we can increase the number of containers.

Problem location
Controller, SegmentStore. Possibly Client.

Suggestions for an improvement
We can design a system where we allow both increasing and decreasing the number of containers. However, handling the decreasing part will be somewhat more complicated than increasing, so we can tackle that later.

Controller:

• We need to allow changing the number of containers over time and keep track of that
  • Currently, this is hardcoded in 2 config files (one in the Segment Store and one in Controller)
  • The Controller can keep a new metadata table ContainerCounts; each such table will have an Epoch which is incremented with every change, and a Count which defines how many containers are in this epoch. For example: {Epoch=1, Count=4}, {Epoch=2, Count=8}, etc.
• Each segment will need to be tagged with the ContainerCountEpoch upon creation. This, along with our hash function, will uniquely assign a Container Id for that segment.
• When asked by the client to locate a segment, the Controller will look up this Segment's ContainerCountEpoch, and use that + the hashing function to return the container id + host where it should be processed

Segment Store

• The SegmentName-to-ContainerId check that is done for every operation should be discarded. Otherwise the Segment Store will also need to be aware of the new metadata in the Controller.

Client

• No changes anticipated

How will this work
When we get a Container Expansion, the Controller will instantiate those new containers, then create a new entry in the ContainerCount metadata (the exact number of steps here may be higher due to other constraints). Every new segment that is created post this will use the latest ContainerCount epoch and container count and will be evenly distributed across the cluster.

Existing segments will still be assigned to whatever containers they were assigned and will continue processing there for the remainder of their lifetimes. Eventually they will be sealed off and their successors will be redistributed using the latest ContainerCount that is available, so given enough time we will achieve a full cluster rebalancing (write-wise).

As for reads, those segments will still be mapped to their old containers, so it is possible that we may get some unbalanced reads, however this may not pose such a big problem as reads are mostly Tier 2 and cache intensive so they do not require as many resources.

Additionally we could think of a scheme where older segments will be eventually migrated to the latest epoch. Such a scheme will involve work from the Segment Store (as we will need to move metadata from the previous container to the new one). However we may not even need to do any of this, given that retention will take care of cleaning old segments so they will not pose a problem anymore.

[fpj]

I think the bulk of the changes in this proposal are in the controller. I'm not sure what this "SegmentName-to-ContainerId check" is, but if we are not moving segments across containers, then the check seems fine.

[andreipaduroiu]

@fpj I agree. Most of this is Controller work.

I'm not sure what this "SegmentName-to-ContainerId check"

When we receive a request into the Segment Store, we only have the segment name. But the Segment Store still needs to route that request to the Container that handles the Segment, hence the need for:

1. An additional config on the Segment Store side for number of containers
2. An additional hash on the Segment Store side to route to a container.

We could change this by either sending the Container Id along with the Segment Name via the Client (virtually every Wire Protocol command will need a change) or have the Segment Store gain access to the Controller's epoch metadata so it can do the internal routing.