Improve Cache Implementation

[leakingtapan]

The current cache implement has some issues that could be improved:

• It requires explicit Deprioritize each time GetNext is called. The only time Deprioritize is called is after GetNext, we can combine the two methods together to help on maintainability and understanbility and reduce the chance that someone forget to call Deprioritize
• The behavior of GetNext is nondeterministic, this is caused by sort.Sort which uses quick sort that is unstable sort.
• Cache is not invalidated after volume is detached.

Proposal:

• Maintain a set of device names that are current attached
• Calling Next() each time attaching a volume. Inside Next() call, looping through all the combinations of device names and returns the first one that is not in the cache set. This won't cause any performance issue, since the loop iteration count is very small (in the scale of number of device names, less than 100)
• Calling Remove(deviceName) each time detaching a volume. Inside Remove() call, remove the device from the device name set.

[leakingtapan]

/cc @bertinatto

Let me know how do you think of the problem and my proposal

[leakingtapan]

Ah. Found out that this what the in-tree implements as well: https://github.com/kubernetes/kubernetes/blob/v1.12.2/pkg/cloudprovider/providers/aws/device_allocator.go#L42

[leakingtapan]

/cc @jsafrane @gnufied

[bertinatto]

Ah. Found out that this what the in-tree implements as well

Yes, I decoupled the device management code from k8s an created the package devicemanager package (and added tests).

The behavior of GetNext is nondeterministic, this is caused by sort.Sort which uses quick sort that is unstable sort.

This is also from in-tree. What kind of problem can we have with sort.Sort?

Cache is not invalidated after volume is detached.

I'm not sure if I'm following. The device release is deferred even when it has a taint.

[gnufied]

I thought the reason GetNext and Deprioritize were separate functions is because we wanted to Deprioritize only after device has been successfully attached. There is already another mechanism that prevents concurrent use of same device names between attaches.

GetNext is indeed non-deterministic and feel free to change it. At the end of day though, the device allocator is a band-aid that exists solely because we have to supply device names on attach. The real fix should be in AWS API somewhere IMO.