Architectural Patterns: Adaptable Systems, Distribution, and MapReduce

11.1 Patterns Recap and the Adaptable Systems Family

11.1.1 What a Pattern Is

A pattern is a standard approach that experienced engineers have deciphered and cataloged from past experience. When a context is common and a particular type of problem keeps appearing, a standard solution normally exists for it. You rarely get an exact solution out of a pattern. What you get is a model — a sort of outline which guides you in how you could formulate a solution to the problem. The pattern is defined well enough to steer your design, yet open enough to fit your exact situation.

Think of a pattern like a floor plan for a house. The plan fixes the big decisions — kitchen near the dining room, bedrooms away from the road — but it does not fix your furniture, your wall colors, or whether you add a balcony. Two families can live in the same plan and both be happy. A software pattern works the same way: it fixes the structural decisions (what major pieces exist, how they talk), and leaves your specific business logic to fill in. The analogy breaks down in one place worth remembering: a floor plan is frozen once built, while a good software pattern is chosen precisely so the building can keep being rebuilt around it later.

Reference catalogs document each pattern with a fixed set of headings — name, context (the situation that gives rise to the problem), problem, summary of solution, strengths, weaknesses, applicability, and related patterns. That structure matters because it turns pattern selection into a checklist: match your context, weigh strengths against weaknesses, and check the related patterns before committing.

The pattern catalog in this course splits into four families: monolithic structure, distributed systems, interactive systems, and adaptable systems. This session concentrates on the last family. Two patterns live inside it: reflection patterns and the microkernel pattern.

11.1.2 Why Systems Must Adapt

What is so great about adaptable systems? They adapt. That sounds like a joke, but it is the whole point. These systems are built for environments that undergo modification all the time. New hardware appears. The Linux operating system is a very old system, yet the hardware underneath it keeps changing. Third-party components and libraries evolve. A design that cannot absorb this churn ages fast.

Adaptable patterns survive for very long periods. What you use today is a matured form of what engineers had decades ago. The very design bears in mind that lots of changes will come — not only changes to things outside the system, but internal modification too. Such systems also carry features that let you understand the system through commands: the software can answer questions about itself. Java, for instance, ships many self-query functions in the language itself; you can write a program that documents another program by reading all the features of a piece of software and reflecting on its own capabilities. That idea gets a full treatment under reflection below.

Where does the pressure to adapt actually come from? Three recurring sources:

• Hardware churn — processors, storage, and peripherals are replaced on cycles far shorter than a software system's life. An operating system outlives several generations of the machines it runs on.
• Third-party evolution — libraries, drivers, and components you depend on get updated or discontinued by their vendors.
• Internal growth — your own feature list grows; modules written years ago must absorb new responsibilities without breaking the old ones.

A design that expected none of this treats each event as an emergency. A design built on an adaptable pattern treats each event as routine.

Real-world: long-lived platforms prove the point. Systems designed for adaptation keep running and growing, while rigid designs get replaced. The clearest single example — decades old and still central to computing — is Unix, so it deserves its own look.

11.1.3 Unix as a Long-Lived Adaptable Design

Look at Unix (or say Linux today — the lineage matters more than the name). People who have worked in Unix call the design marvelous. It can adapt to almost anything, and any operating system that did not follow its basic architectural notions gradually had to move toward them. Why? Because Unix, seen as a software system, seems to be one of the simplest systems you will ever meet:

• Everything is a file. The system does not work with anything except files.
• All processes have IDs, and you have rights controlling everything.
• You can keep adding components, and they interact with each other.
• The basic protocols for interaction were so finely developed that you can even replace individual commands, and the system keeps working.

Each of those four lines hides a deep decision. "Everything is a file" means the system exposes devices, directories, and communication channels through one uniform interface — read and write — so a program written for ordinary files also works on hardware ports or network sockets without knowing the difference. "All processes have IDs" means every running program is addressable and controllable through one naming scheme, and rights attached to those IDs let the system decide who may do what. "Keep adding components" means the design accepts new tools without re-planning the whole. And replaceable commands mean the user-visible surface is composed of small interchangeable parts rather than one monolithic program.

That simplicity is exactly what lets new features be requested late in the day and still be added cleanly. Adaptable systems are beautiful because change was expected from day one.

Visualize the difference as two curves on a chart: the horizontal axis is time, the vertical axis is the cost of absorbing one more change. For the rigid design the curve climbs steeply — each change touches more of the system than the last. For the adaptable design the curve stays nearly flat — changes land in designated extension points. The curves cross early, and after that crossing the adaptable system is always cheaper to evolve.

Real-world and domain connection: operating systems, embedded platforms, and virtual-machine infrastructures all descend from this family — the microkernel pattern in the next section is the formal version of the Unix lesson. When you later study product lines and cloud platforms, notice the same shape again: a stable minimal core plus swappable surroundings. In industry terms, adaptability is what separates a platform (which others build on for decades) from a product (which gets rewritten every few years).

11.2 The Microkernel Pattern

11.2.1 Concept and the Coconut Analogy

The word microkernel borrows from kernel. Think of a coconut: the kernel is the layer inside the coconut which separates the inner part from the shell. The shell is what anybody sees from outside, but the real activity of the coconut is performed by the material below the shell. The coconut picture introduces the microkernel idea perfectly: a small core with everything visible built on top of it.

Extend the picture one step and the mapping is exact. The shell is the visible surface — applications and interfaces. The white flesh under the shell is the working mass of the system — external servers and components doing the real work. And the thin kernel at the center is the only part that ever touches the hard outer world directly. Where does the analogy break? A coconut's kernel is dead packaging, while a software microkernel is the live part of the system — but for structure, not function, the picture is faithful.

A microkernel has minimal core functionalities by design. Its role is this: take any hardware, put the microkernel on top of it, and anybody looking from outside would not know the difference — it is the same software as far as users are concerned. The kernel then serves as a socket onto which you can add any amount of components, extending the system over new internal hardware without disturbing what already works.

One requirement dominates everything: the kernel must be extremely lightweight. The overhead of the microkernel should occupy minimal memory space and consume very little processing power.

11.2.2 Components and Structure

You take the fundamental services — the core services, called the internal server services — and encapsulate them into one component: the microkernel. It takes responsibility for basic hardware functionality, file handling, and process handling. Everything else lies outside the kernel. The component model has five roles:

Read the table as a message path and the design clicks: a client sends a request through an adapter; the adapter speaks either to an external server or straight to the microkernel; the microkernel either answers from its own essential functionality or delegates to an internal server; the reply travels back along the same path. No component talks around the kernel, which is exactly why replacing any single component never disturbs the rest.

Reference material lists step-by-step implementation guidance plus variants of this arrangement; walk through those steps when you build one.

Visualize the structure as concentric rings. At the center, the smallest ring: the microkernel with its internal servers. Around it, a ring of external servers exposing friendly interfaces. Around those, the adapter ring — including virtual machines — facing outward toward the widest ring of all, the clients. Hardware sits underneath the whole picture, touching nothing except the center. One-sentence takeaway: everything the user sees lives in the outer rings; everything that must survive hardware change lives in the center.

11.2.3 Real-World Instances

Real-world: the Java virtual machine is the classic story. Java grew out of automation work where large numbers of machines had to run the same software conveniently. The team created a bare minimum of code which you load on the machine — the Java virtual machine. Once a machine has the JVM, any Java program runs on it. New hardware arrives? All you do is create a virtual machine around it. Beautiful, adaptable design. Windows carries the same idea in the .NET framework, and knowledge of the history of Java and of Unix really helps you see how these pieces have been working together.

Real-world: Linux exposes a shell. Take any hardware, load the shell around it, and you have the Linux microkernel arrangement in spirit. The Android operating system runs the Dalvik virtual machine, and that adapter layer is what made development easy for so many people on so many devices.

Real-world: cars. Both Android and Apple have versions of their operating systems for cars. Somebody must develop the microkernel for each car platform; the car manufacturer concentrates on adapting the microkernel to its equipment, and that adaptation could be done by a third-party agency.

Real-world: Apple and Unix history explains macOS strength. Apple was among the original signatories of the Unix accord — recalled alongside IBM and Sun. Sun Solaris was totally Unix based (and later became part of Oracle). There was a generation when anybody doing creative work — visual graphics or video — did not look at any other machine, because Apple shipped a graphic user interface while Windows was still struggling to put a GUI on top of the disk operating system. Oracle acquired Sun, so Java, MySQL, and Solaris all became Oracle properties; professional developers of an earlier era swore by Solaris. In early LDAP work, integrating Sun Solaris, standard Linux, and Windows into one directory tree across three or four machines was an exciting achievement at the time (Windows was at version 3); today machines interacting with each other is nothing great.

11.2.4 Benefits and Liabilities

Benefits first. A microkernel lets a platform cope with continuous hardware and software evolution — new operating systems, new hardware. You can run the same core functionality over multiple technologies, multiple interfaces, multiple operating systems, multiple hardware targets, and multiple devices. Look at the number of hardware platforms Android runs on today; that reach exists because of the adaptable design.

Liabilities, honestly stated. There is a performance penalty: if applications ran directly on the hardware, they would give a little better performance. When you buy certain hardware equipment, it comes with a chip programmed for that specific hardware — not every piece of hardware carries a microkernel. So why accept the penalty? Reusability. Running applications straight on hardwired components means no reuse across devices, and that headache is worse than the penalty. If you write software for cars, for example, so many applications have to run there that you cannot possibly wire each one directly into the car's components — the penalty is well worth it. The second liability is complexity of design: someone has to develop and adapt the microkernel for each target, which adds real engineering work.

When to pick which: choose direct wiring only for a single fixed device with hard real-time or cost limits; choose the microkernel whenever the same software must outlive or span several hardware generations.

Real-world and domain connection: virtual-machine platforms (JVM, .NET CLR, Dalvik), automotive infotainment, and embedded device families live on this pattern because their economics are pure reuse economics — thousands of SKUs, one core. In the broader field, the microkernel is the architectural ancestor of today's plug-in and container platforms: a stable minimal core hosting swappable surroundings is the shape modern cloud runtimes still copy.

11.3 The Reflection Pattern

11.3.1 Concept: Self-Query and the Meta-Language

Reflection gives you an inner view of the application. Methods and commands are available so that the system allows self-query: it can reflect on itself. The crux of reflection is that it provides a meta-language, and the entire system works on a design identical to the design that runs the system.

Here is an everyday picture to anchor the idea. Think of a library catalog. Normally a catalog describes books. But this catalog also contains an entry describing the catalog itself — how many indexes it has, which shelves it covers, what each field means. So the same lookup procedure that finds any book can also tell you what the catalog contains. That is the heart of reflection: the system's description lives inside the system, reachable with the system's own tools. The analogy breaks at one point worth noting — a paper catalog cannot rewrite itself, while a reflective system can act on what it discovers, changing behavior based on structure it reads at runtime.

Take a database. All the metadata about a database is also stored in a database. So you can query the structure of a database using the same commands you use to query data created in that database. Working on an RDBMS and want to look up the structure of a particular table? Query another table which contains that structure. Want to find out what methods a class has? Write a command to create a class of type Class, and that object tells you the names of the methods, the attributes — everything. This is a reflexive language: you can write the system in its own language.

Is this genuinely new? Veterans who worked the earlier days sometimes feel it is all old wine coming in new bottles — the RMI and CORBA debates sound familiar to them. When the first operating system of solid quality (Unix) was written, a language was written for it in parallel: C was developed by the developers of Unix, side by side with the system. That support was not reflection in the strict sense we discuss here, but the lesson holds: development and developer always go together, and if you develop something which is a development tool, that tool itself can be used to develop itself. That self-application is what reflection is all about.

So state the capability precisely. Reflection is the capability of the language — you are using the language not only to change the structure of a table, but even to look up the structure of a table, and to look up the table not in order to show it on the screen, but so that programs behave differently for different structures automatically.

That last clause is the examinable part. Reading structure to display it is documentation. Reading structure so the program's own behavior changes — different tables produce different reports without recompilation — is reflection as an architectural device.

11.3.2 Worked Examples

Example 1 — The Customized Report

Example 2 — Check Printing Templates

11.3.3 Meta Level and Base Level

Architecturally, reflection splits a system into two major parts: the meta level and the base level. Right through the design, we talk about the meta language and the base language, and the two languages are very similar. Application logic sits in the base level. At the meta level you maintain metaobjects. The base level talks to the meta level, and the metaobject protocol talks to both the meta level and the base level. The object model connects metaobjects, components, and the user interface, and shows how they interact.

Unpack each piece:

• Base level — where the application's real work happens: the objects that process orders, print checks, generate reports.
• Meta level — a parallel world of metaobjects, each one describing some base-level entity: a metaobject for each class listing its methods and attributes, a metaobject for each table listing its columns.
• Meta language vs base language — the two vocabularies are deliberately kept very similar, so the same style of command inspects structure and manipulates data. That similarity is why "query the table about the table" feels natural instead of exotic.
• Metaobject protocol — the defined boundary both levels share. Base-level objects call through it to discover their own structure; tools call through it to observe or adjust the running system.

Software evolves over time, and this architecture is how it stays possible: you should be able to adapt, to make changes, and to see what is happening inside the software while it runs.

Visualize it as a building with two floors connected by one staircase. Downstairs (base level), workers process orders all day. Upstairs (meta level), a mirrored room holds a live scale model of everything downstairs — every workstation, every conveyor. The staircase (the metaobject protocol) lets any worker walk up, consult the model, learn the current layout, and change their own routine accordingly — and lets an architect watch the model to understand the factory without stopping it.

11.3.4 Benefits and Liabilities

Benefits: no explicit modification of source code is needed; change in the software system becomes easy; and support exists for many kinds of changes.

Liabilities deserve equal attention. Modification of the meta language may cause damage. The number of components increases. Efficiency drops — reflective systems pay for their flexibility. Not all potential changes in the software are supported. And not all languages support reflection; even among languages that do, support varies in degree. For one person a given mechanism may be a fine picture of what reflection is; another person may say, oh, that is only partial reflection. Calibrate expectations per language.

Real-world and domain connection: Java's reflection API powering object inspectors and dependency-injection frameworks, relational systems exposing their catalogs as queryable tables, and platform products like Salesforce whose entire business model is runtime-customizable structure all implement this pattern. In the broader field, reflection is what makes frameworks possible at all — a framework must inspect your code to orchestrate it, and inspection is reflection wearing a work uniform.

11.4 The Client–Server Pattern

11.4.1 Resource Sharing Model

The whole idea of client–server is that you want to share resources. There is a lot of benefit in sharing: you can buy one very powerful machine and hold the capability in one place. Typical servers include the database server, mail server, communication server, and file server for storage of data. Many people need to use that capability — we call them clients — and clients interact with the server. Often there is a system of queuing: the server keeps accepting requests in order, so that the very powerful capability does not need to be replicated with each client.

The queuing point deserves a second look because it is what makes sharing safe. If fifty clients fired requests simultaneously at raw hardware, they would trample each other. A server stands between them like a single teller window: requests line up, each is processed to completion in turn, and no client ever sees a half-applied change made by another. Where the generator analogy breaks: electricity flows identically to every house, while server requests carry different data and can change state — which is why the server needs the discipline described next.

The second benefit flows from sharing itself: each client is given the benefit of whatever every other client has done. Data is shared, and updates are always up to date, because a database server enforces the concept called ACID. The details of ACID come later; for now take away consistency: whenever communication happens, the result will be consistent to all users. One caution — this promise gets revisited in a few weeks when distributed databases arrive, because distribution strains it. Within a central client–server setup, though, trust it.

11.4.2 Atomic Updates: The Ticket-Booking Walkthrough

Atomicity says every update happens completely or not at all. Typically, any logical transaction in a persistent space — and persistent space means either a database or a filesystem — should update every aspect of the transaction or nothing at all.

11.4.3 Booking Failures in the Wild

Real-world: everyone has met the failure case. You got a ticket, everything went through except payment — trouble at your bank or a wrong OTP — and when you tried to book again, the ticket was gone. Contrast airlines, at least some years back: if you booked a ticket and your payment did not go through, and you asked somebody else to book the same ticket for you, the fare may have gone up. Your unpaid booking had blocked the low-price seat, and until the release window passed — twenty minutes or half an hour, however it was configured — you started getting quoted the high price. Payment and booking were separate transactions there, but bookings were released if payment did not arrive within the window.

Both behaviors are correct designs — they just chose different transaction boundaries. The rail-style site drew one boundary around booking-plus-payment (all or nothing). The airline drew two boundaries with a timed release between them (book, then pay before the window closes). Neither is wrong; each matches a business judgment about fairness and revenue. Recognizing where the boundary was drawn from observed behavior is the skill this pattern trains.

Visualize load versus users on a chart: horizontal axis, number of concurrent clients; vertical axis, total system cost. The replicated-capability line rises steeply (a copy of the powerful machine for every client); the client–server line stays nearly flat (one machine plus a queue). They cross almost immediately, which is why essentially every multi-user business system you have touched is client–server somewhere inside.

Client–server setups help large numbers of people share resources safely. When the number of interacting people grows and storage must sit in one common place, the design naturally becomes multi-tier — covered in 11.7.

Real-world and domain connection: banking cores, railway and airline reservation systems, corporate mail farms, and web application back ends are all client–server at heart. In the broader field this pattern is the reference point every distribution pattern defines itself against — peer-to-peer removes the center, publisher–subscriber changes who initiates delivery, and multi-tier stacks more machines behind the same idea.

11.5 Peer-to-Peer and Publisher–Subscriber Patterns

11.5.1 Peer-to-Peer Sharing

Peer-to-peer is the situation where people should be able to share data on a one-to-one basis. Most file-sharing applications fall in this category. The Windows networking available on your local area network is a peer-to-peer connection: based on IP addresses, everybody can share data with one another directly, with no central server in the middle.

The mental model is neighbors lending tools over the fence rather than everyone renting from one depot. Each house holds some tools, each can borrow from any other, and no depot exists to run out or break down. Where the analogy breaks: neighbors forget who borrowed what, and software peers must handle that bookkeeping themselves — discovery ("who has this file?") becomes the pattern's real engineering problem once no center tracks it.

When to pick which: pick client–server when many users must see one consistent shared state; pick peer-to-peer when participants mostly exchange with each other directly and can tolerate loose coordination.

11.5.2 Publisher–Subscriber Mechanics

Publisher–subscriber fits a different situation: you have a lot of information which is required by a lot of people; the information is generated in various places and is required by different people differently. Whenever such a situation exists, a newspaper agency — called the publisher — steps in. It has people who collect news, and it registers subscribers. Whenever there is an adequate amount of information to share, it reaches out to the subscribers and asks them to collect their share of the publication. The publisher collates information.

Notice how the responsibilities split, because this split is the essence of the pattern. The publisher's responsibility is only to maintain a list of subscribers and to intimate each subscriber that there is something new to offer. On receiving that intimation, the subscriber picks up whatever it requires, in the form and to the extent required for its purposes. The publisher does not have to keep track of all the various combinations of read events that may be required.

That last sentence is the payoff worth memorizing. If ten subscribers want ten different slices of the same stream, the publisher does not grow ten code paths — it grows one list and one notification loop. All variety lives inside the subscribers, where it belongs.

Trace one cycle concretely:

1. A source delivers new information to the publisher.
2. The publisher appends it to its collated store and walks its subscriber list.
3. Each subscriber receives an intimation: "something new is available."
4. Each subscriber executes its own read event, pulling exactly the slice it needs, in the form it needs.
5. The publisher neither knows nor cares what any subscriber took.

11.5.3 Publisher–Subscriber Inside MVC

The publisher is also the basis for model-view-controller: MVC in a way implements the publisher–subscriber pattern. Data comes in from the action handler and is stored. The publisher notifies all subscribers that there is an update, and the very action that causes the notification can be used to call an event which picks up the data from the publisher. So the notification makes a call to the subscriber to read data from the publisher — and every subscriber may be differently coded, depending on what that subscriber wishes to read. The publisher never tracks those differences; all it does is tell the subscriber to execute the read event, and the read events are coded separately for each subscriber.

Map the roles to make the claim concrete: the model acts as publisher (it holds the data after the action handler stores it); each view is a subscriber registered with the model; a data change triggers notification; each view then runs its own update routine, reading whichever parts of the model it displays. One screen might redraw a chart while another refreshes a table — same notification, different read events. This is also the cleanest evidence for the claim that one pattern can use another: MVC is publish-subscribe wearing application clothing.

11.5.4 Patterns as Vocabulary

Step back and see what these recaps add up to. Patterns give you a vocabulary, and in practical systems they are used almost like grammar in the English language. In any given application you will find a whole lot of these patterns in use — and recognizing them is exactly what assignment two asks of you: point at particular microservices and show how they use publish-subscribe, for instance. With enough variation allowed, one may even argue that one pattern uses another pattern. MVC uses publish-subscribe, as shown above, and you might find hints of publish-subscribe even in Hadoop, because these patterns are the building blocks.

Real-world and domain connection: LAN file sharing and blockchain networks are peer-to-peer; stock-ticker feeds, message brokers, and GUI frameworks' event systems are publisher–subscriber; every front-end framework's reactive views descend from the MVC-as-pub-sub arrangement. In the broader field, these two patterns define the two great alternatives to centralization: remove the center, or keep a center that only announces and never customizes.

11.6 The MapReduce Pattern

11.6.1 Historical Origins: Minicomputers and Costs

MapReduce deserves a little personal history, because the concept is ancient — and yet today you cannot survive without MapReduce. Its presence is enormous.

Go back to the 1980s. Microcomputers had started coming in; the IBM PC arrived in that decade, and before it you had CP/M machines. India had its own twist: the government had decided it wanted local equity operating in computing, and had all but managed to throw out IBM and ICL. DEC PDP systems were present too. Three Indian companies made minicomputers: DCM Data Products, Hindustan Computers Limited, and ORG Systems.

Now the money, because the money explains the engineering. A proper mainframe installation — in an era when an engineer's starting salary was 600 to 1,000 rupees — took infrastructure worth the range of a crore. A minicomputer at 15 to 20 lakhs was a steal by comparison, though even 15 to 20 lakhs was a lot of money. Then came microcomputers, and suddenly you could get a machine for about a lakh of rupees. Even that was roughly a hundred times the salary of an engineer.

Notice what the correction teaches beyond arithmetic: the estimate ten lakh came from treating "fifty thousand" as if it carried only three zeros. Counting digits before trusting an estimate is the same discipline you apply to any scaling argument — and scaling arguments are the whole soul of this topic.

ORG Systems is no longer around. It was the company which originally did the railway reservations system, written on a machine called the ORG Supermax in collaboration with a foreign company, and the program was written in Fortran. Wipro came later and emerged strongly with the downfall of DCM.

11.6.2 Working Within Tiny Memory: External Sorting

Early microcomputers initially came without a hard disk drive. Later you got them with a small hard disk — about ten megabytes on early PC-class machines (the first fixed disks were 5–10 MB), so megabyte-class from the start. Initially you got just a floppy drive, handling 180 kilobytes at first, then 1.44 MB. Memory was only 64 KB — the old disk operating system could handle only 64 kilobytes of memory — and people who had started on IBM mainframes had worked with just 16 kilobytes. So the working style was completely different from what you are accustomed to today: nobody thought of putting everything into memory. Work centered on peripheral devices, and data was sorted in small chunks. With, say, 100,000 records to sort, you would sort only 1,000 at a time.

That last sentence names the technique: external sorting — sorting data that does not fit in memory by sorting pieces and merging the results. The chunk size is not a preference; it is forced by memory. If 64 KB of memory holds about 1,000 records comfortably, then 1,000 is your run size whether you like it or not.

In the mainframe days the loop went through tape: copy records onto tape, download whatever you could sort, sort it, write it into another tape, and repeat. A machine with three tape drives was a luxury. Data centers themselves were rare — hardly three or four in a whole city (Shaw Wallace was one of them) — running ICL machines, rented on hourly payment of around 2,000 rupees an hour initially, later 6,000 rupees an hour.

Why three drives? Because the merge step needs all three at once: two drives feed sorted input while the third receives merged output. Fewer than three and you must stop reading to make room for writing — the loop slows to a crawl.

Here is the merge arithmetic that grew big sorted files out of tiny runs. Sort a chunk into an output file. Then read two files on two drives while writing into a third drive:

$$1,000+1,000=2,000,2,000+2,000=4,000,4,000+4,000=8,000$$

and onward — each merge pass doubles the size of the sorted run. That doubling merge is how the data was built up.

Write the doubling as a rule. Let $S_0$ be the size of one initially sorted run (here $S_0=1,000$ records) and $S_k$ the largest sorted run after $k$ merge passes. Each pass merges two runs of equal size into one run of double size:

$$\begin{array}{rl}{S}_0& =1,000\\ S_{k+1}& =2\cdot S_k\text{(merge two runs of size }{S}_k\text{)}\\ S_k& =S_0\cdot 2^k\end{array}$$

The closed form follows by unrolling: $S_1=2S_0$, $S_2=2S_1=4S_0$, and each pass multiplies by one more factor of 2, giving $S_0\cdot 2^k$ after $k$ passes. To finish a file of $N$ records you need the smallest $k$ with $S_0\cdot 2^k\ge N$, that is $k=\lceil {\log }_2(N/S_0)\rceil$.

When microcomputers arrived, the workflow became a bank of machines. Say five of them. Sorting took time — one sort run took half an hour to one hour on a micro — and if it gave an error you had to resort, then write to a floppy, which was not a reliable medium. So operators were asked to sort data individually on different machines and hand results over to the larger machine with three drives, which could read from two drives and write into the third. Something a single machine might have taken two to three days to finish could be handled in one day using multiple machines.

Hold on to this picture — five machines sorting separately, one machine merging. You have just seen MapReduce in miniature: independent workers map, a coordinator reduces.

11.6.3 From Floppies to Google: Send the Program to the Data

Now watch the same idea go global. Google, many years ago, emerged as a superpower search engine — and the idea they used was exactly what those machine banks did, minus physically carrying floppies around. Over the internet, send the program to every machine which keeps data. Let it run on that machine, and pick up key-value pairs. What is a key-value pair? There is a key and there is an attribute. Say you are trying to arrange words: pick up all the keywords and their locations, and let the word be the key.

Once processing happens on different machines everywhere, look at the parallel processing you get across the world. Having processed locally, results come into a common channel. Before they merge, they are pre-arranged in key order. Then you merge by picking up the highest key value first, keep merging, and take the output. Later, if something new becomes available on any machine anywhere, you simply merge it into the already-merged output.

Hadoop uses this concept in a very big way: it has data nodes, and it has the control managers. The pattern Hadoop follows is the map-reduce pattern.

11.6.4 Map Stage, Sort Stage, and Reduce Stage

Name the stages precisely. The first process is called mapping: you send the program to individual machines, map it onto the data, and ask each machine to process its share. Every piece of output generated is called a partition, and inside a partition you rearrange the data properly so it becomes ready for reduce. The preferred word for that rearrangement is sort, though different people use different terms for it. By this point you have not carried any data you do not require — useless data is done away with at the source, and only the activity you want performed travels.

Then you run the merge: bring the sorted partitions together, remove anything superfluous, and collapse duplicate data during the merge itself. We call this the reduce stage. You reduce, and you provide the output where it is required — it will be stored somewhere for ready use, or used directly if that is the output you wanted.

Assemble the whole procedure as numbered steps:

1. Split — divide the input among machines (or find it already divided, as on the internet).
2. Map — each machine runs the same stateless function over its share, emitting key-value pairs; useless data is dropped at the source.
3. Sort (within partitions) — each machine arranges its emitted pairs in key order so downstream merging is trivial.
4. Reduce (merge) — bring sorted partitions together, collapsing duplicates and superfluous entries during the merge itself.
5. Deliver — store the reduced output for ready use, or consume it directly.

An extract-transform-load framing works too. Elements are mapped: multiple instances deployed across multiple processes perform the extraction — that is the map function. Multiple reduce instances across processes perform the load function of the extract-transform-load pipeline. The infrastructure framework is responsible for deploying map and reduce instances, shepherding the data between them, and detecting and recovering from failure — that is the coordinator. Deployment relations matter: an instance of a map or reduce is deployed on different processes, and instantiate-monitor-control captures the relation between the infrastructure and the map-reduce setup. Whatever data has to exist does so as a set of files.

One property makes this all work: the map functions are stateless. They do not communicate with each other; they work independently all over the place. The only thing common between map and reduce is the key-value pair shape.

Statelessness deserves the emphasis the professor gave it. Because a map instance shares nothing with its siblings, you may run one copy or ten thousand copies, on any machine, in any order, twice if unsure — the result is identical. That is precisely what makes both the parallelism and the fault tolerance of the next subsection possible.

Complexity and cost: work grows linearly with data volume on the map side ($O(N)$ for $N$ records) and the number of reduce inputs shrinks geometrically thanks to pre-sorting — the same doubling-merge economy as the tape era. Practical limits appear where data is indivisible or where jobs need map instances to share information: stateless independence forbids that directly.

11.6.5 Fault Tolerance and the Central Control Unit

This is what we call distributed architecture. Since you allow parallelism, any machine breaking down in between does not make a difference as far as the big picture is concerned. Say you are running a thousand processors and one processor breaks down: some amount of data is not being processed — it does not matter. Later on it will come up and get processed. We know which data has been processed and which has not: a central control unit keeps track of which data has been processed where. The entire operation of distributing, sorting, and merging is handled by that central control unit.

In Hadoop's vocabulary that central control unit is the job tracker sitting above the data nodes: workers report status on a steady heartbeat, and any task whose worker falls silent is simply handed to another node — the bookkeeping lives in one place so no worker needs to know anything about the others.

Many online applications do not even wait for full coverage. There is a steady flow of data, and you serve from whatever has been processed. When you are running a search, by the time you finish typing your first two words, Google lets you know what you probably will type in the next five or ten words — suggestions drawn from already-processed data, not from a completed index.

That reframes failure completely: with partial results served continuously, a slow or dead node degrades freshness slightly instead of stopping the service. Availability stops depending on completing everything first.

11.6.6 Key-Value Pairs Everywhere

The whole idea rides on the key-value pair, so get comfortable with it. People who do not understand key-value pairs get one suggestion: get into regedit and take a look. The entire database which controls your desktop machine is stored in the machine as key-value pairs. Key-value pairs are a very powerful way of storing data and have become increasingly popular. You can create them even from within your application: any static data that your application requires — data you want to read every time the application loads — you normally store in the computer's registry as key-value pairs.

A key-value pair keeps only two things: a key (the name you look things up by) and a value (what you find). No schema, no column types, no joins — which is exactly why it travels so well between machines that agree on nothing else.

11.6.7 When Not to Use MapReduce

Know the limits as well as the power. If the dataset is not very large, the machinery is not justified — if you are a goldsmith, it is ridiculous trying to use a sledgehammer; you do not take a tractor to go to a party. That is hardly a weakness of the pattern: if you are not working with large datasets, why are you thinking of Hadoop? It is meant for big data. If the data is indivisible — you cannot divide it — then you cannot have parallel processing, so forget it here too.

But scanning the internet, gathering information, doing analytics — it is all about parallelism. Without parallelism you always run behind, on a schedule you can compute:

And that is an understatement — things could be much worse. You cannot even dream of browsing the internet without parallel processing.

Read the table as a growth law: backlog compounds because new data arrives daily while yesterday's queue waits. Once arrival rate exceeds serial processing rate, falling behind is not bad luck — it is arithmetic.

Real-world and domain connection: Google web indexing, Hadoop clusters at Yahoo and Facebook, log analytics pipelines, and extract-transform-load systems in every large enterprise run on this pattern; Amazon S3, Cassandra, and JSON-based APIs carry its key-value currency. In the broader field, MapReduce is the bridge between distributed-systems theory and everyday big-data practice — the moment "send the program to the data" became the default shape of data engineering.

11.7 The Multi-Tier Pattern

11.7.1 Layers Versus Tiers

Invariably people think that if you have discussed layered architecture, you have discussed multi-tier. That belief is mistaken, and the distinction between them is the heart of this topic.

Multi-layer talk is basically talk about software layers: the logical division of software into parts so that it can be easily staffed — you can deploy different teams to work on it. Creating different logical units separates the concerns and allows each team to focus on a particular task. The very popular OSI architecture shows the layering habit: application, presentation, session, network, data link, physical.

The correction sticks better with a one-line pair to memorize: layer answers "which piece of software owns this responsibility?"; tier answers "which machine runs that piece?" A system can have seven layers on one laptop (one tier), or three layers spread over five servers (three or more tiers). Neither implies the other — but tiers only make sense once layers exist, because you can only map what you have first divided.

When to pick which: layering is essentially always worth doing for structure; adding tiers is a deployment decision you earn only when load, security, or organization demands separate machines.

11.7.2 Mapping the OSI Layers Onto Machines

Walk the OSI stack and see how each layer can be mapped onto its own machine or combined with a neighbor. The physical layer could be telephone wires, fiber optic, or Wi-Fi. Network and data link can combine into one piece of hardware — the router. Application and presentation layers might run on your client. The session layer might be separated out or brought into the same machine. The transport layer might be handled by a switch, loaded on the same machine, or given to a proxy server. Each layer can be worked on not only by a separate team but even by a separate company: a vendor may work only on the link layer and provide a box which you connect to the physical layer, wiring in whatever external unit — fiber optic cable or otherwise — the site uses.

Tabulate the walk so the mapping habit becomes visible:

Read down that table and notice the freedom: the same seven logical layers produce a different physical picture at every site. One office may run everything from layer 2 up on laptops; a carrier may own dedicated boxes for transport alone. The layers never changed — only the mapping did. That is precisely why the professor insists multi-tier is about mapping, not slicing.

Visualize it as the familiar seven-story OSI building drawn twice. Left drawing: all floors inside one house. Right drawing: floor 1 is a field of cables outside town, floors 2–3 are a router cabinet, floor 4 sits in a switch room, floors 5–7 share your desk. Same building code, two very different skylines.

11.7.3 Application Layering and Load Distribution

Even the application divides further into layers: user interface, business logic, and persistence. Business logic holds all the computation logic. The user interface just takes care of the graphic user interface. Persistence connects to the database. Typical placement: the GUI goes on the client, business logic goes on a web server, and persistence runs as a separate server which in turn connects to a database server. Between the web services you might insert load distribution, and the load distributor might use different machines to handle the load of a given user.

Trace one user request through the standard placement:

1. Browser on the client renders the GUI and submits a form.
2. A load distributor in front of the web services picks a machine to handle this user's request.
3. The chosen web/application server runs the business logic — validating, computing, deciding.
4. That server calls the persistence service, which reads or writes the database server.
5. Results travel back up the same chain to the browser.

Four different machines participated, each running exactly one layer's concern — and each could be replaced, scaled, or crashed independently of the others.

Once you map individual layers onto different machines physically, they are computationally independent, and separating them helps you handle the load — specialized infrastructure and equipment are designed to handle each type of load. Such an arrangement is called a multi-tiered pattern. Reference material shows the canonical labels — client tier, web tier, application tier (in Java shops, the EJB server), and the database/back-end tier — each running on its own machines; smaller deployments collapse them into two or three tiers by co-locating layers. So multi-tier is not just dividing the software into layers; it is basically about mapping — mapping the layers of software to hardware.

Real-world and domain connection: virtually every web application you use is at least three-tier (browser, server farm, database cluster); enterprise Java deployments made the four-tier client/web/EJB/database arrangement an industry standard; and network carriers literally sell individual OSI layers as products — dark fiber for physical, MPLS circuits for link/network. In the broader field, the layers-versus-tiers distinction is how architecture communicates with operations: architects draw layers, operators deploy tiers, and multi-tier is the contract between the two.

11.8 Patterns, Tactics, and Trade-Offs

11.8.1 Pattern Versus Tactic

There is a relationship between patterns and techniques called tactics. The big picture is taken care of by the pattern, and the pattern uses tactics to do the fine-tuning. Put it this way: if the pattern is a molecule, the tactic is the atom.

Extend the chemistry picture and it becomes precise. A molecule's properties come from which atoms are bonded and how — remove one atom and the molecule stops being that molecule. Likewise a pattern works because specific tactics are bonded inside it: drop the tactic and the pattern stops delivering its benefit. Where the analogy breaks: chemists cannot redesign water, but architects can re-bond tactics freely — which is exactly why tactic selection is a design skill and not memorization.

MVC, for example, uses semantic coherence, encapsulation, intermediary, and runtime binding — tactics which MVC draws on to be effective. Unpack each so the list stops being vocabulary:

• Semantic coherence — keep responsibilities that change together in one place; the model holds exactly the data-and-rules that belong together.
• Encapsulation — hide the model's internals behind interfaces so views never reach into its storage.
• Intermediary — the controller stands between user input and the model, so neither side depends directly on the other.
• Runtime binding — views attach to models while the system runs, letting you add or swap views without rebuilding.

Tactics are like fillers. Sometimes patterns will give you problems, and when a problem is there, you select appropriate tactics to take care of it. Reference material catalogs tactic interactions worth reviewing. You can keep adding tactics, but some tactics solve problems and create other problems. After all, the entire purpose of design — the story behind design — is basically give and take.

Watch one give-and-take cycle concretely: suppose changes to the model keep breaking a view. The fix is the intermediary tactic — insert a controller between them. Problem solved; modifiability improved. But now every input crosses one more hop, so response time ticks up slightly — the cure bought modifiability and paid a little performance. That cycle — solve, then pay somewhere else — is not a failure of design; it is design.

11.8.2 Multiple Patterns Coexist

You have already watched it happen this lecture: MVC implements publish–subscribe; Hadoop shows publish–subscribe hints inside MapReduce; a multi-tier deployment may host client–server at one tier and broker-style messaging at another. Real systems are pattern neighborhoods, not pattern moncultures.

From a case study you should be able to recognize a pattern. Assessments show significant features of patterns and expect recognition based on those features. There is no point arguing afterward that some other pattern would also serve the purpose — identify the pattern the features signal.

Real-world and domain connection: framework documentation reads as tactic catalogs once you see them — dependency-injection containers sell runtime binding, message brokers sell intermediary, layered APIs sell semantic coherence. In the broader field, the pattern-tactic relationship is how architecture education scales: tactics give beginners atomic decisions to reason about, patterns give teams whole proven molecules to start from.

Exam Guidance Summary

• Question style: recognition-based. A situation or case study is described with significant features; you name the relevant pattern and justify it from those features. Do not argue alternative patterns after the fact.
• Assignment two ties directly to this material: identify where these patterns exist in a real system (for example, publish-subscribe inside a named microservice) and explain them in discussion.
• Assessment scheme for the assignment cycle: 5 marks for the upload plus 5 marks for observed participation in the group discussion — $5+5=10$ recorded against the upload. Uploads are scored on completeness and choice of project presentation. Participation is judged on maturity: adult, professional interaction; questions asked to understand the system count, and even a short response consumes one of roughly 20–25 daily interaction tickets per person. Each participant creates exactly one thread with the assignment attached.
• Plagiarism surfaces in discussion comments, so present your own work; building on your earlier assignment is allowed, but the current assignment's questions must be answered — resubmitting old work earns nothing.
• Upload is mandatory: marks are given against the upload, so sharing work informally without uploading earns nothing even if participation was strong.
• Work timing: finish in advance and treat the actual deadline as makeup time; last-day submission is a dangerous habit.

Key Industry Applications

• Unix/Linux: everything-is-a-file design, process IDs, rights, replaceable commands — decades of continuous adaptation.
• Java virtual machine, .NET framework, Dalvik: virtual-machine adapters letting one body of software run across heterogeneous hardware; Android's enormous device reach rests on this.
• Automotive software: Android and Apple ship car operating systems; microkernels are adapted per manufacturer, sometimes by third-party agencies.
• Solaris/Oracle lineage: Oracle acquired Sun, taking in Java, MySQL, and Solaris; early LDAP work integrated Solaris, Linux, and Windows into one directory tree.
• Salesforce and BI tools: template-driven customization pays off at scale; modern BI tools expose programmable report interfaces so teams stop rebuilding report designers.
• Banking operations: check and dividend-warrant printing moved from per-bank templates to standardized layouts.
• Google and Hadoop: MapReduce powers web-scale indexing; Hadoop implements it with data nodes and control managers; search-as-you-type suggestions showcase partial-result serving.
• Amazon S3, Cassandra, JSON: key-value storage services and structure-carrying serialization for transporting objects.
• Windows registry: desktop-wide configuration stored as key-value pairs, viewable through regedit.
• Ticketing platforms: atomic all-or-nothing bookings versus split payment windows; airline fare-release windows of twenty minutes to half an hour.
• Networking equipment: routers combining network and data link layers, switches and proxies at transport, vendor boxes for link-layer integration.

Each line above is a pattern wearing work clothes: the platform stories (Unix, JVM, Dalvik) are microkernel economics; Salesforce and check printing are reflection at business scale; ticketing is client–server atomicity; S3, Cassandra, and the registry are key-value culture; Google and Hadoop are MapReduce; and the networking row is multi-tier mapping sold as products. Reading industry news with that decoder is the fastest way to make these patterns permanent.