Commit da87298 does not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Hi @usiegl00, thank you for working on this. However, this work does not check for the conditions mentioned in #21776 which we need in order to have feature parity with MetalLB.

My suggestion is to change the allocator in the LBRange to store a list of ServiceViews and to make an index on the rangesStore that maps from sharing key to LBRange + IP.

The algorithm would go something like:

When we check for an unsatisfied IP:
* We check if the service has a sharing key annotation(cilium version). 
  * If it does, we can see if it exists in the `rangeStore` via the index. 
     * If it exists, we go to the `LBRange` and get the list of `ServiceViews`.
     * Check if the ports and external traffic policy of the current service is compatible with the existing `ServiceViews`
       * if it is, add the service view to the list, and satisfy the IP
* If any of the above fail we allocate a new IP
* Once we allocated a new IP, and we have a sharing key, check if the sharing key is present in the index (we can reuse the result from earlier)
  * If no sharing key exists, add our newly allocated IP to the index
  
When a service is deleted or updated such that it no longer requests the IP:
* remove only the` ServiceView` for which the IP is no longer in use
  * If this was the last `ServiceView`, free the IP from the allocator
* If there are still entries left
  * Scan for other `ServiceViews` with the same sharing key but that are not sharing the key (another index might be wise)
    * Check if they still conflict
       * if they don't conflict, free their current IP and add to the list of `ServiceViews`
       
When a service is updated such that the ports or external traffic policy changes:
* Check if the `ServiceView` has a sharing key
  * If it does, check if its part of the allocation indicated by the sharing key index of the range store
    * If it is not, check if the `ServiceView` is still conflicting, if not, free its allocation and add to the shared IP

That way we nicely handle all scenarios. I know its a lot more work, but such are the requirements of the feature. These behaviors also need to be tested.

Commits da87298, 3428661 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Hi @dylandreimerink, thank you for the detailed code layout. I have begun to implement your algorithm.
By having index on the rangesStore that maps from sharing key to LBRange + IP be a one to one relationship, how do I handle a service with a sharing key that requests multiple ips? Could rangesStore have an index that maps to a slice of ServiceViewIPs instead of just one?
Should the documentation changes go in this pr or a separate one?

Commits da87298, 3428661, a7889b0 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits da87298, 3428661, a7889b0, 152836e do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564, d862068 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564, d862068, 426b161 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564, d862068, 2ce4954 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564, d862068, 070f794 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

handle a service with a sharing key that requests multiple ips? Could rangesStore have an index that maps to a slice of ServiceViewIPs instead of just one?

That is a good point, I think it should. In dual stack mode we expect a service to get an IPv4 and IPv6 address which will both have to be in different ranges.

This also made be think about how to handle requests for specific IPs when dealing with shared IPs 🤔. Currently if two service request the same IP we will error on the second request. But if they have a sharing key set and are compatible then we might want to allow that. That would also mean that we could have multiple IPv4 or IPv6 IPs that are shared under a given sharing key which perhaps complicates things.

Should the documentation changes go in this pr or a separate one?

We typically like doc changes to be in the same PR if possible.

That would also mean that we could have multiple IPv4 or IPv6 IPs that are shared under a given sharing key which perhaps complicates things.

Yeah, my current strategy is to try and slot a service into the existing ips belonging to the sharing key and adding a new ip to the existing if it cannot. This is a simple way of ensuring optimal density when ip space is limited.

I also was thinking about enabling the use of multiple comma-separated sharing keys. This would enable services with both sharing keys to slot into both sharing key svcip groups, whereas a service with just one of the keys would only have to slot in with the rest that share that key. This would enable a service with two or more ips to share them in a predictable manner with other services that have conflicting ports.

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564, d862068, 3a51df8 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564, d862068, 9090715 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564, d862068, 9090715, fd5aade do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits ed1d8a6, 5cbbcbe, df15eb7, 251d564, d862068, 9090715, fd5aade, 10dc0bb do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

Commits bbd5b2b, ca9428d, 95bba17, 5436f81, 01de995, 509023b, 876289c, 6cc6df8 do not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

@dylandreimerink Dylan, I've finished work on the pr it is passing the test I added and I hope to get it reviewed and ready to be merged.

Awesome! I have triggered additional tests which need authorization to run, they revealed some things still. Also, like the bot has been complaining about, the Cilium project requires authors to add signoffs to their commits. See
https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin for details.

If you feel like the PR is complete you can mark it ready for review, at that pointer one or more reviewers are assigned. I will also do an additional review. Once all reviews are in and the full CI is green we can merge.

Thanks! I'll add a signature to the commits and get the tests to green before marking it ready for review.

@dylandreimerink Thanks for the assist! I've squashed everything down to 2 commits. (••) ( ••)>⌐■-■ (⌐■_■)

/test

Commit 68b15ff does not match "(?m)^Signed-off-by:".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin

@dylandreimerink Would you trigger a test again? I just had to rebase on main to pull in some auxiliary fixes. Thanks!

/test

@dylandreimerink This is ready to be merged, the only failing test also failed on main.

/test