Abstract:
The present invention provides a highly reliable and scalable architecture for data centers. Work to be performed is divided into discrete work units. The work units are maintained in a pool of work units that may be processed by any number of different servers. A server may extract an eligible work unit and attempt to process it. If the processing of the work unit succeeds, the work unit is tagged as executed and becomes ineligible for other servers. If the server fails to execute the work unit for some reason, the work unit becomes eligible again and another server may extract and execute it. A server extracts and executes work units when they have available resources. This leads to the automatic load balancing of the data center.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     Mobile electronic devices, such as cell phones, wireless PDAs, wireless laptops and other mobile communication devices are making impressive inroads with consumers. Many of the mobile electronic devices are able to perform a variety of tasks and receive information from many different sources. For example, some mobile devices receive email, instant messages, web content, and other content. Before the content is delivered to the devices it may have to be processed to meets the requirements of the applications residing on the device. Many of the businesses that provide this content rely on data centers to provide the content in a reliable fashion. Failure to provide the content in a reliable and efficient manner may result in problems for the business.  
       SUMMARY OF THE INVENTION  
       [0002]     The present invention is directed at providing a highly reliable and scalable architecture for data centers.  
         [0003]     According to one aspect of the invention, discrete tasks are divided into work units. Generally, a work unit is an independent unit of action that may be completed independently from other work units. The work units are maintained in a pool of work units that may be processed by any available server.  
         [0004]     According to another aspect of the invention, any one of a number of servers running may extract an eligible work unit and attempt to process it. If the processing of the work unit succeeds, the work unit is tagged as executed and becomes ineligible for other servers. If the server fails to execute the work unit for some reason, the work unit becomes eligible again and another server may extract and execute it.  
         [0005]     According to yet another aspect of the invention, a server extracts and executes work units when they have available resources. For example, the available resources may be measured using such statistics as CPU load, available memory, number of threads running, and the like. A server will not extract a work unit once it exceeds a predetermined threshold. This leads to the automatic load balancing of the data center.  
         [0006]     A more complete appreciation of the present invention and its improvements can be obtained by reference to the accompanying drawings, which are briefly summarized below, to the following detailed description of illustrative embodiments of the invention, and to the appended claims. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]      FIG. 1  illustrates an exemplary computing device;  
         [0008]      FIG. 2  illustrates a system for processing work units and broadcasting data to electronic devices;  
         [0009]      FIG. 3  illustrates servers processing available work units;  
         [0010]      FIG. 4  shows a more detailed view of the manager and handlers;  
         [0011]      FIG. 5  shows exemplary work units and a work unit structure;  
         [0012]      FIG. 6  illustrates processing work units;  
         [0013]      FIG. 7  shows a process flow for a handler processing a work unit; and  
         [0014]      FIG. 8  illustrates processing a request for a work unit, in accordance with aspects of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0015]     The present invention relates to providing a highly reliable and scalable architecture for data centers. When a server has available capacity to process a work unit, the server attempts to extract an eligible work unit from a pool of available work units and then attempts to process it. If the processing of the work unit succeeds, the work unit is tagged as executed and becomes ineligible for other servers. If the server fails to execute the work unit, the work unit becomes eligible again and another server may extract and execute it.  
         [0000]     Illustrative Operating Environment  
         [0016]     With reference to  FIG. 1 , one exemplary system for implementing the invention includes a computing device, such as computing device  100 . Computing device may be configured as a client, a server, mobile device, or any other computing device that is part of the system. In a very basic configuration, computing device  100  typically includes at least one processing unit  102  and system memory  104 . Depending on the exact configuration and type of computing device, system memory  104  may be volatile (such as RAM), non-volatile (such as ROM, flash memory, etc.) or some combination of the two. System memory  104  typically includes an operating system  105 , one or more applications  106 , and may include program data  107 . In one embodiment, application  106  includes a management application  120 . Generally, management application is configured to determine the available resources on the computing device and manage the processing of work units on the machine (See FIGURES and related discussion below). This basic configuration is illustrated in  FIG. 1  by those components within dashed line  108 .  
         [0017]     Computing device  100  may have additional features or functionality. For example, computing device  100  may also include additional data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Such additional storage is illustrated in  FIG. 1  by removable storage  109  and non-removable storage  110 . Computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. System memory  104 , removable storage  109  and non-removable storage  110  are all examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device  100 . Any such computer storage media may be part of device  100 . Computing device  100  may also have input device(s)  112  such as keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s)  114  such as a display, speakers, printer, etc. may also be included.  
         [0018]     Computing device  100  also contains communication connections  116  that allow the device to communicate with other computing devices  118 , such as over a network. Communication connection  116  is one example of communication media. Communication media may typically be embodied by computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave or other transport mechanism, and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. The term computer readable media as used herein includes both storage media and communication media.  
         [0000]     Illustrative System for Processing Work Units  
         [0019]      FIG. 2  illustrates system for processing work units and broadcasting data to electronic devices, in accordance with aspects of the invention.  
         [0020]     As illustrated, system  200  includes a broadcast tower (FM transceiver)  202  that broadcasts signals over communication channel  203  to various electronic devices. Example electronic devices that have an FM receiver or transceiver may include a desktop computer, a watch, a portable computer, a wireless cellular telephone (cell phone), and a personal data assistant (PDA). The electronic devices are arranged to receive information from the FM broadcast. The FM broadcast may be any number of types including but not limited to: a standard FM transmission, a sub-carrier FM transmission, or any other type of FM transmission as may be desired. Other means of communicating with the wireless devices may also be used. Each of the electronic devices receives messages/information over the communication channel.  
         [0021]     The electronic devices receive message packets according to shared and private messages that are directed to the device. Message packets are organized in groups according to logical slot (or channel) entry numbers. For example, a particular electronic device is configured to receive a selected group of channels from the available channels. The message packets associated with each of those channels is received, processed, and stored in the client device. Example channels that are broadcast to the devices include: a time channel, a messages channel, a calendar channel, a weather channel, a stocks channel, a news channel, and a movies channel. Messages associated with each channel include message content that is based on the particulars of the channel. For example, a news channel may include a listing of news stories that are currently considered breaking news.  
         [0022]     A user  216  may customize the channels they receive through user web site  218 . Using website  218  the user may set options and select information associated with channels to which they have subscribed. For example, the user may select the news sources which are used to gather data for their electronic device. The selected options are stored in a data store, such as webstore  208 . Channel information and various options may also be automatically retrieved from a web site to which the user participates in. For example, web site  222  may be the user&#39;s home page in which the user has already selected various options customizing their page. These options may be used to populate the options associated with various channels. For example, a user&#39;s selected cities may be used in a weather channel, the user&#39;s selected theaters may be used in a movies channel, a user&#39;s selected stocks they desire to track may be used in a stock channel, and the like.  
         [0023]     Data Collector  210  is configured to collect data from one or more data sources, such as from data source  212  and data source  213 , relating to a channel. For example data collector  210  may be configured to retrieve headline news from data source  212 , and sports news from data source  213 . Generally data sources are used to provide data relating to the various channels that are provided. For example, there are data sources for news information, weather information, movie information, sports information, and the like.  
         [0024]     Data collector  210  may store the data in a data store, such as webstore  208 , for later broadcast. According to one embodiment, data store  210  communicates with network injector  220  which then stores the data in webstore  208 .  
         [0025]     Generally, data collector  212  is configured as a set of servers that can process work units independently from one another. When one server fails, the other servers within the data collector execute the work units that have not been completed. (See FIGURES and discussion below for more details).  
         [0026]     Broadcast transmitter tower  202  is arranged to provide a communication signal that is configured for reception by users with electronic devices that are located within a service region. Broadcast tower  202  transmits in response to generator/broadcast server  404 . Generator  204  may communicate with scheduler  206  via a network communication link. Scheduler  206  is configured to package and schedule broadcast transmissions relating to channel information. Scheduler  206  may also be configured as a set of servers processing work units as described below.  
         [0027]     Selected services are entered in a database, such as webstore  208  for broadcast transmission at a later time. At the designated time (or time interval) scheduler  206  communicates with broadcast server  204  to begin a transmission sequence of data for the selected services. Broadcast server  204  formats the data for reception by one or more wireless client device, queues the data for transmission, and communicates the queued data to FM broadcast tower  202  for transmission. In an alternative example, scheduler  206  communicates the selected services to the broadcast server. The broadcast server schedules the time interval for transmission of the selected service.  
         [0028]     Each broadcast transmission corresponds to the transmission of one or more frames that are arranged in accordance with a frame protocol. Each frame may include multiple messages, where some messages are public broadcast (aka “global” or “shared” messages), while other messages are client specific messages (aka “personal” or “private” messages). Each frame includes a table of contents that indicates the extent of messages that are found within the next transmitted frame. Every client that is located within the designated service region receives the shared and personal messages. Personal messages, however, may only be decoded by a single client.  
         [0029]     Each frame includes a header, a table of contents, and a message payload that includes the content for one or more selected services as previously described. The header also includes other information such as authentication data, identified service region, language, available stations for the identified service region, frame number, and time stamp. Control information may also be included in one of the headers to indicate broadcast conditions such as a change in available channels, an assignment of a service region to a particular wireless client device, and an assignment of a particular channel (frequency). In one example, each frame includes a change counter in one of the headers to indicate a change has taken place in the system. Wireless client devices (clients) may use the change counter to determine when to initiate a failover (when a broadcast tower becomes unavailable).  
         [0030]     Client devices can determine the current service region based on information that is included in the broadcast transmissions. The time zone can be determined based on the current service region such that the client device can adjust any time related information. Moreover, the time and date functions of the client device may be synchronized based on information that is included in the broadcast transmissions.  
         [0031]     Agent  230  is configured to perform maintenance functions. For example, agent  230  is configured to remove data that is not needed any longer from one of the databases. According to one embodiment, agent  230  is configured as a set of servers processing work units (See below).  
         [0032]      FIG. 3  illustrates servers processing available work units, in accordance with aspects of the invention. As displayed, each server includes a manager and handlers for processing work units.  
         [0033]     According to one embodiment, scalable work unit processor  300  is configured to act as a data collector, scheduler, or agent as shown in  FIG. 2 . As shown, each of the servers ( 310   1-N ) includes a manager ( 312   1-N ) and handlers  314   1-N .  
         [0034]     The manager is responsible for managing the handlers and determining available resources for the server. When a server is started, the manager loads the handlers stored on the server. The types of handlers available on a server may change depending on the work the handlers are to perform. For example, a data collector will have data collection handlers, whereas a scheduler will have scheduling handlers. According to one embodiment, each handler is configured to process specific types of work units. For instance, a stock collection handler does not process work units intended for the scheduler. There is generally at least one handler for each designated channel. There may be many different types of channels: including: a stocks channel, a news channel, a sports channel, and the like.  
         [0035]     The handler obtains a work unit and starts processing the work unit. If successful, the handler writes to data store stating that it has finished processing the work unit. If the handler needs more time to process the work unit, then it requests that new checkpoint time be set. The manager may then use this information to update the work unit.  
         [0036]     The manager is also configured to determine its available resources for processing work units. Each server ( 310   1-N ) is configured to execute as many work units ( 320 ) as its resources allow. According to one embodiment, the manager determines the CPU load, available memory, and number of threads running on the server. Other resources may also be monitored to determine the available resources on the server. When the server has resources available to process a work unit the manager requests a work unit from a pool of available work units. Once the work unit is obtained, the manager dispatches the work unit to the appropriate handler for processing. The manager can also keep track of the time and resources used by each of the handlers and can abort a work unit if the handler consumes too many resources or is deadlocked.  
         [0037]     When a server determines that it has reached its predetermined resource limit, it goes into a state where no more work units are accepted. This helps to ensure that a server does not take on too much load. If a server&#39;s resources become critically constrained, the server may enter a critical state where it may abandon work units that it is currently processing. Work units that are not completed by one server may be taken and processed by another one of the available servers. For example, if server  310 , fails, then one of the other servers ( 310   2-N ) can process the work units. If server  310  did not completely fail, but processing of the work unit failed, then server  3101 , or any of the other servers ( 310   2-N ) could be used to process the work unit again. If no servers have available resources then a server(s) may be added to handle the extra load.  
         [0038]     The number of servers used to process work units may be calculated by the formula: N=F+x, where F is the number of machines needed to process all of the work units at full load, and x is the estimated number of machines that can fail simultaneously.  
         [0039]      FIG. 4  shows a more detailed view of the manager and handlers, in accordance with aspects of the invention. As shown, server  400  includes a manager and individual handlers  410   1-N . According to one embodiment, each handler is configured to process a particular type of work unit. For example, hander  410   1  may be configured to collect data relating to stock prices; handler  410   2  may be configured to collect movie theater names; and so on. According to one embodiment, handlers  410   1-N  are implemented as dynamic link libraries.  
         [0040]      FIG. 5  shows exemplary work units and a work unit structure  500 , in accordance with aspects of the invention. According to one embodiment, there are three different types of work units: one shot work units; recurring work units; and long-lived work units.  
         [0041]     One short work units ( 510 ) are work units that are executed one time by the system. For example, a one short work unit may be used to add a new subscriber to the system or remove a subscriber. Once a one-shot work unit is completed it disappears from the pool of available work units.  
         [0042]     Recurring work units ( 520 ) are work units that recur at a predetermined frequency. For example, a recurring work unit may recur every 1 minute, 10 minutes, each day, month, and the like. Once a recurring work unit is completed a new recurring work unit is automatically created and placed within the pool of available work units.  
         [0043]     Long-lived work units ( 530 ) are work units that are attempted to be maintained on a single server since it may be computationally expensive to switch a work unit between different machines. For example, a work unit that creates frames for stations may be a long-lived work unit. If frame  5  was allowed to switch between different servers then any of the state information stored in the server relating to frame  5  would not be available on the different server. Additionally, all of the messages for the state would have to be loaded and cached again.  
         [0044]     Each work unit includes fields  540 . According to one embodiment, work unit  440  includes an ID, a type, a name, a start time, a due time, a checkpoint time, a ticket, a number of attempts, and a state. According to another embodiment, a work unit may include a start time, a retry time, a due time, a status, and an attempts field.  
         [0045]     The ID uniquely identifies the particular work unit. The type of work unit refers to the type of handler that can process the work unit. According to one embodiment, different handlers process different types of work units. For example, a weather handler processes weather work units, a stocks handler processes stock work units, and the like. Work units of different types may reside in the same database, or be stored in separate databases.  
         [0046]     The start time refers to the time the work unit should be processed. The due time is the time the work unit should be finished processing. The checkpoint time is a time that is set when a work unit is dispatched to be processed. The checkpoint time provides a time marker that if the work unit is not completed by the checkpoint time it may become an available work unit which another server may process.  
         [0047]     A server may also update the checkpoint time when it needs more time to complete the work unit. A long-lived work unit may also be created by continually updating the checkpoint time.  
         [0048]     Generally, a work unit is eligible for processing by a server when the time is between the start time and due time. When the time is between the start and due times, the checkpoint time is checked to determine if it has not already been released for processing. If the work unit has already been released then the work unit becomes available after the checkpoint time has passed but the current time is still before the due time.  
         [0049]     Each time a work unit is released for processing a ticket is generated that uniquely identifies the work unit. In order to perform operations on the work unit, such as updating the checkpoint time or changing its state, the server performing the operation must know the ticket contained within the work unit. According to one embodiment, the ticket is a random number that is generated when the work unit is released to a server to be processed.  
         [0050]     An attempts field is used to help detect any “poison pills.” A poison pill is a work unit that can not be processed. Some poison pills could cause havoc on a system if not stopped in a timely manner. Each time a work unit is attempted to be processed the attempts field is incremented by one. According to one embodiment, when a work unit has been attempted to be processed three times, the work unit will not be attempted again. The attempts field is reset when the work unit state changes.  
         [0051]     The state field is used to store any state information associated with the work unit. This way the intermediary results can be obtained without having to restart the entire work unit. For example, if a work unit is created to obtain 200 stock quotes and 100 stock quotes have been processed, then the state field will indicate the completion of 100 stock quotes. If the work unit fails before completing, a server may examine the state field and start processing the second 100 stock quotes since the first 100 quotes have already been completed.  
         [0052]     As mentioned above, a work unit may be completed in more than one step. As processing progresses, the checkpoint time can be continually updated. When the first step is finished, the checkpoint time is updated which extends the period of non-eligibility for that work unit. In other words, the work unit may not be taken and processed by another server.  
         [0053]      FIG. 6  illustrates processing work units, in accordance with aspects of the invention. After a start block, the process flows to block  610  where the resources of the server are determined. According to one embodiment, the framework determines the current CPU load, memory usage, and number of threads running. According to another embodiment, the number of work units is limited to a predetermined number of work units per server. For example, a server may be limited to 16 work units at any one time.  
         [0054]     Transitioning to decision block  620 , a determination is made as to whether the server has capacity to process more work units. When capacity is not available, the process returns to block  610 . When capacity is available, the process moves to block  630  where a work unit is requested.  
         [0055]     The process returns to block  610  when a work unit is not available from a pool of available work units. When a work unit is available, the process flows to block  650  where the work unit is obtained and dispatched to the appropriate handler. The process then moves to an end block and returns to processing other actions.  
         [0056]      FIG. 7  shows a process flow for a handler processing a work unit, in accordance with aspects of the present invention. After a start block, the process flows to block  710  where processing of the work unit is started. Moving to decision block  720  a determination is made as to whether more time is needed to process the work unit. When more time is needed, the process moves to block  730  where the checkpoint time is updated with a new checkpoint time that provides the handler with more time to process the work unit.  
         [0057]     When more time is not needed, the process flows to decision lock  740  where a determination is made as to whether or not the work unit has completed processing. When the work unit has not completed processing, the process moves to block  750  where the process aborts. When processing is completed, the work unit state is updated to indicate that the work item has completed processing. The process then moves to an end block and returns to processing other actions.  
         [0058]      FIG. 8  illustrates processing a request for a work unit, in accordance with aspects of the invention. After a start block, the process moves to block  810  where a request for a work unit is received. Moving to decision block  820 , a determination is made as to whether there is a work unit available. According to one embodiment, a pool of available work units is maintained in a data store, such as a SQL database. When a work unit is not available, the process flows to an end block. When a work unit is available, the process moves to block  830  where a work unit is obtained and a ticket is generated. The ticket is a unique identifier that is used when updating the work unit. Fields within the work unit are not updated unless the ticket provided matches the ticket within the ticket field of the work unit. According to one embodiment, any work order awaiting processing may be obtained. In other words, no priority is assigned to the work units. Moving to block  840 , the work unit fields are updated. According to one embodiment, the checkpoint time is updated, the number of attempts is updated, and the state information may be updated. The process then transitions to block  850  where the work unit is dispatched to the handler for processing. The process then steps to an end block and returns to processing other actions.  
         [0059]     The above specification, examples and data provide a complete description of the manufacture and use of the composition of the invention. Since many embodiments of the invention can be made without departing from the spirit and scope of the invention, the invention resides in the claims hereinafter appended.