Introduce new cell indexing concept

[IvanHristov98]

Introduce new cell indexing concept

Summary

Currently if enabled the bin pack first fit distribution in auctioneer depends on rep indexes which are mapped to bosh cell indexes. Relying on bosh cell indexes is unstable since they are an internal bosh data structure and not a part of its API.

We have the use-case when the linear distribution of bosh cell indexes is broken. This happens when we add an additional AZ to the diego-cell instance group where during deployment:

1. bosh creates the vms from the new AZ with indexes higher than the total number of cells
2. bosh deletes the same amount of vms from the old AZs leaving unused indexes
3. bosh updates the vms from the new AZ

This way cell indexes could end up being not strictly consecutive. E.g. cells indexes [0, 1, 2, 3, 4, 5] would be transformed to [0, 1, 2, 3, 6, 7]. The new order of cell indexes has a negative impact on:

• how to configure (and predict) the diego.auctioneer.bin_pack_first_fit_weight in a deterministic way to have a smooth curve of cell resource utilisation.
• since the diego-cells from the new AZ are indexed highest (in our example 6 and 7) then they will be the least utilised which decreases stability.

Describe alternatives you've considered

We think that it would be best to keep the current mechanism of reading indexes directly from the bosh spec and introduce a way to override it.

If we imagine that the current distribution of cell indexes is a random variable (as in statistics) then it is expected to be an uniform one and we should keep this behaviour. We can introduce a new property of the rep job where a natural number (<= number of cells) is specified. Let us call it x. The number x can then be used to generate a random number between 0 and x as the index of the cell to be used to override the bosh one. This way:

• the uniform distribution of indexes across cells will be preserved after a migration to more AZs.
• the higher indexes won't be clustered only within one of the AZs.
• indexes are changed every time there is a cell update.

The suggestion would require changes only to the diego-release repo.

We would like to hear your opinion over it as well as other suggestions towards solving this problem. We would also be glad to contribute to this enhancement.

Additional Text Output, Screenshots, or contextual information

We use bin pack first fit distribution to make pushing "big" apps (e.g. requiring more than 32G of memory) possible. Since the highest indexes are only given to diego-cells from the new AZ this means that they would be the least utilised and the only ones able to host "big" apps. Hence it would be hard to place such app instances into other AZs.

[cf-gitbot]

We have created an issue in Pivotal Tracker to manage this. Unfortunately, the Pivotal Tracker project is private so you may be unable to view the contents of the story.

The labels on this github issue will be updated when the story is started.

[jvshahid]

The number x can then be used to generate a random number between 0 and x as the index of the cell to be used to override the bosh one.

One issue I can see with that suggestion is that the operator will have to change x everytime more cells are added or removed. Another option is to map the cell indeces before entering this loop.

[IvanHristov98]

Hi @jvshahid! 👋

One issue I can see with that suggestion is that the operator will have to change x everytime more cells are added or removed.

^^^ That's a good point, although I was thinking that there is no actual need to strictly correlate x with the number of diego-cells. Generally on an installation with >= 50 cells the index score between adjacent cells should be negligible thus setting x to a value like 50 and not changing it later on is reasonable. Following the same pattern an operator could increase the value on steps like 10, 25, 50, ....

Another option is to map the cell indeces before entering this loop.

^^^ To be honest I prefer your idea since there won't be any ops overhead. As far as I understand you suggest that cell indices are added to a sorted map (or just a hash set) which solves the problem of having gaps between indices.

Still this doesn't solve the problem with having one AZ less utilised in expense for others. It is just a suggestion but a possible way to handle it is by shuffling the values of the sorted map using a hash function and adding them to another map. Since hash functions are always deterministic the shuffling would output the same result every time the function is run. Of course I think that this "shuffling" should be easy to turn on/off via a config (this way we won't change the old behaviour).

My only concern with this approach is increasing time complexity by adding an additional loop(s) although order shouldn't change (and the number of cells usually are just hundreds 😄). Also using maps would increase memory usage by a little.

Do you think that this would actually work out well? Thank you in advance.

[aminjam]

👋 @IvanHristov98

This is an interesting issue that you are running into. While we were reviewing the PR for this work, the scenario you are explaining came up as a potential issue, but we never ran into it. This is because distributing app instances over AZ would always take precedence over the Cell Indexes.

Can you share with us that exact steps you took to see the algorithm breaking down?

Here is an example of what we ran:

• Scale to 1 AZ and scale up the diego-cells to 100
• Push an application with 100 instances
• Set bin_pack_first_fit_weight to 1
• Add a new AZ and keep the number of diego-cells at 100
• Restart the app
• Observe the distribution -> We saw about half of those instances were on the second AZ even though the Cell Indexes were not in order

[IvanHristov98]

Greetings @aminjam 👋,

Sorry for not providing exact reproduction steps in the first place. I think the problem with your example is in the way that you configure bin_pack_first_fit_weight and that you're using just one app.

Firstly looking at the scheduling algorithm I can see that there is a localityScore which is equal to LocalityOffset * numberOfInstancesWithMatchingProcessGuid where LocalityOffset is a constant always equal to 1000. On the other hand resourceScore + indexScore can hardly ever compare to the order of localityScore if there is an actual LRP with the same ProcessGuid on the cell. That is why when using just one app it always gets uniformly distributed. On the other hand apps usually have between 1-3 instances.

Also setting bin_pack_first_fit_weight to 1 results in a pretty steep distribution of cell utilisation. We prefer to set it like:

bin_pack_first_fit_weight = bin_pack_first_fit_range / (num_cells - 1) , where the bin_pack_first_fit_range is equal to the desired abs(resourceScore(last_cell) - resourceScore(first_cell)). This way we are expected to have a more sloping bias to the distribution of cell utilisation.

Here is how I reproduced it:

• Scale to 1 AZ and scale up the diego-cells to 20
• Scale to 2 AZs and keep the number of diego-cells the same. The cell indices should distributed like:
  • AZ1 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  • AZ2 -> [20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
• Set bin_pack_first_fit_weight to 0.4 / (20-1) ~ 0.021052
• In a loop push several different small apps (e.g. with memory & disk from 500M to ~2G) with instances ranging from 1-3 for each app (picked on a random basis)
• Observe the distribution

Looking at the CapacityRemainingMemory metric for each diego-cell the results were:

All the cells from AZ1 were utilized to their limits while the cells from AZ2 were almost never touched => definitely not an HA setup. Pushing an app which requires more resources (e.g. 6G of memory) during this state would result in having all of its instances in AZ2.

I hope this helps you to crack it. ⚒️

PS - It's a bit hard to communicate since we are on the other side of the globe. 🌍

[aminjam]

@IvanHristov98 We tried the following the script for pushing the apps

#! /usr/bin/env ruby

require "net/https"
require "uri"
require 'json'

how_much_memory= ["500M","1G","2G"]
how_many= [1,2,3,4,5,6]
app_path="<PATH-TO-DORA>"
app_domain="<MY-DOMAIN>"

$i = 0
$num =20

apps= Array.new

while $i < $num  do
  name= "d"+$i.to_s
  instances=how_many.sample
  memory=how_much_memory.sample
  apps.push({"name" => name, "instances" => instances })
  system("cf push -p #{app_path} -i #{instances} -m #{memory} #{name}")
  $i +=1
end

apps.each do |app|
  name= "d"+$i.to_s
  puts "Curling app #{name}"

  $i = 0
  $num = app["instances"]
  while $i < $num do
    uri = URI.parse("http://#{app["name"]}.#{app_domain}/env.json")
    http = Net::HTTP.new(uri.host, uri.port)
    request = Net::HTTP::Get.new(uri.request_uri)
    res = http.request(request)
    response = JSON.parse(res.body)
    instance_ip = response["CF_INSTANCE_IP"].to_s
    system("jq '. | select(.ips==\"#{instance_ip}\")' index.json")
    $i += 1
  end
end

and monitored the following metric from Rep:

cf query 'CapacityRemainingMemory{source_id="rep"}'| jq -c '.data.result[] | [(.value[1]|tonumber), .metric.zone, .metric.ip]' | sort

The following script pushes a lot of apps with odd number of instances which explained why we didn't see an exact split, but when we updated the number of instances to be all even, we saw the number of apps to be distributed evenly. When we have an odd number of apps, the platform has to choose one of the AZs, and it will pick the z1 with lower instance by default.

If you could make sure all of the apps have even number of instances and attach your distribution of apps along with the cell indexes using the above script, it will help us see your distribution so that we can see what's not working in your setup.

bosh instances -i --json | jq .Tables[0].Rows | jq '.[] | select(.instance | startswith("diego-cell")) ' | jq -r '{ips, index, az}'

[IvanHristov98]

@aminjam good catch! I ran the experiment twice as requested:

• once for apps with only an odd number of instances
• once for apps with only an even number of instances.

I've attached the results within bpff_ha_experiment_results.txt and also uploaded them as a gist for easier access.

As expected when using an odd number of app instances they are distributed unevenly across azs because app instances always get uploaded to as many different azs as possible and z1 is "preferred".

If I understand it correctly the RC could be summarized as:

GIVEN diego-cells in zones:

• z₁, z₂, ..., z_n with indices {x₀, x₁, ..., x_m}
• z_n+1 with indices {y₀, y₁, ..., y_k}

where x_i < y_j for i in [0, .., m] and j in [0, ..., k], and bin_pack_first_fit_weight > 0
WHEN multiple apps with num instances h, where h % num_azs != 0, are pushed,
THEN diego-cells in zones z₁, z₂, ..., z_n are more loaded than the ones in z_n+1.

So assuming that the platform operator has no control over how many instances a user pushes I think this behaviour should be fixed.

PS - I also think that @pommi should be aware of this as he is the author of the feature.

[aminjam]

Hi @IvanHristov98 I am following up on the conversation from slack. Couple of question that remains for me:

• If there is a single instance of an app, what would be the difference if the Auctioneer picked the lower indexed cells vs a cell that's in another AZ with a higher index?

So assuming that the platform operator has no control over how many instances a user pushes I think this behavior should be fixed.

• I am curious to hear what solutions you'd propose?

[IvanHristov98]

Hi @aminjam,

If there is a single instance of an app, what would be the difference if the Auctioneer picked the lower indexed cells vs a cell that's in another AZ with a higher index?

TBH I don't think that there is a notable difference. I rather think that the question is what happens when the load between AZs is unbalanced. The bad scenarios I could come up with are:

LET UNBALANCED_AZS_COND = cells with overall memory quota filled up to 75%
    and bin pack first-fit weight configured so that
        the overall memory quota of cells in z1 is filled up to 95% and
        the overall memory quota of cells in z2 is filled up to 55%

GIVEN UNBALANCED_AZS_COND,
WHEN cells in z1 become suspect due to an infrastructure outage,
THEN compared to when the load between z1 & z2 is balanced, convergence
    takes a lot more time,
    has a more undetermined priority when rescheduling app instances [1].

GIVEN UNBALANCED_AZS_COND,
WHEN an app with a big memory quota (e.g. 32G) gets pushed with 2 instances,
THEN compared to when the load between z1 & z2 is balanced,
    there is a higher probability that the only cells capable of hosting it would be in z2 resulting in a non-HA big app.

[1] Since diego-cells in z1 are more attractive than those in z2 most of the app instances with index 0 will get scheduled in z1. Since app instances with lower indices are scheduled with a higher priority, auctioneer wouldn't be able to differentiate between apps with 1 instance and those with more. Thus suspect lrps with more instances might get scheduled before those with one.

My questions are:

1. Do you think that these are actual problems?
2. Can you think of other problems related to having an unbalanced load between cells in different AZs and if so what are they?
3. If questions 1 and 2 are false then I guess there maybe is nothing to do...

I am curious to hear what solutions you'd propose?

Well at the moment I have just one simple thing in mind. Let's assume we have 3 zones with cell indices distributed as:

z1Indices := [0, 2, 4, 6, 8]
z2Indices := [1, 3, 5, 7, 9]
z3Indices := [15, 16, 16, 200, 10000]

Then we could sort them for each zone by keeping a reference from the original index to the new one in a an ordered multi-hash-set:

// This is just some pseudocode...
// Mapping original cell index to new index in ordered hash set
z1SortedIndices := &orderedMultSet{0, 2, 4, 6, 8}
// mapping becomes ----> {0 -> 0, 2 -> 1,  4 -> 2, 6 -> 3, 8 -> 4}
z2SortedIndices := &orderedMultiSet{1, 3, 5, 7, 9}
// mapping becomes ----> {1 -> 0, 3 -> 1, 5 -> 2, 7 -> 3, 9 -> 4}
z3SortedIndices := &orderedMultiSet{15, 16, 16, 200, 10000}
// mapping becomes ----> {15 -> 0, 16 -> 1, 16 -> 2, 200 -> 3, 10000 -> 4}

// Example new index access
z3SortedIndices.GetIndex(200) // returns 3

This information could be kept as a registry within the scheduler and when calculating the index score the new index could be taken instead:

sortedIndex := zoneSortedIndices.GetIndex(c.state.CellIndex)
indexScore := float64(sortedIndex) * binPackFirstFitWeight

Some key benefits by using this approach are:

• no change is need to the scheduling algorithm
• we don't rely on bosh to order the indices in a specific way
• balanced cell attractivity across AZs
• hash set random access is constant on avg so time complexity should be fine

Hope this answers your questions. 😄

[sunjayBhatia]

Your suggestion around normalizing the cell attribute used to weight the bin pack algorithm with within a zone makes sense to me so actual cell index changes (due to additions/removals) don't affect the weight of an individual cell, a cell's weight in this algorithm should remain constant. This could be done with your idea around sorting based on cell index within a zone and then calculating weight based on the sorted order, doing the same with by sorting based on cell guid, or any other attribute of a cell that stays constant I think. The only concern that may arise is around doing the sorting, adding another sort of the cells in a zone adds some expense, but nothing orders of magnitude of complexity more than we already have.

I think we would be happy to take a PR around this and some auction simulation testing if it seems appropriate for the change. Given this should only affect when bin pack is turned on, I don't think the change is too risky.

[sunjayBhatia]

to address the ideas around different AZs being unbalanced, I think it makes sense to make sure they are balanced otherwise having multiple AZs does not produce an HA deployment; at a high level, the bin pack feature only professes to pack app instances tighter on cells, not change the HA characteristics generally of a multi AZ deployment

[IvanHristov98]

We've created a backlog item to track the issue and will probably begin work over it after a week or two.