1. Networks Are Hard
Occasionally, there isn’t enough light for the crows’ mirror systems to transmit a signal, or something is blocking the path of the signal. It is possible for a signal to be sent but never received.
As it is, that will just cause the callback given to send to never be called, which will probably cause the program to stop without even noticing there is a problem. It would be nice if, after a given period of not getting a response, a request would time out and report failure.
Often, transmission failures are random accidents, like a car’s headlight interfering with the light signals, and simply retrying the request may cause
it to succeed. So while we’re at it, let’s make our request function automatically retry the sending of the request a few times before it gives up.
And, since we’ve established that promises are a good thing, we’ll also make our request function return a promise. In terms of what they can express, callbacks and promises are equivalent. Callback-based functions can be wrapped to expose a promise-based interface, and vice versa.
Even when a request and its response are successfully delivered, the response may indicate failure—for example, if the request tries to use a request type that hasn’t been defined or the handler throws an error. To support this, send and defineRequestType follow the convention mentioned before, where the first argument passed to callbacks is the failure reason, if any, and the second is the actual result.
These can be translated to promise resolution and rejection by our wrapper.
class Timeout extends Error {}
function request(nest, target, type, content) {
return new Promise((resolve, reject) => {
let done = false; function attempt(n) {
nest.send(target, type, content, (failed, value) => {
done = true;
if (failed) reject(failed); else resolve(value);
});
setTimeout(() => {
if (done) return;
else if (n < 3) attempt(n + 1);
else reject(new Timeout(“Timed out”));
}, 250);
}
attempt(1);
});
}
Because promises can be resolved (or rejected) only once, this will work. The first time resolve or reject is called determines the outcome of the promise, and any further calls, such as the timeout arriving after the request finishes or a request coming back after another request finished, are ignored.
To build an asynchronous loop, for the retries, we need to use a recursive function—a regular loop doesn’t allow us to stop and wait for an asynchronous action. The attempt function makes a single attempt to send a request. It also sets a timeout that, if no response has come back after 250 milliseconds, either starts the next attempt or, if this was the fourth attempt, rejects the promise with an instance of Timeout as the reason.
Retrying every quarter-second and giving up when no response has come in after a second is definitely somewhat arbitrary. It is even possible, if the request did come through but the handler is just taking a bit longer, for requests to be delivered multiple times. We’ll write our handlers with that problem in mind—duplicate messages should be harmless.
In general, we will not be building a world-class, robust network today. But that’s okay—crows don’t have very high expectations yet when it comes to computing.
To isolate ourselves from callbacks altogether, we’ll go ahead and also define a wrapper for defineRequestType that allows the handler function to return a promise or plain value and wires that up to the callback for us.
function requestType(name, handler) {
defineRequestType(name, (nest, content, source, callback) => {
try {
Promise.resolve(handler(nest, content, source))
.then(response => callback(null, response),
failure => callback(failure));
} catch (exception) { callback(exception);
}
});
}
Promise.resolve is used to convert the value returned by handler to a promise if it isn’t already.
Note that the call to handler had to be wrapped in a try block to make sure any exception it raises directly is given to the callback. This nicely illustrates the difficulty of properly handling errors with raw callbacks—it is easy to forget to properly route exceptions like that, and if you don’t do it, failures won’t get reported to the right callback. Promises make this mostly automatic and thus less error-prone.
2. Collections of Promises
Each nest computer keeps an array of other nests within transmission distance in its neighbors property. To check which of those are currently reachable, you could write a function that tries to send a “ping” request (a request that simply asks for a response) to each of them and see which ones come back.
When working with collections of promises running at the same time, the Promise.all function can be useful. It returns a promise that waits for all of the promises in the array to resolve and then resolves to an array of the values that these promises produced (in the same order as the original array). If any promise is rejected, the result of Promise.all is itself rejected.
requestType(“ping”, () => “pong”);
function availableNeighbors(nest) {
let requests = nest.neighbors.map(neighbor => {
return request(nest, neighbor, “ping”)
.then(() => true, () => false);
});
return Promise.all(requests).then(result => {
return nest.neighbors.filter((_, i) => result[i]); });
}
When a neighbor isn’t available, we don’t want the entire combined promise to fail since then we still wouldn’t know anything. So the function that is mapped over the set of neighbors to turn them into request promises attaches handlers that make successful requests produce true and rejected ones produce false.
In the handler for the combined promise, filter is used to remove those elements from the neighbors array whose corresponding value is false. This makes use of the fact that filter passes the array index of the current element as a second argument to its filtering function (map, some, and similar higher-order array methods do the same).
3. Network Flooding
The fact that nests can talk only to their neighbors greatly inhibits the usefulness of this network.
For broadcasting information to the whole network, one solution is to set up a type of request that is automatically forwarded to neighbors. These neighbors then in turn forward it to their neighbors, until the whole network has received the message.
import {everywhere} from “./crow-tech”;
everywhere(nest => {
nest.state.gossip = [];
});
function sendGossip(nest, message, exceptFor = null) {
nest.state.gossip.push(message);
for (let neighbor of nest.neighbors) {
if (neighbor == exceptFor) continue;
request(nest, neighbor, “gossip”, message);
}
}
requestType(“gossip”, (nest, message, source) => {
if (nest.state.gossip.includes(message)) return;
console.log(‘${nest.name} received gossip ‘${ message}’ from ${source}’);
sendGossip(nest, message, source);
});
To avoid sending the same message around the network forever, each nest keeps an array of gossip strings that it has already seen. To define this array, we use the everywhere function—which runs code on every nest—to add a property to the nest’s state object, which is where we’ll keep nest-local state.
When a nest receives a duplicate gossip message, which is very likely to happen with everybody blindly resending them, it ignores it. But when it receives a new message, it excitedly tells all its neighbors except for the one who sent it the message.
This will cause a new piece of gossip to spread through the network like an ink stain in water. Even when some connections aren’t currently working, if there is an alternative route to a given nest, the gossip will reach it through there.
This style of network communication is called flooding—it floods the network with a piece of information until all nodes have it.
4. Message Routing
If a given node wants to talk to a single other node, flooding is not a very efficient approach. Especially when the network is big, that would lead to a lot of useless data transfers.
An alternative approach is to set up a way for messages to hop from node to node until they reach their destination. The difficulty with that is it requires knowledge about the layout of the network. To send a request in the direction of a faraway nest, it is necessary to know which neighboring nest gets it closer to its destination. Sending it in the wrong direction will not do much good.
Since each nest knows only about its direct neighbors, it doesn’t have the information it needs to compute a route. We must somehow spread the information about these connections to all nests, preferably in a way that allows it to change over time, when nests are abandoned or new nests are built.
We can use flooding again, but instead of checking whether a given message has already been received, we now check whether the new set of neighbors for a given nest matches the current set we have for it.
requestType(“connections”, (nest, {name, neighbors},
source) => {
let connections = nest.state.connections;
if (JSON.stringify(connections.get(name)) ==
JSON.stringify(neighbors)) return;
connections.set(name, neighbors);
broadcastConnections(nest, name, source);
});
function broadcastConnections(nest, name, exceptFor = null) {
for (let neighbor of nest.neighbors) {
if (neighbor == exceptFor) continue;
request(nest, neighbor, “connections”, {
name, neighbors: nest.state.connections.get(name)
});
}
}
everywhere(nest => {
nest.state.connections = new Map;
nest.state.connections.set(nest.name, nest.neighbors);
broadcastConnections(nest, nest.name);
});
The comparison uses JSON.stringify because ==, on objects or arrays, will return true only when the two are the exact same value, which is not what we need here. Comparing the JSON strings is a crude but effective way to compare their content.
The nodes immediately start broadcasting their connections, which should, unless some nests are completely unreachable, quickly give every nest a map of the current network graph.
A thing you can do with graphs is find routes in them, as we saw in Chapter 7. If we have a route toward a message’s destination, we know which direction to send it in.
This findRoute function, which greatly resembles the findRoute function from Chapter 7, searches for a way to reach a given node in the network. But instead of returning the whole route, it just returns the next step. That next nest, using its current information about the network, will decide where it sends the message.
function findRoute(from, to, connections) {
let work = [{at: from, via: null}];
for (let i = 0; i < work.length; i++) {
let {at, via} = work[i];
for (let next of connections.get(at) || []) {
if (next == to) return via;
if (!work.some(w => w.at == next)) {
work.push({at: next, via: via || next});
}
}
}
}
Now we can build a function that can send long-distance messages. If the message is addressed to a direct neighbor, it is delivered as usual. If not, it is packaged in an object and sent to a neighbor that is closer to the target, using the “route” request type, which will cause that neighbor to repeat the same behavior.
function routeRequest(nest, target, type, content) {
if (nest.neighbors.includes(target)) {
return request(nest, target, type, content);
} else {
let via = findRoute(nest.name, target,
nest.state.connections);
if (!via) throw new Error(‘No route to ${target}’);
return request(nest, via, “route”,
{target, type, content});
}
}
requestType(“route”, (nest, {target, type, content}) => {
return routeRequest(nest, target, type, content);
});
We’ve constructed several layers of functionality on top of a primitive communication system to make it convenient to use. This is a nice (though simplified) model of how real computer networks work.
A distinguishing property of computer networks is that they aren’t reliable—abstractions built on top of them can help, but you can’t abstract away network failure. So network programming is typically very much about anticipating and dealing with failures.
5. Async Functions
To store important information, crows are known to duplicate it across nests. That way, when a hawk destroys a nest, the information isn’t lost.
To retrieve a given piece of information that it doesn’t have in its own storage bulb, a nest computer might consult random other nests in the network until it finds one that has it.
requestType(“storage”, (nest, name) => storage(nest, name));
function findInStorage(nest, name) {
return storage(nest, name).then(found => {
if (found != null) return found;
else return findInRemoteStorage(nest, name);
function network(nest) {
return Array.from(nest.state.connections.keys());
}
function findInRemoteStorage(nest, name) {
let sources = network(nest).filter(n => n != nest.name);
function next() {
if (sources.length == 0) {
return Promise.reject(new Error(“Not found”));
} else {
let source = sources[Math.floor(Math.random() *
sources.length)];
sources = sources.filter(n => n != source);
return routeRequest(nest, source, “storage”, name) .then(value => value != null ? value : next(),next);
}
}
return next();
}
Because connections is a Map, Object.keys doesn’t work on it. It has a keys method, but that returns an iterator rather than an array. An iterator (or iter- able value) can be converted to an array with the Array.from function.
Even with promises this is some rather awkward code. Multiple asynchronous actions are chained together in non-obvious ways. We again need a recursive function (next) to model looping through the nests.
And the thing the code actually does is completely linear—it always waits for the previous action to complete before starting the next one. In a synchronous programming model, it’d be simpler to express.
The good news is that JavaScript allows you to write pseudo-synchronous code to describe asynchronous computation. An async function is a function that implicitly returns a promise and that can, in its body, await other promises in a way that looks synchronous.
We can rewrite findInStorage like this:
async function findInStorage(nest, name) {
let local = await storage(nest, name);
if (local != null) return local;
let sources = network(nest).filter(n => n != nest.name);
while (sources.length > 0) {
let source = sources[Math.floor(Math.random() * sources.length)];
sources = sources.filter(n => n != source);
try {
let found = await routeRequest(nest, source, “storage”,name);
if (found != null) return found;
} catch (_) {}
}
throw new Error(“Not found”);
}
An async function is marked by the word async before the function keyword. Methods can also be made async by writing async before their name. When such a function or method is called, it returns a promise. As soon as the body returns something, that promise is resolved. If it throws an exception, the promise is rejected.
Inside an async function, the word await can be put in front of an expression to wait for a promise to resolve and only then continue the execution of the function.
Such a function no longer, like a regular JavaScript function, runs from start to completion in one go. Instead, it can be frozen at any point that has an await, and can be resumed at a later time.
For nontrivial asynchronous code, this notation is usually more convenient than directly using promises. Even if you need to do something that doesn’t fit the synchronous model, such as perform multiple actions at the same time, it is easy to combine await with the direct use of promises.
6. Generators
This ability of functions to be paused and then resumed again is not exclusive to async functions. JavaScript also has a feature called generator functions. These are similar, but without the promises.
When you define a function with function* (placing an asterisk after the word function), it becomes a generator. When you call a generator, it returns an iterator, which we already saw in Chapter 6.
function* powers(n) {
for (let current = n;; current *= n) {
yield current;
}
}
for (let power of powers(3)) { if (power > 50) break;
console.log(power);
}
// → 3 // → 9 // → 27
Initially, when you call powers, the function is frozen at its start. Every time you call next on the iterator, the function runs until it hits a yield expression, which pauses it and causes the yielded value to become the next value produced by the iterator. When the function returns (the one in the example never does), the iterator is done.
Writing iterators is often much easier when you use generator functions. The iterator for the Group class (from the exercise in “Iterable Groups” on page 114) can be written with this generator:
Group.prototype[Symbol.iterator] = function*() {
for (let i = 0; i < this.members.length; i++) {
yield this.members[i];
}
};
There’s no longer a need to create an object to hold the iteration state—generators automatically save their local state every time they yield.
Such yield expressions may occur only directly in the generator function itself and not in an inner function you define inside of it. The state a generator saves, when yielding, is only its local environment and the position where it yielded.
An async function is a special type of generator. It produces a promise when called, which is resolved when it returns (finishes) and rejected when it throws an exception. Whenever it yields (awaits) a promise, the result of that promise (value or thrown exception) is the result of the await expression.
7. The Event Loop
Asynchronous programs are executed piece by piece. Each piece may start some actions and schedule code to be executed when the action finishes or fails. In between these pieces, the program sits idle, waiting for the next action.
So callbacks are not directly called by the code that scheduled them. If I call setTimeout from within a function, that function will have returned by the time the callback function is called. And when the callback returns, control does not go back to the function that scheduled it.
Asynchronous behavior happens on its own empty function call stack. This is one of the reasons that, without promises, managing exceptions across asynchronous code is hard. Since each callback starts with a mostly empty stack, your catch handlers won’t be on the stack when they throw an exception.
try {
setTimeout(() => {
throw new Error(“Woosh”);
}, 20);
} catch (_) {
// This will not run
console.log(“Caught!”);
}
No matter how closely together events—such as timeouts or incoming requests—happen, a JavaScript environment will run only one program at a time. You can think of this as it running a big loop around your program, called the event loop. When there’s nothing to be done, that loop is stopped. But as events come in, they are added to a queue, and their code is executed one after the other. Because no two things run at the same time, slow-running code might delay the handling of other events.
This example sets a timeout but then dallies until after the timeout’s intended point of time, causing the timeout to be late.
let start = Date.now();
setTimeout(() => {
console.log(“Timeout ran at”, Date.now() – start); }, 20);
while (Date.now() < start + 50) {} console.log(“Wasted time until”, Date.now() – start);
// → Wasted time until 50
// → Timeout ran at 55
Promises always resolve or reject as a new event. Even if a promise is already resolved, waiting for it will cause your callback to run after the current script finishes, rather than right away.
Promise.resolve(“Done”).then(console.log);
console.log(“Me first!”);
// → Me first!
// → Done
In later chapters we’ll see various other types of events that run on the event loop.
Source: Haverbeke Marijn (2018), Eloquent JavaScript: A Modern Introduction to Programming,
No Starch Press; 3rd edition.