System and method for bulk processing of semi-structured result streams from multiple resources

A system and associated method for bulk processing of semi-structured results streams from many different resources ingest bytes, parse as many bytes as practical, and return to process additional bytes. The system processes network packets as they arrive from a computing resource, creating intermediate results. The intermediate results are held in a stack until sufficient information is accumulated. The system then merges the intermediate results to form a single document model. As network packets at one connection are consumed by the system, the system can select another connection at which packets are waiting for processing. The processing of a result at a connection can be interrupted while the system processes the results at another connection. In this manner, the system is able to utilize one thread to process many incoming results in parallel.

FIELD OF THE INVENTION

The present invention generally relates to a system and a method for processing incoming or outgoing streams of data from a variety of resources and particularly to computing resources such as databases, servers, and like resources. More specifically, the present invention pertains to the use of a small number of threads to process several parallel incoming streams of semi-structured data in an interleaved fashion.

BACKGROUND OF THE INVENTION

A client program or user utilizing a large distributed computing system typically issues queries, search requests, data selection requests, and so forth, and collects results from a large number of servers in the distributed computing system. The large distributed computing system may be any environment that comprises data that is horizontally partitioned across many servers. A continuing effort has been made to make the process of collecting the information from the servers as efficient as possible with regards to both time and resources. The need for efficient collection of information from large distributed computing systems has become more critical as more systems adopt a web services approach to interfacing with clients.

One conventional approach to issuing queries and collecting results is a sequential processing approach600, illustrated by the diagram ofFIG. 6. A client605sequentially issues a query to and receives a result from server1,610, server2,615, server3,620, and server4,625(collectively referenced as servers630). For example, client605issues a query635to server1,610, and receives a result640. Client605then issues a query645to server2,615, and receives a result650, etc. This sequential process is repeated until all the queries have been issued and all the results returned. Although this technology has proven to be useful, it would be desirable to present additional improvements.

The sequential processing approach600has the advantage of requiring a single thread to process the results. Utilizing a single thread is efficient with respect to resources, but not time. The sequential processing approach600is relatively slow; a delay by one of the servers630delays the overall response to the query. Each of the servers630may take a reasonable amount of time such as, for example, 10 ms to respond to the query. However, for a large number of servers630, the overall response time to the query becomes unacceptably slow. The time required to respond to the query becomes the sum of the time required for each of the remote procedure calls.

Another conventional approach for issuing queries and collecting results is a parallel processing approach700, illustrated byFIG. 7. A client705comprises a thread1,710, a thread2,715, a thread3,720, and a thread4,725(collectively referenced as threads730). Client705issues in parallel a query to and receives results from server1,735, server2,740, server3,745, and server4,750(collectively referenced as servers755). The parallel processing approach700utilizes one of the threads730for each of the servers755to manage input/output communication with each of the servers755. For example, thread1,710, is dedicated to input/output communication with server1,735. Thread2,715, is dedicated to input/output communication with server2,740, etc. Although this technology has proven to be useful, it would be desirable to present additional improvements.

The parallel processing approach700has the advantage of quickly processing the results. Utilizing one of the threads730for each of the servers755is efficient with respect to time, but not resources. Each of the threads730consumes a substantial amount of computing resources. Further, network packets are typically 1.5 Kbytes. If the result of the query is much larger than 1.5 Kbytes, each of the threads730become active when data is ready to be read, resulting in a large number of context switches. As the number of servers755increases, the parallel processing approach700becomes even less efficient.

With both the sequential processing approach600and the parallel processing approach700, the client605and client705are required to wait until sufficient information is accumulated to provide results. Several useful techniques have been developed for managing the collection of results provided in structured formats from a large distributed computing system.

However, the use of semi-structure formats such as XML is proliferating on the Internet and on other networks that are based on a web service model, requiring new approaches for managing bulk XML querying and semi-structured results streams. Structured data informs the client in advance how much data to expect so that the client can know when all the information has arrived and then process the information. Semi-structured data simply arrives at the client as a byte stream. The client then has to interpret the byte stream as it arrives by parsing the byte stream. Consequently, it is difficult to use one thread to process parallel streams of semi-structured data.

What is therefore needed is a system, a computer program product, and an associated method for bulk processing of semi-structured results streams from many different resources. The need for such a solution has heretofore remained unsatisfied.

SUMMARY OF THE INVENTION

The present invention satisfies this need, and presents a system, a computer program product, and an associated method (collectively referred to herein as “the system” or “the present system”) for bulk processing of semi-structured results streams from many different resources such as, for example, databases, servers, and the like. The semi-structured results streams are referenced herein as results; results comprise many packets of information.

The present system can ingest an arbitrary number of bytes, parse as many bytes as practical, and return. Unlike conventional approaches, the present system processes packets as they arrive from a resource, creating intermediate results. The intermediate results are held in a register or stack until sufficient information is accumulated. The present system then merges the intermediate results to form a document model.

As network packets at one connection are consumed by the present system, the present system can select another connection at which packets are waiting for processing. The processing of results at a connection can be interrupted while the present system processes the results at another connection. In this manner, the present system is able to utilize one thread to process many incoming results in parallel. Because the present system functions much faster than the results arrive, the present system is able to provide the document model in a time frame comparable to that of a conventional system that utilizes dedicated threads for each of the incoming results. If data arrives more quickly, this can be easily addressed by using a small number of threads to handle the various connections.

The present system utilizes a pushdown deterministic automata and a finite state model. Because the incoming results are streaming, the present system requires very little state for each parse of the incoming results. Consequently, the present system is able to use a single thread to select from a bank of connections and transmit a query to each of the selected connections. The present system then waits for results to the query, parsing data from the results as it becomes available.

Instead of utilizing a multi-threaded parallel model as in conventional approaches, the present system utilizes a single thread that queries a network of resources in parallel. The query is typically small (on the order of 1 or 2 Kbytes or less). The results of the query are typically very large, hundreds of Kbytes or larger. The present system issues the query sequentially and receives the results from the resources in parallel. To process the results, the present system utilizes a single result thread that maintains state for each one of the resources that the present system has queried.

In one embodiment, system10may be used to process XML utilizing stream-based processors. Rather than generating a document model, the stream-based processor generates callbacks. One common callback interface is SAX (simple API for XML). In this embodiment, system10generates the appropriate SAX callbacks and SAX events from the XML streams. Users that base their event application programming interfaces (APIs) on SAX events can utilize system10to generate those SAX events with one thread rather than many threads in parallel. Further, system10can process the XML stream incrementally, providing a faster access to the SAX events by the event API.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

The following definitions and explanations provide background information pertaining to the technical field of the present invention, and are intended to facilitate the understanding of the present invention without limiting its scope:

API: (Application Program Interface) A language and message format used by an application program to communicate with the operating system or some other system or control program such as a database management system (DBMS) or communications protocol. APIs are implemented by writing function calls in the program, which provide the linkage to the required subroutine for execution. Thus, an API implies that some program module is available in the computer to perform the operation or that it must be linked into the existing program to perform the tasks.

Automata: A machine, system, or subsystem that follows a preset sequence of instructions automatically.

Document Model: A representation of semi-structured data such as an XML data that a program can examine and query.

Internet: A collection of interconnected public and private computer networks that are linked together with routers by a set of standards protocols to form a global, distributed network.

Pushdown Deterministic Automata (PDA): a simple machine, system, or subsystem that manages a stack.

SAX (Simple API for XML): an event-based API that allows programming access to the contents of an XML document.

Semi-structured: Data, such as XML, that has a more loosely defined format than traditional columnar databases.

XML: extensible Markup Language. A standard, semi-structured language used for Web documents. During a document authoring stage, XML “tags” are embedded within the informational content of the document. When the web server subsequently transmits the web document (or “XML document”) to a web browser, the tags are interpreted by the browser and used to parse and display the document. In addition to specifying how the web browser is to display the document, XML tags can be used to create hyperlinks to other web documents.

Xtalk: a binary encoding of XML. Used in high speed XML-RPC systems to reduce the complexity and computational load of the serialization/deserialization step without constraining the format of the query/response.

World Wide Web (WWW, also Web): An Internet client—server hypertext distributed information retrieval system.

FIG. 1portrays an exemplary overall environment in which a system and associated method for bulk processing of semi-structured results streams from many different resources according to the present invention may be used. System10comprises a software programming code or a computer program product that is typically embedded within, or installed on a client15. Client15may comprise a computer, a workstation, a server, or like devices. Alternatively, system10can be saved on a suitable storage medium such as a diskette, a CD, a hard drive, or like devices.

A distributed computing system20comprises computing resources such as a resource1,25, a resource2,30, a resource3,35, through a resource N,40(collectively referenced herein as resources45). Client15can access the distributed computing system20through a network50. Client15is connected to network50via a communications link55such as a telephone, cable, or satellite link. Resource1,25, resource2,30, resource3,35, through resource N,40can be connected to network50via communications link60,65,70,75respectively. While system10is described in terms of network50, client15may also access resources45locally rather than remotely.

FIG. 2illustrates a high-level hierarchy of system10. System10comprises a kernel205. Kernel205is a kernel file descriptor set for select, as is commonly known in the art. Kernel205provides an interface to an operating system of client15.

System10further comprises a single result thread210. The single result thread210manages the operation of system10, retrieves results (semi-structured results streams) from resources45, and processes the results in conjunction with parse states215. Communications from resource1,25, resource2,30, resource3,35, through resource N,40, to system10occur via a connection1,220, a connection2,225, a connection3,230, through a connection N,235(collectively referenced as connections240), respectively. It should be clear that the result thread210represents a single thread or a small number of threads.

Parse states215comprises a parse state for each of the resources45with which client15is communicating. Parse states215comprise a parse state1,245, a parse state2,250, a parse state3,255, through a parse state N,260. In the example ofFIG. 2, system10uses parse state1,245, to process information received from resource1,25, parse state2,250, to process information received from resource2,30, etc.

System10comprises state subroutines265. State subroutines265are called by the single result thread210to process results received from resources45as the results arrive. The specific subroutine in state subroutines265called by the single result thread210depends on a state of the results. The single result thread210retrieves results from each of the connections240much faster than the results can arrive. Consequently, system10is able to process the results as they arrive, rather than waiting for all the results to arrive before processing the results and creating a document model.

FIG. 3illustrates a high level hierarchy of an exemplary parse state, parse state1,245, and a corresponding connection1,220, with results shown as packet1,305, packet2,310, packet3,315, through packet N,320(collectively referenced as packets325). Parse state1,245, comprises a state stack330, a processing stack335, and a dispatch loop340. The state stack330is a stack or register for storing a state associated with packet305. There is no limit to the number of states that can be placed in the state stack330. The state associated with packet305provides to the single result thread210all the information required to properly process packet305. The single result thread210uses the parse state1,245, to perform work on each of the packets325, converting packets325received from one of the resources45into a document model.

In one embodiment, the processing stack335comprises a string stack, an integer stack, and a frame stack. The processing stack335temporarily stores intermediate data, i.e., data that has been processed but is not yet ready to be combined into a document model. For example, as system10pulls a string off connector310, the string is stored in the string stack until it is processed. The frame stack holds the intermediate results, i.e., partially completed results. A state encountered toward the end of processing of the results from one of the resources45consumes all the intermediate results stored in the frame stack to create the final result, i.e., a document model. The integer stack controls the processing stack335by saving the contents of the number of sub-elements remaining of the packet305.

The parse state1,245, is a pushdown deterministic automata. The parse state1,245, is pushing the work required for processing packet305onto the state stack330; whatever state is on top of the state stack330defines the work required by packet305. As packet305is retrieved from connection1,220, by kernel205, the single result thread210determines the state of packet305, selects a corresponding subroutine from the state subroutines265that corresponds to the determined state of packet305, and instructs the corresponding subroutine to process packet305.

The results of processing packet305are stored in the string stack; the current state of packet305is stored in the state stack330. As the single result thread210processes packet305, any additional states representing future processing required by packet305are “queued” by pushing the additional states onto the state stack330. As each corresponding subroutine from the state subroutines265is completed, the single result thread210examines the state stack330to determine if any additional processing remains for packet305. If so, the single result thread210pops the top state off the state stack330(removes the top state from the state stack330), performs the corresponding subroutine from the state subroutines265, and discards the top state.

In addition to popping the top state in the state stack330, the corresponding subroutine in the state subroutines265may remove additional states from the state stack330or add states to the state stack330, depending on the processing performed on packet305. A specific state may appear many times in the state stack330. Any of the state subroutines265may be performed any number of times, as required, to transform packets325into a document model.

The single result thread210continues processing packet305until the state stack330is empty. System10then retrieves packet2,310, packet3,315, through packet N,320, until all packets325have been processed in like fashion. Packets325represent a portion of the results returned by one of the resources45. When no packets325are found at connection1,220, system10proceeds to any other of the connections240that have packets such as packet305waiting for processing. In this manner, system10utilizes the single result thread210to process results that arrive at client15in parallel.

FIG. 4(FIGS. 4A,4B) illustrates a method400of operation of system10. Client15wishes to connect with many different resources and databases such as, for example, resources45in the distributed computing system20(step405). Client15creates a list of questions or requests for resources45and requests the return of results from resources45(step410). Client15broadcasts the list of questions or requests to resources45(step415). The list of questions or requests to resources45may be broadcast, for example, sequentially, in parallel, or by any other method that transmits the query or request to resources45. Resources45return many results to the client15in packets such as packets325(step420). Some of the resources45in the distributed computing system20may not return results if they do not have results that match the query or request.

Results from resources45are returned to client15in pieces; each piece is a packet such as packet305. Typically, packets such as packet305are approximately 1.5 Kbytes on a typical Ethernet. In one embodiment, the results from resources45are returned as a stream of bytes encoded in XML. In another embodiment, the results from resources45are returned in a stream of bytes encoded in binary encoding such as Xtalk. The method400of system10converts the stream of bytes into a document model.

System10processes each of the packets325as packets325arrive at client15(step425) by executing the pseudo code below, which is provided for example purpose only. The single result thread210checks with kernel205to determine which of the connections240have data available for processing (step430) using a “select” method as is currently available and known in the art. If no packets are on any of the connections240(decision step435), system10waits at step440for packets arrive at any of the connections240. If a packet such as packet305is found at any of the connections240(decision step435) such as, for example, connection1,220, the single result thread210utilizes the dispatch loop340to performs a dispatch loop procedure. The dispatch loop procedure examines the related state for the packet and executes the corresponding subroutine of the state subroutines265, creating intermediate results (step445).

If accumulated intermediate results are not sufficient to form a document model (decision step450), system10returns to step430and continues processing packets325. Otherwise, a document model can be formed and system10then merges the intermediate results into a document model (step455). Method400is performed recursively, continually converting into document models semi-structured results that are transmitted in parallel to client15.

FIG. 5illustrates the dispatch loop procedure (step445) in more detail. In step445, system10processes packets325, forms intermediate results, and merges the intermediate results in an interleaved fashion to create a document model. At step505, the dispatch loop340reads packet305off the corresponding connection1,220. At decision step510, the dispatch loop340determines if the state stack330is empty. If yes, no processing is required for packet305and the dispatch loop returns to step505. If the state stack330is not empty at decision step510, the dispatch loop pops the top state off the state stack330(step515). The dispatch loop340then identifies for the popped state a corresponding subroutine from the state subroutines265(step520). The dispatch loop then executes the corresponding subroutine (step525) and stores the intermediate results in the frame stack (step530).

System10repeats steps505through530recursively until all packets325at connections240have been processed. System10processes packets325faster than packets325arrive at client15, allowing one thread, the single result thread210, to handle many parallel streams of results. Results are returned to client15from resources45in a random fashion. Each of the resources45simply sends results to client15when the results are available and not in any particular order. The single result thread210jumps from connection to connection, processing packets as they arrive and merging intermediate results at each of the connections240until all the packets from resources45are retrieved, processed, and formatted as a document model.

In the illustrative pseudo code below, there are shown seventeen states or subprograms that are selectively executed by system10. The following are four exemplary stacks that are used in a preferred embodiment of the present invention; it being understood that other stacks could be used:

the state stack

the integer stack

the frame stack

the string stack

parse begins with the INIT state

INIT:make sure there are 2 bytesconsume themcheck if the first is ‘X’push PINITPINIT:make sure there are 4 bytesthese are the # of processing instructionspush PI this number of timesPI:make sure there is 1 byteif it is a p get rid of the processing instruction bypush DROPSTRINGpush GETSTRINGif it is an E this is the element we want sopush MAKERETURNpush GETFRAMEelse CORRUPTDROPSTRING:pop the top element off the string stackGETSTRING:make sure we have 4 bytesthis is the size of the stringallocate it and set the position pointer to 0push GS1GS1:need at least 1 bytedo we have enough bytes to finish the string?if so,finish the string (copying it into the string buffer)set the pointer forward that many byteselsetake as much as we can (copying it into the string buffer)set the pointer forward that many bytespush GS1GETFRAME:We need the key, then to go on w/ the frame, sopush F1push PUSHSTRINGpush GETSTRINGPUSHSTRING:take the string out of the string buffer and push it on thestring stackF1:make sure we have 4 bytesthis is the number of attributeswe need to get them, then go on with the frameeach attribute has a key and value, sopush F2pushint count (this pushes to the int stack)and then for each attributespush PUSHSTRINGpush GETSTRINGpush PUSHSTRINGpush GETSTRINGF2:make sure we have 4 bytesthis is the number of childrenpushint countpushint F3F3:we need 1 bytethis is the type of the childget the number of children by popintif it is ‘s’ then this whole frame is a leafpush MAKELEAFpush PUSHSTRINGpush GETSTRINGelse, it is an ‘E’ and there are subframespushint countpush MAKENODEpush PUSHFRAMEpush GETFRAMEfor each childpush EATEpush PUSHFRAMEpush GETFRAMEMAKELEAF:gather the value of the leaf (via popstring)the number of attributes (via popint)all of those attributes (via multiple popstring)the key (via popstring)create a leaf and assign it to the frame bufferPUSHFRAME:take the value of the frame buffer and push it on the framestackEATE:make sure we have at least one byte, then check that is an ‘E’andconsume itMAKENODE:gather the number of children (via popint)the number of attributes (via popint)the children (via multiple popframe)the attributes (via multiple popstring)the key (via popstring)create a node and assign it to the frame bufferMAKERETURN:take the value of the frame buffer, move it to the returnvalue and exit the parse

It is to be understood that the specific embodiments of the invention that have been described are merely illustrative of certain applications of the principle of the present invention. Numerous modifications may be made to a system and method for bulk processing of semi-structured results streams from many different resources described herein without departing from the spirit and scope of the present invention. Moreover, while the present invention is described for illustration purpose only in relation to XML web services, the present invention may be applied to any network in which computers are interconnected and can communicate with one another. The present system can further be applied to one computer with many databases. Further, the application of the present invention toward query results or requests is presented for illustration purposes only. The present invention may be applied to any parallel processing of semi-structured streams of data.