Read this post in other languages:
Français, 한국어, 简体中文

This is a multipart series on building Fleet, a next-generation IDE by JetBrains.

In previous parts of this series, we looked at an overview of the Fleet architecture and discussed the algorithms and data structures that are used under the hood in the editor. In this part, we’ll start looking at the approach we take to implement state management. This is a complicated topic, so we’ll devote a couple of blog posts to it. For now, we’ll focus on how we represent and store elements of the application state. In the next part, we’ll talk more about transactional mechanisms around state management in Fleet.

Fleet has a lot of moving parts and performs many different operations, including:

• Rendering UI elements and interacting with users.
• Interacting with other services to obtain data and update UI elements.
• Dealing with files such as saving, loading, parsing, and displaying the differences between them.
• Orchestrating back-ends that deal with code insight, completion, and search results.

Many of these are complex operations that can degrade the responsiveness of the interface. Fleet is a distributed application, so it may have several frontends distributed over the network – this complicates things even further. Nevertheless, we have to display all of the information for our users consistently and correctly and guarantee they can work harmoniously between their frontends.

In terms of state management, all of these operations boil down to either reading or updating states. UI elements read states to provide users with the actual data, while users update states by editing their documents and moving things around. There are thousands of such operations taking place every minute. All of this makes proper state management a key element of Fleet.

Our principles

JetBrains has been developing IDEs for more than 20 years. Our experience has led us to the following guiding principles regarding state management in Fleet:

Principle 1: Don’t block anyone

Living in a concurrent world is hard. In Kotlin (and in Fleet) we use lightweight concurrency primitives, called coroutines, to organize our concurrent code. While reading states from many coroutines at the same time creates almost no problems, mutating them can be dangerous. The traditional approach is to acquire a lock for a single writer thread, which causes a long waiting queue to read something. We believe this is inappropriate – it should be acceptable for readers to read a potentially slightly outdated state without any delays. To achieve this behavior, we use a variation on the MVCC (multiversion concurrency control) model to access state elements from coroutines. These coroutines either read some version of the state or mutate the state by providing the new version of it. We read and mutate the state in transactions which are much easier to implement under MVCC.

Principle 2: Be efficiently reactive

States change all the time and the UI should reflect these changes as quickly as possible. If you’ve ever programmed simple animations with your first programming language, you know how to do that: erase everything and redraw it from scratch. Unfortunately, full redrawing takes a lot of time. A better idea is to redraw the part that was changed. To do that, we need a way to determine what exactly has changed. The fewer changes, the better. Once we’ve located the changed part of the state, we need to decide as quickly as possible what depends on that part and execute the corresponding coroutine. We have to be efficient in our reactions to state changes.

Principle 3: Represent data wisely

The first two principles are no more than good declarations without the third one. We have to think hard about the way we store and process our data. Storage with highly efficient lookup and mutate operations is no longer an area exclusive to database system implementers. Fleet, being a distributed IDE, requires all of this too. To fulfill our needs, we had to develop our own internal database solution that would be both flexible and performant enough.

What is a state?

There are three ideas we need to consider when thinking about states in Fleet.

Firstly, it’s represented as a persistent data structure with different versions that model change in time. One way to describe such a world is a linear sequence of epochs that go one after another, known as an epochal time model. All interested parties (yes, coroutines!) always read one of the epochs, but not necessarily the most recent one.

Secondly, our state is a database of entities that contain information about everything you see on your screen and everything we hide under the hood. As with many databases, these entities relate to each other in various ways. 

Thirdly, the state and its mutations boil down to basic triples, called datoms, which are primitive data items that allow us to achieve the efficiency we need. Let’s discuss these ideas in a little more detail.

An epochal time model

For a long time, our programs mutated state. Unfortunately, it’s almost never enough to update just one variable. Usually, we have to change many of them one after another in a consistent way. What if someone observes our state in a half-baked form or even attempts mutating it? Imagine that we’ve increased the string’s length but haven’t provided new content. Our users definitely shouldn’t be able to see that. The idea is to hide inconsistent states behind some façade. Coming from one consistent state to the next takes time. It’s like how an epoch in time follows another.

The epochal time model was first explained to the wider programming community by Rich Hickey in his beautiful talk Are We There Yet (see the transcript), devoted to his ideas on implementing the Clojure programming language. What he talks about is that for some time our programs can live in an immutable, consistent world. Immutability makes many things easier to implement, but it’s impossible to stay in the same world forever. As a result of state writers’ activities, a new immutable, consistent world always follows the previous one.

Fleet’s state is accessible in the form of an immutable snapshot, a collection of all the state elements with guaranteed consistency between them. In this model, updating the state creates a new snapshot. To guarantee consistency as states change, we implement transactions.

Fleet has a component called the Kernel, which is responsible for transitioning snapshots as a consequence of state writers’ activities and providing a reference to the most recent snapshot. Interested parties, both readers and writers, may obtain this reference when they need it, but they can’t be sure that this reference corresponds to the most recent version of the world by the time they use it. The Kernel is also responsible for broadcasting changes to the parties that depend on them. The nice thing is that we don’t need to subscribe manually – it’s enough to read some value to then be notified about its changes in the future.

Writers line up to create new snapshots, but readers are never blocked. However, they can receive slightly outdated information.

The data model for our state

Now we are ready to answer the question, what’s in our state? Well, literally everything: document content with its corresponding file information, all the inferred information about that content, caret positions, plugins loaded and their configuration, views and panels locations, etc. The corresponding data model is described in Fleet via Kotlin interfaces as:

interface DocumentFileEntity : SharedEntity {
 @Unique
 @CascadeDeleteBy
 var document: DocumentEntity

 @Unique
 var fileAddress: FileAddress

 var readCharset: DetectedCharset
 // ...
}

interface DocumentEntity : SharedEntity {
 var text: Text
 var writable: Boolean
 // ...
}

Note: The type Text is in fact a rope which we covered in the previous part of this series.

We use property annotations to describe entity components and the relationships between them. In this example, a document file entity describes the relation between a unique file on a disk drive and a unique document we’ve read from it. The corresponding document entity should be deleted when the document file entity is deleted.

To maintain such a database of entities, we’ve implemented our own database engine, called RhizomeDB. RhizomeDB does not impose any hierarchy upon the entities, hence the name Rhizome, which is a subterranean plant stem that sends out roots and shoots from its nodes.

To access entities as objects which implement properties from interfaces like the examples above, RhizomeDB provides an API. For example, we can get a document based on the given file address as follows:

val document = lookupOne(DocumentFileEntity::fileAddress,
                         fileAddress)?.document

Now the document object implements the DocumentEntity interface and we can use it to access the content of the document loaded in Fleet.

Our entity data model is flexible enough to represent not only data but also the data model itself. Suppose we want to develop a plugin (we’ll discuss Fleet’s plugins later in this series). Loaded plugins form part of Fleet’s state. All plugins share some common data required to integrate seamlessly with the application. However, every plugin has its own state, described with its own data model. This is not a problem for RhizomeDB. We can represent the plugin’s data model with entities. When we load a plugin, we also load its data model as a new entity. As a result, Fleet’s state management system is ready to accept the plugin’s state data.

State as a set of triples

Although our API gives us objects to work with entities, we don’t store them as such. Instead, we represent them in triples: [entity_id, attribute, value]. We call these triples datoms (the term comes from the Datomic database, which we’ve modeled our data structures after). 

Suppose the entity id for some particular file referring to a document is 18, and the entity id for the corresponding document is 19. The data would be stored as triples:

• [18 :type DocumentFile]
• [18 :document 19]
• [18 :fileAddress "~/file.kt"]
• [18 :readCharset "UTF-8"]

Note that properties of interfaces become attributes of triples. There are also various attributes like :type with special meanings. Types of values depend on the types of properties. When referring to other entities, property values are IDs.

The seemingly primitive structure of triples is quite effective when it comes to looking up data. Our engine is able to return very fast answers to queries in the form of a mask: [entity_id?, attribute?, value?], where any component may be either present or missing. The result of a query is always a set of datoms, which satisfies the given mask.

For example, we can ask for all filenames of currently loaded document files:

[? :fileAddress ?]

Or we can look for entity_id, which corresponds to a file with the given name:

[? :fileAddress "~/file.kt"]

For the second query, thanks to the uniqueness constraint, there should be no more than one answer in the resulting set.

To make queries run fast enough, the RhizomeDB maintains four indexes (each implemented as a hash trie):

• Entity | Attribute | Value
• Attribute | Entity | Value
• Value | Attribute | Entity
• Attribute | Value | Entity

The lookup* family of functions from the RhizomeDB API operates on these indexes to find the corresponding triples and build resultant entity objects.

RhizomeDB is heavily inspired by Datomic but adds some new ideas like read-tracking and query reactivity, which work for our use case. These features help us to deal with state changes as we’ll see shortly.

What is the change?

There is almost nothing curious about an immutable state. Interesting things come up when we change something. We’d like to know what was changed in the state and which UI elements need to be updated. To deal with changes we’ve implemented the following three ideas:

• We record what exactly was changed as the novelty of the change.
• We track what readers are querying.
• We determine which queries would give new results because of this change.

Let’s discuss these ideas and see how they work in Fleet.

Novelty values

Remember that we strive to be immutable whenever possible, so we are not allowed to mutate values. Remember also that our state has the form of a snapshot containing a set of triples with entity IDs, attributes, and their values, representing corresponding data entities. Instead of mutating attributes’ values, for any change, we produce a new state snapshot with a new value of an attribute we want to change. A change then is simply removing an old value and adding a new one. To rename a file, for example, we do the following:

- [18 :fileAddress "~/file.kt"]
+ [18 :fileAddress "~/newFile.kt"]

Note that these two operations must be executed inside a transaction. Otherwise, you would observe the state without a filename at all. Running such a transaction gives us a new state snapshot with a new filename.

As such, any change is just a set of removals and additions of datoms. A transaction may result in many such removals and additions for different entities and attributes. Moreover, the difference between two snapshots is also such a set. From the entity IDs and attributes in the changeset, we know precisely which state components have been changed during the transaction. These are called the novelty of the change. Once we’ve executed a transaction, we record these novelty values.

Read-tracking and query reactivity

We know that readers access data in the state via queries. Queries have the form of a mask. It’s easy to track all the masks from a particular function. Once we have this information for all of our functions, we can determine which functions depend on which mask.

After every change, we get its novelty values. If we go over all the masks queried, we see which queries are affected by the change. Thanks to read-tracking, now we know which functions are affected. Consequently, we can invalidate the UI elements that call these functions. This makes the UI reaction highly efficient.

We use read-tracking for more than just updating UI elements. It’s quite a general mechanism that allows for useful patterns in reactive programming. For example, if we have a function that queries state, we can easily turn it into an asynchronous flow. Whenever changes in the state affect the result of such a function, we emit a new element of the flow. We can also safely cache query results without the risk of having outdated cached values. Once the value is updated in the state, we’ll know that immediately.

Summary

In this part of our series on how we build Fleet, we’ve employed an epochal time model via a series of immutable snapshots and built smart data representation in order to maintain our state. Our data exist on two levels: as data entities convenient for developers to work with, and as triples suitable for efficient looking up. When we change something, we record what was changed, determine those who are interested in these particular changes, and cause them to update the corresponding UI elements.

Keeping this background in mind, now we’re ready to discuss the distributed nature of Fleet’s state and transactional mechanisms that allow us to change it in a consistent way. We’ll do just that in the next blog post of this series. Stay tuned!