Want deterministic VPC Subnet allocation strategy

[bnaecker]

As part of #677, we implemented some validation on user-supplied address ranges for VPC Subnets. Specifically, that PR ensures that the provided IPv4 and IPv6 address ranges do not overlap with any existing ranges within the same VPC. In the case when the user does not provide an IPv6 address range, a random subnet from the VPC's prefix is provided. This is reasonable at this point, but could be improved to use a deterministic allocation strategy.

This work was initially deferred because it's not exactly obvious how to implement it in CockroachDB. IPv6 ranges for VPC Subnets are all /64s, specifically the upper 64 bits of the 128-bit IPv6 address stored in CockroachDB. Cockroach implements addition between an INET and an INT, but the integer required would overflow the widest integer type available, which is 64-bit. Addition between two INETs is not supported.

The most plausible strategy then is to keep track of which ranges are free (or allocated) for each VPC in a separate table. This could be implemented as something like (vpc_id, range_start, range_end), where each row gives the first and last available subnet offsets, as a u16, for a VPC. When a new allocation occurs, we'd look up the next available address, and update that record by moving range_start to range_start + 1.

Freeing is a bit more complicated. We'd probably want to coalesce the ranges as much as possible. If the freed subnet has no neighboring range, it's just a new row in the table. If it has a neighboring range above, or below, those are coalesced by updating those record(s) as appropriate. There's a lot of detail here, but it's similar to how a memory allocator might coalesce free blocks.

One difficulty is how to go from these ranges to the actual IPv6 address range. Suppose the VPC has IPv6 prefix fd00::/48, and that we've determined the next available subnet has value 2. How do we get to the fact that this subnet should be fd00:0:0:2::/64? Again, because there's no u128 type in CockroachDB, we might need to do some annoying byte-munging or bit-shifting to hack it together. We should still probably prefer to do these in the database if possible, rather than in application code, either in a transaction or with an update that's conditional on the relevant records not having changed.

[rzezeski]

This work was initially deferred because it's not exactly obvious how to implement it in CockroachDB. IPv6 ranges for VPC Subnets are all /64s, specifically the upper 64 bits of the 128-bit IPv6 address stored in CockroachDB. Cockroach implements addition between an INET and an INT, but the integer required would overflow the widest integer type available, which is 64-bit. Addition between two INETs is not supported.

One difficulty is how to go from these ranges to the actual IPv6 address range. Suppose the VPC has IPv6 prefix fd00::/48, and that we've determined the next available subnet has value 2. How do we get to the fact that this subnet should be fd00:0:0:2::/64? Again, because there's no u128 type in CockroachDB, we might need to do some annoying byte-munging or bit-shifting to hack it together. We should still probably prefer to do these in the database if possible, rather than in application code, either in a transaction or with an update that's conditional on the relevant records not having changed.

While it's true that an IPv6 address is 128-bits long, that doesn't imply it's a 128-bit number. For doing bit-twiddling things you could certainly treat it as a 128-bit number in the code (if that's an efficient way to operate on the value, which it might not be given the compiler/ISA), but at the end of the day it's really just a sequence of 16 bytes (this is similar to how the internet checksum is operated on as a 16-bit number but that's only for the purpose of efficient computation, it's actually just a 2 byte sequence in the header, not a logical 16-bit integer). So I guess I'm confused about what this paragraph is getting at exactly? Is this something to do with the way we are storing things in Cockroach? If so, perhaps some of your problems go away if we treat it as a byte sequence in Cockroach? Or perhaps break things up into the different parts that make up an IPv6 address like the Prefix, Subnet ID, and Interface ID?

[bnaecker]

Thanks for looking at this Ryan, I appreciate it! I agree that u128 is just a (possibly) convenient way to manipulate an IPv6 address, not it's "real" representation. I'm using that in the Nexus code for making a random subnet, just because it seemed easier to me. But again, convenience, not necessity.

Is this something to do with the way we are storing things in Cockroach?

That's right, I think. We're using CRDB's INET type, which handles both v4 and v6 addresses. There are functions for operating on these, but they're pretty limited. You can, for example, get the netmask or add an integer to an address. That latter function could be used to do the offsetting we need for sequential allocation, except that Cockroach doesn't support an integer type wide enough to manipulate the correct bits of the 128-bit IPv6 address. For example, adding some_address + (1 << 64) fails because that bitshift is out of range.

If so, perhaps some of your problems go away if we treat it as a byte sequence in Cockroach?

I was hoping to avoid this, but it might not be possible. The reason is just that it's more opaque and error-prone. Not too hard, but annoying enough that it gives me pause. We'd need to break apart the IPv6 as it's stored in the DB, manipulate the right bits, and then join the bytes again to an IPv6.

Or perhaps break things up into the different parts that make up an IPv6 address like the Prefix, Subnet ID, and Interface ID?

This is a good idea. Dave and I talked about something similar, storing the Subnet ID in a separate column, which we can increment to get the next ID. I'm still not sure what to do with that number though. We'd need to combine it with the prefix to make an actual IPv6 /64 subnet, but it's not clear to me how to do that with the tools that Cockroach has available. I think we can convert from raw bytes to an INET, but we'd need to concatenate the bytes for the prefix and subnet (and zeros for the interface ID), which I'm not sure how to do. I'm sure there are other ways to do it, but nothing in the CRDB docs leapt out at me as the right solution.

On the extreme end of this spectrum, we could store that 3-tuple, and not the actual INET type. I'd probably prefer to keep that type if possible, since it's used of #677 to verify that two address ranges don't overlap. However, the IPv6 subnets are more constrained than I realized at first. The prefix is always 48 bits, the subnet ID always 16 bits. In fact, we don't need a 3-tuple, just those two, to manage the subnets since the interface ID is always 0. That also means "overlap" of two IPv6 ranges is equality on those two parts, which is easy to express in a query. As I'm writing this, that does sound pretty attractive -- one downside I see now is that we need to construct the actual IPv6 subnet object in Rust, after deserializing the two integers representing the prefix and subnet ID. Not horrible, but not awesome.

Anyway, that was a long response, but hopefully it provides some more context. Let me know if that makes sense, and what you think we could do moving forward. Thanks!