O(1) IP allocator regardless of the network size.

An IP allocator that dosen't care about the network size, or active hosts in the network. If a client requests for a free IP, it will find it in O(1) time. Sounds cool? It's actually dead simple.

Let's first understand my use-case. I am building a vpn secured IaaS using wireguard (open source vpn protocol)

The problem:
Wireguard is not a server-client based one. It's p2p. So, there is no concept of IP allocation in the server side of wireguard in a logical sense. So, I had to write one myself.

Naive Solution:

• The naive approach would be looping through the entire network host portion and finding a free one. But that would take ages. Imagine a network of /8 which has more than 16 million hosts.
• So, I had to think something better.

O(1) Solution:

• I already have a db table where I would store all the public keys and IP's of wireguard peers. But I can't loop over them all to find a free one.
• So, I brought redis stack in. For a simple reason. To push and pop released IP's. Clients may remove their device from the network. In that case, their released IP will be stored in the redis stack.
• So now, if a user requests for a new IP, I would first check if there are any released IP's in the redis stack. If it's not empty, I'll just pop it which is O(1) in time complexity.
• If there are no released IP's in the redis stack, I would then query the DB to get the max IP there is currently and increment that with 1 to get the next free IP.

New problem:

• But now you can see a new issue rising up. Query the DB to get the max IP? How? If you store the IP as a literal string like "10.0.0.1/16" or "10.1.0.0/8", it would be too difficult to parse the string and find the current maximum one.

Solution:

• A simple solution. Don't store the IP as a literal string. Store it as a number. What? How?
• For example, lets take /24 IP addresses as an example. (10.0.x.x)
• If the number is 255, then the equivalent IP is 10.0.0.255. If the number is 256, then the equivalent IP is 10.0.1.0, and so on. I hope you can get the idea.
• It would be super easy to get the maximum of a number from a DB table.
• Now, I just have to write a function that converts the number to the IP equivalent regardless of the CIDR notation.
• I'll share my implementation using basic math operations.

Code that converts the number to IP equivalent:

func (ip *IPAllocator) GenerateIP(hostNumber int) (string, error) {
    firstOctet, secondOctet, thirdOctet := 0, 0, 0

    if ip.CidrValue > 24 || ip.CidrValue < 8 || ip.CidrValue%8 != 0 {
        log.Println("Cannot generate IP for this cidr. Only supports /24, /16, and /8")
        return "", errors.New(status.INVALID_CIDR)
    }

    c := hostNumber / 256

    if c < 256 {
        thirdOctet = hostNumber % 256
        secondOctet = c
        return fmt.Sprintf("10.%d.%d.%d", firstOctet, secondOctet, thirdOctet), nil
    }

    firstOctet = c / 256
    secondOctet = c % 256
    thirdOctet = hostNumber % 256

    return fmt.Sprintf("10.%d.%d.%d", firstOctet, secondOctet, thirdOctet), nil
}

• Now, we have one last problem. It's still not truly O(1) because the DB query to get the maximum number will be O(N)
• The simple solution is to index the column that has the number

Now, the DB query would be something like this.
SELECT ip_address FROM wgpeer ORDER BY ip_address DESC LIMIT 1
where ip_address is the indexed column.

• The magic lies behind how sorting with index works.
• Indexing a column will make the db to create a B+ tree.
• So, if I sort the column with limit 1 and DESC, it will do a backwards index scan which will start from the rightmost leaf node and that is obviously the highest value. It will stop just right there as we have LIMIT 1.
• And this ultimately makes the entire query O(1)

Conclusion:

• Redis push and pop: O(1)
• DB query : O(1)

• number to IP : O(1)

• And ultimately the entire logic of the IP allocator becomes O(1)

Comments

[Kishan Verma]

❤️💀🔥