cidr_set bitmap should be compressed

[rpothier]

Is this a request for help? (If yes, you should use our troubleshooting guide and community support channels, see http://kubernetes.io/docs/troubleshooting/.):

What keywords did you search in Kubernetes issues before filing this one? (If you have found any duplicates, you should instead reply there.):

---

Is this a BUG REPORT or FEATURE REQUEST? (choose one):
BUG REPORT

Kubernetes version (use kubectl version):
latest

Environment:

• Cloud provider or hardware configuration:
• OS (e.g. from /etc/os-release):
• Kernel (e.g. uname -a):
• Install tools:
• Others:

What happened:
cidr_set.go in pkg/controller/node currently uses a bitmap to track the subnets allocated.
The current allocation logic assumes a small allocation range. This bitmap could grow very large with the introduction of IPv6.
The v6 code in cidr_set.go currently limits the difference between the cluster mask size and subnet mask size to 16. This restriction could be removed if the bitmap was compressed.

What you expected to happen:

How to reproduce it (as minimally and precisely as possible):

Anything else we need to know:

[smarterclayton]

We should also support the same compression on other bit masks at the same time. We use random allocation for many of the spaces which leads to sparse masks.

[smarterclayton]

We should replace the current form with http://roaringbitmap.org/about/, but we'll need to record the version change somehow.

[0xmichalis]

@kubernetes/sig-network-misc

[fejta-bot]

Issues go stale after 90d of inactivity.
Mark the issue as fresh with /remove-lifecycle stale.
Stale issues rot after an additional 30d of inactivity and eventually close.

Prevent issues from auto-closing with an /lifecycle frozen comment.

If this issue is safe to close now please do so with /close.

Send feedback to sig-testing, kubernetes/test-infra and/or @fejta.
/lifecycle stale

[fejta-bot]

Stale issues rot after 30d of inactivity.
Mark the issue as fresh with /remove-lifecycle rotten.
Rotten issues close after an additional 30d of inactivity.

If this issue is safe to close now please do so with /close.

Send feedback to sig-testing, kubernetes/test-infra and/or @fejta.
/lifecycle rotten
/remove-lifecycle stale

[fejta-bot]

Rotten issues close after 30d of inactivity.
Reopen the issue with /reopen.
Mark the issue as fresh with /remove-lifecycle rotten.

Send feedback to sig-testing, kubernetes/test-infra and/or fejta.
/close

[aojea]

/reopen

This imposes limitations on IPv6 for the node mask that can be used
#79993

[k8s-ci-robot]

@aojea: Reopened this issue.

In response to this:

/reopen

This imposes limitations on IPv6 for the node mask that can be used
#79993

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

[fejta-bot]

Rotten issues close after 30d of inactivity.
Reopen the issue with /reopen.
Mark the issue as fresh with /remove-lifecycle rotten.

Send feedback to sig-testing, kubernetes/test-infra and/or fejta.
/close

[k8s-ci-robot]

@fejta-bot: Closing this issue.

In response to this:

Rotten issues close after 30d of inactivity.
Reopen the issue with /reopen.
Mark the issue as fresh with /remove-lifecycle rotten.

Send feedback to sig-testing, kubernetes/test-infra and/or fejta.
/close

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

[aojea]

/reopen

[k8s-ci-robot]

@aojea: Reopened this issue.

In response to this:

/reopen

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

[aojea]

/assign

[bowei]

/lifecycle frozen
/remove-lifecycle rotten

[bowei]

It would be good to clarify where the scalability issue lies -- it may be in memory and w/ the serialized format that is stored on disk; would need different strategy for each.

[aojea]

It would be good to clarify where the scalability issue lies -- it may be in memory and w/ the serialized format that is stored on disk; would need different strategy for each.

Right, I'm trying to understand the problem first.
This change (if needed) most sure will need a KEP, as Lubomir just suggested in the PR I'm using to test the related changes.

[aojea]

After being discussed in the KEP kubernetes/enhancements#1534 current size seems enough, we can always revisit if we start to see limitations on the address size.

[aojea]

/close

[k8s-ci-robot]

@aojea: Closing this issue.

In response to this:

/close

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

[BenTheElder]

/reopen
#94029 ?

[k8s-ci-robot]

@BenTheElder: Reopened this issue.

In response to this:

/reopen
#94029 ?

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

[aojea]

/reopen
#94029 ?

I had a working implementation with compressed bitmaps here #86620, but I think that there are better ideas in kubernetes/enhancements#1881 (comment)

[aojea]

/reopen
#94029 ?

I had a working implementation with compressed bitmaps here #86620, but I think that there are better ideas in kubernetes/enhancements#1881 (comment)

/close
this is not the right fix, will be better if we can move away from the allocators

[k8s-ci-robot]

@aojea: Closing this issue.

In response to this:

/reopen
#94029 ?

I had a working implementation with compressed bitmaps here #86620, but I think that there are better ideas in kubernetes/enhancements#1881 (comment)

/close
this is not the right fix, will be better if we can move away from the allocators

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.