Indexes Indexes Indexes
</span></code></pre>
At this point, we have everything we need to build a shard: a collection to list all the documents in the shard and an index for each type. A simple implementation of that shard would look like this.</p>
// an abstraction to be able to map the indexes
</span>enum </span>AnyIndex </span>{
</span> Boolean</span>(</span>BooleanIndex</span>),
</span> Integer</span>(</span>IntegerIndex</span>),
</span> Tag</span>(</span>TagIndex</span>),
</span> Text</span>(</span>TextIndex</span>),
</span>}
</span>
</span>struct </span>Shard </span>{
</span> collection</span>:</span> Collection,
</span> indexes</span>: </span>HashMap</span><</span>Kind, AnyIndex</span>></span>,
</span>}
</span></code></pre>
But this is a single shard representation, we might have several and need to have a representation for all of them.</p>
struct </span>Manager </span>{
</span> shards</span>: </span>BTreeMap</span><</span>u64</span>, Shard</span>></span>,
</span>}
</span></code></pre>
With this representation, the u64</code> in the BTreeMap</code> will represent the minimum in the range of partition handled by that shard. When initialized, the first shard key will be 0</code>.</p>
But the two previous representations are actually wrong: this would mean that we'll load in memory the entire search engine, which doesn't scale. Instead, the Shard</code> structure will only contain the filenames of the collection and indexes, which will be loaded in memory only when needed, and written to disk when they are not needed anymore.</p>
The Manager</code> structure can then be renamed to Manifest</code> and will be, as well, persisting on disk, representing the state of the search engine at a given point in time.</p>
struct </span>Manifest </span>{
</span> shards</span>: </span>BTreeMap</span><</span>u64</span>, Shard</span>></span>,
</span>}
</span>
</span>struct </span>Shard </span>{
</span> collection</span>:</span> Filename,
</span> indexes</span>: </span>HashMap</span><</span>Kind, Filename</span>></span>,
</span>}
</span></code></pre>
This manifest will be stored in the working directory as manifest.bin</code> and every file (collections and indexes) will have a random name.</p>
Sharding architecture highlights:</p>
- Manifest-based shard management</li>
- File-based storage with lazy loading</li>
- Transaction support for concurrent operations</li>
- Dynamic shard splitting based on size</li>
- Recovery mechanism for incomplete transactions</li>
</ul>
Transaction Mechanism</h4>
This level of abstraction for the manifest allows us to add or delete shards when needed but there's an issue: we cannot block the access to the search engine each time we insert a document. We should be able to insert a set of documents while using the index and just block its access when writing the updated manifest to disk.</p>
Following a similar mechanism to a transactional database, inserting data will require initializing a transaction, which will create a temporary manifest file which will contain the names of all the original indexes and the names of the indexes that have been updated. Updating a collection or an index will create a new file on disk but non updated indexes will remain the same.</p>
Original State Transaction Committed State
</span> +--------------+ +--------------+ +--------------+
</span> | manifest.bin | | manifest.tx | | manifest.bin |
</span> +--------------+ +--------------+ +--------------+
</span> | idx1.bin | | idx1.bin | | idx1.bin |
</span> | idx2.bin | --> | idx2_new.bin | --> | idx2_new.bin |
</span> | idx3.bin | | idx3.bin | | idx3.bin |
</span> +--------------+ +--------------+ +--------------+
</span></code></pre>
This would give us this code for shard management</p>
/// represents a file during a transaction
</span>struct </span>TxFile </span>{
</span> </span>/// original file path, if it exists
</span> </span>// a shard can not have any boolean index but it can be created after an update
</span> base</span>: </span>Option</span><</span>Filename</span>></span>,
</span> </span>/// new file path after changes, if modified
</span> </span>// the filename once the transaction is committed
</span> next</span>: </span>Option</span><</span>Filename</span>></span>,
</span>}
</span>
</span>/// represents a shard during a transaction
</span>struct </span>TxShard </span>{
</span> </span>/// collection file state
</span> collection</span>:</span> TxFile,
</span> </span>/// index files state for each kind
</span> indexes</span>: </span>HashMap</span><</span>Kind, TxFile</span>></span>,
</span>}
</span>
</span>/// manages the state of all shards during a transaction
</span>struct </span>TxManifest </span>{
</span> </span>/// maps shard keys to their transaction state
</span> </span>/// uses BTreeMap to maintain order for efficient splits
</span> shards</span>: </span>BTreeMap</span><</span>u64</span>, TxShard</span>></span>,
</span>}
</span></code></pre>
This transaction manifest would be written to the filesystem depending on the platform: in the browser, since we cannot know when the page will be closed, it's better to write it after each operation, while on mobile, the app can do a simple operation before closing. This provides a nice way of being able to recover a transaction that has not been committed.</p>
That commit operation simply consists in, for each file of each shard, taking the next</code> filename if exists or the base</code> one, and write it in the manifest.bin</code>. This commit operation is atomic, and then less prone to errors.</p>
Sharding, Or Not Sharding</h4>
Before talking about how to shard, we should talk about when we should decide to shard.</p>
Considering I've decided to leave the limit configurable depending on the size of the files, we have to be able to determine the size of a index file, once serialized and encrypted. Considering the time needed to serialize and encrypt is CPU bound (and after some experiments), writing the encrypted file to disk in order to determine its size brings too much overhead and kills the performance.</p>
The second option I came up with was to compute the size of the index each time it gets updated. It's quite time consuming and uses a brute-force approach, but it's still minimal compared to the time needed to serialize and encrypt it. And we'll be able to improve this performance later, there's an entire section dedicated for that.</p>
Considering the redundancy in the structure of the indexes, we can make something smart that won't require too much repeat. Let's implement a ContentSize</code> that evaluates the size of the structure.</p>
/// provides size estimation for optimizing shard splits
</span>trait </span>ContentSize </span>{
</span> </span>/// returns estimated size in bytes when serialized
</span> </span>fn </span>estimate_size</span>(&</span>self</span>) -> </span>usize</span>;
</span>}
</span>
</span>// for constant value sizes
</span>macro_rules! </span>const_size </span>{
</span> </span>(</span>$name</span>:</span>ident</span>) => {
</span> </span>impl </span>ContentSize </span>for </span>$name </span>{
</span> </span>fn </span>estimate_size</span>(&</span>self</span>) -> </span>usize </span>{
</span> std</span>::</span>mem</span>::</span>size_of</span>::<</span>$name</span>>()
</span> </span>}
</span> </span>}
</span>
