Safe Methods

The HTTP specification speaks of two properties of methods: safety and idempotence. The first category of methods that we will examine are those that have the property of safety. A safe method does not change the state of the server upon receipt. Verbs like GET and OPTIONS are safe.

Upon receiving a safe request, a server may retrieve information, but it may not alter its state in any observable way. Caching a response, while technically a state change, is not directly observable to a client. Caches are therefore allowed for servers processing safe methods.

As a client, you can feel confident in sending a safe request that you will not trigger any unwanted state changes. You can retry a GET on a different connection if you did not receive a response. The server should theoretically respond in the same way, assuming that no state changes occurred in the interim. Of course, there is no way for the client or the protocol to enforce this convention . It is entirely up to the server to refrain from changing state in response to a safe method.

Idempotent Methods

The second property of methods that HTTP defines is idempotence. This promises that the state of the server will change only upon the first receipt of a distinct message, not a subsequent receipt. All safe methods are by default idempotent; the server will not change state on even the first receipt, let alone the second one. And so the second category that we examine are idempotent, but not safe.

As we’ve learned in Chapter 4, idempotence is an important property of a message handler. It allows peers to retry messages without fear of changing state. If the first message was indeed received, then the second receipt will not change state further. In HTTP, PUT, PATCH, and DELETE are examples of idempotent verbs.

While idempotence is required for reliable message delivery, the reason for these verbs being labeled idempotent is not to permit retries and recover from duplication. It is simply based on the semantics of updating, patching, or deleting a resource. An update sets the state of a resource to a known quantity. A patch sets only some of the properties, but still to known quantities. Logically, one would anticipate that upon duplication, the resource is already in the desired state. Updating or patching the resource would have no effect. A similar argument applies for deleting an already-deleted resource.

Unfortunately, this line of reasoning only considers duplicates without intervening changes. If the resource changes between the original update and the duplicate, then the duplicate will reset the state of the resource back to a previous state. An eventually consistent handling of the message would ignore the duplicate , rather than applying it.

Consider the example in Figure 11-2. The first client issues a PUT request to update the value of a resource to “Bob”. That command takes effect, but the connection is interrupted before the response gets back. Meanwhile, a second client issues a PUT request to update the value of the same resource to “Robert”. That client sees their response. The first client makes a new connection and retries the message. If the server changes the value back to “Bob”, as the HTTP protocol would suggest, then it is not ignoring the duplicate message.

The HTTP server is behaving in an idempotent manner. And yet, the system is not eventually consistent. The problem is that idempotence is not sufficient. As we showed in Chapter 4, a protocol must also be commutative to ensure eventual consistency. If the server in Figure 11-2 had responded in the same way regardless of message order, then the outcome would have been better. Suppose that it treated “Bob” followed by “Robert” the same way as “Robert” followed by “Bob”, for example, by allowing the resource to be in a superposition of the two candidate values. Then, the subsequent receipt of the duplicate message would simply be ignored. Recall the diagram from Chapter 4, repeated in Figure 11-3, illustrating this solution.

The HTTP guarantee of idempotence is only semantic. The kinds of actions that idempotent verbs represent tend to bring a resource to a known state, even after the second application. But they offer no protection against message duplication. HTTP offers no guarantees of commutativity.

Non-idempotent Methods

The third category to consider are the methods that are neither safe nor idempotent. These methods offer no guarantees. They may change state upon every receipt. The POST verb is an example of this kind.

The semantics of POST make it likely that a change will in fact occur. In response to this request, a server creates a new resource and returns its identity in a 201 Created response. Presumably, the identity of the resource was not already known to the client before the request. If it was, the response would not need to include the URL. We can reasonably assume that in most implementations of POST, the identity was generated on the server.

When the identity is generated on the server, then there is little a client can do to prevent duplication. If the connection is lost before it receives the 201 Created response, the client has no recourse but to try again or report the error to the user (who is likely to try again). A second try will likely result in the creation of a second resource. HTTP makes no guarantee that the server will do any different .

Retry Within a Connection

Whatever the state-change guarantee of the HTTP method, the transport layer can only provide confirmation within the scope of a connection. Connections are relatively short-lived and reside entirely in memory. They represent a single-threaded communication channel between two peers.

Applications built on connection-oriented protocols need not retry messages on the same connection. TCP guarantees byte order, which implies that the retry would not be received until after the original message. But if the connection fails, then all bets are off. The sender has no knowledge of whether unconfirmed messages were received or not.

A connection can use delivery confirmation to guarantee that a message has been received. It cannot guarantee that a message will be received at some point in the future. Confirmation is a necessary, but not sufficient condition for durability. While HTTP only forwards the connection semantics from the transport layer, other application-layer protocols add durability.

Queues

AMQP is a standard application-layer protocol for exchanging messages in queues. It is implemented by such queueing systems as RabbitMQ, Apache ActiveMQ, and Azure Service Bus. AMQP is a configurable protocol, offering several levels of service. Some of those service levels provide at least once delivery or the guarantee that the sender will keep trying until a message is received. This promise survives beyond a single connection or session. It even survives power outages.

To provide this guarantee, AMQP implementations store messages on the client side. When a user publishes a message to an AMQP provider, it stores the message immediately, before contacting any remote peers. At that point, the application can be assured that the message will be delivered. The engine begins the background process of creating a connection, transmitting messages, and receiving confirmations. Once a message is confirmed, it can be removed from client storage. Until then, it must be preserved.

Topics

Where AMQP defines queues, Kafka defines topics. A topic is a persistent stream of records. Unlike a queue, records in a topic are not removed when they are consumed. This allows a Kafka topic to support multiple subscribers, each of which receives all messages.

In addition to multiple subscribers, message retention allows topics to provide a stronger delivery guarantee. Since all past messages are still in storage, a topic can determine whether a message is a duplicate. It can ignore the duplicate, preventing it from being sent to the subscribers. This level of guarantee is referred to as exactly once delivery.

Duplicate detection only lasts as long as the messages are persisted. Not all topic implementations store messages indefinitely. Kafka topics, for example, have a configurable retention period that defaults to 7 days. If a duplicate message arrives after the retention period expires, then it will be sent to subscribers.

For immutable architectures, at least once delivery is sufficient. Such applications are based on data structures that persist historical facts indefinitely. If a duplicate is received, it will be detected, as the fact is already in storage. And since records are identified by their content-based address, collisions are prevented at the storage level. Even though a durable protocol might offer exactly once delivery guarantees, enabling that configuration might prove to be as expensive as it is unnecessary.

Pivots

When producing a historical model, we identified regions. These were areas of the model in which all of the facts originated from a particular actor. When a predecessor/successor relationship crosses a boundary between two regions, two actors are collaborating with one another. I call such a predecessor/successor relationship a pivot.

The diagram that we used to introduce regions is reproduced in Figure 11-4. I have highlighted the pivots.

During the analysis phase, a region represented the responsibilities of a single actor or set of actors. As we transition into implementation, we will construct a microservice for each audience. And so each region now represents a microservice. In this example, conference organizers have a microservice for collecting proposals and defining schedules. Speakers have a microservice for viewing calls, submitting proposals, and learning about acceptance. Finally, attendees have a microservice for viewing a conference schedule, selecting sessions to attend, and submitting ratings. The pivots are points of integration among these microservices.

The microservice at the head of a pivot needs to publish the predecessor fact so that the microservice at the tail can subscribe to it. Let’s begin with the topmost predecessor in the causal chain, the call for speakers. This fact is in the organizer microservice.

Multiple Subscribers

Pivots at the top of the causal chain tend to be places where facts are published for multiple subscribers. The publisher might not have one specific use case in mind, and future subscribers could be added at any time. But even when there is a known use case, as in this example, sending a message to a specific subscriber introduces unnecessary coupling. And so top-level pivots are good candidates for topics, such as those provided by Kafka.

The microservice at the head of the arrow publishes a message to a topic when the predecessor fact is created. This message includes all of the information contained in the fact and all of its predecessors. To compute the set of all facts included in the message, perform a transitive closure over the predecessors. Recursively visit the predecessor relationships until the entire set is gathered. The message should contain all of this information, and only this information.

Two problems arise when publishing a message that contains more than the transitive closure of the predecessors. The first is that message is not deterministic. If the message contains internal database IDs, the time of creation, or any other detail not already part of the facts, then running the process again produces a different message. The process could be repeated for any number of reasons: there was an infrastructure glitch, the fact was produced by two redundant instances, the user clicked the submit button twice, and so on. If any of these situations arise, we want the process of generating a message from a fact to be deterministic, so that the downstream consumer can practice idempotence and ignore the duplicate.

The second problem is that the message might contain information in successor facts. Successors can be created either before or after the message is published. If the message contains successor information, then subscribers will not learn of new successors created after the fact. In the example in Figure 11-4, the transitive closure of the call for speakers fact includes the conference. It does not include times or rooms. If speakers needed to know (for some reason) the number of rooms at the conference, this information might or might not be available at the time of publication. If a room is added later, they will not learn about it.

There are some successors that you will want subscribers to learn about. For example, the conference date (not shown in Figure 11-4) will be an important part of knowing whether to submit a proposal. Given that that is likely to be a mutable property of a conference, it will be modeled as a successor. Analysts have two options for resolving this problem: they can turn the successor into a predecessor of the published fact, or they can publish the successor.

To turn the successor into a predecessor, apply the Transaction pattern described in Chapter 8. An example is shown in Figure 11-5. The published fact is a transaction that brings together all of the successors that are current at the time of publication. This brings those successors into the transitive closure. An organizer can change the date or location of the conference after publishing a call for speakers, but they now have a clear indication of the information that a speaker had when they proposed their sessions. They can use this information to publish a new call for speakers and contact the speakers who replied to the earlier one.

To publish the successor , produce an additional topic. Subscribers to the pivot can also subscribe to this topic. They will correlate the messages between the two topics using their common predecessor, in this case the conference. If the conference date is changed after the call for speakers has been published, then the subscriber will see that change and update their data store.

Responses

Facts on the tail of a pivot represent responses to messages. Responses are directed back toward earlier microservices. It therefore makes sense to use queues instead of topics for these kinds of messages. The producer of the original message includes the name of a response queue. Subscribers post response messages to the given queue. This manages coupling between publisher and subscriber, because the queue name is provided dynamically. In Figure 11-4, the proposal fact is a response to the call for speakers. It is directed toward the organizer microservice. That microservice will therefore create and manage a queue specifically for accepting proposals.

The response message, like the original message, is composed from the transitive closure of the fact. In this case, that means that the proposal contains information about the abstract and the speaker. If successors are required (such as speaker name), then the response should follow the Transaction pattern, as shown in Figure 11-6. Notice also that the message contains the call for speakers. The original message is a predecessor and will therefore be part of the transitive closure. This gives the original microservice sufficient information to correlate the responses.

Since the speaker microservice knows about the call for speakers topic, it is tempting to also have it know about the proposal queue. Doing so would seem not to increase coupling between the two services. But that would be a mistake. Only the organizer microservice knows how it will respond to proposals. It might change the topology in a future release. It alone should be responsible for deciding where the response queue is located.

Pivots further down in the causal chain also represent responses. In Figure 11-4, the reject and accept facts are responses to the proposal. These kinds of responses should follow the same pattern. When the speaker microservice generates the proposal message, it includes the name of its own response queue .

Notifications

Not all responses are direct successors of pivots. And not all two-way conversations between microservices appear as arrows crossing region boundaries in both directions. Sometimes the relationships are hidden a little deeper in the model.

Every conversation between microservices ends with a message that has no response. This message serves only as a notification. It informs the recipient of the outcome of a process. These appear as leaves in the model below pivots. The rate fact is an example in Figure 11-4.

When a conference attendee rates a session that they have attended, they are simply giving feedback to the organizer. They do not expect any response to that rating. There is therefore no further pivot below the rate fact indicating that the conversation continues. The rating is pushed to a queue that the organizer provides, just as any other response. The name of that queue will be included in the schedule message, as that is the predecessor of the nearest pivot.

Async over HTTP

External organizations will often need to publish messages to your services. Semantically, these are commands, instructing your service to perform some kind of business function. In a historical model, these are simply predecessors of a pivot, created in a remote region of the model. If we were working entirely within the scope of a single organization, we might choose a topic or queue to publish these messages. But since we are providing an endpoint for a partner, we will instead use HTTP. We can design the endpoint with additional constraints, not part of the HTTP specification, to make it work well with immutable architectures.

According to the HTTP specification, POST is neither required to be safe nor idempotent. However, an endpoint provided to partner organizations will clearly benefit from idempotence. This does not rule out HTTP POST. It only means that we implement the server to uphold stronger guarantees than the specification requires.

First, we ensure that the body of the message contains enough information to generate a unique identity. When we receive this request, we will generate a fact. The contents of this new fact need to be completely determined by the contents of the message. We will not use the time of receipt, a server-generated ID, or any other nondeterministic data to produce this fact. This guarantees that if the partner repeats this request, they will generate the same fact. That is the first step to making POST idempotent.

Second, we generate the URL of the resource using only information from the new fact and computing the transitive closure of the new fact to find the graph of all predecessors. Pull fields from these predecessors, and assemble them into a path. Append that path to the host name of the exposed endpoint to compose the URL. Assuming that we have used all of the fields, this generates a one-to-one mapping between facts and URLs. When the partner makes a subsequent call to the endpoint, we will be able to pull the components out of the path and reconstruct the fact.

And third, respond to the POST immediately after the new fact is stored. Do not wait until the request is processed. Before storing the fact, you will have the opportunity to run the authorization rules to make sure the partner is authorized to make this request. But there is no need to wait until the request is processed. You can complete processing asynchronously.

An endpoint implemented according to these constraints will be idempotent. Any subsequent POST of the same request will yield the existing fact. Because the service is using content-addressed storage, it will recognize that the fact already exists. It simply responds with the same URL as it had originally produced.

Such an endpoint is also durable. It does not respond until the fact is stored. A side effect of storing the fact might also be adding it to a topic or queue for further processing. The delivery confirmation of 201 Created indicates that this storage has occurred and has been committed. The sender may stop sending at that point; the message has been saved.

Finally, this endpoint is location independent. The URL does not contain any server-generated IDs. If the request had been handled by a different server, it would have produced the same URL and the same fact. We are free to reorganize our infrastructure, fail over to a backup datacenter, or mirror requests to different geographical regions . None of these implementation details will be visible to our partners.

Webhooks

If our infrastructure were completely within our control, we could just post responses to a queue. When working with partners, though, we sometimes don’t have the luxury of using queueing protocols. Yet we still want to pass the names of queues across organizational boundaries to reduce coupling between peer services.

The equivalent of a response queue in HTTP is a webhook. A webhook is an HTTP endpoint intended for use as a callback, a place to which to send responses. One service registers a webhook with another by providing an endpoint URL. The other service POSTs to this endpoint whenever there is new information to report about the topic.

A response in a historical model appears as the immediate or eventual successor of a pivot. We should generate webhooks based on the pivot’s predecessor. As described previously, compute the transitive closure of the predecessor and extract all fields of those facts. Construct a path and append it to a host name. That URL can now be used as a webhook. The service listening at that host can reconstruct the predecessor from the path.

Since the path contains all of the information necessary to reconstruct the predecessor, the body of the message does not need to include it. The body is all of the information necessary to create the successor fact except for the predecessor identified in the path. The service handling the webhook will follow all of the constraints of the command endpoint described earlier to ensure that responses are idempotent, durable, and location independent .

Emulating REST

In many integrations , an organization that has adopted immutable architecture will be integrating with one that has not. We might not have the luxury of defining the API so that it works well with immutability. We might have to adhere to an API that the partner has defined or provide one that is more familiar to them. In those situations, we can both consume and implement REST APIs from immutable services.

To consume a REST API from an immutable model, apply the Outbox pattern as described in Chapter 8. The Outbox pattern creates a bridge between a historical model and a third-party API. The caller maps facts that the partner needs to know about into API calls. They record a journal of the responses from those API calls indexed by the hash of the facts. While this pattern cannot turn a REST API into an idempotent, durable data exchange, it provides at least a little protection against infrastructure failures. The rest is up to the partner.

To produce a REST API with an immutable model, we apply the Structural patterns in Chapter 8 to map all of the incoming requests into semantically equivalent facts. A POST maps to an Entity fact and likely one or more Mutable Property facts. A PUT or PATCH maps to one or more Mutable Properties. A DELETE generates a Delete fact. Based on the semantics of the domain, other patterns could be brought into play.

Where possible, generate URLs as described previously using only information found in the transitive closure. Ideally, all of the information needed to generate the fact will be present in the request. That would produce a truly idempotent API. However, this will not always be possible. In particular, Mutable Property facts cannot be generated based only on the desired value of those properties. They need to know their predecessors, which is not something traditionally given in a REST API.

If the query results in one fact, and the value of that fact matches the desired value in the PUT or PATCH, then ignore the request. The property already unambiguously has the desired value. But if the number of results is not 1, or the current value is different, then create a new property fact having these results as predecessors. This algorithm allows the client to resolve conflicts by putting the desired value. Unfortunately, it does not capture what the client actually believed the original value to be and therefore record the real causal graph. Only a client participating in the immutable model and using an appropriately designed API could do that.

To GET a resource from a historical model, you will need to run several property queries. Generate the starting entity fact from the URL as described previously. Then run queries for all properties that you intend to return. If any of those queries returns more than one result, apply a conflict resolution function to determine the desired result. REST consumers are not used to properties having more than one value. Do not save the results of your conflict resolution. GETs are supposed to be safe.

A REST API produced from a historical model will compromise some of the benefits of immutability. It will only be as idempotent as a traditional REST implementation. It will not have the commutativity guarantees of an end-to-end immutable architecture. But it will be more familiar to partners who have not yet adopted these strategies .

Client-Side Queue

As the user interacts with the client application, it will generate facts. These facts will be stored in its local subset of the historical graph. They will also be added to an outgoing queue. The user is permitted to continue interacting with the application as soon as the fact is stored and the message is queued. They do not have to wait for it to be sent to the server.

Mobile applications can use a local SQLite, Core Data, or Realm database for both fact and queue storage. To design the fact storage, see all of the advice given in Chapter 10. The outgoing queue is simply a record of which facts have not yet been sent to the server. It could be as simple as a table of foreign keys into the fact storage.

Progressive web applications can use IndexedDB to store facts and queues. This browser feature is not as rich as a SQL database. Instead, it is simply a set of name/value pair collections. Consider using one collection per type of fact. The keys of these collections are the hashes of the facts. In addition, the PWA has a collection for the outbound queue, indexed using a monotonically increasing key.

To send the outgoing messages to the server, the mobile application or PWA calls an HTTP endpoint. This is not a RESTful endpoint providing the usual semantics of POST, PUT, PATCH, and DELETE. That kind of endpoint compromises the value of an immutable architecture and is intended for use by clients that do not participate in the historical model. Instead, this is a more constrained endpoint to which messages can be POSTed in an idempotent and commutative way, as described for intraorganizational command transfer.

To reduce latency and make the most efficient use of the network, clients will batch several outbound facts into a single request. The contents of a POST will be a collection of facts of various types. My favorite way to encode a batch is as a JSON object in which the keys are base-64 encoded hashes. This makes it easy for the server to find incoming facts by their hash and helps to ensure that a fact is not unnecessarily duplicated within the same batch. The body of each fact contains the type, the fields, and the hashes of its predecessors.

Assuming that the predecessors were already known to the server before the upload began, it would have no trouble finding them by their hash and establishing the link in its own database. However, this assumption cannot be guaranteed in practice. A client might not be talking to the same server from one session to the next. Servers may be spread across different datacenters to gain redundancy or geographic proximity. It is therefore wise to include the transitive closure over the predecessors of all outgoing facts. This is why it is important to eliminate unnecessary duplication within the batch.

When the server receives the batch, it must store each of the facts in turn. Storing a fact requires executing authorization queries and setting up foreign keys. For those reasons, the server must have already stored the predecessors. It therefore processes the incoming batch in topological order. It recursively visits all predecessors before handling each message. When it visits a fact, it first looks in a temporary data structure to see if it has already visited that fact. If not, it verifies the hash, then looks in its own database for that record. If it is present, it moves on. If not, it runs the authorization rules and saves the new fact.

When it is done, the server responds with a 200 OK message. After that, the client can delete all facts sent in the batch from its outbound queue. The client continues until the queue is empty .

Client-Side Bookmark

Because clients outnumber servers, all of the meta-information is kept on the client. This includes the outbound queue that we just discussed. And it also includes information about inbound facts. Rather than keeping a per-client queue on the server, each client keeps its own bookmark.

A bookmark is a placeholder within a sequence of facts. It identifies the last fact that the client has received and stored. The client can ask for a batch of facts greater than a given bookmark, and the server will respond with both a collection of facts and a new bookmark. That new bookmark corresponds to the last fact in the batch.

Because we need to know which facts came after a given bookmark, these identifiers must be totally ordered. A total order is one that allows us to compare any two elements in the sequence. We can tell for sure whether one element is before or after another. In every other sense, however, facts are partially ordered. You know that a predecessor came before a predecessor, but you cannot compare two facts that are not causally related. Furthermore, facts are usually identified by their hash, which does not obey any kind of order. We therefore need a new method of identifying facts for use with a bookmark.

The identity of a fact within a sequence must be monotonically increasing. Later facts cannot be given identifiers less than or equal to earlier ones. If that were ever violated, then a client using a bookmark from an earlier fact would miss later facts on subsequent requests. Timestamps alone are not sufficient for this purpose, as two facts could be stored at exactly the same time. An auto-incremented ID is the best choice. Even then, extra precautions must be taken to avoid reading a later ID before earlier IDs have been committed. One such precaution is to remove facts from the end of the batch until one is found that is old enough for concurrent writes to have settled. This implies that clients might not receive the absolute latest information until a subsequent read, but it mitigates against writes that happen out of order of ID allocation.

Imposing a total order on a partially ordered collection has a serious drawback. It means that bookmarks are location specific. If the mobile device or PWA were to connect to a different server on a subsequent fetch, the bookmark that it received from the last fetch would be meaningless. Different back-end nodes might have put the partially ordered facts into different total orders. For this reason, the client needs to keep a separate bookmark for each data store it contacts.

A datacenter having a load-balanced cluster of servers all sharing a common database is not a concern. No matter which server the client uses, the shared database generates the monotonically increasing IDs. The issue only arises when servers use different data stores. So bookmarks are really per database, not per server. Each database should generate its own unique identifier and use that to distinguish its bookmarks from those of other databases.

The client sends all of its bookmarks with the request. The server determines which bookmark is associated with the database it is using. If the client has no bookmark for that database, it starts at the beginning. The server then responds with a batch of facts, the database ID, and the new bookmark. The client stores all of those facts and updates its bookmark for that specific database. It repeats until the request yields no new facts.

In most network topologies, including a database ID is an overabundance of caution. The entire population of mobile clients can be served from a single database. As long as that remains true, then the clients will each have one bookmark that marches steadily forward. However, if the day ever comes that the database needs to fail over to a standby, then there is no guarantee that the order of insertions will be consistent between the two. Clients will find themselves redownloading the data set, but they will be able to detect and ignore duplicates. They will also be guaranteed not to miss any information as a result of data stored in different orders across different databases .

Choosing a Subset

A mobile or PWA client rarely needs to fetch the entire contents of the data model. These clients will have a single user, and that user will have access to only a subset of the data. Occasionally connected clients should fetch only the facts that their user needs. Based on an understanding of the model and how it will be used, we can divide facts into subsets. A particular user will have access to a small number of these subsets. The client will therefore need to keep track of separate bookmarks. It has one bookmark per database per subset.

A subset of a model can be defined by a single root fact. The subset includes all of the direct and indirect successors of that root. Imagine a cone extending down from the root and gathering together everything it touches, as illustrated in Figure 11-7. That is the subset of the model that the user needs to interact with that root.

There are two kinds of facts that make for good subset roots: groups and periods. A group is a top-level fact participating in the Membership pattern defined in Chapter 8. A membership fact has two predecessors: a group and a user. It grants the user membership into the group and therefore access to its resources. Membership facts often determine authorization and distribution rules. A user need not see facts outside of the groups of which he is a member.

A period is a near top-level fact participating in the Period pattern. This fact breaks successors down across time. A natural clock within the problem domain moves forward and points to the current period. This might be a date of business at a restaurant or a semester at a school. New facts are added to the current period. So client apps can focus only on recent periods and ignore older ones.

When a user interacts with an occasionally connected client, they only need the successors of the groups to which they belong and the most recent periods. But to understand a successor, they also need the transitive closure of its predecessors. For this reason, the subset that is actually downloaded to the device includes predecessors of those successors. The cone bounces back up the graph, forming a lattice structure as illustrated in Figure 11-8.

Recall the example of the secret channel that we studied in Chapter 7. In this example, the creator of a secret channel sent an invitation to their collaborators. Members of the channel could then exchange messages with one another. The diagram is recreated in Figure 11-9.

If we were to construct an occasionally connected mobile app or PWA for this model, SecretChannel would be an excellent choice of a fact that identifies a subset. If the user of the app is the creator or a collaborator in the channel, then they would expect all of the messages to be downloaded to their device. The group defines a subset of the graph containing the transitive closure of its successors.

This example illustrates one more root fact and one more rule of subsets. The user themselves should be the first root. This gives them a subset of all of the groups that they have created or been invited to join. That subset, however, should stop at the roots of other subsets. In Figure 11-10, for example, Alice both created a channel and was invited to Bob’s channel. The subset with Alice as the root includes her channel and the invitation, but does not include the messages in her channel. She specifically needs to pull those messages from that subset.

The algorithm for identifying facts within a subset boils down to a recursive traversal of the graph. Start at the identified root. Recursively visit all successors of that fact. Add that successor and its transitive closure of predecessors to the subset. If the visited fact is not itself a root, continue with its successors. This will give the set of facts that an occasionally connected client needs to serve its user.

Each client keeps a different set of bookmarks for each root. When it fetches facts from the server, it identifies the root by hash. The server responds with a batch of facts that are in that subset. In the case of the model in Figure 11-10, the first root is the logged in user. That fetches the channels that they have created and the invitations that have been sent to them. With that information, the client makes additional requests for each of those channels. This fetches the subset of messages that the user can see. And each channel has its own bookmark.

Avoiding Redundant Downloads

With queues for uploading facts and bookmarks for downloading them, we are starting to construct an algorithm for background data synchronization in an occasionally connected app. But as we put the two together, a problem emerges. All of the facts that a client uploads will be appended to the total order on the server. They will be greater than the client’s bookmark. That means that they will be downloaded again to the client the next time it fetches. This is a waste of bandwidth.

We would like the client to fetch only the facts that it itself did not upload. We can get close to this behavior by simply performing the download first, then the upload. The client downloads facts greater than its current bookmark. It stops when the fetch returns no new facts. Then it uploads batches from its outgoing queue. It stops when the queue is empty.

At that point—ideally—the only facts greater than its bookmark would be the ones it just uploaded. So if we could update the bookmark without redownloading those facts, we would avoid the redundancy. The problem is that other facts may have been added in the meantime. Other clients might have uploaded their facts, or other processes might have created information that should be sent to the client. And so we cannot assume that we can update the bookmark without missing something that happened concurrently.

A good optimization is to send with the fetch request a list of hashes. These are the facts that the client just finished uploaded. The server will filter out these facts from the response. In the ideal scenario, no new facts have been added, and so the entire download batch is filtered. In this case, the server returns an empty collection and a new bookmark. The client updates their bookmark, and we have avoided redundant downloads.

If, on the other hand, new facts were added concurrently, then the server would return only those new facts. It would also return the latest bookmark, including the new and the filtered facts. Upon seeing that response, the client would store the concurrent facts and update its bookmark. We achieve the correct behavior and avoid the redundant downloads.

This solution keeps all of the meta-information on the client. The client keeps track of the uploaded fact hashes in memory during the background sync operation. The server receives this information in the request and only uses it to filter that response. It does not store any per-client information in order to optimize network usage. And if something fails on the client, then it simply falls back to the correct, if suboptimal, redownloading of facts.