Patent Publication Number: US-9430255-B1

Title: Updating virtual machine generated metadata to a distribution service for sharing and backup

Description:
BACKGROUND 
     This specification relates to cloud computing. 
     Cloud computing is network-based computing in which typically large collections of servers housed in data centers or “server farms” provide computational resources and data storage as needed to remote end users. Some cloud computing services provide access to software applications such as word processors and other commonly used applications to end users who interface with the applications through web browsers or other client-side software. Users&#39; electronic data files are usually stored in the server farm rather than on the users&#39; computing devices. Maintaining software applications and user data on a server farm simplifies management of end user computing devices. Some cloud computing services allow end users to execute software applications in virtual machines. 
     SUMMARY 
     A virtual machine can write metadata to a metadata service as it is running. The written metadata can be used to persist the state of the virtual machine when restarted on a different host machine. 
     In general, one innovative aspect of the subject matter described in this specification can be embodied in methods that include the actions of initializing a first virtual machine (VM) on a first host machine using one or more elements of user-specified initialization metadata; receiving a notification that the first VM has published one or more elements of VM-generated metadata; obtaining the one or more elements of VM-generated metadata; receiving a request for the one or more elements of VM-generated metadata; and providing the one or more elements of VM-generated metadata in response to the request. Other embodiments of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods. A system of one or more computers can be configured to perform particular operations or actions by virtue of having software, firmware, hardware, or a combination of them installed on the system that in operation causes or cause the system to perform the actions. One or more computer programs can be configured to perform particular operations or actions by virtue of including instructions that, when executed by data processing apparatus, cause the apparatus to perform the actions. 
     The foregoing and other embodiments can each optionally include one or more of the following features, alone or in combination. Receiving the request for the one or more elements of VM-generated metadata comprises receiving the request from a user-device external to a datacenter hosting the first VM. Receiving the request for the one or more elements of VM-generated metadata comprises receiving the request from a second VM hosted in a datacenter hosting the first VM. The actions include receiving an indication that the first VM has failed; initializing a second VM on a different second host machine; and configuring the second VM using the one or more elements of VM-generated metadata. The actions include overwriting one or more elements of the user-specified initialization metadata with one or more elements of VM-generated metadata from the first VM. The VM-generated metadata represents a state of the first VM. Initializing a second VM on a different second host machine comprises resuming the state of the first VM in the second VM. The VM-generated metadata comprises one or more attributes of an application running within the first VM. The actions include configuring a second VM using the one or more elements of VM-generated metadata including: starting an application on the second VM; and restoring a state of the application to a previous state using the one or more elements of VM-generated metadata. The first VM intermittently publishes one or more elements of VM-generated metadata to a metadata service. 
     In general, another innovative aspect of the subject matter described in this specification can be embodied in methods that include the actions of initializing a first virtual machine (VM) on a first host machine using user-specified metadata; receiving one or more elements of VM-generated metadata from the first VM; receiving an indication that the first VM has failed; initializing a second VM on a different second host machine; and configuring the second VM using the one or more elements of VM-generated metadata. Other embodiments of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods. 
     The foregoing and other embodiments can each optionally include one or more of the following features, alone or in combination. The user-specified metadata includes initialization metadata. After receiving the one or more elements of VM-generated metadata from the first, the method further comprises overwriting one or more elements of the initialization metadata with the one or more elements of VM-generated metadata. Initializing the second VM on the different second different host machine comprises initializing the second VM using the user-specified metadata. Initializing the second VM using the one or more retrieved elements of VM-generated metadata comprises restoring a state of the first VM. The actions include receiving VM-generated metadata defining the state of an application running within the first VM; starting the application on the second VM; and restoring a state of the application using the VM-generated metadata. The actions include intermittently providing one or more elements of metadata for the first VM to a metadata service. 
     Particular embodiments of the subject matter described in this specification can be implemented so as to realize one or more of the following advantages. Persisting VM metadata using a metadata service can provide of level of VM persistence without requiring the overhead of persistent disks. The lower storage space requirements for metadata allow for more frequent updates of VM state to the metadata service. Storing VM metadata in a writable metadata service provides for VMs and guest applications that expand beyond the lifetime of a single VM instance. Storing VM-generated metadata in a writable metadata service allows a current state of the VM to be stored and persisted outside of a particular host machine hosting the VM. This allows other entities inside or outside the system to obtain an up-to-date view of the state of the VM without querying the VM itself. In addition, VM&#39;s themselves can determine and communicate their own roles in a distributed system, allowing for the design of more dynamic systems. Storing the state of the VM in the metadata service also allows persistence of the VM and migration of the VM from one host machine to another. 
     The details of one or more embodiments of the subject matter of this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic illustration of an example virtual machine system. 
         FIG. 2  is a sequence diagram of using a metadata service to store VM metadata. 
         FIG. 3  is a flow chart of an example process for obtaining VM metadata. 
         FIG. 4  is a flow chart of an example process for restarting a VM using metadata. 
     
    
    
     Like reference numbers and designations in the various drawings indicate like elements. 
     DETAILED DESCRIPTION 
       FIG. 1  is a schematic illustration of an example virtual machine system  100 . The system  100  includes one or more host machines such as, for example, host machine  102  and host machine  104 . Generally speaking, a host machine is one or more data processing apparatus such as rack mounted servers or other computing devices. The data processing apparatus can be in different physical locations and can have different capabilities and computer architectures. Host machines can communicate with each other through an internal data communications network  116 . The internal network can include one or more wired, e.g., Ethernet, or wireless, e.g., WI-FI, networks, for example. In some implementations the internal network  116  is an intranet. Host machines can also communicate with devices on external networks, such as the Internet  122 , through one or more gateways which are data processing apparatus responsible for routing data communication traffic between the internal network  116  and the external network  122 . Other types of external networks are possible. 
     Each host machine  102 ,  104 , executes a host operating system  106 ,  108 . A host operating system  106 ,  108 , manages host machine resources. In this example, host operating systems  106 ,  108 , run software, e.g. a virtual machine monitor (“VMM”) or a hypervisor, that virtualizes the underlying host machine hardware and manages concurrent execution of one or more virtual machines (“VMs”). In this example, the host operating system  106  manages two VMs, VM  110  and VM  112 , while a different host operating system  108  manages a single VM  114 . VMs can be migrated from one host machine to another host machine. In addition, a single VM can be managed by multiple host machines. A host machine can, in general, manage multiple virtual machines, however, the quantity may be limited based on physical resources of the host machine. 
     Each VM provides an emulation of a physical hardware system which may, but need not, be based on the host machine hardware architecture. The simulated version of the hardware is referred to as virtual hardware, e.g., virtual hardware  110   a ,  112   a , and  114   a . Software that is executed by the virtual hardware is referred to as guest software. In some implementations, guest software cannot determine if it is being executed by virtual hardware or by a physical host machine. If guest software executing in a VM, or the VM itself, is compromised, malfunctions, or aborts, other VMs executing on the host machine may not be affected. A host machine&#39;s microprocessor(s) can include processor-level mechanisms to enable virtual hardware to execute software applications efficiently by allowing guest software instructions to be executed directly on the host machine&#39;s microprocessor without requiring code-rewriting, recompilation, or instruction emulation. 
     Each VM, e.g., VMs  110 ,  112 , and  114 , is allocated a set of virtual memory pages from the virtual memory of the underlying host operating system and is allocated virtual disk blocks from one or more virtual disk drives for use by the guest software executing on the VM. For example, host operating  106  allocates memory pages and disk blocks to VM  110  and VM  112 , and host operating system  108  does the same for VM  114 . In some implementations, a given VM cannot access the virtual memory pages assigned to other VMs. For example, VM  110  cannot access memory pages that have been assigned to VM  112 . A virtual disk drive can be persisted across VM restarts. Virtual disk blocks are allocated on physical disk drives coupled to host machines or available over the internal network  116 , for example. In addition to virtual memory and disk resources, VMs can be allocated network addresses through which their respective guest software can communicate with other processes reachable through the internal network  116  or the Internet  122 . For example, guest software executing on VM  110  can communicate with guest software executing on VM  112  or VM  114 . In some implementations, each VM is allocated one or more unique Internet Protocol (IP) version 4 or version 6 addresses and one or more User Datagram Protocol (UDP) port numbers. Other address schemes are possible. The VM IP addresses are visible on the internal network  116  and, in some implementations, are visible on the Internet  122  if the addresses are advertised using a suitable routing protocol, for instance. 
     A VM&#39;s guest software can include a guest operating system, e.g., guest operating systems  110   b ,  112   b , and  114   b , which is software that controls the execution of respective guest software applications, e.g., guest applications  110   c ,  112   c , and  114   c , within the VM and provides services to those applications. For example, a guest operating system could be a version of the UNIX operating system. Other operating systems are possible. Each VM can execute the same guest operating system or different guest operating systems. In further implementations, a VM does not require a guest operating system in order to execute guest software applications. A guest operating system&#39;s access to resources such as networks and virtual disk storage is controlled by the underlying host operating system. 
     By way of illustration, and with reference to virtual machine  110 , when the guest application  110   c  or guest operating system  110   b  attempts to perform an input/output operation on a virtual disk, initiate network communication, or perform a privileged operation, for example, the virtual hardware  110   a  is interrupted so that the host operating system  106  can perform the action on behalf of the virtual machine  110 . The host operating system  106  can perform these actions with a process that executes in kernel process space  106   b , user process space  106   a , or both. 
     The kernel process space  106   b  is virtual memory reserved for the host operating system  106 &#39;s kernel  106   d  which can include kernel extensions and device drivers, for instance. The kernel process space has elevated privileges, sometimes referred to as “supervisor mode”; that is, the kernel  106   d  can perform certain privileged operations that are off limits to processes running in the user process space  106   a . Examples of privileged operations include access to different address spaces, access to special functional processor units in the host machine such as memory management units, and so on. The user process space  106   a  is a separate portion of virtual memory reserved for user mode processes. User mode processes cannot perform privileged operations directly. 
     In various implementations, a portion of VM network communication functionality is implemented in a communication process, e.g., communication process  106   c . In some implementations, the communication process executes in the user process space, e.g., user process space  106   a , of a host operating system, e.g., host operating system  106 . In other implementations, the communication process can execute in the kernel process space, e.g., kernel process space  106   d  of the host operating system. In yet further implementations, some portion of the communication process executes in the user process space and another portion executes in the kernel process space. 
     The system  100  includes an API server  120  that provides control and connectivity between users and VMs in the system  100 . For example, the API server  120  can receive commands from user device  124  over the Internet  122 , e.g. to start a VM in the system  100 . 
     The system  100  includes a metadata service  130  that manages and provides access to metadata for VMs in the system  100 . VMs in the system  100  can read their metadata from the metadata service  130  and can also write their metadata to the metadata service  130 . For example, a VM in the system can read from the metadata service  130  the name of the host machine on which it is running Metadata can be written to and read from the metadata service  130  using any appropriate network communications protocol. In some implementations, the read and write commands are implemented using conventional hypertext transfer protocol (HTTP) “GET” and “PUT” commands. 
     Generally, VMs read and write their own metadata using the metadata service  130 . However, a VM may also read metadata of other VMs and write metadata to be read by other VMs as well. A VM can query the metadata service  130  for its own metadata by specifying a unique VM identifier for the VM. The metadata service  130  can also identify a VM by the network address of the VM making the request. 
     The metadata service  230  can also store metadata for groups of VMs. For example, VMs can be grouped into a “project” with a project identifier. The metadata service  130  can receive and store metadata about the project, e.g. a project description, a number of VMs in the project, a list of VMs in the project, in addition to other types of metadata. VMs grouped into a project can also be assigned metadata that is common to all VMs in the project. For example, each VM in a particular project may store metadata that describes a VMs role, e.g. “front-end server.” 
     VMs in the same project can use the metadata service  130  to read status information of other VMs in the project. For example, a VM can query the metadata service  130  to read status information for all VMs in the project. A VM can also write its own status to the metadata service  130  for access by other VMs in the project. Thus, VMs can use the metadata service as a way to share state information with other VMs in the system  100 . 
     The metadata service  130  can be implemented as one or more computer programs installed on one or more computers in system  100 . The metadata service  130  can, for example, be installed on a particular host machine. The metadata service  130  can also run on a VM instance in the system  100 . Generally, the metadata service  130  will be located in the same datacenter as VMs that it services, although the metadata service can also be located elsewhere, for example, accessible over the Internet. 
       FIG. 2  is a sequence diagram of using a metadata service to store and publish VM metadata. In  FIG. 2 , the metadata service is used to provide startup metadata for a VM, preserve the state of the VM outside the VM itself, and to publish the state of the VM for access by other entities. 
     A user device  224  launches a VM by specifying startup metadata ( 202 ). Generally, starting a VM on a particular host machine includes specifying a VM image and VM initialization metadata. The VM image can include device drivers, application executables, kernel binaries, file system specifications, in addition to a variety of other files required to start a VM instance. 
     The VM metadata can include any attributes of a particular VM instance started from the VM image. Each element of metadata is a key-value pair. The key uniquely identifies a type of metadata. The value can be one or more pieces of data, for example, text strings. 
     Some examples of common VM metadata include a list of ephemeral and persistent disks associated with the VM, a VM description, a host machine domain, a geographic location of the VM, a VM configuration image name, a VM identifier, a VM type, a host machine type, a user identifier, tags associated with the VM, and Secure Shell (SSH) keys for communicating with the VM. 
     When a VM instance is starting, users can customize a VM by providing the VM with one or more elements of initialization metadata. The initialization metadata may also include startup scripts that specify packages to install and code to download or execute upon starting. 
     The API server  220  accepts the request to start the VM and writes the VM startup metadata to the metadata service  230  ( 204 ). Writing the VM startup metadata to the metadata service  230 , the newly started VM can access the metadata to configure itself. 
     The API server  220  launches a VM instance ( 206 ). The API server can for example, pass the VM image to a VMM running on host machine  206 . The VMM can then use the specified VM image to launch a VM instance on the host machine  206 . 
     The host machine  206  requests VM startup metadata from the metadata service  230  ( 208 ). Although some of the VM startup metadata can be specified in the VM image itself, the host machine  206  can also read the startup metadata that was written to the metadata service  230  through the API server  220 . 
     The host machine  206  receives startup metadata ( 212 ). After receiving the startup metadata, the host machine can fully initialize a VM instance running on host machine  206 . 
     The VM writes additional metadata to the metadata service  230  ( 214 ). In addition to user-specified initialization metadata, a VM itself may also generate metadata while it is running. For example, once a VM is fully booted, a startup script running on the VM can write metadata to the metadata service indicating that the VM has successfully started up. Without writing such metadata, it may be difficult for a user to determine the startup state of the VM. As another example, a VM instance may generate an SSH key to be used while other entities are communicating with the VM. The SSH key may generated after the VM has been running for some period of time. 
     VMs can generally write arbitrary key-value pairs to the metadata service  130 , although some special key names may be reserved or require specially-formatted data. The system  100  can define default values for some VM metadata elements. The default values can be overwritten by subsequent writes to the metadata service  130 . However, some metadata key-value pairs may be read-only, which prevents subsequent overwrites. 
     The metadata service  230  can be used to persist VM metadata, for example, when a VM is migrated from one host machine to another. Thus, a VM can preserve its current state by writing metadata to the metadata service  130 . In this context, metadata preserving the “state” of a VM can include metadata values sufficient to restart the VM on another host machine, including application-specific values for applications running within the VM. Thus, what metadata is sufficient to preserving the state of a VM depend on the particular task or VM implementation. 
     A VM can intermittently write metadata to the metadata service  230  to preserve its state from time to time. When the VM needs to be restarted on another host machine, the metadata written to the metadata service  230  can be obtained to restore the state of the VM on a second host machine. 
     Guest applications running on a VM, e.g. guest applications  106   c , can also be programmed to write their metadata to the metadata service  230  as a way of preserving state. Then, if a particular VM is migrated to a different host machine or rebooted, the VM can read application metadata stored in the metadata service to resume applications that were previously running on the VM. 
     The host machine  206  notifies the API server  220  that new metadata has been written to the metadata service  230  ( 216 ). For example, when a VM writes metadata to the metadata service  230 , the VMM hosting the VM can notify the API server that new metadata is available. Thus, the API server can be notified about new metadata published by the VM without intermittently querying the metadata service or the VM instance. In some implementations, the notification rate can be capped or buffered to avoid overloading the API server or abuse. 
     The API server  220  requests metadata from the metadata service  230  ( 218 ). The API server can maintain a partial or complete set of metadata for a particular VM for serving to other entities, which may be user devices outside a datacenter hosting the VM, e.g. user device  224 , or other VMs in the same datacenter. In response to the request, the metadata service  230  provides the requested metadata ( 222 ). 
     The user device  224  requests VM metadata from the API server  220  ( 226 ). The request for VM metadata can be part of a request for information about the specific VM generally, or as part of a request for information about a group of VMs. 
     In response to the request, the API server  220  provides the requested metadata to the user device  224  ( 228 ). Because the API server is notified by the VMM on host machine  206  when the VM generates new metadata, the API server can maintain a set of the most-recent metadata for access by the user device  224 . For example, metadata reflecting the startup state of the VM can be provided to the user device  224 , thus informing a user that the VM has successfully booted. 
       FIG. 3  is a flow chart of an example process  300  for obtaining VM metadata. In general, a first VM writes metadata to a metadata service. The metadata stored by the metadata service can then be used to provide metadata to other entities or to resume the first VM on a second host machine. The process  300  can be performed by an API server, e.g. the API server  120  as shown in  FIG. 1 . For convenience, the process  300  will be described as being performed by an appropriately programmed system of one or more computers. 
     The system initializes a VM on a first host machine using user-specified metadata ( 210 ). As described above, a VM can be started and configured using a VM image and initialization metadata, which can be provided through a startup script or can be provided manually by a user. 
     The system receives a notification of VM-generated metadata from the VM ( 220 ). After the VM has started, the VM can communicate with a metadata service to provide arbitrary key-value pairs of metadata. The VM-generated metadata can also represent the state of the VM or of applications running within the VM. As described above, the notification can be received from a VMM hosting the VM. The notification can also be received from the metadata service. 
     The system obtains the VM-generated metadata ( 330 ). Upon receiving a notification of new VM metadata, the system can obtain an up-to-date view of the VM metadata. 
     The system receives a request for the one or more elements of VM-generated metadata ( 340 ). For example, the system can receive a request over the Internet from a user device of a user that started the VM. The user device can be external to a datacenter hosting the VM. The system can also receive the request from entities within the same datacenter. For example, the system can receive a request for the up-to-date VM metadata from other VMs in the datacenter. 
     The system provides one or more elements of VM-generated metadata in response to the request ( 350 ). The system can thus provide a view of the metadata and state of the VM without interrupting operation of or querying the VM itself. 
     In some implementations, the elements of VM-generated metadata are partitioned into groups that are only accessible by particular entities. For example, some elements of VM metadata may be readable by only a single VM, only a group of VMs in a particular role, or may be globally readable. The system can thus determine whether to provide the VM metadata based on the entity making the request. 
       FIG. 4  is a flow chart of an example process  400  for restarting a VM using metadata. In general, a first VM writes its metadata to a metadata service. The metadata stored by the metadata service can then be used to resume the first VM on a second host machine. For convenience, the process  400  will be described as being performed by an appropriately programmed system of one or more computers. 
     The system initializes a first VM on a first host machine using user specified metadata ( 410 ). As described above, a VM can be configured using initialization metadata provided through a custom VM image, a startup script, or provided manually by a user. 
     The system receives VM generated metadata from the first VM ( 420 ). After the VM has started, the VM can communicate with a metadata service to provide arbitrary key value pairs of metadata. Applications running on the VM can also provide application specific metadata to the metadata service. 
     The system receives an indication that the first VM has failed ( 430 ). A user or a datacenter management system can receive an indication that the first VM has failed, e.g. due to a time out or failure to respond, a received error message, or a host machine failure. In some implementations, other VMs grouped in a project can read metadata from the metadata service about a particular VM and can determine that the VM has failed and needs to be rebooted. For example, if a VM reaches a particular error condition, the VM can write metadata to the metadata service indicating that the VM has effectively failed and should be rebooted. 
     The system initializes a second VM on a second host machine ( 440 ). In response to the VM failure, a datacenter management system can automatically reboot the VM on the same or a different host machine. A user can also manually reboot the VM on the same or a different host machine. 
     To restart the VM on a different host machine, the VM can be configured with the same initialization metadata used to start the VM on the first host machine, e.g. initialization metadata provided by the VM image or through startup scripts. 
     The system configures the second VM with VM-generated metadata from a metadata service ( 450 ). In addition to the user-specified initialization metadata, the VM is also configured with VM-generated metadata that had been provided to the metadata service while the VM was running on the first host machine. 
     Thus, a VM can effectively be migrated to and resumed on the second host machine using metadata provided to the metadata service while the VM was running on the first host machine. A VM can effectively persist its state on a restarted VM by intermittently providing VM-specific to the metadata service while running. This ensures that the state of the VM and applications running on the VM are preserved by the metadata service. 
     Embodiments of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly-embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible non-transitory program carrier for execution by, or to control the operation of, data processing apparatus. Alternatively or in addition, the program instructions can be encoded on an artificially-generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. The computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them. 
     The term “data processing apparatus” encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them. 
     A computer program (which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub-programs, or portions of code. A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. 
     The processes and logic flows described in this specification can be performed by one or more programmable computers executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit). 
     Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, or any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device, e.g., a universal serial bus (USB) flash drive, to name just a few. 
     Computer-readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. 
     To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user&#39;s client device in response to requests received from the web browser. 
     Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back-end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front-end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back-end, middleware, or front-end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet. 
     The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other. 
     While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any invention or of what may be claimed, but rather as descriptions of features that may be specific to particular embodiments of particular inventions. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination. 
     Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system modules and components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products. 
     Particular embodiments of the subject matter have been described. Other embodiments are within the scope of the following claims. For example, the actions recited in the claims can be performed in a different order and still achieve desirable results. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain implementations, multitasking and parallel processing may be advantageous.