Distributed network address allocation management

Disclosed are various embodiments for distributed network address allocation management. In one embodiment, a first instance of a plurality of instances of an allocation management service assigns a first portion of a network address space to the first instance and a second portion of the network address space to a second instance of the plurality of instances. The second instance receives a request to allocate a particular network address block. The second instance allocates the particular network address block from the second portion of the network address space by updating an allocation data structure. An allocation of the particular network address block is returned in response to the request. A copy of the allocation data structure maintained by the first instance is updated asynchronously based at least in part on the allocation of the particular network address block.

BACKGROUND

Network addresses for the Internet are specified in respective addressing schemes for Internet Protocol version 4 (IPv4) and Internet Protocol version 6 (IPv6). IPv4 addresses are 32 bits in length and are usually visually represented by dotted quad notation, with four octets, each ranging from 0 to 255 and separated by periods. There are roughly 232or 4,294,967,296 addresses, less reserved and/or system address ranges. The use of Classless Inter-Domain Routing (CIDR) allowed for allocation of addresses using variable length subnet masks and accompanying arbitrary length network prefixes. For example, a network “192.168.1.0/24” indicates a network prefix 24 bits in length using CIDR notation, with the equivalent subnet mask of “255.255.255.0” being implied by the “/24” CIDR notation. While four billion addresses may seem like a large number, every top-level block of IPv4 addresses has already been allocated. Because of IPv4 address exhaustion, the Internet is transitioning to the use of IPv6, which uses 128-bit addresses and 2128possible addresses. IPv6 addresses are represented as eight groupings of four hexadecimal digits, each ranging from 0000 to ffff, and separated by colons.

DETAILED DESCRIPTION

The present disclosure relates to network address allocation management that is distributed across multiple locations and is fault tolerant. An organization may rely upon an allocation management service to issue, reclaim, and otherwise manage network address allocations in the organization, such as IPv4 address allocations or IPv6 allocations. The allocation management service ensures that allocations of a given network address block are made only once at a time in a particular network scope. This ensures that network users will not inadvertently be allocated the same network address block or overlapping network address blocks within a particular network scope, which would prevent proper network functioning.

While a single instance of an allocation management service using a centralized database may be appropriate for a network in one region, problems can occur when a network spans multiple regions. For example, suppose that a network of an organization spans a first region and a second region, but an allocation management service is operated solely in the first region. If the first region goes offline, or connectivity between the first and second regions is impaired, devices in the second region would not be able to obtain or release network address allocations. Such problems can occur in networks spanning multiple fault containers, such as regions, availability zones, data centers, and so on, which could fail independently of one another.

Various embodiments of the present disclosure introduce distributed implementations of an allocation management service, where respective instances of the allocation management service can be executed in corresponding regions or fault containers. One of the instances may be selected as a leader and delegates authority for a portion of the address space in a network to respective other ones of the instances. Thus, each instance of the allocation management service is able to allocate network address blocks in each respective region or fault container, irrespective of whether another region or fault container has gone offline or is unreachable. Information about the network address allocations made in each respective region and fault container may be asynchronously propagated via snapshots to the leader instance of the allocation management service. In this way, the leader instance may maintain access to a global snapshot and can respond to queries or otherwise provide information about the global state of the network address allocations and associated metadata attributes. In other implementations, snapshot information may be exchanged between peer instances of an allocation management service, e.g., as in a peer-to-peer network or a mesh network.

As will be described, the allocation management service may use prefix allocation trees for managing network address allocations, with the prefix allocation trees being maintained using one or more asynchronous workflows. The network address allocations in the prefix allocation trees may be associated with arbitrary user attributes. Organizations that manage networking infrastructure may need to keep track of network address allocations in order to know what address ranges are already allocated, or conversely, are unallocated and available for allocation. In various scenarios, a customer may be seeking a new network address allocation with at least a certain number of network addresses to configure a subnetwork in a cloud provider network, where the addresses are allocated from a pool of available addresses from the cloud provider or from a pool of addresses that the customer already controls. Using CIDR notation, the “/X” number of bits subtracted from the number of bits in the address yields the number of addresses available in a network according to the formula 2(32-X)for IPv4 or 2(128-X)for IPv6. For example, a request for a “/28” network allocation in IPv4 would be for 2(32-28)or 16 contiguous addresses.

It is also important to avoid unnecessary fragmentation of larger network address blocks to preserve them for customers who may require such larger allocations. To illustrate, within a “/30” block of four contiguous addresses in IPv4 are two “/31” blocks of two contiguous addresses each. Allocating a single address from the first “/31” block and a single address from the second “/31” block would make it impossible to allocate an entire “/31” block of two addresses. Thus, an allocation management system should seek to allocate both single addresses (each considered “/32” blocks) within one “/31” block, thus preserving the entire remaining “/31” block for a possible future allocation request of two contiguous addresses.

With IPv4, network address allocation management could be done with a relatively simple table structure in a database. However, such an approach is not practical or scalable for IPv6, particularly in locating free space of a certain size that can be allocated to the customer within the global pool of network addresses. This is a problem because traditional indexes index data but not the absence of data, and the IPv6 address space is effectively infinite. Thus, occupying all the free space with indexable records is not practical. Moreover, traditional data structures are designed for single-threaded machines and do not scale well to multiple machines or concurrent mutations. Also, making a network call to obtain data from a remote database is five orders of magnitude more computationally expensive than dereferencing a pointer, such as in traditional data structures.

Various embodiments of the present disclosure may use a prefix allocation tree data structure in order to manage network address allocation. The prefix allocation tree may also be referred to as a trie. A trie is a type of search tree data structure that can be used to store sequences of values, in which each node represents a single string or a prefix, and all the children of a node have a common prefix of the string associated with that parent node. The presently disclosed trie can be distributed across a number of separate computing devices, for example across a number of different servers in a cloud computing environment.

The prefix allocation tree provides the advantages of representing all of the IPv6 space efficiently; providing transactional, linear-time, O(depth) create, read, update, and delete operations; providing transactional, linear-time, O(depth) allocations of arbitrary size; and providing reliable, non-blocking time-bound snapshots. Although the present disclosure focuses on the example of network address allocation, the prefix allocation tree may be used in any other context in which a power-of-two allocator may be desired, which could include applications such as assigning seats in a concert hall or arena, reserving space in an exhibition hall, allocating time slots on a calendar, and so forth.

Turning now toFIG.1A, shown is a drawing of an example prefix allocation tree100configured for a 128-bit network address, such as an IPv6 network address. Each node corresponds to a level in the tree100and a bit position in the corresponding network address, while the transition corresponds to the data encoded by the tree100. A binary alphabet (“0” and “1”) are used in this example. At each node, the bit value may be either “0” or “1”, using this alphabet. The tree100has a depth of 128, corresponding to the 128 bits represented. Traversing the tree100using the leftmost transitions yields the value of “0” 128 times, or the address “::”, while traversing the tree100using the rightmost transitions yields the value of “1” 128 times, or the address “ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff”.

At each node in the tree100, a pointer can provide data relating to the allocation of the network address space falling under that corresponding node. Such data can include whether the network address space is available within a pool or is owned by a network services provider or a customer, and whether the network address space (or a portion thereof) has been allocated. With 128 levels, the vast majority of nodes would serve no purpose and would add unnecessary round-trip latencies during path traversals.

FIG.1Bshows another example of a prefix allocation tree110, but this time using the hexadecimal alphabet (“0” thorough “f”) instead of the binary alphabet. This prefix allocation tree110also represents the entire 128-bit address space of IPv6, but now with 32 levels instead of 128. Traversing the tree110using the leftmost transitions yields the value of “0” 32 times, or the address “::”, while traversing the tree110using the rightmost transitions yields the value of “f”32 times, or the address “ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff”.

While 32 levels may offer latency improvements to the 128-level tree ofFIG.1B, computing service implementation details may weigh toward different trees. As a non-limiting example, a data storage service may have a transaction limit of 25 items per transaction. The ability to alter or mutate a tree using native transactions of the data storage service may significantly simplify the implementation of mutations, particularly involving multi-tenancy, which can result in concurrent requests from different customers. A typical tree, by contrast, is not a concurrent data structure and cannot be used in parallel by multiple users. Thus, in various implementations, a prefix allocation tree has a number of levels less than or equal to a maximum number of items per transaction supported by a data storage service.

In various implementations, each parent node in a prefix allocation tree holds references to its child nodes in order to solve the problem of indexing unoccupied space. However, the number of child references grows exponentially as the tree depth decreases. A data storage service may have a constraint that limits due to data size the number of references that can be stored for a given parent node. Therefore, although shallower trees may be preferable, making the tree shallower causes the amount of data stored for each node to increase. Moreover, as the amount of data stored for each node increases, contention increases. The same number of mutations have to happen on a smaller set of data items, and as those items grow larger, those mutations become more input/output (I/O) intensive and take longer to perform.

FIG.1Cshows another example of a prefix allocation tree120with a top-level address block of “10.0.0.0/8” in CIDR notation. In this example, the nodes of the prefix allocation tree120are eight-bit aligned, though other alignments may be chosen in other examples. That is to say, the prefix length is divisible by a value, which is eight in this case. Being eight-bit aligned, the top-level node is a “/8,” the next child nodes are “/16,” and the grandchild nodes are “/24.” Thus, the successive child nodes are a next multiple of the value. In another example, the nodes are four-bit aligned, which would lead to a greater number of nodes, e.g., “/8” followed by “/12,” followed by “/16,” followed by “/20,” and so forth.

Each node encompasses the named address block and all children that are less specific than that named by the child node. For instance, the node for the “10.0.0.0/8” block includes child address blocks within the named block of sizes from “/8” to “/15,” while the node for the “10.1.0.0/16” block includes child address blocks within the named block of sizes from “/16” to “/23,” and so forth. In special edge cases, the node for a “/24” block may include “/32” child address blocks for IPv4, and the node for a “/120” block may include “/128” child address blocks for IPv6, as these latter address blocks are in fact single addresses.

In order to optimize performance in view of underlying data storage system constraints, invariants may be maintained for the prefix allocation tree120. For example, when an allocation exists for an address block, all of that address block's space is precisely and completely covered by a combination of suballocations and free block indicators for the allocation.

Non-limiting examples of advantages of the disclosed prefix allocation tree techniques include allowing for suballocations to arbitrary depth; allowing for arbitrary user attributes to be atomically stored and indexed alongside allocations; allowing for consistent snapshots to be taken of an entire prefix allocation tree, potentially in the face of concurrent mutations; allowing for splitting an allocation into several pieces for independent management; scaling and performance improvements; allowing for synchronizing an entire prefix allocation tree to a given baseline of content, while calculating differences between the prefix allocation tree and the baseline; storing user content separately from the structure of the prefix allocation tree; avoiding reliance on global indices maintained by a data storage service; and so forth. In the following discussion, a general description of the system and its components is provided, followed by a discussion of the operation of the same.

With reference toFIG.2A, shown is a networked environment200according to various embodiments. The networked environment200includes a computing environment203, and one or more client devices206, which are in data communication with each other via a network209. The network209includes, for example, the Internet, intranets, extranets, wide area networks (WANs), local area networks (LANs), wired networks, wireless networks, cable networks, satellite networks, or other suitable networks, etc., or any combination of two or more such networks.

The networked environment200may correspond to a cloud provider network (sometimes referred to simply as a “cloud”), which is a pool of network-accessible computing resources (such as compute, storage, and networking resources, applications, and services), which may be virtualized or bare-metal. The cloud can provide convenient, on-demand network access to a shared pool of configurable computing resources that can be programmatically provisioned and released in response to customer commands. These resources can be dynamically provisioned and reconfigured to adjust to variable loads. Cloud computing can thus be considered as both the applications delivered as services over a publicly accessible network (e.g., the Internet, a cellular communication network) and the hardware and software in cloud provider data centers that provide those services.

A cloud provider network can be formed as a number of regions, where a region is a separate geographical area in which the cloud provider clusters data centers. Example regions include U.S. East (located on the east coast of the U.S.), U.S. West (located on the west coast of the U.S.), Europe—London, and Europe—Paris. Each region can include two or more availability zones connected to one another via a private high-speed network, for example a fiber communication connection. An availability zone refers to an isolated failure domain including one or more data center facilities with separate power, separate networking, and separate cooling from those in another availability zone. Preferably, availability zones within a region are positioned far enough away from one other that the same natural disaster should not take more than one availability zone offline at the same time. Customers can connect to availability zones of the cloud provider network via a publicly accessible network (e.g., the Internet, a cellular communication network) to access resources and services of the cloud provider network. Transit Centers (TCs) are the primary backbone locations linking customers to the networked environment200, and may be co-located at other network provider facilities (e.g., Internet service providers, telecommunications providers). Each region can operate two TCs for redundancy. The cloud provider network may deliver content from points of presence outside of, but networked with, these regions by way of edge locations and regional edge cache servers (points of presence, or PoPs). This compartmentalization and geographic distribution of computing hardware enables the cloud provider network to provide low-latency resource access to customers on a global scale with a high degree of fault tolerance and stability.

Generally, the traffic and operations of a cloud provider network may broadly be subdivided into two categories: control plane operations carried over a logical control plane and data plane operations carried over a logical data plane. While the data plane represents the movement of user data through the networked environment200, the control plane represents the movement of control signals through the networked environment200. The control plane generally includes one or more control plane components distributed across and implemented by one or more control servers. Control plane traffic generally includes administrative operations, such as system configuration and management (e.g., resource placement, hardware capacity management, diagnostic monitoring, system state information). The data plane includes customer resources that are implemented on the provider network (e.g., computing instances, containers, block storage volumes, databases, file storage). Data plane traffic generally includes non-administrative operations such as transferring customer data to and from the customer resources. The control plane components are typically implemented on a separate set of servers from the data plane servers, and control plane traffic and data plane traffic may be sent over separate/distinct networks.

In some embodiments, the computing environment203may correspond to a virtualized private network within a physical network comprising virtual machine instances executed on physical computing hardware, e.g., by way of a hypervisor. The virtual machine instances may be given network connectivity by way of virtualized network components enabled by physical network components, such as routers and switches.

Various applications and/or other functionality may be executed in the computing environment203according to various embodiments. Also, various data is stored in a data store212that is accessible to the computing environment203. The data store212may be representative of a plurality of data stores212as can be appreciated. The data stored in the data store212, for example, is associated with the operation of the various applications and/or functional entities described below.

The applications and/or functionality executed in the computing environment203include an allocation management service214, an address allocation application programming interface (API)215, one or more asynchronous workflows216, a data storage service218, and/or other applications, systems, services, engines, and/or other functionality. The allocation management service214is executed to issue network address allocations to requestors from a pool of network addresses corresponding to a portion of network address space available to a customer. In some cases, the network address space may correspond to a private network address space (e.g., “10.x.x.x” or “192.168.x.x” in IPv4), or the network address space may correspond to publicly routable network address space. The allocation management service214may also release network address allocations and perform other functions implemented by the address allocation API215.

The address allocation API215supports various functionality to manage network address allocations backed by allocation data structures such as prefix allocation trees220. Functionality provided by the address allocation API215may include tree management functions222, an allocate function223, a release function224, a shatter function225, a set attributes function226, a get block function227, a find parents function228, a find immediate children function229, a find by attribute function230, and/or other functions. These functions will be described in more detail below.

The asynchronous workflows216may include one or more workflows that are asynchronously performed with respect to mutations resulting from requests submitted via the address allocation API215. In other words, the asynchronous workflows216are not executed as part of the mutations and are not necessarily executed immediately after or in response to the mutations. The asynchronous workflows216may include an update attribute index workflow240, a consolidate free space workflow241, a snapshot workflow242, a cleanup workflow243, and/or other workflows. These workflows will be described in more detail below.

The data storage service218may correspond to a cloud service that provides data storage management on behalf of the data store212. In one implementation, the data storage service218may correspond to a distributed hash table with key/value-based operations, such as “put,” “get,” “delete,” and so on. In another embodiment, the data storage service218may correspond to a relational database management system. For efficiency, the data storage service218may have a constraint on a maximum quantity of data to be stored as a value associated with a key. The data storage service218may also have a constraint on a maximum number of data items that can be mutated in a single transaction. The data storage service218may support eventually consistent reads and/or strongly consistent reads.

The data store212includes one or more prefix allocation trees220to manage a set of network address allocations, one or more consistent snapshots245of one or more of the prefix allocation trees220, and/or other data. Each prefix allocation tree220may include one or more nodes246and an attribute index247. It is noted that individual nodes246within the prefix allocation tree220and the attribute index247may be distributed among multiple computing devices by the data storage service218in some embodiments.

A prefix allocation tree220may be created with a root node246or top-level node246corresponding to a largest network address block that may then be suballocated as desired. For example, the root node246may correspond to a “/8” network, but other sizes can be used. In some scenarios, a prefix allocation tree220may have a plurality of top-level nodes246corresponding to non-contiguous top-level allocations. In some scenarios, a prefix allocation tree220may have a plurality of top-level nodes246corresponding to contiguous top-level allocations, if the user wishes to manage the contiguous top-level allocations separately. Each of the nodes246may include one or more attributes251, a tree identifier252, a hash key253, an address block254, one or more child address blocks255, references to one or more child nodes256, one or more vector clocks257, one or more free indicators258, and/or other data. In one embodiment, the attributes251and the free indicators258are attached to the individual child address blocks255, rather than the node246as a whole, and the free indicators258may be managed as one type of attribute251. The nodes246may correspond to JavaScript object notation (JSON), yet another markup language (YAML), extensible markup language (XML), and/or any other object serialization or format for storing data in the data storage service218.

The attributes251correspond to name-value pairs that can associate arbitrary user data with particular nodes246. For example, a user may wish to denote a particular address allocation as corresponding to a type of cost center or usage in an organization. In addition to arbitrary user data, the attributes251can include administratively defined attributes such as the vector clock257, the free indicator258, allocation identifiers, data shard identifiers, tokens, ownership identifiers, parent node identifiers, and/or any other data of the nodes246. In one implementation, each attribute251includes a name string and a value that can be a string, a list of strings, or a map from string to string. Other data types may be used in other implementations.

The tree identifier252may correspond to a unique identifier of the prefix allocation tree220in which the node246is contained. The hash key253in one example may be a combination of the address block254and the tree identifier252, though other data may be used in other examples.

The address block254may correspond to a block of network addresses in CIDR notation. In various embodiments, the address block254is used as a unique identifier for the node246. In one embodiment, the address block254is constrained to be aligned by some number of bits, such as eight, such that the prefix length in bits is evenly divisible by that value. The address block254in a node246may be completely free, completely allocated, or partially allocated and partially free. If the address block254contains a suballocation, the node246may include one or more child address blocks255corresponding to suballocations or free parts. In one embodiment, the address block254may appear within the child address blocks255if there are one or more attributes251associated with the address block254. When an address block254is shattered, or prepared for suballocation, multiple child address blocks255at a next level are created and marked completely free for allocation. It is noted that child address blocks255may be further shattered and subdivided for possible allocation. Each of the child address blocks255may be associated with attributes251, including their own child address blocks255.

To simplify the prefix allocation tree220, the node246encompasses child address blocks255having a prefix length greater than or equal to the prefix length of the address block254up to one less than a next multiple of the value by which the prefix length of the address block254is aligned. That is to say, where the nodes246are eight-bit aligned and the prefix length of the address block254is eight, the node246may include child address blocks255of prefix lengths eight through fifteen. A different node246would be created for the next subdivision, or prefix length sixteen, and a reference or identifier of that node246would be stored in the child nodes256. For example, with an eight-bit alignment, there may be a maximum of 255 child nodes256.

The vector clocks257are used to track mutations and in generating consistent snapshots245of the prefix allocation tree220. Each of the address block254and the child address blocks255may have its own vector clock257, or the vector clock257may be specific to the node246. In one embodiment, the values in the vector clock257are initialized upon creation to be a current wall clock time in milliseconds. Each time the respective address block254or child address block255is mutated (e.g., shattered, allocated, released, attributes changed, etc.), the respective value of the vector clock257may be incremented and/or set to a pairwise maximum as compared to corresponding values in a child or parent vector clock257. In one implementation, a node246may track all vector clock257values of itself, its immediate parent node246, and all of its child nodes256, which may be a maximum of 258 vector clocks257to track. As the allocation or releasing of space is propagated up or down, the vector clocks257are updated with the latest values by applying the pairwise maximum.

The free indicator258indicates whether a child address block255is completely free. The child address block255is not completely free if it is either completely allocated or contains at least one allocation in combination with free space. The child address blocks255may have their own respective free indicators258within the node246. In one implementation, instead of being a Boolean flag value, the free indicator258is a reference to an allocation of which the child address block255is a completely free part.

To illustrate the usage of the free indicator258, in one implementation, when a prefix allocation tree220is first created in IPv4, it may have one allocation (e.g., the allocation is of “0.0.0.0/0” and the allocation identifier is the address family root sentinel identifier. Hence on creating a prefix allocation tree220, there may be one free indicator258, namely that “0.0.0.0/0” is a completely free part of the address family root sentinel identifier. The API for inserting a top-level node246may be a suballocation from the address family root sentinel identifier to the top-level sentinel identifier. Hence on inserting “10.0.0.0/8” as a top-level node246, the address block254of “10.0.0.0/8” may be marked with the top-level sentinel allocation identifier, and also “10.0.0.0/8” may be marked as a completely free part of the top-level sentinel allocation ID. At the same time, the shatter set “0.0.0.0/0” minus “10.0.0.0/8” may each be marked as a completely free part of the address family root sentinel identifier.

For example, “11.0.0.0/8”, part of the shatter set, is marked as a free part of the address family root sentinel identifier. This means that the address block254“11.0.0.0/8” or any child could be a top-level node246at some point if an insert top-level API call is invoked on the “11.0.0.0/8” or any child. This mechanism may prevent overlapping top-level nodes from being inserted, even by concurrent calls. Also, two key invariants may be maintained across the entire address family, namely that every network address in the address family is allocated to something and also a free part of something else, and every network address in an allocation is either a free part of the allocation or suballocated. These may be considered transactional guarantees, such that there is no moment when any caller to allocate or release will observe them as being violated, nor will any consistent snapshot contain a violation of these invariants.

In such an implementation, a call to the allocate function223may be a suballocation from the top-level sentinel identifier. The process is similar to the above. Suppose one allocates the address block254“10.1.2.0/24” out of the top level “10.0.0.0/8”, yielding an allocation identifier of “alloc-123.” Then, “10.1.2.0/24” may be marked as a completely free part of “alloc-123” in the corresponding free indicator258so that “alloc-123” can be suballocated from that address block254later if needed. Meanwhile, the shatter set “10.0.0.0/8” minus “10.1.2.0/24” may be marked as a completely free part of the top-level sentinel identifier, so that other parts of the top-level node246can be allocated later. A suballocating call to the allocate function223may be a suballocation from the given allocation identifier.

The attribute index247is an index of nodes246by their attributes251using attribute index items259. In one embodiment, the attribute index247is distributed among multiple systems using a plurality of shards. The quantity of shards may be dynamic based at least in part on the size of a prefix allocation tree220. A large prefix allocation tree220with a small number of shards will be suboptimal, as would be a small prefix allocation tree220with a large number of shards. In one implementation, buckets of shard quantities may be used (e.g., powers of 10), each of which may be tied to a threshold size for a prefix allocation tree220. For example, when the prefix allocation tree220reaches a threshold size, the number of shards may be increased from 10 to 100.

The attribute index items259may include a tree identifier252; a hash key253that includes an identifier of the attribute index item259, the tree identifier252, an attribute name, an attribute value, and a shard identifier; an address block254; and a range key. In one implementation, the range key corresponds to the address block254formatted in a non-standard way, with the prefix length followed by the network address, with the prefix length and each entry in the dotted quad notation being padded with leading zeros to be three digits. The range key may then be used with the data storage service218to scan through the attribute index247in lexicographic order of their range keys, which is equivalent to scanning through the attribute index247in order of prefix length followed by network address bytes. To locate all address blocks254with a given name/value pair, N parallel queries to the attribute index247may be made, one per shard, for all items with the hash keys253that include the name/value pair.

In various implementations, the attribute index247may include one or more secondary indices that are generated to optimize lookups by particular parameters other than the primary key. For example, a delete tree function of the tree management functions222may need to locate all nodes246in a prefix allocation tree220, and having a secondary index that is indexed by the tree identifier252may optimize this function. The secondary indices may also be sharded.

The snapshots245correspond to consistent snapshots245of one or more prefix allocation trees220. As portions of a prefix allocation tree220may be mutated while other portions are not yet updated to reflect the mutation, it is important to be able to have a snapshot245that is consistent.

In some implementations, at least a portion of content for the attributes251may be stored in offboarded attributes260. For example, the data storage service218may have a data item size limit for storage of data items, and the attributes251may exceed this data item size limit. In such cases, the data item, or a portion of the data item exceeding the data item size limit may be stored as offboarded attributes260by an alternative data storage service218that does not have the particular data item size limit. In some cases, the portion of the data item exceeding the data item size limit may be stored as a sequence of component data items by the data storage service218, such as a linked list of data items. With the offboarded attributes260, the attributes251stored by the data storage service218may include a reference to the corresponding offboarded attributes260. In order to provide transactional safety guarantees, these offboarded attributes260may be immutable and read with strongly consistent reads. Furthermore, the offboarded attributes260may be constructed and flushed to storage prior to creating any references to the offboarded attributes260. Thus, in such an implementation, if a child address block255has an attribute251referencing an offboarded attribute260, the offboarded attribute260exists and has fixed content.

Returning now to the functions implemented by the address allocation API215, the tree management functions222may include functions to create a new prefix allocation tree220for an address family (e.g., IPv4 or IPv6), delete a prefix allocation tree220, create a prefix allocation tree220from a snapshot245, obtain a snapshot245for a given prefix allocation tree220, synchronize a prefix allocation tree220to a given snapshot245(which may return the differences between the prefix allocation tree220and the snapshot245), and other functions.

Synchronizing a prefix allocation tree220to a given snapshot245may be implemented as a batch process in a write-efficient way, so that it performs only the write operations that are needed to make a prefix allocation tree220have the same content as the snapshot245. This is in contrast to an approach that would delete and recreate the prefix allocation tree220from the snapshot245. As this is a batch operation, it may be possible for the synchronization function to fail in process (e.g., if power is lost). The vector clocks257and the snapshot workflow242can be used to detect such a failure. This is because the vector clocks257can indicate if a given item was updated but its parent or child was not.

The allocate function223is used to allocate address blocks254from a prefix allocation tree220. A special case of the allocate function223may be to insert a new top-level address block254into the prefix allocation tree220. For example, the user may specify a tree identifier252, an address block254, one or more attributes251, and an idempotency token to insert the new top-level address block254. The allocate function223may allocate a specifically requested address block254or some address block254having a particular prefix length that is available that is a suballocation of a top-level address block254or a specific suballocation of the top-level address block254. The return value may be the newly allocated address block254and an allocation identifier. The allocation identifier can be used to alter the attributes of the allocation, to release the allocation, or to suballocate from the allocation.

Internally, the allocate function223may update a parent address block254to remove a free indicator258, add the allocation, and add free address blocks254for portions of the parent address block254outside of the desired allocation. Each of these portions are other address blocks254and the total number of such portions is equal to the prefix length of the allocated address block254minus the prefix length of the parent. The set of address blocks254that needs new free indicators258is called the shatter set and can be produced by the shatter function225.

The release function224is used to release a prior allocation from the prefix allocation tree220. The allocation may be identified by the identifier returned by the allocate function223and/or the address block254of the allocation. Also in some cases, the release function224may be used to delete an address block254from a prefix allocation tree220. The user may also specify a tree identifier252and an idempotency token. Internally, the release function224may verify that there are no suballocations, to delete the allocation state, and change the address block254to have a free indicator258indicating that the address block254is a free part of the parent address block254.

The shatter function225may be used to shatter an existing allocation into parts. The shatter function225may take as parameters the tree identifier252, an address block254, an allocation identifier, and an idempotency token. The shatter set is the set of address blocks254left after subtracting a child address block254from a parent address block254. The size of this set is equal to the child prefix length minus the parent prefix length. As an example, if one subtracts “10.0.0.0/10” from “10.0.0.0/8”, then the result is {10.128.0.0/9, 10.64.0.0/10}-two address blocks254. If one subtracts “10.1.2.3/32” from “10.0.0.0/8,” then the result would be 32−8=24 address blocks254. Listing them out: “10.1.2.2/32”, “10.1.2.0/31”, “10.1.2.4/30”, “10.1.2.8/29”, “10.1.2.16/28”, “10.1.2.32/27”, “10.1.2.64/26”, “10.1.2.128/25”, “10.1.3.0/24”, “10.1.0.0/23”, “10.1.4.0/22”, “10.1.8.0/21”, “10.1.16.0/20”, “10.1.32.0/19”, “10.1.64.0/18”, “10.1.128.0/17”, “10.0.0.0/16”, “10.2.0.0/15”, “10.4.0.0/14”, “10.8.0.0/13”, “10.16.0.0/12”, “10.32.0.0/11”, “10.64.0.0/10,” and “10.128.0.0/9”. The nodes246to be updated to capture such an allocation, while updating the free indicators258, is the set of all nodes246that contain any address block254in the shatter set, also referred to as a shatter node set. The number of nodes246in the shatter node set may be equal to one less than twice the number of nodes246in the parent lineage.

Continuing with the above example, if one wants to allocate “10.1.2.3/32” out of “10.0.0.0/8”, then the nodes246corresponding to the parent lineage may be updated “10.1.2.0/24,” “10.1.0.0/16,” and “10.0.0.0/8.” The shatter node set also contains “10.1.3.0/24” (a sibling of “10.1.2.0/24”) and “10.0.0.0/16” (a sibling of “10.1.0.0/16”). This is because after subtracting “10.1.2.3/32” from “10.0.0.0/8”, “10.1.3.0/24” and “10.0.0.0/16” are part of the shatter set and therefore need to be marked as free. Hence the shatter node set comprises these five nodes246: {“10.1.2.0/24”, “10.1.3.0/24”, “10.1.0.0/16”, “10.0.0.0/16”, and “10.0.0.0/8” }. In one implementation, the shatter function225will split the allocation into the shatter set, not the shatter node set.

The set attributes function226may set attributes for a given allocation identifier. The attributes may be set conditionally based upon a map of conditions that are atomically checked prior to setting the attribute values. Parameters may include a tree identifier252, an allocation identifier, an address block254, and the attributes251to be set. If an attribute exceeds a data size limit of the data storage service218, the set attributes function226may store the attribute as an offboarded attribute260.

The get block function227returns the attributes251of a given address block254from a prefix allocation tree220identified by a tree identifier252. In some cases, the attributes251may be fetched from the offboarded attributes260. The attributes251are returned from a snapshot245. The find parents function228returns a snapshot245of all parents of an address block254in a prefix allocation tree220identified by a tree identifier252. The find immediate children function229returns a snapshot245of all immediate children of a given address block254. The find by attribute function230locates all address blocks254having a given value of an attribute251.

As to the asynchronous workflows216, the update attribute index workflow240is executed asynchronously to update the attribute index247. This may involve reading the node246, creating all missing attribute index items259for the corresponding node246, and deleting any obsolete attribute index items259. In some cases, the update attribute index workflow240may index offboarded attributes260. The consolidate free space workflow241is executed asynchronously to consolidate free space within a node246and then consolidate free space across all nodes246in the prefix allocation tree220. Consolidating free space in a node246involves reading the node246, performing the calculations, and writing back the node246. Consolidating free space across nodes246may comprise a transaction involving three nodes246: two adjacent siblings and their parent. The free space from the two siblings can be consolidated into the parent when an allocation is marked as free at the node246of each sibling.

The snapshot workflow242is executed asynchronously to generate consistent snapshots245or to verify whether a snapshot245is consistent. In order to generate consistent snapshots245, the snapshot workflow242reads the prefix allocation trees220and ensures that the copies of the individual vector clocks257are consistent with each other. In one scenario, the snapshot workflow242generates an alarm notification if the snapshot245is inconsistent and the prefix allocation tree220has not changed. In other scenarios, the snapshot245may be inconsistent if a mutation is happening. In one embodiment, if the snapshot workflow242observes an inconsistency in a copy of the same vector clock257, the snapshot workflow242retries to generate the consistent snapshot245until consistency can be observed. The snapshot workflow242may also implement structural checks to ensure that each node246is referenced as a child of its parent, and that every child referenced in a node246is in a snapshot245. The snapshot workflow242may also implement checks to ensure that system invariants are met in the snapshot245(e.g., that each allocation identifier is precisely and completely covered by suballocations and free indicators258). It is noted that a caller may request a consistent snapshot245at any time. The snapshot workflow242will then take the snapshot, optionally perform consistency checks if the caller wants, and if the consistency checks fail, report that failure to the caller. The caller may accept the inconsistency, alarm about it, retry, or so on.

The cleanup workflow243is executed asynchronously to perform clean up tasks in the prefix allocation trees220and the attribute index247, which may include deleting attribute index items259that are outdated or not correct references and also deleting offboarded attributes260that are no longer referenced or are out of date. To this end, the offboarded attributes260may be associated with timestamps and/or version identifiers corresponding to the child address block254to which the offboarded attribute260pertains. The timestamps and/or version identifiers can be used in determining whether the offboarded attribute is260is safe to delete. In some cases, the cleanup workflow243may delay purging offboarded attributes260for a particular period of time to ensure that updates are not likely happening simultaneously.

The client device206is representative of a plurality of client devices that may be coupled to the network209. The client device206may comprise, for example, a processor-based system such as a computer system. Such a computer system may be embodied in the form of a server computer, a desktop computer, a laptop computer, personal digital assistants, cellular telephones, smartphones, set-top boxes, music players, web pads, tablet computer systems, game consoles, electronic book readers, smartwatches, head mounted displays, voice interface devices, or other devices.

The client device206may be configured to execute various applications such as a client application261and/or other applications. The client application261may be executed in a client device206, for example, to access network content served up by the computing environment203and/or other servers. To this end, the client application261may comprise, for example, a service client, a browser, a dedicated application, etc. The client device206may be configured to execute applications beyond the client application261such as, for example, email applications, social networking applications, word processors, spreadsheets, and/or other applications.

Continuing toFIG.2B, shown is a networked environment262that encompasses a plurality of fault containers263according to various embodiments. In various scenarios, the networked environment262corresponds to a cloud provider network or a distributed organizational network. The networked environment262is made up of a plurality of fault containers263that individually correspond to portions of the networked environment262that are configured to fail independently of one another. That is to say, if a particular fault container263experiences a malfunction or goes offline, resources in the other fault containers263should continue to operate as normal. To this end, the resources in each fault container263may be largely duplicative of each other fault container263to allow for this continued operation. The fault containers263may individually correspond to a region, a local zone, an availability zone, a data center, an edge location, or other network subdivision.

In this non-limiting example, five fault containers263a,263b,263c,263d, and263eare shown, but other numbers of fault containers263may be present in other examples. Each of the fault containers263has a respective instance of an allocation management service214a,214b,214c,214d, or214eand a respective copy of an allocation data structure265a,265b,265c,265d, or265e. The allocation data structures265may correspond to prefix allocation trees220(FIG.2A) as previously described or other data structures that track network address allocations. In one implementation, the respective allocation data structures265are maintained in a respective distributed hash table in the respective fault container263. The respective distributed hash table may include one or more replicas within the fault container263to provide for data integrity and high availability.

Communication between the instances of the allocation management service214may be organized such that one particular instance of the allocation management service214is designated as a leader, primary, or root, while the other instances are considered a follower, secondary, or leaf. In this example, the allocation management service214amay be the leader instance. For example, an administrative user may manually designate the allocation management service214aas a leader instance. In some cases, the leader instance designation may change over time, or the leader instance may be chosen specifically based upon compliance rules relating to data sovereignty, privacy, security, and so forth.

In some implementations, a tree-like hierarchy may be used, such that there is one leader instance, but some follower instances may act as intermediate nodes for other follower instances. For example, the allocation management service214emay communicate with the allocation management service214aby way of the allocation management service214d. Likewise, the allocation management service214dmay suballocate a subportion of its own portion of network address space to the allocation management service214e, similarly to how the leader instance the allocation management service214ahas allocated a portion of address space to the allocation management service214d.

The allocation management service214aassigns respective portions of network address space267to itself and to the other allocation management services214b,214c,214d, and214e. The portions of the network address space267are non-overlapping and may be different sizes based upon expected demand for network addresses in the corresponding fault containers263. The respective portions of the network address space267may be top-level nodes246(FIG.2A) in a prefix allocation tree220.

In this regard, the portions of the network address space267may be manually configured as to size or may be automatically determined based upon one or more metrics indicating expected demand in the fault container263, such as network address assignment velocity, a quantity of machine instances, historical usage patterns, and so on. In one embodiment, the leader instance provides an additional portion of the network address space267upon a remaining quantity of network address blocks assigned to the corresponding fault container263falling below the threshold. For example, the respective instance of the allocation management service214may request additional network address space upon determining that the remaining quantity of network address blocks has fallen below the threshold.

A respective instance of the allocation management service214allocates network address blocks254(FIG.2A) from within its designated portion of network address space267to requestors within its corresponding fault container263. Even if the leader instance goes offline, other instances of the allocation management service214can continue allocating address blocks254. In some scenarios, a particular instance of the allocation management service214in a first fault container263may function as a failover for another instance of the allocation management service214in a second fault container263using particular address space designated for failover. The respective instance of the allocation management service214can perform other operations using the address allocation API215(FIG.2A) including releasing address blocks254, setting attributes251(FIG.2A), and tree management functions222(FIG.2A).

The respective allocation data structures265are updated by the respective instances of the allocation management service215as these operations are performed. A follower instance of the allocation management service214periodically and asynchronously sends a snapshot245of the allocation data structure265to the leader instance (or an intermediate instance) of the allocation management service214so that the leader instance (or the intermediate instance) may generate a global consistent snapshot245from the various snapshots245. The global consistent snapshot245may be generated from the snapshots245using techniques described in U.S. patent application Ser. No. 17/491,429, entitled “ASYNCHRONOUS CONSISTENT SNAPSHOTS IN A DISTRIBUTED SYSTEM,” and filed on Sep. 30, 2021, which is incorporated herein by reference in its entirety. The leader instance can then respond to queries such as the find by attribute function230(FIG.2A) and so on with reference to the global consistent snapshot245. In some cases, each of the follower instances may also maintain a global consistent snapshot245, as the leader instance may propagate the snapshots245for ingestion by the follower instances. In other embodiments, the leader instance may maintain a global snapshot that is not specifically a consistent snapshot245.

When a fault container263goes offline, it may be important not to build up a queue of incoming requests from other fault containers263that would overwhelm the services in the fault container263that are coming back online. In this regard, if the leader instance of the allocation management service214returns online, the leader instance may be configured to process only a most recent snapshot245from each of the follower instances, while ignoring previous snapshots245from the respective follower instances. Also, the follower instances of the allocation management service214may be configured to send the data for the snapshots245to the leader instance at a predictable rate, such as a constant rate. In some implementations, the predictable rate may be a maximum rate for sending the snapshots245. In some cases, the allocation management service214may be configured to pad the data files corresponding to the snapshots245with filler data to ensure that the snapshots245are sent at a maximum data rate or predictable data rate.

Moving now toFIG.2C, shown is an example transaction state machine270that may be used for assignments of network address space to different fault containers263(FIG.2B) according to one or more embodiments. In making cross-fault container network address allocations, it is desired that the allocation management service214never accidentally allocate overlapping network address space to two different targets. Also, if an allocation of a portion of network address space267(FIG.2B) is incomplete (e.g., the leader instance goes offline after reserving the portion of network address space267but before finalizing the assignment and notifying the follower instance to which the portion of network address space267is to be assigned), then the portion of network address space267should be reclaimed, either by a roll forward action or a roll back action.

Once an assignment of the portion of network address space267is finalized to a follower instance of the allocation management service214, additional communication between the follower instance and the leader instances is not necessary to allow further suballocations from the portion of network address space267. In some examples, no quorum or consensus protocol is needed to reassess the status of the portion of network address space267once the assignment is complete. It may be desirable to transactionally allocate across fault containers263without timestamp-based heuristics to clean up abandoned transactions.

The transaction state machine270has three states: open272, complete274, and cancelled276. Open272is the initial state. Complete274and cancelled276are final states, and open272has transitions either to complete274or cancelled276. A compare-and-swap function may be used to set the transaction state either to complete274or cancelled276in an atomic operation.

Turning now toFIG.2D, shown is a flowchart that provides one example of the operation of a portion of the allocation management service214according to various embodiments. It is understood that the flowchart ofFIG.2Dprovides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the allocation management service214as described herein. As an alternative, the flowchart ofFIG.2Dmay be viewed as depicting an example of elements of a method implemented in the computing environment203(FIG.2A) according to one or more embodiments.

Beginning with box282, the allocation management service214generates a transaction identifier in order to allocate or assign a portion of network address space267(FIG.2B) from a source pool to a destination fault container263(FIG.2B). In box284, the allocation management service214inserts an open transaction (with a state of open272(FIG.2C) in a transaction state machine270(FIG.2C)) into an allocation data structure265(FIG.2B) of a target fault container263.

In box286, the allocation management service214allocates a portion of network address space267from a source network space. This may be an atomic operation using the transaction identifier as metadata on the allocation record. The portion of network address space267may be specifically identified or may be identified based upon address block size. In box288, the allocation management service214inserts the portion of network address space267into the destination network space in the allocation data structure265of the destination fault container263, using the transaction identifier as metadata on the allocation record.

In box290, the allocation management service214performs an atomic compare-and-swap operation to set the transaction record identified by the transaction identifier to the complete274(FIG.2C) state in the allocation data structure265in the destination fault container263. At this point, the transaction is logically committed. Otherwise, if a problem is detected, such as a destination portion of network address space267being deleted or otherwise becoming unavailable between boxes286and288, the agent can automatically rule back the transaction by comparing-and-swapping the transaction record to the cancelled276(FIG.2C) state.

In box292, the allocation management service214performs an atomic compare-and-swap operation to remove the transaction record identified by the transaction identifier in the allocation data structure265in the destination fault container263. In box294, the allocation management service214performs an atomic compare-and-swap operation to remove the transaction record identified by the transaction identifier in the allocation data structure265in the source fault container. Thereafter, the operation of the operation of the portion of the allocation management service214ends.

In an alternative embodiment, the allocation management service214may employ a two-phase commit protocol in lieu of use of a compare-and-swap operation with the transaction state machine270.

Referring next toFIG.3A, shown is a flowchart that provides one example of the operation of a portion of the address allocation API215according to various embodiments. It is understood that the flowchart ofFIG.3Aprovides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the address allocation API215as described herein. As an alternative, the flowchart ofFIG.3Amay be viewed as depicting an example of elements of a method implemented in the computing environment203(FIG.2A) according to one or more embodiments.

Beginning with box303, the address allocation API215creates a prefix allocation tree220(FIG.2A) with a particular top-level address block254(FIG.2A). The particular top-level address block254may be assigned to a corresponding instance of an allocation management service214(FIG.2A) by a leader instance of the allocation management service214. Creating the prefix allocation tree220can involve using one or more tree management functions222(FIG.2A) to create the prefix allocation tree220and then a function to insert a root node246(FIG.2A) or other node246with a top-level address block254that is initially marked free and which can be subdivided or suballocated.

In box306, the address allocation API215receives a request to allocate a particular network address block254via the allocate function223(FIG.2A). The request may indicate a network prefix in CIDR notation for the particular network address block254and/or a prefix length (e.g., size) for the address block254to be allocated. The request may also specify one or more attributes251(FIG.2A) for the address block254to be allocated, which may include arbitrary user-specified attributes251. In some scenarios, the request to allocate may specify a list of address blocks254that should not be used to fulfill the allocation. For example, problems may occur if a customer wishes to connect two networks and the networks have overlapping address blocks254. If two devices in a TCP/IP network have the same IP address, then TCP/IP generally does not function correctly, and similar problems arise if two networks in a TCP/IP internetwork have the overlapping address blocks.

In box309, the address allocation API215via the allocate function223updates the prefix allocation tree220to indicate that the particular network address block254corresponding to the prefix is allocated instead of free and to associate the attributes251with the particular network address block254. Updating the prefix allocation tree220may include updating the free indicator258(FIG.2A) to indicate that the address block254is not completely free. If the requested allocation is smaller in size or differs from the top-level address block254, the allocate function223may request via the shatter function225(FIG.2A) to shatter the address block254in order to make a suballocation and shatter the address block254into a plurality of child address blocks255(FIG.2A). The shatter request may indicate directly or indirectly a quantity of the child address blocks255into which the particular network address block254is to be shattered. When a child address block255is created, a value in the vector clock257(FIG.2A) for the node246can be initialized. In some cases as described, child nodes256(FIG.2A) may be created when a node246cannot store additional child address blocks255of a smaller size than permissible.

The shatter process can be repeated recursively multiple times until the address block254of an appropriate size is generated. In some instances, the shatter process does not need to be invoked, where address blocks254of the desired size were previously created through shattering. In scenarios where a specific network address block254is not identified in the request, free space including the address block254may be found from the attribute index247using the find by attribute function230(FIG.2A).

When the particular network address block254is identified, the free indicator258is updated to indicate that it is no longer a completely free part of another address block. Further, other free indicators258of parent network address blocks254and/or child network address blocks255(and potentially child nodes256) may need to be updated. Each change or mutation will result in incrementing a respective value in the vector clock257of the network address block254that is changed, and the updated value in the vector clock257will be propagated through the prefix allocation tree220for the relevant nodes246(child nodes256and a parent node246). In various implementations, when a mutation happens to several nodes246, the nodes' vector clocks'257values are each updated following the elementwise-max approach in such a way that a vector clock257contains entries for this node's address block254, its parent address block, and the child address blocks. Stated another way, a given node's address block254may not appear in any grandchild node's or grandparent node's vector clock257, nor that of any sibling or cousin node-a given node's address block254may only appear in its parent's and children's vector clocks257(as well as its own vector clock257).

In box312, the address allocation API215returns an allocation identification for the particular network address block254that has been allocated. If allocation were to fail, the address allocation API215may instead return an exception. Thereafter, the operation of the portion of the address allocation API215ends.

Continuing toFIG.3B, shown is a flowchart that provides one example of the operation of a portion of the asynchronous workflows216according to various embodiments. It is understood that the flowchart ofFIG.3Bprovides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the asynchronous workflows216as described herein. As an alternative, the flowchart ofFIG.3Bmay be viewed as depicting an example of elements of a method implemented in the computing environment203(FIG.2A) according to one or more embodiments.

Beginning with box315, the update attribute index workflow240(FIG.2A) is asynchronously executed to update the attribute index247(FIG.2A) based on data in the prefix allocation tree220(FIG.2A). That is to say, when a prefix allocation tree220is mutated, changes to the attributes251(FIG.2A) of the nodes246(FIG.2A) may not be synchronously propagated to the attribute index247. Thus, the update attribute index workflow240may be executed later, potentially with a lower priority, to update the attribute index247.

In box318, the snapshot workflow242(FIG.2A) is asynchronously executed to generate a consistent snapshot245(FIG.2A) of the prefix allocation trees220. In so doing, the snapshot workflow242may compare copies of a vector clock257(FIG.2A) for a particular address block254(FIG.2A) to ensure that the copies are in agreement as to the value of the vector clock257. If the copies are not in agreement, the data is not yet consistent and a snapshot245cannot yet be produced. The snapshot workflow242may retry until a consistent snapshot245can be produced, as indicated by the agreement of values of the copies of the vector clock257.

In box321, the consolidate free space workflow241(FIG.2A) is asynchronously executed to consolidate free space in a prefix allocation tree220. For example, if two adjacent address blocks254are released in separate transactions, the free indicator258(FIG.2A) of the parent address block254should be updated to be completely free. The consolidate free space workflow241reviews the consistent snapshot245to determine address blocks254that have become completely free, which may be a recursive process moving up within the prefix allocation tree220to successively mark free potentially multiple parent address blocks254.

In box324, the cleanup workflow243(FIG.2A) may perform various clean up tasks such as deleting attributes251in attribute index items259(FIG.2A) that are no longer referenced or ensuring that invariants are respected in the prefix allocation tree220. The operation of the asynchronous workflows216may proceed continuously or they may be executed periodically. In some instances, each of the asynchronous workflows216may be launched in response to user requests rather than automatically.

Referring next toFIG.3C, shown is a flowchart that provides one example of the operation of a portion of the address allocation API215according to various embodiments. It is understood that the flowchart ofFIG.3Cprovides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the address allocation API215as described herein. As an alternative, the flowchart ofFIG.3Cmay be viewed as depicting an example of elements of a method implemented in the computing environment203(FIG.2A) according to one or more embodiments.

Beginning with box327, the address allocation API215receives a request to release a particular address block254(FIG.2A) via a release function224(FIG.2A). In box330, the release function224updates the prefix allocation tree220(FIG.2A) to indicate that the address block254is free instead of allocated via updating the free indicator258. The release function224may also update child address blocks255(FIG.2A) and child nodes256(FIG.2A) of the particular address block254to indicate that those address blocks254are also free. In box333, the release function224returns the result of releasing the particular address block254, which may be a Boolean value indicating success or failure. Thereafter, the operation of the portion of the address allocation API215ends.

Continuing toFIG.3D, shown is a flowchart that provides one example of the operation of a portion of the shatter function225according to various embodiments. It is understood that the flowchart ofFIG.3Dprovides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the shatter function225as described herein. As an alternative, the flowchart ofFIG.3Dmay be viewed as depicting an example of elements of a method implemented in the computing environment203(FIG.2A) according to one or more embodiments.

Beginning with box336, the shatter function225receives a request to shatter an allocation of a particular address block254(FIG.2A), identified by an allocation identifier, into parts. In box339, the shatter function225divides the particular address block254into a shatter set of suballocations of child address blocks255(FIG.2A). For example, if there is an allocation “alloc-123” for “10.0.0.0/8” and the shatter function225is invoked with the allocation identifier “alloc-123” and the parameter “10.1.2.3/32” to shatter out a “/32,” then the result will be 25 allocations: one for the “/32” requested, and one for each of the 24 address blocks254in the shatter set. In box342, the shatter function225may return allocation identifiers for each of the suballocations. Thereafter, the operation of the portion of the shatter function225ends.

Referring next toFIG.3E, shown is a flowchart that provides one example of the operation of a portion of the allocation management service214according to various embodiments. It is understood that the flowchart ofFIG.3Eprovides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the allocation management service214as described herein. As an alternative, the flowchart ofFIG.3Emay be viewed as depicting an example of elements of a method implemented in the computing environment203(FIG.2A) according to one or more embodiments.

Beginning with box345, a leader instance of the allocation management service214assigns respective portions of network address space267(FIG.2B) to each of a plurality of instances of the allocation management service214in a plurality of fault containers263(FIG.2B). The assignment may be based upon manual configuration or an automatic determination based at least in part on an estimated demand for network addresses in a portion of the network having the corresponding fault container263. The assignment may use a two-phase commit protocol or a compare-and-swap operation along with the approach illustrated inFIGS.2C and2D.

In box347, the leader instance of the allocation management service214generates allocations of address blocks254(FIG.2A) from the respective portion of the network address space267. In box349, the follower instance(s) of the allocation management service214generate allocations of address blocks254from the respective portion(s) of the network address space267. It is noted that these allocations (or suballocations) may occur irrespective of the operational status of the leader instance. Subsequently, particular network address blocks254may be released and made available for reallocation.

In box351, the follower instance(s) of the allocation management service214asynchronously or periodically send respective snapshots245(FIG.2B) of their respective allocation data structure265(FIG.2B) to the leader instance of the allocation management service214. The follower instance(s) may send the snapshots245at a constant or predictable rate, in some cases padding data files to a fixed or maximum data size. The leader instance in turn is able to generate a globally consistent snapshot245from the set of snapshots245from the respective follower instances. Thereafter, the operation of the portion of the allocation management service214ends.

With reference toFIG.4, shown is a schematic block diagram of the computing environment203according to an embodiment of the present disclosure. The computing environment203includes one or more computing devices400. Each computing device400includes at least one processor circuit, for example, having a processor403and a memory406, both of which are coupled to a local interface409. To this end, each computing device400may comprise, for example, at least one server computer or like device. The local interface409may comprise, for example, a data bus with an accompanying address/control bus or other bus structure as can be appreciated.

Stored in the memory406are both data and several components that are executable by the processor403. In particular, stored in the memory406and executable by the processor403are the allocation management service214, the address allocation API215, the asynchronous workflows216, the data storage service218, and potentially other applications. Also stored in the memory406may be a data store212and other data. In addition, an operating system may be stored in the memory406and executable by the processor403.

Also, the processor403may represent multiple processors403and/or multiple processor cores and the memory406may represent multiple memories406that operate in parallel processing circuits, respectively. In such a case, the local interface409may be an appropriate network that facilitates communication between any two of the multiple processors403, between any processor403and any of the memories406, or between any two of the memories406, etc. The local interface409may comprise additional systems designed to coordinate this communication, including, for example, performing load balancing. The processor403may be of electrical or of some other available construction.

Although the flowcharts ofFIGS.2D-3Eshow a specific order of execution, it is understood that the order of execution may differ from that which is depicted. For example, the order of execution of two or more blocks may be scrambled relative to the order shown. Also, two or more blocks shown in succession inFIGS.2D-3Emay be executed concurrently or with partial concurrence. Further, in some embodiments, one or more of the blocks shown inFIGS.2D-3Emay be skipped or omitted. In addition, any number of counters, state variables, warning semaphores, or messages might be added to the logical flow described herein, for purposes of enhanced utility, accounting, performance measurement, or providing troubleshooting aids, etc. It is understood that all such variations are within the scope of the present disclosure.

Further, any logic or application described herein, including the allocation management service214, the address allocation API215, the asynchronous workflows216, and the data storage service218, may be implemented and structured in a variety of ways. For example, one or more applications described may be implemented as modules or components of a single application. Further, one or more applications described herein may be executed in shared or separate computing devices or a combination thereof. For example, a plurality of the applications described herein may execute in the same computing device400, or in multiple computing devices400in the same computing environment203.