Fleet | "backstage exploration" issue 3: status management

《Fleet Backstage agent Secret 》 Series of blog posts

️ The third part ️

️ Review the first two issues ️

The first part ——  Architecture Overview

The second part ——  Editor details

In the first of this series One 、 Two In the part , We introduced Fleet The overall architecture of , The algorithm and data structure used in the background of the editor are also discussed .  In this part , We will show you how to implement state management .  This is a complex subject , So we have prepared many blog posts .  The point of this article is Representation and storage of application state elements ,  The next section will explore Fleet Transaction mechanism around state management in .

Fleet There are many moving parts , It also performs many different operations , Include ：

• present UI Element and interact with users .

• Interact with other services to get data and updates UI Elements .

• Processing documents , For example, save 、 load 、 Parse the file and show its differences .

• Choreography deals with code insight 、 Back end of completion and search results .

Many operations are complex , It may reduce the responsiveness of the interface .  meanwhile , because Fleet It's a distributed application , There may be multiple front ends distributed across the network , Make the whole process more complicated .  For all that , We still have to keep displaying all the information correctly for users , Ensure that users can work steadily between the front ends .

In terms of state management , Operations are divided into read status and update status .UI The element provides the actual data to the user after reading the state , Users update status by editing documents and moving content . There are thousands of such operations per minute ,  It also makes correct state management Fleet The key elements of .

Our principles

JetBrains stay IDE The development has 20 Years of history .  We draw the following conclusions based on experience Fleet The guiding principles of state management ：

principle 1： Don't block anyone

In a concurrent environment, you need to pay more attention .  stay Kotlin（ and Fleet） in , We use lightweight concurrency primitives called coroutines to organize concurrent code .  Although reading state from multiple collaborators at the same time hardly causes any problems , But changing them can be dangerous .  The traditional approach is to acquire a lock for a single writer thread , This can lead to long waiting queues for reading certain content .  We don't think this is appropriate , The reader should be able to read states that may be slightly out of date without delay .  In order to achieve this behavior , We use  MVCC（ Multi version concurrency control ） Model ¹ A variant of C .  These collaborators either read the status of a version , Or change the status by providing a new version of the status .  stay MVCC Next , It is easier to read state and change state in a transaction .

principle 2： React efficiently

The state is always changing ,UI These changes should be reflected immediately .  As long as you have written animation in your first programming language , Just know how to do it ： Erase everything , Redraw from scratch .  However , Complete redrawing takes a lot of time .  It is better to redraw the changed parts .  So , We need to be able to determine what has changed .  The less change the better .  Find the part with changed state , It is necessary to decide what depends on this part as soon as possible and execute the corresponding collaborative program .  We must respond efficiently to changes in state .

principle 3： Show the data wisely

If there is no third principle , The first two principles are just nice statements .  We must seriously think about how we store and process data .  Storage with efficient discovery and change operations is no longer the exclusive domain of database system implementers .Fleet As distributed IDE Also need these .  In order to meet the needs , We must develop our own internal database solutions that are both flexible and efficient .

What is state ？

about Fleet The state of , We need to consider three ideas .

First , It is expressed as Persistent data structures ², With different versions , The model changes over time .  One way to describe it is a linear periodic sequence one after another , namely Cycle time model ³.  All interested parties （ Collaborative process ！） Will read one of the cycles , But not necessarily the latest cycle .

secondly , Our state is an entity database , Contains information about everything on the screen and in the background .  Like many databases , These entities are related to each other in various ways .

Third , The state and its changes are grouped into basic triples , namely datom. They are metadata entries , Enables us to achieve the efficiency we need .  Next , We will discuss these ideas in detail .

Cycle time model

For a long time , Our programs change state .  However , Just updating a variable is almost never enough .  Usually , We have to make a lot of changes consistently one by one .  If someone observes our immaturity , Even trying to change it , What should I do ？  Suppose we increase the length of the string , But there is no new content .  Users should never see this .  At this time , Inconsistencies should be hidden behind some masking .  It takes some time from one consistent state to the next .  It's like one cycle following another .

Rich Hickey In his wonderful speech  Are We There Yet⁴ （ View the voice script ⁵） The cycle time model was first explained to the wider programming community in , Shows him about implementing Clojure The idea of programming languages .  He said , Over a period of time , Our programs can exist in an immutable, consistent world .  Immutability makes many things easier to achieve , But nothing can stay in the same world forever .  Due to the activity of the status writer , A new immutable consensus world always follows the previous world .

Fleet The state of can be accessed in the form of immutable snapshots , A snapshot is a collection of all state elements and the consistency between state elements is guaranteed .  In this model , Updating the status will create a new snapshot .  In order to ensure the consistency of state changes , We implemented the transaction .

Fleet There is one called kernel (kernel) The components of , It is responsible for converting snapshots according to the activity of the state writer and providing a reference to the latest snapshot .  Interested parties , Whether it's a reader or a writer , You can get this reference when you need it , However, it is not possible to determine whether this reference corresponds to the latest version of the world when used .  The kernel is also responsible for broadcasting changes to those who depend on them .  Fortunately, we don't need to subscribe manually , Just read some values , Then it is enough to be notified of the changes in the future .

Writers queue to create new snapshots , But the reader will never be blocked .  However , They may receive slightly outdated information .

Data model of our state

Now we will answer this question ： What is in our state ？  It contains everything ： Document contents and corresponding file information 、 All inferred information about this content 、 Text cursor position 、 Loaded plug-ins and their configurations 、 View and panel position, etc .  The corresponding data model is in Fleet Pass through Kotlin The interface is described 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
 // ...
}

Be careful ：Text The type is actually this series In the previous section To introduce the rope .

We use attribute annotations to describe entity components and their relationships .  In this example , The document file entity describes the relationship between the unique file on the disk drive and the unique document we read from .  When the document file entity is deleted , The corresponding document entity should be deleted .

To maintain such an entity database , We have implemented our own database engine  RhizomeDB.RhizomeDB No hierarchy is imposed on entities , So it's called Rhizome, This is an underground plant stem , Send out roots and buds from nodes .

To access entities as objects that implement attributes from interfaces , As shown in the example above ,RhizomeDB Provides a API.  for example , We can get a document according to the given file address , As shown below ：

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

The document object has been implemented DocumentEntity Interface , We can use it to access Fleet Contents of the document loaded in .

Our entity data model is quite flexible , Not just data , It also represents the data model itself .  Suppose we want to develop plug-ins （ We will discuss... Later in this series Fleet Plug in for ）.  The loaded plug-ins consist of Fleet Part of the state .  All plug-ins share some common data needed for seamless integration with Applications .  However , Each plug-in has its own state , Describe with its own data model .  This is right RhizomeDB It's not a problem .  We can represent the data model of the plug-in through entities .  When loading plug-ins , We also load its data model as a new entity .  And then ,Fleet The status management system of can accept the status data of the plug-in .

The state is a set of triples

Even though API Provides us with an object that handles entities , But we didn't store it .  contrary , We use triples to represent them ：[entity_id, attribute, value].  We call these triples  datom（ Terminology derived from  Datomic⁶ database , On this basis, we model the data structure ）. 

Suppose an entity that references a particular file in a document  ID  by 18, The entity of the corresponding document  ID  by 19.  The data will be stored as triples ：

• [18 :type DocumentFile]

• [18 :document 19]

• [18 :fileAddress "~/file.kt"]

• [18 :readCharset "UTF-8"]

Be careful , The properties of the interface will become the characteristics of triples . There are many other features , For example, with special meaning :type.  The type of value depends on the type of attribute .  When referring to other entities , The property value is  ID.

When looking for data , The seemingly primitive structure of triples is very effective .  Our engine can quickly return the answer to the query in the form of a mask ：[entity_id?, attribute?, value?], Any of these components may be present or missing .  The result of a query is always a set of that can satisfy a given mask datom.

for example , We can query all the file names of the currently loaded document file ：

[? :fileAddress ?]

perhaps , lookup entity_id, It corresponds to a file with a given name ：

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

On the second query , Because of the uniqueness constraint , There should not be more than one answer in the result set .

To make the query fast enough ,RhizomeDB Maintain four indexes （ Each is implemented as Hash tree ⁷）：

• Entity | characteristic | value

• characteristic | Entity | value

• value | characteristic | Entity

• characteristic | value | Entity

RhizomeDB API Medium lookup* A series of functions operate on these indexes , Find the corresponding triples and build the resulting entity object .

RhizomeDB Yes Datomic The great impact of , But it also adds new ideas , Such as read tracking and query responsiveness , For our use cases .  These functions help to handle state changes .

What is change ？

Immutable states are hardly new .  Only when we change something , Things will be interesting .  We want to know what has changed in the state and what UI Element needs to be updated .  In response to change , We realized the following three ideas ：

• We record the exact change as the novelty of the change .

• We track the contents of reader queries .

• We determine which queries will produce new results as a result of this change .

Let's discuss these ideas further , Look at them in Fleet How Chinese works .

Novel point value

please remember , We try to be immutable , Therefore, we cannot change the value .  in addition , Our state is in snapshot form , Contains a set of entities ID、 Triples of attributes and their values , Represents the corresponding data entity .  For any change , Neither of us will change the value of the property , Instead, a new state snapshot is generated , Include the new value of the property we want to change .  then , The change is simply to remove the old value and add a new value .  for example , To rename a file , We do the following ：

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

Be careful , These two operations must be performed inside the transaction .  otherwise , You will observe a state where there is no file name at all .  Running such a transaction results in a new state snapshot with a new file name .

therefore , Any change is just datom A set of remove and add .  Transactions can result in many such removals and additions for different entities and attributes .  in addition , The difference between two snapshots is also a group of removal and addition .  Entities from the changeset ID And characteristics , We can know exactly which state components have changed during a transaction .  These are called novel points of change .  After the execution of the transaction , We will record these novel point values .

Read trace and query reactivity

We know , The reader accesses the data in the state by querying .  The query has the form of a mask .  For specific functions , All masks can be tracked .  After getting this information for all the functions , We can then determine which functions depend on which mask .

After every change , We all get their novelty point value .  Check the mask of all queries , You can see which queries are affected by the changes .  Benefit from read trace , We can know which functions are affected .  therefore , We can make the call to these functions UI Invalid element .  This will enable UI The reaction is very efficient .

We don't just use the read trace for updates UI Elements .  This is a very general mechanism , It can be used in reactive programming .  for example , If there is a function to query the status , We can easily turn it into Asynchronous flow ⁸.  Whenever a change in state affects the result of such a function , We will emit new elements of the stream .  We can also safely cache query results , There is no risk of cache value obsolescence .  After the value in the status is updated , We will know immediately .

summary

stay Fleet In this part of the build Methods series , We run a cycle time model through a series of immutable snapshots , And built intelligent data representation to maintain our state .  Our data exist on two levels ： As a data entity for developers to use , And triples for efficient lookup .  When making changes , We will record the changes , Identify interested parties for these specific changes , And make it update accordingly UI Elements .

Based on this background , We will then discuss Fleet The distributed nature of state , And transaction mechanisms that allow us to make changes consistently .  Look forward to the next blog post in this series .  Stay tuned ！

Reference link ：

1. MVCC（ Multi version concurrency control ） Model ：

   https://en.wikipedia.org/wiki/Multiversion_concurrency_control

2. Persistent data structures ：

   https://en.wikipedia.org/wiki/Persistent_data_structure
   

3. Cycle time model ：

   https://donnywinston.com/posts/the-materials-paradigm-and-epochal-time/
   

4. Are We There Yet：

   https://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey/

5. Speech manuscript ：

   https://github.com/matthiasn/talk-transcripts/blob/9f33e07ac392106bccc6206d5d69efe3380c306a/Hickey_Rich/AreWeThereYet.md
   

6. Datomic：

   https://docs.datomic.com/cloud/whatis/data-model.html
   

7. Hash tree ：

   https://en.wikipedia.org/wiki/Hash_trie
   

8. Asynchronous flow ：

   https://kotlinlang.org/docs/flow.html
   

The original author of this blog in English ：Vitaly Bragilevsky

  About Fleet What's new  

Fleet Is in the closed preview stage , At present, the trial application channel has been closed , Please pay attention to JetBrains China's official social media get the latest progress for the first time .

• If you are not registered for closed preview , You can scan the code to subscribe Fleet Journalism , To ensure that you are notified when you publicly preview the launch »»»
  

• If you submit a request for closed preview , You may receive an invitation , It depends on how fast we process the feedback .

stamp 「 Read the original 」 Learn more about

This article is from WeChat official account. - JetBrains（JetBrainsChina）.
If there is any infringement , Please contact the [email protected] Delete .
Participation of this paper “OSC Source creation plan ”, You are welcome to join us , share .