I want to propose such an example, which I call naive mapreduce. Despite its name, it is not a form, simplified or otherwise, of an actual Mapreduce algorithm; it does, however, simulate certain aspects of its operation. For the purposes of this particular discussion, we will start with the assumption that there will always be at least one CPU available for any thread when it is started or awakened from a waiting cycle, and that we are using kernel threads (to be exact: that the thread creation, wait, IPC, and termination are performed through system calls, either explicit or implicit, that all scheduling is by the kernel scheduler, and that threads can be scheduled to run on any free CPU). These conditions can be changed to explore different issues, but anyone discussing a variant should say so explicitly; for now, let's keep to fairly idealized assumptions about the CPU scheduling to avoid contention over which conditions apply.
The Naive Mapreduce problem, broadly speaking, is to fingerprint all the possible links reachable from a given hypertext document (or unspecified format), using one thread or process per document found during the tree-building process. The specific approach I want to suggest we discuss would be:
- a request is made to map the document's link tree.
- A primary thread is started for processing the links within that document. The thread contains three tables: one cataloging the links within the current page and their corresponding threads (more later), one cataloging links reachable from documents that the current document links, and one cataloging any incoming links back to it that the child threads find.
- A child thread replicates the parent, save for its tables, thread ID, and parent ID. The incoming links table of a new child is seeded with the link to the page that first found it.
- Each thread can receive five messages from another thread: An 'update incoming links' message (which can come from any thread); an 'update secondary links' message (from a child thread); a 'document processing complete' message (from a child thread); a 'all child document processes complete' message (from a child after all of its own chiuldren have reported completion); and a 'flush all data to log then forward to parent' (which the parent can issue to a completed child after both it and the child have completed their document processing ansd that of the child's children).
- Upon finding a link in its own document, a thread searches for the link in its outgoing links table; if the link isn't already cataloged, it adds it to the table and spawns as child thread to process the links of that document. It also passes the new link up to its parent thread, if any, so that it can be added to the parent's secondary links table along with the thread id of the child it spawned to process the new link. Each parent thread stores this locally before propagating up to its own parent.
- Upon finding a link that already exists in the table, a thread will look up the thread processing said document and pass it an update incoming links message.
- Upon completing its own document processing, a thread will send a self completion message to its parent, if any; then wait for any messages from its own children (if any); when all of its own children have notified that they and all of their children have completed, it then sends them a flush request, causing them to log their own data in a file, then return a copy of their tables to the parent for possible further processing. It then notifies its own parent that it's fully completed it's task and waits for its own flush message. Once a thread has flushed, it requests a termination on itself.
