Forem: Stopa

Database in the Browser, a Spec

Stopa — Thu, 17 Jun 2021 18:32:00 +0000

How will we build web applications in the future?

If technological follows it's usual strategy, then whatever is difficult and valuable to do today, will become the easy and normal tomorrow.

How? With the discover of new abstractions. I imagine that writing Google Docs tomorrow will be the same difficulty as the average web app today.

And this begs the question -- what will those abstractions look like? Can we discover them today?

One way to find out, is to look at all the schleps we have to go through in building applications today, and see what we can do about it.

I think by the end, you'll agree with me that one of the most useful abstractions looks like a database in the browser. I'm getting ahead of myself though, let's start at the beginning:

Client

The journey of our web application begins with Javascript in the browser

A. Data Plumbing

The first job we have is to fetch information and display it in different places. For example, we may display a friends list, a friends count, a modal with a specific group of friends, etc

The problem we face, is that all components need to see consistent information. If one component sees different data for friends, it’s possible that you’ll get the wrong "count" showing up, or a different nickname in one view versus another.

To solve for this, we need to have a central source of truth. So, whenever we fetch anything, we normalize it and plop it in one place (often a store). Then, each component reads and transforms the data it needs (using a selector), It’s not uncommon to see something like:

// normalise [posts] -> {[id]: post}
fetchRelevantPostsFor(user).then(posts => {
  posts.forEach(post => {
    store.addPost(post);
  })
})

// see all posts by author: 
store.posts.values().reduce((res, post) => { 
  res[post.authorId] = res[post.authorId] || []; 
  res[post.authorId].push(post);
  return res;
}, {})

The question here is, why should we need to do all this work? We write custom code to massage this data, while databases have solved this problem for a long time now. We should be able to query for our data. Why can’t we just do:

SELECT posts WHERE post.author_id = ?;

on the information that we have inside the browser?

B. Change

The next problem is keeping data up to date. Say we remove a friend — what should happen?

We send an API request, wait for it to complete, and write some logic to "remove" all the information we have about that friend. Something like this:

deleteFriend(user, friend.id).then(res => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
})

But, this can get hairy to deal with quick: we have to remember every place in our store that could possibly be affected by this change. It’s like playing garbage collector in our heads. Our heads are not good at this.

One way folks avoid it, is to skip the problem and just re-fetch the whole world:

deleteFriend(user, id).then(res => {
  fetchFriends(user);
  fetchPostsRelevantToTheUser(post);
})

Neither solutions are very good. In both cases, there are implicit invariants we need to be aware of (based on this change, what other changes do we need to be aware of?) and we introduce lag in our application.

The rub is, whenever we make a change to the database, it does it’s job without us having to be so prescriptive. Why can’t this just happen automatically for us in the browser?

DELETE FROM friendships WHERE friend_one_id = ? AND friend_two_id = ?
-- Browser magically updates with all the friend and post information removed

C. Optimistic Updates

The problem you may have noticed with B., was that we had to wait for friendship removal to update our browser state.

In most cases, we can make the experience snappier with an optimistic update — after all, we know that the call will likely be a success. To do this, we do something like:

friendPosts = userStore.getFriendPosts(friend);
userStore.remove(friend.id);
postStore.removeUserPosts(friend.id);
deleteFriend(user, id).catch(e => { 
  // undo
  userStore.addFriend(friend);
  postStore.addPosts(friendPosts);
})

This is even more annoying. Now we need to manually update the success operation, and the failure operation.

Why is that? On the backend, a database is able to do optimistic updates ¹ — why can’t we do that in in the browser?

DELETE friendship WHERE friend_one_id = ? AND friend_two_id = ?
-- local store optimistically updated, if operation fails we undo

D. Reactivity

And data doesn’t just change from our own actions. Sometimes we need to connect to changes that other users make. For example, someone could unfriend us, or someone could send us a message.

To make this work, we need to do the same work that we did in our API endpoints, but this time on our websocket connection:

ws.listen(`${user.id}/friends-removed`, friend => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
}

But, this introduces two problems. First, we need to play garbage collector again, and remember every place that could be affected by an event.

Second, if we do optimistic updates, we have race conditions. Imagine you run an optimistic update, setting the color of a shape to blue, while a stale reactive update comes in, saying it’s red.

1. Optimistic Update: `Blue`
2. Stale reactive update: `Red`
3. Successful Update, comes in through socket: `Blue`

Now, you’ll see a flicker. The optimistic update will come in to blue, a reactive update will change it to red, but once the optimistic update succeeds, a new reactive update will turn it back to blue again. ²

Solving stuff like this has you dealing with consistency issues, scouring literature on…databases.

It doesn’t have to be that way though. What if each query was reactive?

SELECT friends FROM users JOIN friendships on friendship.user_one_id = ?

Now, any change in friendships would automatically update the view subscribed to this query. You wouldn’t have to manage what changes, and your local database could figure out what the "most recent update" is, removing much of the complexity.

Server

It only gets harder on the server.

E. Endpoints

Much of backend development ends up being a sort of glue between the database and and the frontend.

// db.js
function getRelevantPostsFor(userId) { 
    db.exec("SELECT * FROM users WHERE ...")
}

// api.js
app.get("relevantPosts", (req, res) => { 
  res.status(200).send(getRelevantPosts(req.userId));
})

This is so repetitive that we end up creating scripts to generate these files. But why do we need to do this at all? They are often coupled very closely to the client anyways. Why can’t we just expose the database to the client?

F. Permissions

Well, the reason we don’t, is because we need to make sure permissions are correctly set. You should only see posts by your friends, for example. To do this, we add middleware to our API endpoints:

app.put("user", auth, (req, res) => { 
  ...
}

But, this ends up getting more and more confusing. What about websockets? New code changes sometimes introduce ways to update database objects that you didn’t expect. All of a sudden, you’re in trouble.

The question to ask here, is why is authentication at the API level? Ideally, we should have something very close to the database, making sure any data access passes permission checks. There’s row-level security on databases like Postgres, but that can get hairy quick ³. What if you could "describe" entities near the database?

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfSameUser(),
  ]
}

Here we compose authentication rules, and make sure that any way you try to write too and update a user entity, you are guaranteed to that you are permitted. All of a sudden, instead of most code changes affecting permissions, only a few do.

G. Audits, Undo / Redo

And at some point, we get requirements that blow up complexity for us.

For example, say we need to support "undo / redo", for friendship actions. A user deletes a friend, and then they press "undo" — how could we support this?

We can’t just delete the friendship relation, because if we did, then we wouldn’t know if this person was "already friends", or was just asking now to become friends. In the latter case we may need to send a friend request.

To solve this, we’d evolve our data model. Instead of a single friendship relation, we’d have "friendship facts"

[
  {status: "friends", friend_one_id: 1, friend_two_id: 2, at: 1000}, 
  {status: "disconnected", friend_one_id: 1, friend_two_id: 2, at: 10001},
]

Then the "latest fact" would represent whether there is a friendship or not.

This works, but most databases weren’t designed for it: the queries don’t work as we expect, optimizations are harder than we expect. We end up having to be very careful about how we do updates, in case we end up accidentally deleting records.

All of a sudden, we become "sort of database engineers", devouring literature on query optimization.

This kind of requirement seems unique, but it’s getting more common. If you deal with financial transactions, you need something like this for auditing purposes. Undo / Redo is a necessity in lots of apps.

And god forbid an error happens and we accidentally delete data. In a world of facts there would be no such thing — you can just undo the deletions. But alas, this is not the world most of us live in.

There are models that treat facts as a first class citizen (Datomic, which we’ll talk about soon), but right now they’re so foreign that it’s rarely what engineers reach too. What if it wasn't so foreign?

H. Offline Mode

There’s more examples of difficulty. What about offline mode? Many apps are long-running and can go for periods without internet connection. How can we support this?

We would have to evolve our data model again, but this time really keep just about everything as a "fact", and have a client-side database that evolve it’s internal state based on them. Once a connection is made, we should be able to reconcile changes.

This gets extremely hard to do. In essence, anyone who implements this becomes a database engineer full-stop. But, if we had a database in the browser, and it acted like a "node" in a distributed database, wouldn’t this just happen automatically for us?

Turns out, fact-based systems in fact make this much, much easier. Many think we need to resort to operational transforms to do stuff like this, but as figma showed [^5], as long as we’re okay with having a single leader, and are fine with last-write-wins kind of semantics, we can drastically simplify this and just facts are enough. When time for even more serious resolution comes, you can open up the OT rabbit hole.

Imagine…offline mode off the bat. What would the most applications feel like after this?

I. Reactivity

We talked about reactivity from the client. On the server it’s worrying too. We have to ensure that all the relevant clients are updated when data changes. For example, if a "post" is added, we need to make sure that all possible subscriptions related to this post are notified.

function addPost(post) {
  db.addPost(post);
  getAllFriends(post).forEach(notifyNewPost);
}

This can get hairy. It’s hard to know all the topics that could be related. It could also be easy to miss: if a database is updated with a query outside of addPost, we’d never know. This work is up to the developer to figure out. It starts off easy, but gets ever more complex.

Yet, the database could be aware of all these subscriptions too, and could just handle updating the relevant queries. But most don’t. RethinkDB is the shining example that did this well. What if this was possible with the query language of your choice?

J. Derived Data

Eventually, we end up needing to put our data in different places: either caches (Redis), search indexes (ElasticSearch), or analytics engines (Hive). Doing this becomes pretty daunting. You may need to introduce some sort of a queue (Kafka), so all of these derived sources are kept up to date. Much of this involves provisioning machines, introducing service discovery, and the whole shebang.

Why is this so complicated though? In a normal database you can do something like:

CREATE INDEX ...

Why can’t we do that, for other services? Martin Kleppman, in his Data Intensive Applications, suggests a language like this:

db |> ElasticSearch
db |> Analytics
db.user |> Redis
// Bam, we've connected elastic search, analytics, and redis to our db

Monkey Wrenches

Wow, we’ve gone up to J. But these are only issues you start to face once you start building your application. What about before?

K. TTP — Time to Prototype

Perhaps the most restrictive problem for developers today is how hard it is to get started. If you want to store user information and display a page, what do you do?

Before, it was a matter of index.html and FTP. Now, it’s webpack, typescript, build processes galore, often multiple services. There are so many moving pieces that it’s hard to take a step.

This can seem like a problem only inexperienced people need to contend with, and if they just spent some time they’ll get faster. I think it’s more important than that. Most projects live on the fringe — they aren’t stuff you do as a day job. This means that even a few minutes delay in prototyping could kill a magnitude more projects.

Making this step easier would dramatically increase the number of applications we get to use. What if it was easier than index.html and FTP?

Current Solutions

Wow, that’s a lot of problems. It may seem bleak, but if you just look a few years back, it’s surprising how much has improved. After all, we don’t need to roll our own racks anymore. And in the spirit of the early days of painting, many great folks are working on solutions to these problems. What are some of them?

1) Firebase

I think Firebase has done some of the most innovative work in moving web application development forward. The most important thing they got right, was a database on the browser.

With firebase, you query your data the same way you would on the server. By creating this abstraction, they solved A-E. Firebase handles optimistic updates, and is reactive by default. It obviates the need for endpoints by providing support for permissions.

They’re strength also stems for K: I think it still has the best time-to-prototype in the market. You can just start with index.html!

However, it has two problems:

First, query strength. Firebase’s choice of a document model makes the abstraction simpler to manage, but it destroys your query capability. Very often you’ll fall into a place where you have to de-normalize data, or querying for it becomes tricky. For example, to record a many-to-many relationship like a friendship, you’d need to do something like this:

userA: 
  friends: 
    userBId: true 
userB:
  friends:
    userAId: true

You de-normalize friendships across two different paths (userA/friends/userBId) and (userB/friends/userAId). Grabbing the full data requires you to manually replicate a join:

1. get `userA/friends`
2. for each id, get `/${id}`

These kind of relationships sprout up very quickly in your application. It would be great if a solution helped you handle it.

Second, permissions. Firebase lets you write permissions using a limited language. In practice, these rules get hairy quickly — to the point that folks resort to writing some higher-level language themselves and compiling down to Firebase rules.

We experimented a lot on this at Facebook, and came to the conclusion that you need a real language to express permissions. If Firebase had that, it would be much more powerful.

With the remaining items (audits, Undo / Redo, Offline Mode for writes, Derived Data) — Firebase hasn’t tackled them yet.

2) Supabase

Supabase is trying to do what Firebase did for Mongo, but for Postgres. If they did this, it would be quite an attractive option, as it would solve Firebase’s biggest problem: query strength.

Supabase has some great wins so far. Their auth abstraction is great, which makes it one of the few platforms that are as easy to get started with as firebase was.

Their realtime option allows you to subscribe to row-level updates. For example, if we wanted to to know whenever a friendship gets created, updated, or changed, we could write this:

const friendsChange = supabase
  .from('friendships:friend_one_id=eq.200')
  .on('*', handleFriendshipChange)
  .subscribe()

This in practice can get you far. It can get hairy though. For example, if a friend is created, we may not have the user information and we’d have to fetch it.

function handleFriendshipChange(friendship) { 
  if (!userStore.get(friendship.friend_two_id)) { 
      fetchUser(...)
  }
}

This points to Supabase’s main weakness: it doesn’t have a "database on the browser" abstraction yet. Though you can make queries, you are responsible for normalizing and massaging data. This means that they can’t do optimistic updates automatically, reactive queries, etc.

Their permission model is also similar to Firebase, in that they defer to Postgres’ row-level security. This can be great to start out, like Firebase gets hairy quickly. Often these rules can slow down the query optimizer, and the SQL itself gets harder and harder to reason about.

3) GraphQL + Hasura

GraphQL is an excellent way to declaratively define data you want from the client. services like Hasura can take a database like Postgres, and do smart things like give you a GraphQL API out of it.

Hasura is very compelling for reads. They do a smart job of figuring joins, and can get you a good view for your data. With a flip, you can turn any query into a subscription. When I first tried turning a query into a subscription, it certainly felt magical.

The big issue today with GraphQL tools in general, is their time-to-prototype. You often need multiple different libraries and build steps. Their write-story is also a little less compelling. Optimistic Updates don’t just happen automatically — you have to bust it yourself.

Lay of the Land

We’ve looked at the three most promising solutions. Right now, Firebase solves the most problems off the bat. Supabase gives you query strength at the expense of more client-side support. Hasura gives you more powerful subscriptions and more powerful local state, at the expense of time-to-prototype. As far as I can see, none are handling conflict resolution, undo / redo, powerful reactive queries on the client yet.

Future

Now the question: what will the evolution of these tools look like?

In some ways, the future is happening now. I think Figma, for example, is an app from the future: it handles handle offline-mode, undo / redo and multiplayer beautifully.

If we wanted to make an app like that, what would an ideal abstraction for data look like?

Requirements

1) A database on the client, with a powerful query language

From the browser, this abstraction would have to be like firebase, but with a strong query language.

You should be able to query your local data, and it should be as powerful as SQL. Your queries should be reactive, and update automatically if there are changes. It should handle optimistic updates for you too.

user = useQuery("SELECT * FROM users WHERE id = ?", 10);

2) A real permission language

Next up, we’d need a composable permission language. FB’s EntFramework is the example I keep going back too, because of how powerful it was. We should be able to define rules on entities, and should just be guaranteed that we won’t accidentally see something we’re not allowed to see.

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
  ]
}

3) Offline Mode & Undo / Redo

Finally, this abstraction should make it easy for us to implement offline mode, or undo redo. If a local write happens, and there’s a conflicting write on the server, there should be a reconciler which does the right thing most of the time. If there are issues, we should be able to nudge it along in the right direction.

Whatever abstraction we choose, it should give us the ability to run writes while we’re offline.

4) The Next Cloud

Finally, we should be able to express data dependencies without having to spin anything up. With a simple

db.user |> Redis

all queries to users would magically be cached by Redis.

Sketch of an Implementation

Okay, those requirements sound magical. What would an implementation look like today?

Datomic & Datascript

In the Clojure world, folks have long been fans of Datomic, a facts-based database that lets you "see every change over time". Nikita Tonsky also implemented datascript, a client-side database and query engine with the same semantics as Datomic!

They’ve been used to build offline-enabled applications like Roam, or collaborative applications like Precursor. If we were to package up a Datomic-like database on the backend, and datascript-like database on the frontend, it could become "database on the client with a powerful query language"!

Reactivity

Datomic makes it easy for you to subscribe to new committed facts to the database. What if we made a service on top if, which kept queries and listened to these facts. From a change, we would update the relevant query. All of a sudden, our database becomes realtime!

Permission Language

Our server could accept code fragments, which it runs when fetching data. These fragments would be responsible for permissions, giving us a powerful permission language!

Pipe

Finally, we can write up some DSL, which lets you pipe data to Elastic Search, Redis, etc, all according to the user’s preferences.

With that, we have a compelling offering.

Considerations

So, why doesn’t this exist yet? Well...

Datalog is unfamiliar

If we were to use a Datomic-like database, we wouldn’t use SQL anymore. Datomic uses a logic-based query language called Datalog. Now, it is just as, if not more, powerful than SQL. The only gotcha is that for the uninitiated it looks very daunting:

[:find [(pull ?c [:conversation/user :conversation/message]) ...]
 :where [?e :session/thread ?thread-id] 
        [?c :conversation/thread ?thread-id]]

This query would find all messages, alongside with the user information, for the active thread in this current "session". Not bad!

Once you get to know it, it’s an unbelievably elegant language. However, I don’t think that’s enough. Time-to-prototype needs to be blazing fast, and having to learn this may be too much.

There have been some fun experiments in making this easier. Dennis Heihoff tried using natural language for example. This points to an interesting solution: Could we write a slightly more verbose, but more natural query language that compiles to Datalog? I think so.

The other problem, is that data modeling is also different from what people are used too. Firebase is the gold-standard, where you can write your first mutation without specifying any schema.

Though it will be hard, I think we should aim to be as close to "easy" as possible. Datascript only requires you to indicate references and multi-valued attributes. Datomic requires a schema, but perhaps if we used an open-source, datalog-based database, we could enhance it to do something similar. Either as little schema as possible, or a "magically detectable schema".

Datalog would be hard to make reactive

A big problem with both SQL and Datalog, is that based on some new change, it’s hard to figure out which queries need to be updated.

I don’t think it’s impossible though. Hasura does polling and it scaled ⁴. We could try having a specific language for subscriptions as well, similar to Supabase. If we can prove certain queries can only change by some subset of facts, we can move them out of polling.

This is a hard problem, but I think it’s a tractable one.

A permission language would slow things down

One problem with making permission checks a full-blown language, is that we’re liable to overfetch data.

I think this is a valid concern, but with a database like Datomic, we could handle it. Reads are easy to scale and cache. Because everything’s a fact, we could create an interface that guides people to only fetch the values they need.

Facebook was able to do it. It will be hard, but it’s possible.

It may be too large of an abstraction

Frameworks often fail to generalize. For example, what if we wanted to share mouse position? This is ephemeral state and doesn’t fit in a database, but we do need to make it realtime — where would we keep it? There’s a lot of these-kinds-of-things that are going to pop up if you build an abstraction like this, and you’re likely to get it wrong.

I do think this is a problem. If someone were to tackle this, the best bet would be to go the Rails approach: Build a production app using it, and extract the internals out as a product. I think they’d have a good shot at finding the right abstraction.

It will only be used for toys

The common issue with these kind of products, is that people will only use them for hobby projects, and there won’t be a lot of money in it. I think Heroku and Firebase point to a bright future here.

Large companies start as side-projects. Older engineers may look at Firebase like a toy, but many a successful startup now runs on it. Instead of being a just a database, perhaps it’ll become a whole new platform — the successor to AWS.

The Market is very competitive

The market is competitive and the users are fickle. Slava’s Why RethinkDB Failed paints a picture for how hard it is to win in the developer tools market. I don’t think he is wrong. Doing this would require a compelling answer to how you’ll build a moat, and expand towards The Next AWS.

Fin

Well, we covered the pains, covered the competitors, covered an ideal solution, and went through the considerations. Thank you for walking with me on this journey!

Like-Minded Folks

These ideas are not new. My friends Sean Grove and Daniel Woelfel’s built Dato, a framework that integrated a bunch of these ideas. Nikita Tonsky wrote Web After Tomorrow an essay with a very similar spirit. Perhaps most exciting, I discovered http://homebase.io: their ideas look very compelling, and are looking for the solution in a similar way.

It may require some iteration to figure out the interface, but the there’s an interesting road ahead.

Next Up

I’m toying with some ideas in this direction. The big problem to solve here, is how important this is for people, and whether a good abstraction can work. To solve the first, I wrote this essay. Is this a hair-on-fire problem that you’re facing? If it is, to the point that you’re actively looking for solutions, please reach out to me on Twitter! I’d love to learn your use case 🙂. As I create applications, I’ll certainly keep this back of mind — who knows, maybe a good abstraction can be pulled out.

Thanks Joe Averbukh, Sean Grove, Ian Sinnott, Daniel Woelfel, Dennis Heihoff, Mark Shlick, Alex Reichert, Alex Kotliarskyi, Thomas Schranz, for reviewing drafts of this essay

You may not notice this as Postgres gives a consistency guarantee. However, for them to support multiple concurrent transactions, they in effect need to be able to keep "temporary alterations" ↩
Figma mentions this problem in their mutiplayer essay ↩
Plain SQL and boolean logic is hard to reuse, and can slow down the query planner. Many folks who have medium-sized apps experience this quickly. ↩
Take a look at Hasura’s notes ↩

[Spec] A Database in the Browser

Stopa — Thu, 17 Jun 2021 18:27:17 +0000

If you look at the the ecosystem of web applications and measure by difficulty, what apps come to the top of the list?

If you asked me, I think Google Docs and Figma would be prime contenders. They're so seamless it slips our mind that they function offline, they're multiplayer, they handle conflicts, and they support intricate undo / redo.

This gets me excited about whats to come, because what's at the edge of difficulty today tends to become the new normal tomorrow. I think the average application will function more and more like Google Docs and Figma.

How will that be possible? We'll need to find new abstractions that will make building Google Docs as easy as writing a CRUD app today.

And that begs the question: what will those abstractions look like?

One way to find out, is to look at all the schleps we have to go through today, and see what we can do about it.

Dear reader, this essay is my attempt to follow that plan. We’ll take a tour of what's it like to build a web application today: we'll go over the problems we face, assess solutions like Firebase, Supabase, Hasura and friends, and see what's left to do. I think by the end, you'll agree with me that one of the most useful abstractions looks like a powerful database in the browser.

I'm getting ahead of myself though, let's start at the beginning:

Client

The journey of our web application begins with Javascript in the browser

A. Data Plumbing

The first job we have is to fetch information and display it in different places. For example, we may display a friends list, a friends count, a modal with a specific group of friends, etc

// normalise [posts] -> {[id]: post}
fetchRelevantPostsFor(user).then(posts => {
  posts.forEach(post => {
    store.addPost(post);
  })
})

// see all posts by author: 
store.posts.values().reduce((res, post) => { 
  res[post.authorId] = res[post.authorId] || []; 
  res[post.authorId].push(post);
  return res;
}, {})

SELECT posts WHERE post.author_id = ?;

on the information that we have inside the browser?

B. Change

The next problem is keeping data up to date. Say we remove a friend — what should happen?

We send an API request, wait for it to complete, and write some logic to "remove" all the information we have about that friend. Something like this:

deleteFriend(user, friend.id).then(res => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
})

One way folks avoid it, is to skip the problem and just re-fetch the whole world:

deleteFriend(user, id).then(res => {
  fetchFriends(user);
  fetchPostsRelevantToTheUser(post);
})

The rub is, whenever we make a change to the database, it does it’s job without us having to be so prescriptive. Why can’t this just happen automatically for us in the browser?

DELETE FROM friendships WHERE friend_one_id = ? AND friend_two_id = ?
-- Browser magically updates with all the friend and post information removed

C. Optimistic Updates

The problem you may have noticed with B., was that we had to wait for friendship removal to update our browser state.

In most cases, we can make the experience snappier with an optimistic update — after all, we know that the call will likely be a success. To do this, we do something like:

friendPosts = userStore.getFriendPosts(friend);
userStore.remove(friend.id);
postStore.removeUserPosts(friend.id);
deleteFriend(user, id).catch(e => { 
  // undo
  userStore.addFriend(friend);
  postStore.addPosts(friendPosts);
})

This is even more annoying. Now we need to manually update the success operation, and the failure operation.

Why is that? On the backend, a database is able to do optimistic updates ¹ — why can’t we do that in in the browser?

DELETE friendship WHERE friend_one_id = ? AND friend_two_id = ?
-- local store optimistically updated, if operation fails we undo

D. Reactivity

And data doesn’t just change from our own actions. Sometimes we need to connect to changes that other users make. For example, someone could unfriend us, or someone could send us a message.

To make this work, we need to do the same work that we did in our API endpoints, but this time on our websocket connection:

ws.listen(`${user.id}/friends-removed`, friend => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
}

But, this introduces two problems. First, we need to play garbage collector again, and remember every place that could be affected by an event.

1. Optimistic Update: `Blue`
2. Stale reactive update: `Red`
3. Successful Update, comes in through socket: `Blue`

Solving stuff like this has you dealing with consistency issues, scouring literature on…databases.

It doesn’t have to be that way though. What if each query was reactive?

SELECT friends FROM users JOIN friendships on friendship.user_one_id = ?

Server

It only gets harder on the server.

E. Endpoints

Much of backend development ends up being a sort of glue between the database and and the frontend.

// db.js
function getRelevantPostsFor(userId) { 
    db.exec("SELECT * FROM users WHERE ...")
}

// api.js
app.get("relevantPosts", (req, res) => { 
  res.status(200).send(getRelevantPosts(req.userId));
})

F. Permissions

Well, the reason we don’t, is because we need to make sure permissions are correctly set. You should only see posts by your friends, for example. To do this, we add middleware to our API endpoints:

app.put("user", auth, (req, res) => { 
  ...
}

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfSameUser(),
  ]
}

G. Audits, Undo / Redo

And at some point, we get requirements that blow up complexity for us.

For example, say we need to support "undo / redo", for friendship actions. A user deletes a friend, and then they press "undo" — how could we support this?

To solve this, we’d evolve our data model. Instead of a single friendship relation, we’d have "friendship facts"

[
  {status: "friends", friend_one_id: 1, friend_two_id: 2, at: 1000}, 
  {status: "disconnected", friend_one_id: 1, friend_two_id: 2, at: 10001},
]

Then the "latest fact" would represent whether there is a friendship or not.

All of a sudden, we become "sort of database engineers", devouring literature on query optimization.

H. Offline Mode

There’s more examples of difficulty. What about offline mode? Many apps are long-running and can go for periods without internet connection. How can we support this?

Imagine…offline mode off the bat. What would the most applications feel like after this?

I. Reactivity

function addPost(post) {
  db.addPost(post);
  getAllFriends(post).forEach(notifyNewPost);
}

J. Derived Data

Why is this so complicated though? In a normal database you can do something like:

CREATE INDEX ...

Why can’t we do that, for other services? Martin Kleppman, in his Data Intensive Applications, suggests a language like this:

db |> ElasticSearch
db |> Analytics
db.user |> Redis
// Bam, we've connected elastic search, analytics, and redis to our db

Monkey Wrenches

Wow, we’ve gone up to J. But these are only issues you start to face once you start building your application. What about before?

K. TTP — Time to Prototype

Perhaps the most restrictive problem for developers today is how hard it is to get started. If you want to store user information and display a page, what do you do?

Before, it was a matter of index.html and FTP. Now, it’s webpack, typescript, build processes galore, often multiple services. There are so many moving pieces that it’s hard to take a step.

Making this step easier would dramatically increase the number of applications we get to use. What if it was easier than index.html and FTP?

Current Solutions

1) Firebase

I think Firebase has done some of the most innovative work in moving web application development forward. The most important thing they got right, was a database on the browser.

They’re strength also stems for K: I think it still has the best time-to-prototype in the market. You can just start with index.html!

However, it has two problems:

userA: 
  friends: 
    userBId: true 
userB:
  friends:
    userAId: true

You de-normalize friendships across two different paths (userA/friends/userBId) and (userB/friends/userAId). Grabbing the full data requires you to manually replicate a join:

1. get `userA/friends`
2. for each id, get `/${id}`

These kind of relationships sprout up very quickly in your application. It would be great if a solution helped you handle it.

We experimented a lot on this at Facebook, and came to the conclusion that you need a real language to express permissions. If Firebase had that, it would be much more powerful.

With the remaining items (audits, Undo / Redo, Offline Mode for writes, Derived Data) — Firebase hasn’t tackled them yet.

2) Supabase

Supabase is trying to do what Firebase did for Mongo, but for Postgres. If they did this, it would be quite an attractive option, as it would solve Firebase’s biggest problem: query strength.

Supabase has some great wins so far. Their auth abstraction is great, which makes it one of the few platforms that are as easy to get started with as firebase was.

Their realtime option allows you to subscribe to row-level updates. For example, if we wanted to to know whenever a friendship gets created, updated, or changed, we could write this:

const friendsChange = supabase
  .from('friendships:friend_one_id=eq.200')
  .on('*', handleFriendshipChange)
  .subscribe()

This in practice can get you far. It can get hairy though. For example, if a friend is created, we may not have the user information and we’d have to fetch it.

function handleFriendshipChange(friendship) { 
  if (!userStore.get(friendship.friend_two_id)) { 
      fetchUser(...)
  }
}

3) GraphQL + Hasura

GraphQL is an excellent way to declaratively define data you want from the client. services like Hasura can take a database like Postgres, and do smart things like give you a GraphQL API out of it.

Lay of the Land

Future

Now the question: what will the evolution of these tools look like?

In some ways, the future is happening now. I think Figma, for example, is an app from the future: it handles handle offline-mode, undo / redo and multiplayer beautifully.

If we wanted to make an app like that, what would an ideal abstraction for data look like?

Requirements

1) A database on the client, with a powerful query language

From the browser, this abstraction would have to be like firebase, but with a strong query language.

user = useQuery("SELECT * FROM users WHERE id = ?", 10);

2) A real permission language

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
  ]
}

3) Offline Mode & Undo / Redo

Whatever abstraction we choose, it should give us the ability to run writes while we’re offline.

4) The Next Cloud

Finally, we should be able to express data dependencies without having to spin anything up. With a simple

db.user |> Redis

all queries to users would magically be cached by Redis.

Sketch of an Implementation

Okay, those requirements sound magical. What would an implementation look like today?

Datomic & Datascript

Reactivity

Permission Language

Our server could accept code fragments, which it runs when fetching data. These fragments would be responsible for permissions, giving us a powerful permission language!

Pipe

Finally, we can write up some DSL, which lets you pipe data to Elastic Search, Redis, etc, all according to the user’s preferences.

With that, we have a compelling offering.

Considerations

So, why doesn’t this exist yet? Well...

Datalog is unfamiliar

[:find [(pull ?c [:conversation/user :conversation/message]) ...]
 :where [?e :session/thread ?thread-id] 
        [?c :conversation/thread ?thread-id]]

This query would find all messages, alongside with the user information, for the active thread in this current "session". Not bad!

Once you get to know it, it’s an unbelievably elegant language. However, I don’t think that’s enough. Time-to-prototype needs to be blazing fast, and having to learn this may be too much.

The other problem, is that data modeling is also different from what people are used too. Firebase is the gold-standard, where you can write your first mutation without specifying any schema.

Datalog would be hard to make reactive

A big problem with both SQL and Datalog, is that based on some new change, it’s hard to figure out which queries need to be updated.

This is a hard problem, but I think it’s a tractable one.

A permission language would slow things down

One problem with making permission checks a full-blown language, is that we’re liable to overfetch data.

Facebook was able to do it. It will be hard, but it’s possible.

It may be too large of an abstraction

It will only be used for toys

The Market is very competitive

Fin

Well, we covered the pains, covered the competitors, covered an ideal solution, and went through the considerations. Thank you for walking with me on this journey!

Like-Minded Folks

It may require some iteration to figure out the interface, but the there’s an interesting road ahead.

Next Up

Thanks Joe Averbukh, Sean Grove, Ian Sinnott, Daniel Woelfel, Dennis Heihoff, Mark Shlick, Alex Reichert, Alex Kotliarskyi, Thomas Schranz, for reviewing drafts of this essay

You may not notice this as Postgres gives a consistency guarantee. However, for them to support multiple concurrent transactions, they in effect need to be able to keep "temporary alterations" ↩
Figma mentions this problem in their mutiplayer essay ↩
Plain SQL and boolean logic is hard to reuse, and can slow down the query planner. Many folks who have medium-sized apps experience this quickly. ↩
Take a look at Hasura’s notes ↩

Web Applications from the Future: A Database in the Browser

Stopa — Wed, 02 Jun 2021 01:12:23 +0000

If you look at the the ecosystem of web applications and measure by difficulty, what apps come to the top of the list?

If you asked me, I think Google Docs and Figma would be there. They're so seamless it seldom enters our mind that they function offline, they're multiplayer, they handle conflicts, and they even support intricate undo / redo.

This bodes for optimism in the future, because what's at the edge of difficulty today tends to become the new normal tomorrow. I think the average application will function more and more like Google Docs and Figma.

For that to be possible, difficulty will need to go down. We'll need to find new abstractions which will make writing these kind of applications as easy as writing a CRUD app today.

What will these abstractions look like?

Dear reader, this question has led me on the journey that produced this essay.

One way to find out, is to look at all the schleps we have to go through today, and see what we can do about them. In this essay we'll take a tour of what's it like to build a web application: we'll go over the problems we face, assess solutions like Firebase, Supabase, Hasura and friends, and see what's left to do. I think by the end, you'll agree with me that one of the most useful abstractions looks like a powerful database in the browser. I'm getting ahead of myself though, let's start at the beginning:

Client

The journey of our web application begins with Javascript in the browser

A. Data Plumbing

The first job we have is to fetch information and display it in different places. For example, we may display a friends list, a friends count, a modal with a specific group of friends, etc

// normalise [posts] -> {[id]: post}
fetchRelevantPostsFor(user).then(posts => {
  posts.forEach(post => {
    store.addPost(post);
  })
})

// see all posts by author: 
store.posts.values().reduce((res, post) => { 
  res[post.authorId] = res[post.authorId] || []; 
  res[post.authorId].push(post);
  return res;
}, {})

SELECT posts WHERE post.author_id = ?;

on the information that we have inside the browser?

B. Change

The next problem is keeping data up to date. Say we remove a friend — what should happen?

We send an API request, wait for it to complete, and write some logic to "remove" all the information we have about that friend. Something like this:

deleteFriend(user, friend.id).then(res => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
})

One way folks avoid it, is to skip the problem and just re-fetch the whole world:

deleteFriend(user, id).then(res => {
  fetchFriends(user);
  fetchPostsRelevantToTheUser(post);
})

The rub is, whenever we make a change to the database, it does it’s job without us having to be so prescriptive. Why can’t this just happen automatically for us in the browser?

DELETE FROM friendships WHERE friend_one_id = ? AND friend_two_id = ?
-- Browser magically updates with all the friend and post information removed

C. Optimistic Updates

The problem you may have noticed with B., was that we had to wait for friendship removal to update our browser state.

In most cases, we can make the experience snappier with an optimistic update — after all, we know that the call will likely be a success. To do this, we do something like:

friendPosts = userStore.getFriendPosts(friend);
userStore.remove(friend.id);
postStore.removeUserPosts(friend.id);
deleteFriend(user, id).catch(e => { 
  // undo
  userStore.addFriend(friend);
  postStore.addPosts(friendPosts);
})

This is even more annoying. Now we need to manually update the success operation, and the failure operation.

Why is that? On the backend, a database is able to do optimistic updates ¹ — why can’t we do that in in the browser?

DELETE friendship WHERE friend_one_id = ? AND friend_two_id = ?
-- local store optimistically updated, if operation fails we undo

D. Reactivity

And data doesn’t just change from our own actions. Sometimes we need to connect to changes that other users make. For example, someone could unfriend us, or someone could send us a message.

To make this work, we need to do the same work that we did in our API endpoints, but this time on our websocket connection:

ws.listen(`${user.id}/friends-removed`, friend => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
}

But, this introduces two problems. First, we need to play garbage collector again, and remember every place that could be affected by an event.

1. Optimistic Update: `Blue`
2. Stale reactive update: `Red`
3. Successful Update, comes in through socket: `Blue`

Solving stuff like this has you dealing with consistency issues, scouring literature on…databases.

It doesn’t have to be that way though. What if each query was reactive?

SELECT friends FROM users JOIN friendships on friendship.user_one_id = ?

Server

It only gets harder on the server.

E. Endpoints

Much of backend development ends up being a sort of glue between the database and and the frontend.

// db.js
function getRelevantPostsFor(userId) { 
    db.exec("SELECT * FROM users WHERE ...")
}

// api.js
app.get("relevantPosts", (req, res) => { 
  res.status(200).send(getRelevantPosts(req.userId));
})

F. Permissions

Well, the reason we don’t, is because we need to make sure permissions are correctly set. You should only see posts by your friends, for example. To do this, we add middleware to our API endpoints:

app.put("user", auth, (req, res) => { 
  ...
}

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfSameUser(),
  ]
}

G. Audits, Undo / Redo

And at some point, we get requirements that blow up complexity for us.

For example, say we need to support "undo / redo", for friendship actions. A user deletes a friend, and then they press "undo" — how could we support this?

To solve this, we’d evolve our data model. Instead of a single friendship relation, we’d have "friendship facts"

[
  {status: "friends", friend_one_id: 1, friend_two_id: 2, at: 1000}, 
  {status: "disconnected", friend_one_id: 1, friend_two_id: 2, at: 10001},
]

Then the "latest fact" would represent whether there is a friendship or not.

All of a sudden, we become "sort of database engineers", devouring literature on query optimization.

H. Offline Mode

There’s more examples of difficulty. What about offline mode? Many apps are long-running and can go for periods without internet connection. How can we support this?

Imagine…offline mode off the bat. What would the most applications feel like after this?

I. Reactivity

function addPost(post) {
  db.addPost(post);
  getAllFriends(post).forEach(notifyNewPost);
}

J. Derived Data

Why is this so complicated though? In a normal database you can do something like:

CREATE INDEX ...

Why can’t we do that, for other services? Martin Kleppman, in his Data Intensive Applications, suggests a language like this:

db |> ElasticSearch
db |> Analytics
db.user |> Redis
// Bam, we've connected elastic search, analytics, and redis to our db

Monkey Wrenches

Wow, we’ve gone up to J. But these are only issues you start to face once you start building your application. What about before?

K. TTP — Time to Prototype

Perhaps the most restrictive problem for developers today is how hard it is to get started. If you want to store user information and display a page, what do you do?

Before, it was a matter of index.html and FTP. Now, it’s webpack, typescript, build processes galore, often multiple services. There are so many moving pieces that it’s hard to take a step.

Making this step easier would dramatically increase the number of applications we get to use. What if it was easier than index.html and FTP?

Current Solutions

1) Firebase

I think Firebase has done some of the most innovative work in moving web application development forward. The most important thing they got right, was a database on the browser.

They’re strength also stems for K: I think it still has the best time-to-prototype in the market. You can just start with index.html!

However, it has two problems:

userA: 
  friends: 
    userBId: true 
userB:
  friends:
    userAId: true

You de-normalize friendships across two different paths (userA/friends/userBId) and (userB/friends/userAId). Grabbing the full data requires you to manually replicate a join:

1. get `userA/friends`
2. for each id, get `/${id}`

These kind of relationships sprout up very quickly in your application. It would be great if a solution helped you handle it.

We experimented a lot on this at Facebook, and came to the conclusion that you need a real language to express permissions. If Firebase had that, it would be much more powerful.

With the remaining items (audits, Undo / Redo, Offline Mode for writes, Derived Data) — Firebase hasn’t tackled them yet.

2) Supabase

Supabase is trying to do what Firebase did for Mongo, but for Postgres. If they did this, it would be quite an attractive option, as it would solve Firebase’s biggest problem: query strength.

Supabase has some great wins so far. Their auth abstraction is great, which makes it one of the few platforms that are as easy to get started with as firebase was.

Their realtime option allows you to subscribe to row-level updates. For example, if we wanted to to know whenever a friendship gets created, updated, or changed, we could write this:

const friendsChange = supabase
  .from('friendships:friend_one_id=eq.200')
  .on('*', handleFriendshipChange)
  .subscribe()

This in practice can get you far. It can get hairy though. For example, if a friend is created, we may not have the user information and we’d have to fetch it.

function handleFriendshipChange(friendship) { 
  if (!userStore.get(friendship.friend_two_id)) { 
      fetchUser(...)
  }
}

3) GraphQL + Hasura

GraphQL is an excellent way to declaratively define data you want from the client. services like Hasura can take a database like Postgres, and do smart things like give you a GraphQL API out of it.

Lay of the Land

Future

Now the question: what will the evolution of these tools look like?

In some ways, the future is happening now. I think Figma, for example, is an app from the future: it handles handle offline-mode, undo / redo and multiplayer beautifully.

If we wanted to make an app like that, what would an ideal abstraction for data look like?

Requirements

1) A database on the client, with a powerful query language

From the browser, this abstraction would have to be like firebase, but with a strong query language.

user = useQuery("SELECT * FROM users WHERE id = ?", 10);

2) A real permission language

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
  ]
}

3) Offline Mode & Undo / Redo

Whatever abstraction we choose, it should give us the ability to run writes while we’re offline.

4) The Next Cloud

Finally, we should be able to express data dependencies without having to spin anything up. With a simple

db.user |> Redis

all queries to users would magically be cached by Redis.

Sketch of an Implementation

Okay, those requirements sound magical. What would an implementation look like today?

Datomic & Datascript

Reactivity

Permission Language

Our server could accept code fragments, which it runs when fetching data. These fragments would be responsible for permissions, giving us a powerful permission language!

Pipe

Finally, we can write up some DSL, which lets you pipe data to Elastic Search, Redis, etc, all according to the user’s preferences.

With that, we have a compelling offering.

Considerations

So, why doesn’t this exist yet? Well...

Datalog is unfamiliar

[:find [(pull ?c [:conversation/user :conversation/message]) ...]
 :where [?e :session/thread ?thread-id] 
        [?c :conversation/thread ?thread-id]]

This query would find all messages, alongside with the user information, for the active thread in this current "session". Not bad!

Once you get to know it, it’s an unbelievably elegant language. However, I don’t think that’s enough. Time-to-prototype needs to be blazing fast, and having to learn this may be too much.

The other problem, is that data modeling is also different from what people are used too. Firebase is the gold-standard, where you can write your first mutation without specifying any schema.

Datalog would be hard to make reactive

A big problem with both SQL and Datalog, is that based on some new change, it’s hard to figure out which queries need to be updated.

This is a hard problem, but I think it’s a tractable one.

A permission language would slow things down

One problem with making permission checks a full-blown language, is that we’re liable to overfetch data.

Facebook was able to do it. It will be hard, but it’s possible.

It may be too large of an abstraction

It will only be used for toys

The Market is very competitive

Fin

Well, we covered the pains, covered the competitors, covered an ideal solution, and went through the considerations. Thank you for walking with me on this journey!

Like-Minded Folks

It may require some iteration to figure out the interface, but the there’s an interesting road ahead.

Next Up

Thanks Joe Averbukh, Sean Grove, Ian Sinnott, Daniel Woelfel, Dennis Heihoff, Mark Shlick, Alex Reichert, Alex Kotliarskyi, Thomas Schranz, for reviewing drafts of this essay

You may not notice this as Postgres gives a consistency guarantee. However, for them to support multiple concurrent transactions, they in effect need to be able to keep "temporary alterations" ↩
Figma mentions this problem in their mutiplayer essay ↩
Plain SQL and boolean logic is hard to reuse, and can slow down the query planner. Many folks who have medium-sized apps experience this quickly. ↩
Take a look at Hasura’s notes ↩

A Database in the Browser

Stopa — Fri, 28 May 2021 17:51:39 +0000

If you look at the the ecosystem of web applications and measure by difficulty, what apps come to the top of the list?

If you asked me, I think Google Docs and Figma would be staple contenders. They're so seamless that it barely enters our mind they function offline, they're multiplayer, they handle conflicts, and they even support intricate undo / redo.

What's at the edge of difficulty today tends to become the new normal tomorrow. This means that the average application in the future, I think, will look more like Google Docs or Figma.

For that to be possible though, difficulty will need to go down. There will have to be new abstractions which will make writing these kind of applications as easy as writing a CRUD app today.

What will these abstractions look like?

Dear reader, this question has led to the journey, which ended up producing this essay. One way to find these abstractions is to look at all the schleps we have go through today, and see what we can do about them. Come with me on a journey of building a web application: we'll go over the problems we face, assess solutions in the forms of Firebase, Supabase, Hasura and friends, and see what's left to do.

I think by the end, you'll agree with me that the abstraction that would solve the largest schleps looks like a powerful database on the browser. Without further ado, let's see what building a web application likes today!

Client

The journey begins in the browser.

A. Data Plumbing

The first job we have is to fetch information and display it in different places. For example, we may display a friends list, a friends count, a modal with a specific group of friends, etc

// normalise [posts] -> {[id]: post}
fetchRelevantPostsFor(user).then(posts => {
  posts.forEach(post => {
    store.addPost(post);
  })
})

// see all posts by author: 
store.posts.values().reduce((res, post) => { 
  res[post.authorId] = res[post.authorId] || []; 
  res[post.authorId].push(post);
  return res;
}, {})

SELECT posts WHERE post.author_id = ?;

on the information that we have inside the browser?

B. Change

The next problem is keeping data up to date. Say we remove a friend — what should happen?

We send an API request, wait for it to complete, and write some logic to "remove" all the information we have about that friend. Something like this:

deleteFriend(user, friend.id).then(res => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
})

One way folks avoid it, is to skip the problem and just re-fetch the whole world:

deleteFriend(user, id).then(res => {
  fetchFriends(user);
  fetchPostsRelevantToTheUser(post);
})

The rub is, whenever we make a change to the database, it does it’s job without us having to be so prescriptive. Why can’t this just happen automatically for us in the browser?

DELETE FROM friendships WHERE friend_one_id = ? AND friend_two_id = ?
-- Browser magically updates with all the friend and post information removed

C. Optimistic Updates

The problem you may have noticed with B., was that we had to wait for friendship removal to update our browser state.

In most cases, we can make the experience snappier with an optimistic update — after all, we know that the call will likely be a success. To do this, we do something like:

friendPosts = userStore.getFriendPosts(friend);
userStore.remove(friend.id);
postStore.removeUserPosts(friend.id);
deleteFriend(user, id).catch(e => { 
  // undo
  userStore.addFriend(friend);
  postStore.addPosts(friendPosts);
})

This is even more annoying. Now we need to manually update the success operation, and the failure operation.

Why is that? On the backend, a database is able to do optimistic updates ¹ — why can’t we do that in in the browser?

DELETE friendship WHERE friend_one_id = ? AND friend_two_id = ?
-- local store optimistically updated, if operation fails we undo

D. Reactivity

And data doesn’t just change from our own actions. Sometimes we need to connect to changes that other users make. For example, someone could unfriend us, or someone could send us a message.

To make this work, we need to do the same work that we did in our API endpoints, but this time on our websocket connection:

ws.listen(`${user.id}/friends-removed`, friend => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
}

But, this introduces two problems. First, we need to play garbage collector again, and remember every place that could be affected by an event.

1. Optimistic Update: `Blue`
2. Stale reactive update: `Red`
3. Successful Update, comes in through socket: `Blue`

Solving stuff like this has you dealing with consistency issues, scouring literature on…databases.

It doesn’t have to be that way though. What if each query was reactive?

SELECT friends FROM users JOIN friendships on friendship.user_one_id = ?

Server

It only gets harder on the server.

E. Endpoints

Much of backend development ends up being a sort of glue between the database and and the frontend.

// db.js
function getRelevantPostsFor(userId) { 
    db.exec("SELECT * FROM users WHERE ...")
}

// api.js
app.get("relevantPosts", (req, res) => { 
  res.status(200).send(getRelevantPosts(req.userId));
})

F. Permissions

Well, the reason we don’t, is because we need to make sure permissions are correctly set. You should only see posts by your friends, for example. To do this, we add middleware to our API endpoints:

app.put("user", auth, (req, res) => { 
  ...
}

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfSameUser(),
  ]
}

G. Audits, Undo / Redo

And at some point, we get requirements that blow up complexity for us.

For example, say we need to support "undo / redo", for friendship actions. A user deletes a friend, and then they press "undo" — how could we support this?

To solve this, we’d evolve our data model. Instead of a single friendship relation, we’d have "friendship facts"

[
  {status: "friends", friend_one_id: 1, friend_two_id: 2, at: 1000}, 
  {status: "disconnected", friend_one_id: 1, friend_two_id: 2, at: 10001},
]

Then the "latest fact" would represent whether there is a friendship or not.

All of a sudden, we become "sort of database engineers", devouring literature on query optimization.

H. Offline Mode

There’s more examples of difficulty. What about offline mode? Many apps are long-running and can go for periods without internet connection. How can we support this?

Imagine…offline mode off the bat. What would the most applications feel like after this?

I. Reactivity

function addPost(post) {
  db.addPost(post);
  getAllFriends(post).forEach(notifyNewPost);
}

J. Derived Data

Why is this so complicated though? In a normal database you can do something like:

CREATE INDEX ...

Why can’t we do that, for other services? Martin Kleppman, in his Data Intensive Applications, suggests a language like this:

db |> ElasticSearch
db |> Analytics
db.user |> Redis
// Bam, we've connected elastic search, analytics, and redis to our db

Monkey Wrenches

Wow, we’ve gone up to J. But these are only issues you start to face once you start building your application. What about before?

K. TTP — Time to Prototype

Perhaps the most restrictive problem for developers today is how hard it is to get started. If you want to store user information and display a page, what do you do?

Before, it was a matter of index.html and FTP. Now, it’s webpack, typescript, build processes galore, often multiple services. There are so many moving pieces that it’s hard to take a step.

Making this step easier would dramatically increase the number of applications we get to use. What if it was easier than index.html and FTP?

Current Solutions

1) Firebase

I think Firebase has done some of the most innovative work in moving web application development forward. The most important thing they got right, was a database on the browser.

They’re strength also stems for K: I think it still has the best time-to-prototype in the market. You can just start with index.html!

However, it has two problems:

userA: 
  friends: 
    userBId: true 
userB:
  friends:
    userAId: true

You de-normalize friendships across two different paths (userA/friends/userBId) and (userB/friends/userAId). Grabbing the full data requires you to manually replicate a join:

1. get `userA/friends`
2. for each id, get `/${id}`

These kind of relationships sprout up very quickly in your application. It would be great if a solution helped you handle it.

We experimented a lot on this at Facebook, and came to the conclusion that you need a real language to express permissions. If Firebase had that, it would be much more powerful.

With the remaining items (audits, Undo / Redo, Offline Mode for writes, Derived Data) — Firebase hasn’t tackled them yet.

2) Supabase

Supabase is trying to do what Firebase did for Mongo, but for Postgres. If they did this, it would be quite an attractive option, as it would solve Firebase’s biggest problem: query strength.

Supabase has some great wins so far. Their auth abstraction is great, which makes it one of the few platforms that are as easy to get started with as firebase was.

Their realtime option allows you to subscribe to row-level updates. For example, if we wanted to to know whenever a friendship gets created, updated, or changed, we could write this:

const friendsChange = supabase
  .from('friendships:friend_one_id=eq.200')
  .on('*', handleFriendshipChange)
  .subscribe()

This in practice can get you far. It can get hairy though. For example, if a friend is created, we may not have the user information and we’d have to fetch it.

function handleFriendshipChange(friendship) { 
  if (!userStore.get(friendship.friend_two_id)) { 
      fetchUser(...)
  }
}

3) GraphQL + Hasura

GraphQL is an excellent way to declaratively define data you want from the client. services like Hasura can take a database like Postgres, and do smart things like give you a GraphQL API out of it.

Lay of the Land

Future

Now the question: what will the evolution of these tools look like?

In some ways, the future is happening now. I think Figma, for example, is an app from the future: it handles handle offline-mode, undo / redo and multiplayer beautifully.

If we wanted to make an app like that, what would an ideal abstraction for data look like?

Requirements

1) A database on the client, with a powerful query language

From the browser, this abstraction would have to be like firebase, but with a strong query language.

user = useQuery("SELECT * FROM users WHERE id = ?", 10);

2) A real permission language

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
  ]
}

3) Offline Mode & Undo / Redo

Whatever abstraction we choose, it should give us the ability to run writes while we’re offline.

4) The Next Cloud

Finally, we should be able to express data dependencies without having to spin anything up. With a simple

db.user |> Redis

all queries to users would magically be cached by Redis.

Sketch of an Implementation

Okay, those requirements sound magical. What would an implementation look like today?

Datomic & Datascript

Reactivity

Permission Language

Our server could accept code fragments, which it runs when fetching data. These fragments would be responsible for permissions, giving us a powerful permission language!

Pipe

Finally, we can write up some DSL, which lets you pipe data to Elastic Search, Redis, etc, all according to the user’s preferences.

With that, we have a compelling offering.

Considerations

So, why doesn’t this exist yet? Well...

Datalog is unfamiliar

[:find [(pull ?c [:conversation/user :conversation/message]) ...]
 :where [?e :session/thread ?thread-id] 
        [?c :conversation/thread ?thread-id]]

This query would find all messages, alongside with the user information, for the active thread in this current "session". Not bad!

Once you get to know it, it’s an unbelievably elegant language. However, I don’t think that’s enough. Time-to-prototype needs to be blazing fast, and having to learn this may be too much.

The other problem, is that data modeling is also different from what people are used too. Firebase is the gold-standard, where you can write your first mutation without specifying any schema.

Datalog would be hard to make reactive

A big problem with both SQL and Datalog, is that based on some new change, it’s hard to figure out which queries need to be updated.

This is a hard problem, but I think it’s a tractable one.

A permission language would slow things down

One problem with making permission checks a full-blown language, is that we’re liable to overfetch data.

Facebook was able to do it. It will be hard, but it’s possible.

It may be too large of an abstraction

It will only be used for toys

The Market is very competitive

Fin

Well, we covered the pains, covered the competitors, covered an ideal solution, and went through the considerations. Thank you for walking with me on this journey!

Like-Minded Folks

It may require some iteration to figure out the interface, but the there’s an interesting road ahead.

Next Up

Thanks Joe Averbukh, Sean Grove, Ian Sinnott, Daniel Woelfel, Dennis Heihoff, Mark Shlick, Alex Reichert, Alex Kotliarskyi, Thomas Schranz, for reviewing drafts of this essay

You may not notice this as Postgres gives a consistency guarantee. However, for them to support multiple concurrent transactions, they in effect need to be able to keep "temporary alterations" ↩
Figma mentions this problem in their mutiplayer essay ↩
Plain SQL and boolean logic is hard to reuse, and can slow down the query planner. Many folks who have medium-sized apps experience this quickly. ↩
Take a look at Hasura’s notes ↩

A Database on The Client

Stopa — Thu, 27 May 2021 14:52:15 +0000

How do we make it easy to write applications like Google Docs or Figma? This question led me on a journey, and this essay was the result.

If you look at the the ecosystem of web applications today and measure by difficulty, I think Google Docs and Figma would be among the top of the list. They work so seamlessly that it barely comes to our mind that they function offline, they are multiplayer, they handle conflicts, and they even support intricate undo / redo.

In technology, what's at the edge of difficulty today becomes the new normal tomorrow. Users want higher fidelity and engineers will discover new abstractions to support it. These abstractions will need to make writing Google Docs tomorrow as easy as writing the average application today.

That begs the question: what would these abstractions look like? One way to find out is to attune ourselves to the schleps we go through. Let's go through the process for building a web application, and catalog al pains along the way.

Client

The journey begins on the browser.

A. Data Plumbing

The first job we have is to fetch information and display it in different places. For example, we may display a friends list, a friends count, a modal with a specific group of friends, etc

// normalise [posts] -> {[id]: post}
fetchRelevantPostsFor(user).then(posts => {
  posts.forEach(post => {
    store.addPost(post);
  })
})

// see all posts by author: 
store.posts.values().reduce((res, post) => { 
  res[post.authorId] = res[post.authorId] || []; 
  res[post.authorId].push(post);
  return res;
}, {})

SELECT posts WHERE post.author_id = ?;

on the information that we have inside the browser?

B. Change

The next problem is keeping data up to date. Say we remove a friend — what should happen?

We send an API request, wait for it to complete, and write some logic to "remove" all the information we have about that friend. Something like this:

deleteFriend(user, friend.id).then(res => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
})

One way folks avoid it, is to skip the problem and just re-fetch the whole world:

deleteFriend(user, id).then(res => {
  fetchFriends(user);
  fetchPostsRelevantToTheUser(post);
})

The rub is, whenever we make a change to the database, it does it’s job without us having to be so prescriptive. Why can’t this just happen automatically for us in the browser?

DELETE FROM friendships WHERE friend_one_id = ? AND friend_two_id = ?
-- Browser magically updates with all the friend and post information removed

C. Optimistic Updates

The problem you may have noticed with B., was that we had to wait for friendship removal to update our browser state.

In most cases, we can make the experience snappier with an optimistic update — after all, we know that the call will likely be a success. To do this, we do something like:

friendPosts = userStore.getFriendPosts(friend);
userStore.remove(friend.id);
postStore.removeUserPosts(friend.id);
deleteFriend(user, id).catch(e => { 
  // undo
  userStore.addFriend(friend);
  postStore.addPosts(friendPosts);
})

This is even more annoying. Now we need to manually update the success operation, and the failure operation.

Why is that? On the backend, a database is able to do optimistic updates ¹ — why can’t we do that in in the browser?

DELETE friendship WHERE friend_one_id = ? AND friend_two_id = ?
-- local store optimistically updated, if operation fails we undo

D. Reactivity

And data doesn’t just change from our own actions. Sometimes we need to connect to changes that other users make. For example, someone could unfriend us, or someone could send us a message.

To make this work, we need to do the same work that we did in our API endpoints, but this time on our websocket connection:

ws.listen(`${user.id}/friends-removed`, friend => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
}

But, this introduces two problems. First, we need to play garbage collector again, and remember every place that could be affected by an event.

1. Optimistic Update: `Blue`
2. Stale reactive update: `Red`
3. Successful Update, comes in through socket: `Blue`

Solving stuff like this has you dealing with consistency issues, scouring literature on…databases.

It doesn’t have to be that way though. What if each query was reactive?

SELECT friends FROM users JOIN friendships on friendship.user_one_id = ?

Server

It only gets harder on the server.

E. Endpoints

Much of backend development ends up being a sort of glue between the database and and the frontend.

// db.js
function getRelevantPostsFor(userId) { 
    db.exec("SELECT * FROM users WHERE ...")
}

// api.js
app.get("relevantPosts", (req, res) => { 
  res.status(200).send(getRelevantPosts(req.userId));
})

F. Permissions

Well, the reason we don’t, is because we need to make sure permissions are correctly set. You should only see posts by your friends, for example. To do this, we add middleware to our API endpoints:

app.put("user", auth, (req, res) => { 
  ...
}

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfSameUser(),
  ]
}

G. Audits, Undo / Redo

And at some point, we get requirements that blow up complexity for us.

For example, say we need to support "undo / redo", for friendship actions. A user deletes a friend, and then they press "undo" — how could we support this?

To solve this, we’d evolve our data model. Instead of a single friendship relation, we’d have "friendship facts"

[
  {status: "friends", friend_one_id: 1, friend_two_id: 2, at: 1000}, 
  {status: "disconnected", friend_one_id: 1, friend_two_id: 2, at: 10001},
]

Then the "latest fact" would represent whether there is a friendship or not.

All of a sudden, we become "sort of database engineers", devouring literature on query optimization.

H. Offline Mode

There’s more examples of difficulty. What about offline mode? Many apps are long-running and can go for periods without internet connection. How can we support this?

Imagine…offline mode off the bat. What would the most applications feel like after this?

I. Reactivity

function addPost(post) {
  db.addPost(post);
  getAllFriends(post).forEach(notifyNewPost);
}

J. Derived Data

Why is this so complicated though? In a normal database you can do something like:

CREATE INDEX ...

Why can’t we do that, for other services? Martin Kleppman, in his Data Intensive Applications, suggests a language like this:

db |> ElasticSearch
db |> Analytics
db.user |> Redis
// Bam, we've connected elastic search, analytics, and redis to our db

Monkey Wrenches

Wow, we’ve gone up to J. But these are only issues you start to face once you start building your application. What about before?

K. TTP — Time to Prototype

Perhaps the most restrictive problem for developers today is how hard it is to get started. If you want to store user information and display a page, what do you do?

Before, it was a matter of index.html and FTP. Now, it’s webpack, typescript, build processes galore, often multiple services. There are so many moving pieces that it’s hard to take a step.

Making this step easier would dramatically increase the number of applications we get to use. What if it was easier than index.html and FTP?

Current Solutions

1) Firebase

I think Firebase has done some of the most innovative work in moving web application development forward. The most important thing they got right, was a database on the browser.

They’re strength also stems for K: I think it still has the best time-to-prototype in the market. You can just start with index.html!

However, it has two problems:

userA: 
  friends: 
    userBId: true 
userB:
  friends:
    userAId: true

You de-normalize friendships across two different paths (userA/friends/userBId) and (userB/friends/userAId). Grabbing the full data requires you to manually replicate a join:

1. get `userA/friends`
2. for each id, get `/${id}`

These kind of relationships sprout up very quickly in your application. It would be great if a solution helped you handle it.

We experimented a lot on this at Facebook, and came to the conclusion that you need a real language to express permissions. If Firebase had that, it would be much more powerful.

With the remaining items (audits, Undo / Redo, Offline Mode for writes, Derived Data) — Firebase hasn’t tackled them yet.

2) Supabase

Supabase is trying to do what Firebase did for Mongo, but for Postgres. If they did this, it would be quite an attractive option, as it would solve Firebase’s biggest problem: query strength.

Supabase has some great wins so far. Their auth abstraction is great, which makes it one of the few platforms that are as easy to get started with as firebase was.

Their realtime option allows you to subscribe to row-level updates. For example, if we wanted to to know whenever a friendship gets created, updated, or changed, we could write this:

const friendsChange = supabase
  .from('friendships:friend_one_id=eq.200')
  .on('*', handleFriendshipChange)
  .subscribe()

This in practice can get you far. It can get hairy though. For example, if a friend is created, we may not have the user information and we’d have to fetch it.

function handleFriendshipChange(friendship) { 
  if (!userStore.get(friendship.friend_two_id)) { 
      fetchUser(...)
  }
}

3) GraphQL + Hasura

GraphQL is an excellent way to declaratively define data you want from the client. services like Hasura can take a database like Postgres, and do smart things like give you a GraphQL API out of it.

Lay of the Land

Future

Now the question: what will the evolution of these tools look like?

In some ways, the future is happening now. I think Figma, for example, is an app from the future: it handles handle offline-mode, undo / redo and multiplayer beautifully.

If we wanted to make an app like that, what would an ideal abstraction for data look like?

Requirements

1) A database on the client, with a powerful query language

From the browser, this abstraction would have to be like firebase, but with a strong query language.

user = useQuery("SELECT * FROM users WHERE id = ?", 10);

2) A real permission language

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
  ]
}

3) Offline Mode & Undo / Redo

Whatever abstraction we choose, it should give us the ability to run writes while we’re offline.

4) The Next Cloud

Finally, we should be able to express data dependencies without having to spin anything up. With a simple

db.user |> Redis

all queries to users would magically be cached by Redis.

Sketch of an Implementation

Okay, those requirements sound magical. What would an implementation look like today?

Datomic & Datascript

Reactivity

Permission Language

Our server could accept code fragments, which it runs when fetching data. These fragments would be responsible for permissions, giving us a powerful permission language!

Pipe

Finally, we can write up some DSL, which lets you pipe data to Elastic Search, Redis, etc, all according to the user’s preferences.

With that, we have a compelling offering.

Considerations

So, why doesn’t this exist yet? Well...

Datalog is unfamiliar

[:find [(pull ?c [:conversation/user :conversation/message]) ...]
            :where [?e :session/thread ?thread-id] 
                   [?c :conversation/thread ?thread-id]]

This query would find all messages, alongside with the user information, for the active thread in this current "session". Not bad!

Once you get to know it, it’s an unbelievably elegant language. However, I don’t think that’s enough. Time-to-prototype needs to be blazing fast, and having to learn this may be too much.

The other problem, is that data modeling is also different from what people are used too. Firebase is the gold-standard, where you can write your first mutation without specifying any schema.

Datalog would be hard to make reactive

A big problem with both SQL and Datalog, is that based on some new change, it’s hard to figure out which queries need to be updated.

This is a hard problem, but I think it’s a tractable one.

A permission language would slow things down

One problem with making permission checks a full-blown language, is that we’re liable to overfetch data.

Facebook was able to do it. It will be hard, but it’s possible.

It may be too large of an abstraction

It will only be used for toys

The Market is very competitive

Fin

Well, we covered the pains, covered the competitors, covered an ideal solution, and went through the considerations. Thank you for walking with me on this journey!

Like-Minded Folks

It may require some iteration to figure out the interface, but the there’s an interesting road ahead.

Next Up

Thanks Joe Averbukh, Sean Grove, Ian Sinnott, Daniel Woelfel, Dennis Heihoff, Mark Shlick, Alex Reichert, Alex Kotliarskyi, Thomas Schranz, for reviewing drafts of this essay

You may not notice this as Postgres gives a consistency guarantee. However, for them to support multiple concurrent transactions, they in effect need to be able to keep "temporary alterations" ↩
Figma mentions this problem in their mutiplayer essay ↩
Plain SQL and boolean logic is hard to reuse, and can slow down the query planner. Many folks who have medium-sized apps experience this quickly. ↩
Take a look at Hasura’s notes ↩

Web Applications from the Future

Stopa — Thu, 13 May 2021 16:43:21 +0000

A new medium appears, and people are so excited about it that they explore most of its possibilities in the first couple generations. Hacking seems to be in this phase now.

— Paul Graham

PG once wrote that hacking today was like painting during the pre-renaissance period. It started out awkward and two-dimensional, but in just a few generations we got the Sistene Chapel.

I was thrilled when I first read that. With how technology has taken over the world, one would think we’re at the tail end of this journey. But, when I reflect on how we hack today, all signs point to nascency.

Programming is still awkward: common solutions are frequently dogma ¹ and most of our attention is spent solving problems unrelated to product. In fact, so much of our attention is spent on what shouldn’t matter, it begs the question: just what kind of productivity will we unleash in the future?

One way to find out, is to attune ourselves to what shouldn’t matter today. Let’s start with web applications. Come with me on a journey of building one, and let’s catalog the pains along the way.

Client

The journey begins on the browser.

A. Data Plumbing

The first job we have is to fetch information and display it in different places. For example, we may display a friends list, a friends count, a modal with a specific group of friends, etc

// normalise [posts] -> {[id]: post}
fetchRelevantPostsFor(user).then(posts => {
  posts.forEach(post => {
    store.addPost(post);
  })
})

// see all posts by author: 
store.posts.values().reduce((res, post) => { 
  res[post.authorId] = res[post.authorId] || []; 
  res[post.authorId].push(post);
  return res;
}, {})

SELECT posts WHERE post.author_id = ?;

on the information that we have inside the browser?

B. Change

The next problem is keeping data up to date. Say we remove a friend — what should happen?

We send an API request, wait for it to complete, and write some logic to "remove" all the information we have about that friend. Something like this:

deleteFriend(user, friend.id).then(res => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
})

One way folks avoid it, is to skip the problem and just re-fetch the whole world:

deleteFriend(user, id).then(res => {
  fetchFriends(user);
  fetchPostsRelevantToTheUser(post);
}

The rub is, whenever we make a change to the database, it does it’s job without us having to be so prescriptive. Why can’t this just happen automatically for us in the browser?

DELETE FROM friendships WHERE friend_one_id = ? AND friend_two_id = ?
-- Browser magically updates with all the friend and post information removed

C. Optimistic Updates

The problem you may have noticed with B., was that we had to wait for friendship removal to update our browser state.

In most cases, we can make the experience snappier with an optimistic update — after all, we know that the call will likely be a success. To do this, we do something like:

friendPosts = userStore.getFriendPosts(friend);
userStore.remove(friend.id);
postStore.removeUserPosts(friend.id);
deleteFriend(user, id).catch(e => { 
  // undo
  userStore.addFriend(friend);
  postStore.addPosts(friendPosts);
})

This is even more annoying. Now we need to manually update the success operation, and the failure operation.

Why is that? On the backend, a database is able to do optimistic updates ² — why can’t we do that in in the browser?

DELETE friendship WHERE friend_one_id = ? AND friend_two_id = ?
-- local store optimistically updated, if operation fails we undo

D. Reactivity

And data doesn’t just change from our own actions. Sometimes we need to connect to changes that other users make. For example, someone could unfriend us, or someone could send us a message.

To make this work, we need to do the same work that we did in our API endpoints, but this time on our websocket connection:

ws.listen(`${user.id}/friends-removed`, friend => { 
  userStore.remove(friend.id);
  postStore.removeUserPosts(friend.id);
}

But, this introduces two problems. First, we need to play garbage collector again, and remember every place that could be affected by an event.

1. Optimistic Update: `Blue`
2. Stale reactive update: `Red`
3. Successful Update, comes in through socket: `Blue`

Solving stuff like this has you dealing with consistency issues, scouring literature on…databases.

It doesn’t have to be that way though. What if each query was reactive?

SELECT friends FROM users JOIN friendships on friendship.user_one_id = ?

Server

It only gets harder on the server.

E. Endpoints

Much of backend development ends up being a sort of glue between the database and and the frontend.

// db.js
function getRelevantPostsFor(userId) { 
    db.exec("SELECT * FROM users WHERE ...")
}

// api.js
app.get("relevantPosts", (req, res) => { 
  res.status(200).send(getRelevantPosts(req.userId));
})

F. Permissions

Well, the reason we don’t, is because we need to make sure permissions are correctly set. You should only see posts by your friends, for example. To do this, we add middleware to our API endpoints:

app.put("user", auth, (req, res) => { 
  ...
}

The question to ask here, is why is authentication at the API level? Ideally, we should have something very close to the database, making sure any data access passes permission checks. There’s row-level security on databases like Postgres, but that can get hairy quick ⁴. What if you could "describe" entities near the database?

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfSameUser(),
  ]
}

G. Audits, Undo / Redo

And at some point, we get requirements that blow up complexity for us.

For example, say we need to support "undo / redo", for friendship actions. A user deletes a friend, and then they press "undo" — how would could support this?

To solve this, we’d evolve our data model. Instead of a single friendship relation, we’d have "friendship facts"

[
  {status: "friends", friend_one_id: 1, friend_two_id: 2, at: 1000}, 
  {status: "disconnected", friend_one_id: 1, friend_two_id: 2, at: 10001},
]

Then the "latest fact" would represent whether there is a friendship or not.

All of a sudden, we become "sort of database engineers", devouring literature on query optimization.

And god forbid an error happens and accidentally delete data. In a world of facts there would be no such thing — you can just undo the deletions. But alas, this is not the world most of us live in.

H. Offline Mode

There’s more examples of difficulty. What about offline mode? Many apps are long-running and can go for periods without internet connection. How can we support this?

Imagine…offline mode off the bat. What would the most applications feel like after this?

I. Reactivity

function addPost(post) {
  db.addPost(post);
  getAllFriends(post).forEach(notifyNewPost);
}

J. Derived Data

Why is this so complicated though? In a normal database you can do something like:

CREATE INDEX ...

Why can’t we do that, for other services? Martin Kleppman, in his Data Intensive Applications, suggests a language like this:

db |> ElasticSearch
db |> Analytics
db.user |> Redis
// Bam, we've connected elastic search, analytics, and redis to our db

Monkey Wrenches

Wow, we’ve gone up to J. But these are only issues you start to face once you start building your application. What about before?

K. TTP — Time to Prototype

Perhaps the most restrictive problem for developers today is how hard it is to get started. If you want to store user information and display a page, what do you do?

Before, it was a matter of index.html and FTP. Now, it’s webpack, typescript, build processes galore, often multiple services. There are so many moving pieces that it’s hard to take a step.

Making this step easier would dramatically increase the number of applications we get to use. What if it was easier than index.html and FTP?

Current Solutions

1) Firebase

I think Firebase has done some of the most innovative work in moving web application development forward. The most important thing they got right, was a database on the browser.

They’re strength also stems for K: I think it still has the best time-to-prototype in the market. You can just start with index.html!

However, it has two problems:

userA: 
  friends: 
    userBId: true 
userB:
  friends:
    userAId: true

You de-normalize friendships across two different paths (userA/friends/userBId) and (userB/friends/userAId). Grabbing the full data requires you to manually replicate a join:

1. get `userA/friends`
2. for each id, get `/${id}`

These kind of relationships sprout up very quickly in your application. It would be great if a solution helped you handle it.

We experimented a lot on this at Facebook, and came to the conclusion that you need a real language to express permissions. If Firebase had that, it would be much more powerful.

With the remaining items (audits, Undo / Redo, Offline Mode for writes, Derived Data) — Firebase hasn’t tackled them yet.

2) Supabase

Supabase is trying to do what Firebase did for Mongo, but for Postgres. If they did this, it would be quite an attractive option, as it would solve Firebase’s biggest problem: query strength.

Supabase has some great wins so far. Their auth abstraction is great, which makes it one of the few platforms that are as easy to get started with as firebase was.

Their realtime option allows you to subscribe to row-level updates. For example, if we wanted to to know whenever a friendship gets created, updated, or changed, we could write this:

const friendsChange = supabase
  .from('friendships:friend_one_id=eq.200')
  .on('*', handleFriendshipChange)
  .subscribe()

This in practice can get you far. It can get hairy though. For example, if a friend is created, we may not have the user information and we’d have to fetch it.

function handleFriendshipChange(friendship) { 
  if (!userStore.get(friendship.friend_two_id)) { 
      fetchUser(...)
  }
}

3) GraphQL + Hasura

GraphQL is an excellent way to declaratively define data you want from the client. services like Hasura can take a database like Postgres, and do smart things like give you a GraphQL API out of it.

Lay of the Land

Future

Now the question: what will the evolution of these tools look like?

In some ways, the future is happening now. I think Figma, for example, is an app from the future: it handles handle offline-mode, undo / redo and multiplayer beautifully.

If we wanted to make an app like that, what would an ideal abstraction for data look like?

Requirements

1) A database on the client, with a powerful query language

From the browser, this abstraction would have to be like firebase, but with a strong query language.

user = useQuery("SELECT * FROM users WHERE id = ?", 10);

2) A real permission language

User { 
  view: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
    IAllowIfSameUser(),
  ]
  write: [
    IAllowIfAdmin(),
    IAllowIfFriend(),
  ]
}

3) Offline Mode & Undo / Redo

Whatever abstraction we choose, it should give us the ability to run writes while we’re offline.

4) The Next Cloud

Finally, we should be able to express data dependencies without having to spin anything up. With a simple

db.user |> Redis

all queries to users would magically be cached by Redis.

Sketch of an Implementation

Okay, those requirements sound magical. What would an implementation look like today?

Datomic & Datascript

Reactivity

Permission Language

Our server could accept code fragments, which it runs when fetching data. These fragments would be responsible for permissions, giving us a powerful permission language!

Pipe

Finally, we can write up some DSL, which lets you pipe data to Elastic Search, Redis, etc, all according to the user’s preferences.

With that, we have a compelling offering.

Considerations

So, why doesn’t this exist yet? Well...

Datalog is unfamiliar

[:find [(pull ?c [:conversation/user :conversation/message]) ...]
            :where [?e :session/thread ?thread-id] 
                   [?c :conversation/thread ?thread-id]]

This query would find all messages, alongside with the user information, for the active thread in this current "session". Not bad!

Once you get to know it, it’s an unbelievably elegant language. However, I don’t think that’s enough. Time-to-prototype needs to be blazing fast, and having to learn this may be too much.

The other problem, is that data modeling is also different from what people are used too. Firebase is the gold-standard, where you can write your first mutation without specifying any schema.

Datalog would be hard to make reactive

A big problem with both SQL and Datalog, is that based on some new change, it’s hard to figure out which queries need to be updated.

I don’t think it’s impossible though. Hasura does polling and it scaled ⁵. We could try having a specific language for subscriptions as well, similar to Supabase. If we can prove certain queries can only change by some subset of facts, we can move them out of polling.

This is a hard problem, but I think it’s a tractable one.

A permission language would slow things down

One problem with making permission checks a full-blown language, is that we’re liable to overfetch data.

Facebook was able to do it. It will be hard, but it’s possible.

It may be too large of an abstraction

It will only be used for toys

The Market is very competitive

Fin

Well, we covered the pains, covered the competitors, covered an ideal solution, and went through the considerations. Thank you for walking with me on this journey!

Like-Minded Folks

It may require some iteration to figure out the interface, but the there’s an interesting road ahead.

Next Up

Thanks Joe Averbukh, Sean Grove, Ian Sinnott, Daniel Woelfel, Dennis Heihoff, Mark Shlick, Alex Reichert, Alex Kotliarskyi, Thomas Schranz, for reviewing drafts of this essay

Think OO, microservices. Here’s a my thoughts on one of them. ↩
You may not notice this as Postgres gives a consistency guarantee. However, for them to support multiple concurrent transactions, they in effect need to be able to keep "temporary alterations" ↩
Figma mentions this problem in their mutiplayer essay ↩
Plain SQL and boolean logic is hard to reuse, and can slow down the query planner. Many folks who have medium-sized apps experience this quickly. ↩
Take a look at Hasura’s notes ↩

Simulating RAM in Clojure

Stopa — Tue, 13 Oct 2020 22:33:07 +0000

“Computers are all made out of logic gates”. We’ve heard that saying before. We also have a sense that logic gates are very simple machines, analogous to light switches even. This raises the question: how exactly do kind-of-light-switches come together to form computers? How does “storing a variable” or “calling a function” translate into logic gates going on or off?

On a journey to answer that question, I discovered J Clark Scott’s excellent book “How do It Know?”. He starts with NAND gates and takes you on a journey to build a computer using them.

I liked his book so much that I took his schematic for RAM, and simulated it in Clojure. In this essay, I’ll guide you through doing just that: we’ll simulate NAND gates, and use about 14 thousand of them to build 256 bytes of RAM.

Going through this simulation ingrained an “aha” feeling in me: watching 14 thousand little machines chug away makes you feel that whoever uses a computer is a wizard. A wizard with an army of millions of machine servants doing billions of little jobs for them every second. I hope it gives you the same feeling. 🙂

Pre-requisites

To grok this essay, you need to understand this picture:

This describes a NAND gate. A NAND gate is a machine that has two input wires. If both input wires have a “high” charge (represented as 1), the output charge is “low” (represented as zero). With any other combination of input charges, the output charge is high.

Notice that the wires carry a charge, but we choose to interpret meaning in the charge. “high charge” means 1, and “low charge” means 0. Nothing changes in the machine, this is just something we decided as humans (1).

On the left you see a circuit diagram. You can read it as input wires a and b carrying charges into the NAND gate. The NAND gate has a wire c, carrying the output charge. For all the circuit diagrams we’ll draw, you can read them as electricity “flowing” from left to right, or top to bottom.

On the right is a “truth” table for a NAND gate. This is just a fancy name for summarizing every state a NAND gate can be, based on the input wires.

Now, we can start even lower than a NAND gate, but this machine is simple enough. It can’t be so hard to build something that turns off when two inputs are turned on. You don’t have to take my word for it though, you can search up “building a NAND gate with transistors”, and come back when you’re convinced.

Time to code! 🙂

0: State

First things first, we need some way to represent the state of our circuit. We know that our RAM will be built completely from NAND gates, so let’s take inspiration from one:

If we look at this example we can see that:

We have wires.
Wires have charges.
We hook wires together with NAND Gates

Here’s one way we can map that to a data structure in Clojure:

(def ex-state-v0 {:charge-map {:a 1 :b 1 :c 0}
                  :nand-gates [{:ins [:a :b]
                                :out :c}]})

We can use keywords to represent our wires. We can also keep a map that tells us the charges of our wires. Finally, we can keep a list of NAND gates, which tell us how these wires connect.

Fine enough way to represent our circuit for now! Let’s create a few functions that can help us manage this representation:

; update state v0
; ---------------

(def empty-state {:charge-map {} :nand-gates []})

(defn charge [state wire]
  (get-in state [:charge-map wire]))

(defn charges [state wires]
  (map (partial charge state) wires))

(defn set-charge [state wire charge]
  (assoc-in state [:charge-map wire] charge))

(defn wire-nand-gate [state a b o]
  (update state :nand-gates conj {:ins [a b] :out o}))

These are all the basic tools we need to “connect” a NAND gate into our circuit. Let’s try them out in the REPL:

(charges (-> empty-state
               (set-charge :a 1)
               (set-charge :b 0))
           [:a :b])
; => (1 0)
(wire-nand-gate empty-state :a :b :c)
; => {:charge-map {}, :nand-gates [{:ins [:a :b], :out :c}]}

Nice! We can now “wire” up a circuit. Let’s run some electricity through it.

1: Trigger

To figure out how to simulate electricity into our circuit, let’s remember our diagram again:

One way we can model this is to imagine that electricity is like water: It “flows” from sources into wires, and “triggers” all the devices that are connected to those wires.

With a model like that, here’s what would happen if a charge was “triggered” on a:

First, a‘s charge would update.
After that a ‘s charge would transfer to all the NAND gates that are connected to it. In this case, it would be our one NAND gate above.
Each NAND gate would then recompute its charge, and if it changed, trigger its output wire in turn. In our case that’s c
If c was connected to other NAND gates, those gates would trigger, and the process would continue.

Now, this is a very naive view of how electricity works (2), but it’s good enough for us to model RAM!

Let’s translate this into code.

To do that, we need a way to model what a NAND gate does:

(defn nand-output [a b]
  (if (= a b 1) 0 1))

(nand-output 0 0)
; => 1
(nand-output 1 1)
; => 0

Our nand-output function takes two input charges, and produces the output charge that a NAND gate would produce.

Next, we need a function to find all the NAND gates that are connected to a specific wire:

(defn dependent-nand-gates [state wire]
  (filter 
    (fn [{:keys [ins]}] (some #{wire} ins)) 
    (:nand-gates state)))

(dependent-nand-gates (wire-nand-gate empty-state :a :b :c) :a)
; => ({:ins [:a :b], :out :c})

This searches all of our NAND gates in our circuit, and finds the ones which are connected to a specific wire.

With that, we have what we need to implement trigger:

(declare trigger-nand-gate)
(defn trigger
  ([state wire new-v]
   (let [old-charge (charge state wire)
         state' (set-charge state wire new-v)
         new-charge (charge state' wire)]
     (if (= old-charge new-charge)
       state'
       (reduce (fn [acc-state out] (trigger-nand-gate acc-state out))
               state'
               (dependent-nand-gates state' wire))))))

This follows exactly the model we described:

Update the charge of the wire that was triggered
Find all the NAND gates that the wire was connected too
Trigger those NAND gates if needed.

What’s left is to implement what a NAND gate does when it is triggered:

(defn trigger-nand-gate
  [state {:keys [ins out]}]
  (let [new-charge (apply nand-output (charges state ins))]
    (trigger state out new-charge)))

This calculates the new charge of a NAND gate, and triggers the output wire with that charge.

Great, we have a way to simulate charges flowing through NAND gates!

One final helper function: let’s create something that will will let us “trigger” many wires:

(defn trigger-many [state wires charges]
  (reduce
    (fn [acc-state [wire charge]]
      (trigger acc-state wire charge))
    state
    (map vector wires charges)))

We’ll want to do this so much that it’s good to have around.

2: Simulate NAND

We have what we need to simulate a simple charge flowing through a NAND gate. Let’s write a test for that:

(deftest test-nand-gate
  (let [s1 (-> empty-state
               (wire-nand-gate :a :b :o)
               (trigger-many [:a :b] [1 0]))
        s2 (-> s1
               (trigger :b 1))]
    (testing "just a is on"
      (is (= '(1 0 1) (charges s1 [:a :b :o]))))
    (testing "both a and b are on"
      (is (= '(1 1 0) (charges s2 [:a :b :o]))))))

; Ran 1 test containing 2 assertions.
; No failures.

Works like a charm!

3: Simulate NOT

What would happen, if we took a NAND gate, and fed the same wire in both inputs?

Well, the output would end up being the opposite of its input. When a is zero, c is 1, when a is 1, c is 0. Boom, that happens to be a NOT gate. Here’s how that looks:

To implement our NOT gate, we can do exactly as our diagram described: Feed the same wire to both inputs of a NAND gate:

(defn wire-not-gate
  ([state a o]
   (wire-nand-gate state a a o)))

🤯 1 line of code. If we test that out…

(deftest test-not-gate
  (let [s1 (-> empty-state
               (wire-not-gate :a :o)
               (trigger :a 0))
        s2 (-> s1
               (trigger :a 1))]
    (testing "a is off"
      (is (= '(0 1) (charges s1 [:a :o]))))
    (testing "a is on"
      (is (= '(1 0) (charges s2 [:a :o]))))))

; Ran 1 test containing 2 assertions.
; No failures

It works! Onwards.

4: Simulate AND

What if we plugged the output of one NAND as the input of a NOT gate?

Well, it would be opposite of a NAND gate: d would only be 1 when both a and b are 1. That’s the AND gate:

To implement AND, we can follow just that schematic:

(defn wire-and-gate [state a b o]
  (let [nand-o :c]
    (-> state
        (wire-nand-gate a b nand-o)
        (wire-not-gate nand-o o))))

This would work…almost. The tricky thing here is that inside the function we have an “intermediary” wire c, which connects the NAND gate and NOT gate. If we made two AND gates for example, then they would share the same wire :c!

To fix this, let’s write some helper functions to create unique wires:

(def _u (atom {}))
(defn uniq-n [k]
  (swap! _u update k (fn [i] (inc (or i 0))))
  (get @_u k))

(defn kw [& args]
  (->> args
       (map (fn [x] (if ((some-fn keyword? symbol?) x)
                      (name x)
                      x)))
       (apply str)
       keyword))

(defn wire
  ([n]
   (let [i (uniq-n n)]
     (if (> i 1) (kw n "#" i) n))))

Let’s see how it looks:

[(wire :a) (wire :a)]
=> [:a :a#2]

Now if we create a wire with a name that already exists, it’ll add a nice little “#2” beside it.

Nice! Let’s use it in wire-and-gate

(defn wire-and-gate [state a b o]
  (let [nand-o (wire (kw a b :and-nand-o))]
    (-> state
        (wire-nand-gate a b nand-o)
        (wire-not-gate nand-o o))))

If we test this out…

(deftest test-and-gate
  (let [s1 (-> empty-state
               (wire-and-gate :a :b :o)
               (trigger-many [:a :b] [1 0]))
        s2 (-> s1
               (trigger :b 1))]
    (testing "just a is on"
      (is (= '(1 0 0) (charges s1 [:a :b :o]))))
    (testing "a and b on"
      (is (= '(1 1 1) (charges s2 [:a :b :o]))))))

; Ran 1 test containing 2 assertions.
; No failures.

Works like a charm!

5: Simulate Bits

Now comes one of the hardest and most important circuits we’ll need to understand. Let’s start by describing our goal:

Notice the interesting thing here. When the s wire is “1”, the value of i is transferred to o. When it is “0”, the value of o is no longer affected by i. o's charge is whatever it was before.

If we can make something like this, that would mean that the charge on “o” is stored. Since it can be either 1 or 0, we can in effect “store” 1 bit of data.

Here’s how we can do this:

The trick with this circuit is the way o and c are connected together. This intertwining thing is called a “latch”, because once a charge gets set in a certain way, these gates will find an equilibrium that causes o to be stored. Pretty cool!

This circuit is pretty complicated and a bit hard to understand (3), but we’ve got the power of simulation at our fingertips! Let’s try building it and test it out:

(defn wire-memory-bit
  "To understand the variables in this circuit,
  follow along with the diagram in the tutorial"
  ([state s i o]
   (let [a (wire :a)
         b (wire :b)
         c (wire :c)]
     (-> state
         (wire-nand-gate i s a)
         (wire-nand-gate a s b)
         (wire-nand-gate a c o)
         (wire-nand-gate b o c)))))

Looks so pretty for such a complicated machine. Now the ultimate question…will it work?!

(deftest test-memory-bit
  (let [s1 (-> empty-state
               (wire-memory-bit :s :i :o)
               (trigger-many [:i :s] [1 0]))
        s2 (-> s1
               (trigger :s 1))
        s3 (-> s2
               (trigger-many [:s :i] [0 0]))]
    (testing "turning i on does not affect the rest"
      (is (= '(0 1 0) (charges s1 [:s :i :o]))))
    (testing "enabling set transfers i to o"
      (is (= '(1 1 1)
             (charges s2 [:s :i :o]))))
    (testing "disabling set, removes further effects on o"
      (is (= '(0 0 1)
             (charges s3 [:s :i :o]))))))

; Ran 1 test containing 3 assertions.
; No failures.

Oh ma gad…it works!

6: Simulate Bytes

Now that we have a bit, we can take one s wire and tie 8 memory bits together with it. That would let us set 8 bits together, which means we can “store” 8 bits of data…which gives us a byte! (5). Here’s how that would look:

Note that in our diagram now “two wires together” is short-hand for writing 8 wires.

Let’s write up a byte in our simulation:

(defn wire-byte [state s ins outs]
  (reduce (fn [acc-state [i o]]
            (wire-memory-bit acc-state s i o))
          state
          (map vector ins outs)))

Easy peasy!

To test this out though, we’re going to need a way to “create” a bunch of names for wires. Let’s write a few helper functions that make this easy:

(defn names [n r]
  (mapv (fn [i] (kw n "-" i)) (range r)))

(def wires (comp (partial mapv wire) names))

Here’s how we could make 8 wires with the name :i

(wires :i 8)
; => [:i-0 :i-1 :i-2 :i-3 :i-4 :i-5 :i-6 :i-7]

Nice! Now to write our test for the byte:

(deftest test-byte
  (let [ii (wires :i 8)
        os (wires :o 8)
        s1 (-> empty-state
               (wire-byte :s ii os)
               (trigger-many ii [1 1 1 0 0 0 0 0])
               (trigger :s 0))
        s2 (-> s1
               (trigger :s 1))
        s3 (-> s2
               (trigger :s 0)
               (trigger-many ii [0 0 0 0 0 0 0 1]))]
    (testing "disabling set, removes further effects on o"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s1 ii)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s1 os))))
    (testing "set s, so os become 1 1 1"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s2 ii)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s2 os))))
    (testing "freeze by disabling s. see that further changes to i do nothing to o"
      (is (= '(0 0 0 0 0 0 0 1)
             (charges s3 ii)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s2 os))))))

Phoof…does it work?

; Ran 1 test containing 6 assertions.
; No failures.

Yes!

7: Simulate Enabler

Now, imagine we had two bytes, connected like this:

Notice how the output wires are shared between B1 and B2. If B1 had a charge of “11110000”, and B2 had a charge of “0001111”, what would happen to the output wires? It would carry a charge of “1111111”! Say we wanted to make sure only one of the bytes sent their output charge into output wires. How could we do that?

We’ll need a new machine. Let’s consider what would happen if we took a bunch of AND gates, and connected them together like this:

Now, if the “e” wire is “on”, the output wires are charged with whatever the input wires are. Buut, if the “e” wire is “off”, the output zeroes out. This machine is called the “enabler”. If we put this together right, we could control what charge gets sent to output wires!

Let’s set it up first, it should be easy peasy:

(defn wire-enabler
  [state e ins outs]
  (reduce
    (fn [acc-state [in out]]
      (wire-and-gate acc-state e in out))
    state
    (map vector ins outs)))

Looks nice! Let’s see the test:

(deftest test-enabler
  (let [ii (wires :i 8)
        os (wires :o 8)
        s1 (-> empty-state
               (wire-enabler :e ii os)
               (trigger-many ii [1 1 1 0 0 0 0 0])
               (trigger :e 0))
        s2 (trigger s1 :e 1)
        s3 (trigger s2 :e 0)]
    (testing "is should be set, but os should be 0"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s1 ii)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s1 os))))
    (testing "os should pass if enabled"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s2 ii)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s2 os))))
    (testing "os should revert if disabled"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s3 ii)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s3 os))))))

; Ran 1 test containing 6 assertions.
; No failures.

🔥

8: Simulate Register

Here’s how we could “fix” our problem with B1 and B2:

If we stuck an “enabler” in front of each byte, we could control what gets sent to output wires. If we wanted to have B1's charge, we would “enable E1”, and make sure E2 was disabled, and vice versa.

This combination of byte and enabler is so common that we can build a machine for that:

It’s called a register! Registers let us both control what bytes are stored, and when these bytes are exposed as output.

To set this up, all we need to do is to tie together a byte and an enabler:

(defn wire-register [state s e ins bits outs]
  (-> state
      (wire-byte s ins bits)
      (wire-enabler e bits outs)))

Badabing, badaboom, it should work. This is a pretty important machine, so let’s make darn sure it works:

(deftest test-register
  (let [ii (wires :i 8)
        bs (wires :b 8)
        os (wires :o 8)
        s1 (-> empty-state
               (wire-register :s :e ii bs os)
               (trigger-many ii [1 1 1 0 0 0 0 0])
               (trigger :s 0)
               (trigger :e 0))
        s2 (trigger s1 :s 1)
        s3 (trigger s2 :e 1)
        s4 (-> s3
               (trigger :s 0)
               (trigger-many ii [0 0 0 0 0 0 0 1]))
        s5 (trigger s4 :e 0)]
    (testing "is should be set, but bs and os should be 0, b/c s & e are 0"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s1 ii)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s1 bs)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s1 os))))
    (testing "is & bs should be set, as s is on. but os should be 0, b/c e is off"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s2 ii)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s2 bs)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s2 os))))
    (testing "is & bs should be set, as s is on. but os should be 0, b/c e is off"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s3 ii)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s3 bs)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s3 os))))
    (testing "is should be new v, but bs and os should be the old value"
      (is (= '(0 0 0 0 0 0 0 1)
             (charges s4 ii)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s4 bs)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s4 os))))
    (testing "os should 0 out again"
      (is (= '(0 0 0 0 0 0 0 1)
             (charges s5 ii)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s5 bs)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s5 os))))))

; Ran 1 test containing 15 assertions.
; No failures.

Very cool!

9: Simulate Bus

Okay, let’s continue our experiment, to an astounding result: what if we connected the inputs and outputs of a bunch of registers to the same wires?

Now, remember that s allows us to decide what gets “stored” into a register, and “e” lets us “pass” the charge of a register’s byte through to the output.

What would happen in the following scenario. Say R1’s byte contains “111”, all s and e wires are 0.

“Charge R1’s e to 1”.
1. Now R1 would enable, and the bus wires would carry the same charge as R1
“Charge R3’s s to 1, then 0”.
1. This would set the value of R3, to the current charge flowing in bus. This happens to be the output of R1!
“Set R1's e to 0” Now the current in bus would disappear again

The result? The byte in R1 would have been “copied” to R3. We’ve just created a bus.

To create a bus, all we need to do is to connect a register’s input and output to the same “bus” wires:

(defn wire-bus [state bus-wires s e bits]
  (wire-register state s e bus-wires bits bus-wires))

This is only a single line, but it’s pretty important to get right. It’s what lets us “copy” registers after all. Let’s see if it works:

(deftest test-wire-bus
  (let [bw (wires :bw 8)
        r1-bits (wires :r1 8)
        r2-bits (wires :r2 8)
        r3-bits (wires :r2 8)
        s1 (-> empty-state
               (wire-bus bw :s1 :e1 r1-bits)
               (wire-bus bw :s2 :e2 r2-bits)
               (wire-bus bw :s3 :e3 r3-bits)
               (trigger-many bw [1 1 1 0 0 0 0 0])
               (trigger :s1 0)
               (trigger :e1 0))
        s2 (-> s1
               (trigger :s1 1)
               (trigger :s1 0)
               (trigger-many bw [0 0 0 0 0 0 0 0]))
        s3 (-> s2
               (trigger :e1 1)
               (trigger :s3 1)
               (trigger :s3 0)
               (trigger :e1 0))]
    (testing "only bus should have charge"
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s1 bw)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s1 r1-bits)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s1 r2-bits)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s1 r3-bits))))
    (testing "r1 should have the charge"
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s2 bw)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s2 r1-bits)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s2 r2-bits)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s2 r3-bits))))
    (testing "move r1 to r3"
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s3 bw)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s3 r1-bits)))
      (is (= '(0 0 0 0 0 0 0 0)
             (charges s2 r2-bits)))
      (is (= '(1 1 1 0 0 0 0 0)
             (charges s3 r3-bits))))))

; Ran 1 test containing 12 assertions.
; 4 failures, 0 errors.

🙀 uh oh, it doesn’t work…

10: Evolve Trigger

Let’s look at this diagram again:

Remember that the bus wires can “receive” a charge now from the outputs of R1 , R2, or R3. Here’s how our set-charge looked:

(defn set-charge [state wire charge]
  (assoc-in state [:charge-map wire] charge))

Imagine if R1 was enabled and a wire was charged to 1. What would happen if R3 got triggered?

It would overwrite our charge!

Time to to evolve our model. One way to think about it, is that bus wires now have multiple “sources” that can provide a charge. Let’s update our charge functions to keep track of this “source”

(defn set-charge
  ([source state w v]
   (assoc-in state [:charge-map w source] v)))

(defn charge [{:keys [charge-map]} w]
  (when-let [charges (vals (charge-map w))]
    (apply max charges)))


(set-charge empty-state :nand-a :w 1)
; => {:charge-map {:w {:nand-a 1}}, :nand-gates []}
(let [s1 (-> empty-state
               (set-charge :nand-a :w 1)
               (set-charge :nand-b :w 0))]
    (charge s1 :w))
; => 1

Nice. Now, whenever we set a charge, we are aware of waht source it comes from.

Let’s update trigger to include a source too:

(defn trigger
  ([state wire new-v] (trigger :repl state wire new-v))
  ([source state wire new-v]
   (let [old-charge (charge state wire)
         state' (set-charge state source wire new-v)
         new-charge (charge state' wire)]
     (if (= old-charge new-charge)
       state'
       (reduce (fn [acc-state out] (trigger-nand-gate acc-state out))
               state'
               (dependent-nand-gates state' wire))))))

And let’s make trigger-nand-gate use a source:

(defn trigger-nand-gate
  [state {:keys [ins out]}]
  (let [new-charge (apply nand-output (charges state ins))]
    (trigger (apply kw (conj ins out)) state out new-charge)))

Now each NAND gate triggers with a specific name as a source. This would make it so R1's output trigger wouldn’t interfere with R2 output trigger! Let’s test out the bus again:

; Ran 1 test containing 12 assertions.
; No failures.

We’re back.

11: Simulate and-n

Right now, our and gate only tests whether two inputs are both 1. What if we wanted to test that three inputs are all 1? We could just wire up a bunch of AND gates together:

Let’s call this the AND-N gate. It can take N number of inputs, and produces one output. We can wire this up using some nice recursion:

(defn wire-and-n [state ins out]
  (let [[a b] (take 2 ins)
        rem (drop 2 ins)]
    (if-not (seq rem)
      (wire-and-gate state a b out)
      (let [w (wire (kw a b :-and))]
        (wire-and-n
          (wire-and-gate state a b w)
          (list* w rem)
          out)))))

We keep recursing wire up the inputs as AND gates, until we’re only left with two. Let’s see how it works:

(deftest test-and-n
  (let [ii [:a :b :c :d :e]
        s1 (-> empty-state
               (wire-and-n ii :o)
               (trigger-many ii [1 1 1 1 0]))
        s2 (trigger-many s1 ii [1 1 1 1 1])]
    (testing "if only some are charged, o is off"
      (is (= '(1 1 1 1 0)
             (charges s1 ii)))
      (is (= 0 (charge s1 :o))))
    (testing "if all are on, we are on"
      (is (= '(1 1 1 1 1)
             (charges s2 ii)))
      (is (= 1 (charge s2 :o))))))

; Ran 1 test containing 4 assertions.
; No failures.

12: Simulate decoder

Now, Say we have two inputs (a b), and we want to know how they are charged: (a0 b0) (a0 b1) (a1 b0) (a1 b1).

We could make a machine that figures that out:

It’s called a decoder. It guarantees that only one wire will turn on, and each wire will represent a specific state of a and b. Here’s how we could do it:

This looks like a lot, but in essence it’s pretty simple. Each input is wired into a NOT gate. Now let’s take an example: what would happen If we wire the NOT outputs of a & b to an AND gate?

If that AND output turned “1”, it would mean that both a and b had to be 0! This would mean the output wire of that AND gate, when “1”, represents the selection (a0 b0). We can keep wiring AND gates like this, to represent all different selections.

It can even be generalized: for N inputs, we create N NOT outputs. Then we can wire them up to and-n gates in such a way that the output represents the a special selection.

Let’s do that. First, we’ll need to install Clojure’s math combinatorics library in our deps.edn:

{:deps {org.clojure/math.combinatorics {:mvn/version "0.1.6"}}}

Now let’s require it:

(:require [clojure.math.combinatorics :as c])

With this we can create a quick function that produces our “wire” selection mapping:

(def decoder-mapping (partial c/selections [0 1]))

(decoder-mapping 2)
; => ((0 0) (0 1) (1 0) (1 1))

Perfect, this gives us a “selection”. We can use these “selections”, to decide what the combination of wires should be for an and-n gate.

Here’s how the decoder could look:

(defn wire-decoder
  [state ins outs]
  (let [ins-nots (mapv #(wire (kw % :-not)) ins)
        state' (reduce
                 (fn [acc-state [in out]]
                   (wire-not-gate acc-state in out))
                 state
                 (map vector ins ins-nots))
        state'' (reduce
                  (fn [acc-state [sel out]]
                    (let [and-ins (map-indexed
                                    (fn [i sign]
                                      (if (= sign 0)
                                        (nth ins-nots i)
                                        (nth ins i)))
                                    sel)]
                      (wire-and-n acc-state and-ins out)))
                  state'
                  (map vector (wire-mapping (count ins)) outs))]
    state''))

…Pretty elegant. Thank you Clojure. We first wire up a bunch of NOT wires. Then we generate a bunch of selections, and for each one wire up and and-n gate. We wire either from ins or in-nots, based on what the selection tells us.

The ultimate question…will it work?!

(deftest test-decoder
  (let [ii (wires :i 4)
        os (wires :o 16)
        sels (wire-mapping (count ii))
        sel (nth sels 5)
        o (nth os 5)
        s1 (-> empty-state
               (wire-decoder ii os)
               (trigger-many ii sel))]
    (testing "only 1 output is on"
      (is (= 1 (charge s1 o)))
      (is (every? zero? (charges s1 (remove #{o} os)))))))

; Ran 1 test containing 2 assertions.
; No failures.

😦

13: Simulate Lookup

With all of this, we can wire together the first part of RAM. We need a way to “look up” a byte.

What if we took one byte — let’s call it mar — and wired the first 4 outputs to one decoder, and the last 4 outputs to another decoder?

Well, this would produce 256 output wires. For each value in the mar byte, two output wires would be on: one from the first decoder, and the other from the second decoder.

We can think of this then, like a 16x16 grid. Each “byte” in mar represents a unique “intersection” in the grid. Now, in the future we can tie some registers to those grid wires, and when an “intersection” is on, we can make that register active! Pretty cool.

Let’s build it:

(defn wire-mar
  [state s is os first-4-outs last-4-outs]
  (-> state
      (wire-byte s is os)
      (wire-decoder (take 4 os) first-4-outs)
      (wire-decoder (drop 4 os) last-4-outs)))

Will it work?

(deftest test-mar
  (let [ii (wires :i 8)
        os (wires :o 8)
        first-4-decoders (wires :fd 16)
        last-4-decoders (wires :ld 16)
        s1 (-> empty-state
               (wire-mar :s ii os first-4-decoders last-4-decoders)
               (trigger-many ii [0 0 0 0 0 0 0 0])
               (trigger :s 0))
        sel (nth (wire-mapping 4) 5)
        s2 (trigger-many s1 ii (concat sel sel))
        s3 (-> s2
               (trigger :s 1)
               (trigger :s 0))
        test-idx (fn [state idx]
                   (let [fd (nth first-4-decoders idx)
                         ld (nth last-4-decoders idx)]
                     (is (= 1 (charge state fd)))
                     (is (every? zero? (charges state (remove #{fd} first-4-decoders))))
                     (is (= 1 (charge state ld)))
                     (is (every? zero? (charges state (remove #{ld} last-4-decoders))))))]
    (testing
      "by default only one wire is on, and it's the correct mapping"
      (test-idx s1 0))
    (testing
      "even if ii changes, sel doesn't change b/c s is 0"
      (test-idx s2 0))
    (testing
      "once s triggers, the sel does change"
      (test-idx s3 5))))

; Ran 1 test containing 12 assertions.
; No failures.

Nice, we can look something up!

14: Simulate IO

Time to complete the picture:

We’re going to add an io bus at the bottom, a set wire an enable wire. For each “intersection” from our decoders, what would happen if we did this?

The top decoder wire and left decoder wire are fed into an AND gate that outputs x. x will only be “on” when both decoder wires are “on”. That means x would represent whether our intersection is active!

x and io-s are fed into an AND gate, which produces s. s will only turn on, when both io-s is charged and the intersection is active.

x and io-e are fed an AND gate, producing e. This will only turn on, when both io-e is charged, and the intersection is active.

After that, we take s e and the io wires, and connect them to a register.

If we follow that logic, it means that this register can be enabled and set, only when the intersection is “on”! If hooked this up to each intersection…all of a sudden we have 256 bytes of memory!

Let’s write this to work with just one intersection:

(defn wire-io
  [state io-s io-e ios decoder-o-1 decoder-o-2 register-bits]
  (let [x (wire (kw decoder-o-1 decoder-o-2 :x))
        s (wire (kw decoder-o-1 decoder-o-2 :s))
        e (wire (kw decoder-o-1 decoder-o-2 :e))]
    (-> state
        (wire-and-gate decoder-o-1 decoder-o-2 x)
        (wire-and-gate x io-s s)
        (wire-and-gate x io-e e)
        (wire-bus ios s e register-bits))))

Does it work?

(deftest test-io
  (let [ios (wires :io 8)
        rs (wires :r 8)
        s1 (-> empty-state
               (wire-io :s :e ios :w1 :w2 rs)
               (trigger-many ios [0 0 0 0 0 0 0 0])
               (trigger-many [:s :e :w1 :w2] [0 0 0 0])
               (trigger-many ios [1 1 1 0 0 0 0 0]))
        s2 (trigger s1 :s 1)
        s3 (trigger-many s2 [:w1 :w2] [1 1])
        s4 (-> s3
               (trigger :s 0)
               (trigger-many ios [0 0 0 0 0 0 0 0]))
        s5 (trigger s4 :e 1)]
    (testing "io set, but reg not affected"
      (is (= '(1 1 1 0 0 0 0 0) (charges s1 ios)))
      (is (= '(0 0 0 0 0 0 0 0) (charges s1 rs))))
    (testing "io set enable doesn't change, because intersection is not on"
      (is (= '(1 1 1 0 0 0 0 0) (charges s2 ios)))
      (is (= '(0 0 0 0 0 0 0 0) (charges s2 rs))))
    (testing "once intersection is on, charge transfers"
      (is (= '(1 1 1 0 0 0 0 0) (charges s3 ios)))
      (is (= '(1 1 1 0 0 0 0 0) (charges s3 rs))))
    (testing "once s turns off again, changes to io don't make a difference"
      (is (= '(0 0 0 0 0 0 0 0) (charges s4 ios)))
      (is (= '(1 1 1 0 0 0 0 0) (charges s4 rs))))
    (testing "if we turn on e, the r charge transfers to the io"
      (is (= '(1 1 1 0 0 0 0 0) (charges s5 ios)))
      (is (= '(1 1 1 0 0 0 0 0) (charges s5 rs))))))

; Ran 1 test containing 10 assertions.
; No failures.

Great!

15: Wire RAM

Now, all we need to do is to wire-mar, and for each intersection, wire-io. Let’s do that:

(defn wire-ram [state mar-s mar-is io-s io-e ios]
  (let [mar-os (wires :mar-o 8)
        mar-first-4-outs (wires :mar-dec-f 16)
        mar-last-4-outs (wires :mar-dec-l 16)
        state' (wire-mar state mar-s mar-is mar-os mar-first-4-outs mar-last-4-outs)
        intersections (c/cartesian-product mar-first-4-outs mar-last-4-outs)
        state'' (reduce
                  (fn [acc-state [fw lw]]
                    (wire-io acc-state io-s io-e ios fw lw
                             (wires (kw fw lw :rb) 8)))
                  state'
                  intersections)]
    state''))

We first wire-mar. Then, we use cartesian-product to create a list of decoder intersections. For each of those intersections, we wire-io. Congratulations, you’ve wired together RAM!

16: Evolve state

Now, let’s take a look at how many NAND gates we have when we set our ram up:

(def ram (wire-ram
           empty-state
           :mar-s
           (wires :mar-i 8)
           :io-s
           :io-e
           (wires :io 8)))


(count (:nand-gates ram))
; => 14056

That’s a lot. Let’s try triggering something. How long does it take?

(trigger ram :mar-s 1)
; ...

Oi. Veery long. Why? Well, let’s remember our dependent-nand-gates:

(defn dependent-nand-gates [state wire]
  (filter
    (fn [{:keys [ins]}] (some #{wire} ins))
    (:nand-gates state)))

Every time a wire is triggered, we go through all 14056 NAND gates! That’s a lot of iteration for finding what is probably a few NAND gates.

Let’s make that faster:

(def empty-state {:charge-map {} :in->nand-gate {}})

(defn wire-nand-gate [state a b o]
  (reduce
    (fn [acc-state in]
      (update-in acc-state
                 [:in->nand-gate in]
                 (fn [xs] (conj (or xs []) {:ins [a b] :out o}))))
    state
    [a b]))

(defn dependent-nand-gates [state wire]
  (get-in state [:in->nand-gate wire]))

Here, we make accessing dependent NAND gates fast. Now it’s a matter of a dictionary lookup. If we try it out, it’ll be muuch faster!

17: Testing it out!

Okay, we built it, we made it fast, but will it work? Let’s imagine we built a machine like this:

We wire up mar switches to the mar byte, and add a switch to the set wire
1. Depending on which switches we turn on, we can set a specific byte in mar, and access a specific “register” in our grid!
We wire up io lights
1. Whenever io has a charge, those lights will go on. Whichever light is on means 1, whichever light is off means 0. This will tell us the byte that is on the io bus!
We tie the io-s wire to the io set switch
1. When that switch is on, the io-s wire will be on, and as a result the currently active register’s “set” wire will be on. This will let us “save” whatever charge is in io!
We tie the io-e wire to an io enable switch
1. When that switch is on, the io-e wire will be on, and as a result the currently active register’s “enable” wire will be on. This will let us “pass” the active register’s charge into io. That will cause io lights to turn on and let us read the value in the register!
We wire up io switches
1. These switches will allow us to set a specific charge into io. If we combine this by toggling our io “set” switch, we can save a specific charge into the active register!

With a machine like that, we can now use our RAM! Here’s how.

(I recommend following along on the diagram above)

To access a specific register:

Use the MAR switches, to select the exact intersection we want, and toggle the mar set switch
Toggle the io enable switch . This will send the active register’s data into io
Look at the io lights: The combination of lights that are on represent the value of the register!
When done, toggle the io enable switch off.

To set data to a specific register:

Use the MAR switches, to select the exact intersection we want
Use the IO switches, to set the charge in IO that represents the data we want to save.
Toggle the io set switch on. Now the charge of io will be saved to that specific register!
Now toggle the io set switch off, and toggle all the io switches off.
Badabing, badaboom. you’ve saved your data!

Let’s go ahead and create that machine.

First, let’s create a quick helper function to initialize our RAM:

(defn initialize-ram [mar-s mar-is io-s io-e ios]
  (-> empty-state
      (wire-ram mar-s mar-is io-s io-e ios)
      (trigger-many mar-is [0 0 0 0 0 0 0 0])
      (trigger-many ios [0 0 0 0 0 0 0 0])
      (trigger-many [mar-s io-s io-e]
                    [0 0 0])))

Next, here’s a quick helper function to “set” data into our mar byte:

(defn set-mar [state mar-s mar-is mar-vs]
  (-> state
      (trigger-many mar-is mar-vs)
      (trigger mar-s 1)
      (trigger mar-s 0)))

Here’s the function that follows our recipe to “access a specific register”

(defn handle-read [state mar-s mar-is io-e ios loc]
  (let [charge-bus-with-register (-> state
                                     (set-mar mar-s mar-is loc)
                                     (trigger io-e 1))
        next (-> charge-bus-with-register
                 (trigger io-e 0))]
    (println (str "> " (string/join (charges charge-bus-with-register
                                          ios))))
    next))

Here’s the function that follows our recipe to “set data to a specific register”

(defn handle-write [state mar-s mar-is io-s ios loc vs]
  (let [next (-> state
                 (set-mar mar-s mar-is loc)
                 (trigger-many ios vs)
                 (trigger io-s 1)
                 (trigger io-s 0)
                 (trigger-many ios [0 0 0 0 0 0 0 0]))]
    (println "> done")
    next))

With these two things, we can create a REPL loop:

(defn ram-repl []
  (println
    (str "🔥 Ram Simulation: Type a command. Here's what you can do: \n"
         "   (read [1 0 1 0 1 0 1 0]) \n"
         "   (write \[1 0 1 0 1 0 1 0\] [1 1 1 1 1 1 1 1]) \n"
         "   (exit)"))
  (let [mar-is (wires :mar-i 8)
        ios (wires :mar-io 8)
        initial-state (initialize-ram :mar-s mar-is :io-s :io-e ios)]
    (loop [state initial-state]
      (let [input (read-string (read-line))
            cmd (first input)
            args (rest input)]
        (condp = cmd
          'read
          (recur (handle-read state :mar-s mar-is :io-e ios (first args)))
          'write
          (recur (handle-write state :ms mar-is :io-s ios (first args) (second args)))

          'exit
          (println "> Goodbye!"))))))

And see how it goes:

Let’s take a moment to bask in our circuit:

Fin

Wow. we did it. 14056 NAND gates. 256 bytes of RAM. I hope you had a blast 🙂 — If you want to see how the rest of the computer is made, I definitely suggest checking out Scott’s book. He also has a great site with more example projects. To see the code all together, here’s the repo.

Thanks to Daniel Woelfel, Julien Odent, Sean Grove, Paul Vorobyev, Alexander Kotliarskyi, Alex Reichert, Poornamidam for reviewing drafts of this essay.

(1) I say this pretty lightly, but treating the charge on circuits as code was a pretty phenomenal innovation. I could only imagine what it might have been like, when Shannon showed a full-adder.

(2) To really model circuits, we’d need to learn about Maxwell’s equations. Just ordered a textbook for this, so maybe next time 🙂.

(4) That stack exchange question helped me a lot. If you’re even more curious, start with this youtube video, and follow along until the gentleman gets to the “D” latch. He uses NOR gates, but the essence is the same.

(5) There were a lot of different kind of architectures that were tried.

Classes are just a fancy way of writing higher order functions

Stopa — Wed, 09 Sep 2020 16:15:08 +0000

Joe and I recently kicked of a re-read of SICP. I can say that it is the most interesting textbook I have gone through. Imagine, you begin with just 4 or 5 constructs, and you end up building algebraic equation solvers, circuit simulators, and even logic programming languages. Because you start off with such few constructs, the added benefit is that you begin to see the fundamentally simple, shared essence in programming.

I wanted to give you one example that surprised me in the book. We tend to think that classes belong in a fundamentally different category from functions.

But are they so different?

For example, let’s say we have a class like this:

class Person { 
  constructor(firstName, lastName) {
    this.fName = firstName; 
    this.lName = lastName;
  }
  getFullName() { 
    return this.fName + ' ' + this.lName;
  }
  setFirstName(firstName) {
    this.fName = firstName;
  }
}

Well, if we think about it, this is really just a higher order function. a Person higher order function accepts arguments (constructor), and returns a list of functions that can manipulate those arguments (methods). We could write Person like this:

 function Person(firstName, lastName) {
  let fName = firstName; 
  let lName = lastName;

  function getFullName() { 
    return fName + ' ' + lName;
  }

  function setFirstName(firstName) { 
    fName = firstName
  }

  return function(method) { 
    switch (method) { 
      case 'getFullName': 
        return getFullName;
      case 'setFirstName': 
        return setFirstName;  
    }
  }
}

Now,

const person = new Person("Ben", "Bitdiddle")
person.getFullName()

becomes

const person = Person("Ben", "Bitdiddle")
person('getFullName')()

Here, instead of invoking a method, we are “passing” a message. This is why by the way, many classic OO folks talk about object orientation really being about message passing.

Yup, really. Classes are just higher order functions, which accept arguments (constructor) and return a list of functions that can manipulate those arguments (methods).

When you previously thought two concepts were different, but they turn out to be the same, you’re ripe to discover new ideas: you can find the deeper abstractions between them, apply ideas from across those seemingly different categories, and move between concepts more fluidly. So, not only are epiphanies like this fun, but they’re much more useful than you’d think.

If you liked this, there are a ton of similar epiphanies in the textbook. To experience it best, I suggest picking a partner and working through the book together.

Thanks to Daniel Woelfel, Alex Reichert, Jacky Wang for reviewing drafts of this essay

The Hacker Way: How I taught my nephew to program

Stopa — Thu, 06 Aug 2020 16:08:07 +0000

Over the last year, my 13 year old nephew developed a love for hacking. From anime chat, to snake, a minimal twitter, a blog, to an anime music startup, he’s built some cool stuff (1). What I’m most proud of though, is that he’s done this with self directed play, rather than with a rigid curriculum.

To help him do this, I acted as a yoda in the background. I experimented with a personal teaching philosophy, and I wanted to share the core tenets with you — I call it “The Hacker Way”:

Principle A: Learning is Play

Kids are taught to associate learning with responsibility. Learning is stuff you don’t want to do, but have to because it’s either good for you or will make your parents happy — sort of like broccoli. With a belief like this, both the kid and the teacher are playing life on hard mode. The kid will lean towards the bare minimum. They won’t have any desire to self-direct and look deeper. The teacher has to constantly push the student along.

This method is disastrous for mastery. Mastery requires depth, and you’d need a kid with incredible self-disciple, and a teacher with an incredible amount of time, to reach the kind of depth mastery demands. Imagine the alternative: what if the kid was genuinely interested? All of a sudden, learning is play, and depth is exploration.

My primary goal throughout every one of our conversations was to help him cement this view: learning is play. So, how do we do that?

Principle B: Meet them at their interests

Well one of the key differences between play and work is freedom: play happens when you’re doing what you want to be doing. This means, you need to make sure that the kid is working on what they’re actually interested in. Even though you know, that if they just hung on for some time, they’d learn to love it, it’s more harm than good: it’s unlikely they’ll persevere and regardless they’ll remember the pain.

The solution to the problem is to meet them where they’re at, and guide them from there. For example, say you want to get a kid to read books. Well, if they like cartoons now, what if you suggested anime? (japanese tv shows). If they love the anime they’ll soon discover manga (japanese comic books). Once they read a bunch of manga, all of a sudden reading is something they like to do. What if you threw in some adventure novels after that, like Dune? Slowly but surely they’re on the road to voracious reading.

The key idea to notice, is that we expect kids to grok ideas that are several steps away from their development. If you observe what they’re interested in right now, then form a plan from there, it’s going to be a lot more smooth. This requires patience, but that is the reality of things.

For my nephew, programming started out as drawing. I knew he liked to draw. He began designing apps with paper and pencil. So I got him sketch. and sat him down one day to show him the basics. He was into youtube, so he started designing banners. With that, he had a joyous entry point.

So, it was smooth sailing from there, they saw that work was play?

Principle C: Let kids drop things

Not quite. The other difference between play and work, is that you can stop playing any time. It’s common amongst older folks to teach a kid something — especially if they pay for some item — and then expect that the kid will devote themselves seriously to it.

This of course, is never the case. Kids don’t know what they want and they certainly don’t have large attention spans. The common adult reaction is to guilt trip the kid — you said you wanted this, and now it’s collecting dust. The ostensible purpose is to teach a kid the value of a dollar, but I don’t think this is what actually happens. Instead, they learn to avoid taking risks. They may force themselves to continue on with that activity too, which teaches them to dislike learning.

What if you encouraged the opposite? Any time you gave a gift, you said: hey, if at any point this becomes boring, promise me to stop and do something else. All of a sudden the pressure is gone. They can explore at their leisure, discover more of what they like, and it becomes natural to come back to things.

I did just this. With books, every time I suggested something, I told him to only read when he felt like it, and to stop and do something else as soon as he was bored. Lo and behold, he finished more books than I could have imagined, and started to form his own taste.

With programming, after the youtube design, he had a bit of a lull, where he focused on other things. Eventually though, curiosity and desire rose in him again: how could he make these designs real? How could he make real websites?

At this point, the desire was hot, and it was time to transform it forward. We can teach them something now. But how?

Principle D: Treat kids like junior apprentices

We teach kids in two common ways. The first is to form a “classical” environment: you start from first principles, and guide them through the fundamentals: what is a string, what is an array, etc. This is often the most boring approach — if a kid doesn’t understand why they need to learn something, it’s much harder to learn it.

The second is to form a “kid-size” environment: maybe a dummy programming language that works on kid-style problems. This may be better than the classical approach, but I think it still suffers from similar problems: the kid doesn’t really understand why they’re doing this. Most game-like tools are less fun than real games too, so if they see this strictly as games…there are much better options. (2)

An alternative method is to treat them with a bit more respect. What if you treated them like an intern? Imagine how a kid would feel if they worked on what the pro adults did. It’s intriguing, and it may even be something their friends think is cool.

My working approach is to do just that and treat them like junior apprentices. They get the same tools as adults: but like all apprentices, they need to start by learning subsets first. For programming, I started by showing him how to make a simple site with HTML and CSS. Just the basics — enough for him to make something.

With HTML & CSS he built a personal news site, a blog, a tic tac toe board, and started doing his school projects as websites. He saw how this really did feel like the real thing — it spiked his imagination and got him exploring further.

Note, that like most apprentices, he did the majority of the research and work: I simply gave the problems, and was available for video calls when he got stuck. Those video calls were import though: Like a real apprentice I made sure to treat his questions seriously, and gave him answers that satisfied his curiosity. This also let me figure out what kind of project he could find interesting next. The work itself was up to him.

Eventually, he wanted to make the news site do dynamic things: How can you hide and show content? How can you make buttons work? Well, time to learn a little bit of javascript. There’s a valley here — he may need to understand strings now — but he’s built enough that he can probably stomach a few videos on the fundamentals. With that, he’s off to the races — until he decides to work on something else for a bit of course 🙂

Fin

And that’s my Hacker’s Way. Instill in the idea that learning is play. Meet the kid where they’re at, let them explore, and treat them like a junior apprentice.

Aside: a curriculum

I didn’t go too deep into the curriculum in the essay, because it depends on the kid: where are they at, and what are they interested in now? Nevertheless, to get a taste, here’s a small subset of how his exploration developed:

Started off with Sketch. Made youtube banners, small site designs, etc
Moved to HTML & CSS. Made a blog, a news site, a tic tac toe board,
Showed him how to deploy sites to firebase, so he could show his friends
Could stomach some codecademy + youtube lessons, to learn some basics of javascript: strings, arrays, etc
Guided him through a simple tutorial: given an input, take the value and make it the background color. This was one of the few times I actually sat down with him. He could use the ideas there to build a bunch more stuff
He started building a bunch of javascript-enabled sites: cooler blogs, a todo app, an anime app, some school projects, etc
Eventually, the curiosity came: how can I save data?
Showed him how to use firebase. He went on a spree after that: built tic tac toe, snake, anime chat, etc
Eventually, he expressed an interest in python. I challenged him to make a text-based twitter bot
He wanted to turn it into an app, so he started playing with flask. I walked him through deploying it to Heroku
Now he’s interested in building animusic: an app to let you list your favorite songs in anime.

Note, at some point, I may build something to help kids learn like this. If you’re interested in that, follow me on twitter — will announce if I do anything there : }

Thanks Joe Averbukh, Daniel Woelfel, Ilia Parunashvili, Nino Parunashvili, Alex Reichert for reviewing drafts of this essay

(1) If you’re a hacker you may notice some glaring security vulnerabilities. Please leave them alone, or if you like, hack with jest :}. Think a lesson on security will get in the way for now

(2) Some environments, like Roblox, could be great: the motivation is real (wow I can make a real game), and what they learn is real (Lua). One of my other nephews is playing with this, let’s see how it goes : }

Assessing Abstractions

Stopa — Fri, 17 Jul 2020 18:53:35 +0000

Some abstractions are ticking time bombs, while others help you move fast. How can you tell? What follows is my personal exploration for how I assess abstractions.

Problem

We add abstractions in our programs to solve problems. So, let’s start with the fundamental value proposition: what problem does our abstraction solve?

Let’s take a look at one example abstraction:

    NLP.parse(...) // => { intent: "set_alarm", at: "1593538633430" }

This could be a natural language processing abstraction, which lets us take a piece of text, and extract meaning from it. The inherent problem of natural language processing is pretty darn complex, so an abstraction that helps us solve it would be very valuable. This is a sign of a good abstraction.

Now let’s compare that to

    StringSplitter.easySplit(str, splitStr)

Maybe this abstraction, adds a light layer on top of string.split. For example, it may make it so you don’t have to worry about regexes, and can turn common string patterns into regexes. The value of a StringSplitter abstraction is pretty darn low. Maybe StringSplitter treats splitStr in a way that’s a bit more in-line with the someone’s thinking, but at the end of the day this boils down to an indirection.

This leads us to the first principle. The more complex the problem it solves for you, the better the abstraction [1].

Interface

After we’re convinced that the abstraction we are about to add solves a tough problem for us, the next thing to consider is the interface: how do we interact with the abstraction? Imagine if NLP.parse was called like this:

    NLP.parse(lang, text)

This is a great interface. It’s small. We don’t need to understand any internals. For the main use-case, all we need to do is to provide language and text. Compare that with

    NLP.parse(
      text,
      lang, 
      strategy,
      shouldUseFlagA,
      ...
      shouldUseFlagZ
    )

In order to use this version, we’d need to deeply understand the internals of NLP.parse. This lowers the value of the abstraction, because we need to do more work to solve the same level of complexity.

This leads us to the second principle: great abstractions have small interfaces.

Breakthrough Cost

Now that we have an abstraction with a simple interface that solves a hard problem, we need to ask a possibly fatal question: what happens when we need to break through the abstraction?

All abstractions are leaky at some point. What will happen when you need the abstraction to behave differently? What will happen when it doesn’t work as you expect?

For example, for NLP.parse(lang, text), what if we needed to sort and score the results differently? What if there’s a bug, and we aren’t getting the entity we expect, can we look through and debug?

Understanding the answer to this, will give us the breakthrough cost. To do this, we need to peak through the code. How is NLP.parse implemented?

    parse(lang, text) { 
      return format(scoreEntities(fetchEntities(lang, text)))
    }

In one solution, it could be composed of other abstractions that we can take advantage of. This is a great sign, because we can reuse the underlying abstractions in cases where we need to do something more complicated. Compare that to

    parse(lang, text) { 
     internalParse(lang, text, flagA, flagB, ...flagZ)
    }

This feels more dangerous. If these flags all head to the same function, it’s a sign that a bunch of different features are complected together. It’s also worrying: what if one of these flags don’t do what you want? you may have to fork the abstraction.

This leads us to the third principle: great abstractions are transparent. I think this principle is the most overlooked. It’s easy to take the productivity win upfront, but if the abstraction you add can’t be changed, and can’t be introspected, it’s very likely to bite you at some point.

Generality

The final principle is orthogonal to the last three, but maybe it’s the most important. Hardy said there is no permanent place in the world for ugly mathematics — So it is with abstractions. The beauty in math relates to how “general” and “tight” the solution is. I think this parallels well with abstractions.

If you use an abstraction that is “essentially” simpler, it’s more likely to last, and it’s likely to be more powerful.

Consider if the abstraction for NLP, was made up of specific algorithms, just for natural language processing. This would still be very valuable, but what would be even more valuable, is if the abstractions that this library was composed of was more general: if the parts that compose it were deep learning abstractions, you could reuse them for other problems.

Fin

And we reach the end. To pick great abstractions: pick the ones that solve a complex problem for you. Make sure they have a simple interface, and take a look at the internals, so you’re confident you can jig things up if needed. The more general and simple you can get for the same amount of power, the better.

Want to see some great abstractions in the wild? First, chances are you are using many of them: TCP, higher order functions like map & filter, React. Some you may not have explored: Go’s CSP, Rich Hickey’s Datomic, or his seq abstraction in Clojure. As you pick up abstractions, I encourage you to run each one as an experiment: ask yourself at the end how things went, discuss them with your friends, and soon you’ll develop a much more nuanced taste.

[1] The rabbit hole gets deeper. Even if an abstraction solves a complex problem you have, you may need to take a step back and also ask: why do I have this problem? For example, kubernetes may be a great solution to building distributed systems, but why do you have a distributed systems problem? Many times the problem itself can be avoided. For the answer to that, Hacker’s Paradise tries to covers it.

Thanks to Alex Reichert, Daniel Woelfel, Martin Raison, Sean Grove for reviewing drafts of this essay

Sets and Probability

Stopa — Wed, 27 May 2020 17:25:35 +0000

I’ve been a big fan of Nassim Taleb’s Incerto. He wrote a series of essays on life, where all the topics revolve around decision making under uncertainty. I wanted to dig deeper on some of the more technical concepts he alluded too, so last year I explored on a few textbooks on probability theory.

I was surprised with how elegant the field was. The most inspiring idea to me was how the originators interpreted probability through set theory. Not only is it a beautiful way to look at things, but by seeing it this way, they could apply few axioms, leverage set theory, and badabing badaboom they had a whole field’s worth of discoveries.

I wanted to share with you an example from one of the textbooks, that illustrated the power of seeing probability through this lens, and demonstrated how you could begin deriving complex ideas from the simplest kernel.

Boxes and balls

Let’s say you have 2 boxes. In Box 1, you have 99 red balls, and 1 white ball. In Box 2, you have 99 white balls, and 1 red ball.

You pick a box at random, then, you pick a ball from that box.

Question 1: What’s the chance that you pick a red ball?

Memory

This can get a bit tough to reason about. There’s a 50% chance you pick Box 1. In Box 1, you have a 99% chance. If you picked Box 2, you have a 1% chance. How do we combine these probabilities together?

If you reason the way you were taught in high school, you may think like this:

Well, there’s a 50% chance I pick Box 1, and a 99% chance after that to pick a red ball
And, there’s a 50% chance I pick Box 2, and a 1% chance after that to pick a white ball.

So the total probability can be 50% * 99% + 50% * 1%

Which is 49.5% + 0.5% which is…50%

Now this will work, but notice how the probability was 50% — Did you really need to do all that work to figure this out? (1)

Intuition

Let’s reimagine what probability here means. First, let’s consider: what are all the possible outcomes?

For out experiment, an outcome must contain two choices: The box we chose, and the ball we chose after that. We could represent it like this:

This is one outcome — we picked box 1, then picked red ball 1.

How many of these outcomes do we have?

We can list it out: we pick box 1, red ball 1, box 1…red ball 99, etc. In total, we would have 200 possible outcomes.

Now that we have all the outcomes in mind, we can answer the question: what’s the probability that we pick a red ball?

Well, how many outcomes contain a “red ball”?

Looks like 100. This means that 100 of 200 outcomes would give us the result “we got a red ball” — 100/200 makes 50%

Note how this boiled down to just “counting” the outcomes we cared about. Is it really that easy? Let’s try with a harder example.

Question 2: You picked a red ball, what’s the probability that it came from Box 1?

Memory

This question can get pretty hairy to answer from what we learned in high school. Given that we chose a red ball, what’s the chance that it was Box 1? Well, there are 99 red balls in Box 1, and only 1 red ball in Box 2, so the chance that it came from Box 1 is very high. But how high?

We may recall Bayes Theorem here, but the formula can be hard to remember.

Intuition

However, if we think in sets, we can kind of derive Bayes Theorem. Let’s look at our outcomes again:

How many of these outcomes contain “red ball”?

Yup, 100 total. Since we know we got a red ball, this means that we could have only gotten one of these 100 outcomes.

Out of these outcomes, how many come from “Box 1”?

That's 99 outcomes. So out of 100 outcomes that could have happened, 99 of those came from Box 1. 99/100 and you have a 99% chance that given a red ball, it came from Box 1.

This too, just came down to counting the number of outcomes. Now, it can get a lot more difficult — what if you can’t possibly count the number of outcomes? what if each outcome has a different probability? But, just from this notion of events forming a set of possible outcomes, we can chug along and derive out quite a bit.

(1) Alexandre came up with a pretty beautiful intuitive solution to question 1: consider symmetry — since the problem is symmetric (you can reverse white and red), it implies the only solution could be 50%

Thanks to Daniel Woelfel, Alexandre Lebrun, Bipin Suresh, Mark Shlick for reviewing drafts of this essay

Hacker's Paradise

Stopa — Thu, 07 May 2020 18:05:51 +0000

Note: this essay tries to answer the question “What is the essence of System Design, and how do you do it?”. It covers broad strokes. At some point I hope to go much deeper. Meanwhile, I hope you find this enjoyable :)

What is a hacker’s paradise?

My vote would be the beginning years of a startup.

The whole system fits in your head. All your problems are important, and you can solve them any way you like. You’re spinning clay while the world is pouring concrete. If you love to create it’s easy to see: despite all the schleps of a startup, an environment with speed, independence, and changeability is paradise.

Elephant

But we know this doesn’t last long. When those same startups become big, most of them slow down to a crawl. Why is that?

In one of Rich Hickey’s talks, he made a metaphor that could explain it. Paraphrased, he said “Your system grows into an elephant. Every new feature is you teaching it new tricks”.

The larger and hairier the elephant, the harder it is to teach it tricks. And, of course some tricks become off-limits: you can’t teach an elephant to do backflips.

So companies slow down because their systems get large and hairy. Is that the only reason? I don’t think so, but it is certainly one of the biggest. An argument could be made for organizational issues: there’s a cost to lots of people working together. But systems grow exponentially in size, so even if everyone agreed and they worked together perfectly, I’d bet that system complexity would take a fair amount of the blame.

System Design

Taming that elephant, I think, is the essence of system design. So how do we *do s*ystem design?

A lot of complex ideas come to mind when we think about what’s involved: Robustness, performance, stability, safety, scale. These are all important concepts, but I think they are not the central goal.

The central goal is much simpler. It’s singular and defensive. Remember that when we started, we already had a hacker’s paradise, Our goal is to hold the fort. To do this, just one idea encapsulates it all: changeability. Changeability maximizes the impact an engineer can have on your system, and at the end of the day it’s those engineers who can affect any improvement to your system. This means that robustness, performance, stability, safety, scale, and all else are dependent on changeability.

System design is then the constant answer to the question: “How can I make my system as changeable as possible?”. That’s a simpler question, but the answer is no less difficult. Note one more surprising bit about it: we must answer this question differently over time. This means that design is dependent on time and context. Your answer can be right if applied at T0, but wrong if applied at T200.

Guide

Now, if making our system as changeable as possible is our primary act, how do we do it?

First, we’ll need to start off with the maximum level of changeability. Systems that are maximally changeable are as simple as possible. A simple system is the system that solves a problem with the minimum amount of specific concepts, in a way that keeps all these concepts as decoupled as possible.

That implies a few things: we would want to choose the most powerful language we can to solve our problem. This lets us use the most powerful abstractions, which will allow us to keep the number of specific concepts that define our program at a minimum. We would want to use powerful, immutable data structures, which will help us keep our abstractions concise and decoupled. It also means that we would want to use the simplest infrastructure we need to solve our problem. Simpler infrastructure allows us to avoid introducing concepts that aren’t needed to solve our problems. The same applies for the abstractions we choose: we’d want to use the abstractions that best solve for our specific use cases, rather than solve generally for potential future usecases we don’t have.

Note that if you follow these ideas, your initial system may look like a toy. It certainly won’t use kubernetes. Remember that system design is context-dependent, and at this point in time this is the best solution.

Now, we must iterate. At every step of the way, ask: what’s slowing down our productivity? Pick the highest impact issues and start to address them. Privacy getting too hairy? Introduce an abstraction that centralizes the complexity of privacy, and removes it from the realm of product engineering. Site going down too much? Introduce infrastructure for detection and debugging. Once that’s not enough, consider incident management systems.

The common theme here: centralize and push complexity down. You take pieces of complexity that every engineer needs to deal with, and create an interface they can use which abstracts the complexity away. As you do that, you try to make that infrastructure accessible: this means it’s written in a place where every engineer can access, in a language that every engineer can change. That will enable all engineers to use your abstraction, while having the option to dive deeper.

The fact that system design is iterative has two importance consequences.

The first is that you cannot escape technical debt. Because a solution at T0 becomes more and more incorrect as context changes, you are constantly accruing technical debt. Because of this, there can be no perfect system. It’s your job to constantly manage the tradeoff between quality and debt, and this iterative cycle is your sword.

The second is that applying blanket solutions will lead to failure. As you get more technical debt, you will invariably end up with a desire to enforce a new paradigm on the system: microservices being the common one today. Because a paradigm solves multiple general *issues, you invariably introduce some concepts that don’t *specifically solve your issues, and have their own tradeoffs. The solution is again to lean in to the iterative model: apply specific solutions to specific problems*.*

Debt

As you iterate, you’ll constantly run into the struggle between accruing and paying down debt: do you slow down your velocity now to improve future changeability later? The context we work in is so complicated that there can’t be a simple formula here. But, like in most craft, we can lean in rules of thumb.

The first problem comes when you are considering introducing new debt. The key rule to consider here is the nature of the debt. Not all debt are created equal — some have higher interest. Let’s compare two examples to illustrate. The first involves introducing a staging environment, or improving performance. This does not get appreciably harder later. Compare that to knowingly introducing a data model change, that you know you’ll need to migrate later. This involves significantly more incidental work: dual writes, backfills, shadow testing, the whole schebang. Based on the nature of the debt and the importance of your current commitments, you need to balance and make a choice.

The second problem comes when you are considering paying down debt. The key rule to consider here is pain. You already have a sense of the debt that is either causing the biggest slow down, or is about too. It’s difficult to measure your success here, as if you do your job well, no one will even feel the pain. Nevertheless this skill can be learned from your mistakes. First fix what causes the most pain immediately. Then, get better and better at pre-empting the largest amount of pain earlier. That, granted is a lofty goal — I have never worked at a company where there wasn’t at least one glaring way to make things a magnitude better.

Fin

So we come down to the central idea. To keep your hacker’s paradise you need to tame your system complexity elephant. To do that, you need to keep your system as changeable as possible. To do that, you need to start out with a simple system, and evolve it iteratively as you grow. There’s so much more I want to go deeper into, but that will have to wait for another. I hope this gives you a good model to think with.

Thanks to Mark Shlick, Jacky Wang, Daniel Woelfel, Irakli Popkhadze, David Magaltadze, Irakli Safareli, for reviewing drafts of this essay