# US 2014/0156847 A1 · Service Allocation in a Distributed Computing Platform > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0156847 A1 - Document ID: US20140156847A1 - Status: Published application - Kind: A1 - Application number: 13/705,039 - Filed: 2012-12-04 - Published: 2014-06-05 - Earliest claimed: 2012-12-04 - Assignees: Microsoft Corporation - Applicants: Microsoft Corporation - Inventors: Thomas Moscibroda; Zhengping Qian; Mark Eugene Russinovich; Xiangyao Yu; Jiaxing Zhang; Feng Zhao - Web page: https://patentgrep.com/patent/US20140156847A1 ## CPC - G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)} - G06F 8/60: Software deployment - G06F 8/65: Updates (security arrangements therefor G06F21/57) - G06F 9/5072: {Grid computing} - H04L 67/1095: Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract The techniques and arrangements described herein provide for updating services, host operating systems and other applications while satisfying update domain constraints. In some examples, one or more controller modules may maintain a data structure including a plurality of server update domains, each server update domain including a set of machines of a plurality of machines of a distributed computing system which may be concurrently updated. The one or more controller modules may allocate the plurality of instances to the plurality of machines such that a number of server update domains is minimized. ## Claims ### Claim 1 A distributed computing system comprising: one or more computer-readable storage media storing computer-executable instructions of a controller module executed by one or more processors to: maintain a data structure including a plurality of server update domains, each server update domain including a set of machines of a plurality of machines which may be concurrently updated, the plurality of machines hosting a plurality of instances of each of a plurality of services, each service having a plurality of respective update domains, each instance being assigned to one of the plurality of update domains of the respective service and wherein an allocation of instances to the plurality of machines is constrained such that each machine of the plurality of machines may not host instances from different update domains of the same service and an updating of the distributed computing system is constrained such that different machines hosting instances of different update domains of the same service may not be concurrently updated; and allocate the plurality of instances to the plurality of machines, the controller module allocating the instances to the plurality of machine such that a number of server update domains is minimized by, for at least one instance, determining at least one machine of the plurality machines that, if allocated the at least one instance, may be assigned to a lowest server update domain based on an ordered identification system of the server update domains. ### Claim 2 (depends on 1) The distributed computing system of claim 1, wherein the update domains of each service are identified using the ordered identification system of the server update domains and the controller allocates at least one instance of a service of the plurality of services to a machine of a server update domain with an identifier that is the same as a identifier of the update domain of the instance. ### Claim 3 (depends on 1) The distributed computing system of claim 1, wherein the controller module maintains, for each service of the plurality of services, a mapping from each update domain of the service to at least one server update domain. ### Claim 4 (depends on 3) The distributed computing system of claim 3, wherein the mapping from each update domain of the service to the at least one server update domain indicates one or more server update domains that include at least one machine hosting instances of the update domain of the service. ### Claim 5 (depends on 1) The distributed computing system of claim 1, wherein the controller module controls an updating of the plurality of machines such that the machine are updated in an order based at least in part on the server update domains. ### Claim 6 A computer-implemented method comprising: under control of one or more processors configured with executable instructions, allocating a plurality of instances of each of a plurality of services to a plurality of machines of a distributed computing system, each service having a plurality of respective domains, each instance being assigned to one of the plurality of domains of the respective service and wherein the allocating of instances to the plurality of machines is constrained such that each machine of the plurality of machines may not host instances from different domains of the same service and an operation of the distributed computing system is constrained such that different machines hosting instances of different domains of the same service may not be concurrently unavailable; and maintaining a data structure including a plurality of server domains, each server domain including a set of machines of the plurality of machines which may be concurrently be unavailable. ### Claim 7 (depends on 6) The computer-implemented method of claim 6, wherein each machine of the plurality of machines that hosts an instance of the plurality of services in assigned to one of the server domains. ### Claim 8 (depends on 6) The computer-implemented method of claim 6, wherein the allocating is performed such that a number of server domains is minimized. ### Claim 9 (depends on 8) The computer-implemented method of claim 8, wherein the number of server domains is minimized by, for at least one instance, determining at least one machine of the plurality machines that, if allocated the at least one instance, may be assigned to a lowest server domain based on an ordered identification system of the server domains. ### Claim 10 (depends on 6) The computer-implemented method of claim 6, further comprising: maintaining, for at least one service of the plurality of services, a mapping from each domain of the service to at least one server domain. ### Claim 11 (depends on 10) The computer-implemented method of claim 10, wherein the mapping from each domain of the service to the at least one server domain indicates one or more server domains that include at least one machine hosting instances of the domain the service. ### Claim 12 (depends on 6) The computer-implemented method of claim 6, further comprising: updating the plurality of machines such that the machine are updated in an order based at least in part on the server domains. ### Claim 13 One or more computer-readable storage media storing computer-executable instructions that, when executed on one or more processors, perform acts comprising: allocating a plurality of instances of each of a plurality of services to a plurality of machines of a distributed computing system, each service having a plurality of respective update domains, each instance being assigned to one of the plurality of update domains of the respective service and wherein the allocating of instances to the plurality of machines is constrained such that each machine of the plurality of machines may not host instances from different update domains of the same service and an updating of the distributed computing system is constrained such that different machines hosting instances of different update domains of the same service may not be concurrently updated; and wherein the allocating is performed such that a number of groups of different machines that may be updated concurrently to update the plurality of machines is minimized. ### Claim 14 (depends on 13) The one or more computer readable storage media of claim 13, the acts further comprising: maintaining a data structure including the groups of different machines that may be updated concurrently to update the plurality of machines. ### Claim 15 (depends on 13) The one or more computer readable storage media of claim 13, wherein each machine of the plurality of machines that hosts an instance of the plurality of services in assigned to one of the groups. ### Claim 16 (depends on 13) The one or more computer readable storage media of claim 13, wherein the allocating is performed to minimize the number of groups by, when a first instance is to be allocated to a machine of the plurality of machines: if a first machine that is available to host the first instance is also part of a group hosting at least one second instance of the same update domain of the service as the instance to be allocated, allocating the instance to be allocated to the first machine. ### Claim 17 (depends on 13) The one or more computer readable storage media of claim 13, wherein the allocating is performed to minimize the number of groups by, when a first instance is to be allocated to a machine of the plurality of machines: if there is no first machine that is available to host the first instance and is also part of a group hosting at least one second instance of the same update domain of the service as the first instance and there is a second machine of the plurality of machines not currently hosting instances of the plurality of services, allocating the first instance to the second machine. ### Claim 18 (depends on 13) The one or more computer readable storage media of claim 13, wherein the allocating is performed to minimize the number of groups by, when a first instance is to be allocated to a machine of the plurality of machines: if there is no first machine that is available to host the first instance and is also part of a group hosting at least one second instance of the same update domain of the service as the first instance, there is no second machine of the plurality of machines not currently hosting instances of the plurality of services, and there is a third machine which may host the first instance without incurring an update domain constraint violation, allocating the first instance to the third machine. ### Claim 19 (depends on 13) The one or more computer readable storage media of claim 13, wherein the allocating is performed to minimize the number of groups by, when a first instance is to be allocated to a machine of the plurality of machines: if there is no first machine that is available to host the first instance and is also part of a group hosting at least one second instance of the same update domain of the service as the first instance, there is no second machine of the plurality of machines not currently hosting instances of the plurality of services, and there are a plurality of third machines which may host the first instance without incurring an update domain constraint violation, determining at least one third machine that, if allocated the first instance, may be assigned to a lowest group identifier based on an ordered identification system of the groups; and allocating the first instance to the determined machine. ### Claim 20 (depends on 14) The one or more computer readable storage media of claim 14, the acts further comprising: updating the plurality of machines such that the machines are updated in an order based at least in part on the groups of different machines included in the data structure.