<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Evgeniy Zuykin on Medium]]></title>
        <description><![CDATA[Stories by Evgeniy Zuykin on Medium]]></description>
        <link>https://medium.com/@eugenzuy?source=rss-3a7109501dd6------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*SHDbam2KfJbCSPcYEgvJxg.jpeg</url>
            <title>Stories by Evgeniy Zuykin on Medium</title>
            <link>https://medium.com/@eugenzuy?source=rss-3a7109501dd6------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 09:57:38 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@eugenzuy/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Counting words - distributed Scatter/Gather case study]]></title>
            <link>https://medium.com/@eugenzuy/counting-words-distributed-scatter-gather-case-study-8512ab36429d?source=rss-3a7109501dd6------2</link>
            <guid isPermaLink="false">https://medium.com/p/8512ab36429d</guid>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[mapreduce]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Evgeniy Zuykin]]></dc:creator>
            <pubDate>Tue, 27 Aug 2024 13:26:10 GMT</pubDate>
            <atom:updated>2024-08-28T04:35:26.393Z</atom:updated>
            <content:encoded><![CDATA[<p>Imagine an API, counting words in a selected text file on a local file system. Simple, right? Just open the file, read it, and count all the separate words found. What if the file size is several GB? Also simple — just spawn multiple threads and read from multiple positions in the file. But what if the file itself cannot be stored in a single instance VM, or if you want to analyze thousands of different files sitting in an object store? In this case, it would require distributing the workload across multiple instances. This process is called scatter-gather or map-reduce. In this blog, I will cover some possible approaches in detail.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vjjj4v0cY0AgCA2fth1GGA.png" /></figure><p>Before we begin, let’s specify the environment and requirements we have.</p><h4><strong>Constraints</strong></h4><ul><li>We store text files in the object store, let’s say S3.</li><li>Each file has metadata, such as the time it was created, an author, and a name.</li><li>Files’ metadata is stored separately in some database, let’s say PostgreSQL.</li><li>The total number of files is reasonable, so it is totally possible to cache all files’ metadata in the memory of the process.</li><li>The same files are often queried with different queries.</li><li>New files are appearing in the object store at a relatively low rate.</li></ul><h4>Requirements</h4><p>We need to count all words in files matching the query:</p><ul><li>Match files created in a time range.</li><li>From a specific author or many.</li><li>With a specific name or many.</li><li><em>Count only words matching a provided regular expression.</em></li></ul><p>The query must be executed within 10 seconds.</p><p>To start simple, we can have a single instance connected to both a metadata store and an object store.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*PcsUuZwyGmLuvw11" /></figure><p>This approach is great in terms of simplicity but will crumble under a bigger load since it is just a single instance. In that case, let us put our application behind a load balancer (for example, Nginx) and spawn many instances.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*XLblczvtgF42F-1Q" /></figure><p>Although now our system can scale and process more requests, all of them are still processed by a single instance. It means queries requiring to iterate over hundreds of files will most likely just timeout since the computational power of a single server is limited. Thus, we need to split some queries across multiple servers.</p><p>To split requests, we need to have an additional entity in front of our instances, which will distribute queries between them. To avoid confusion, let us call it the <strong><em>coordinator</em></strong> and the instances we had before the <strong><em>workers</em></strong>. Now our schema will look something like this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*LJPCyLV997K9J37f" /></figure><p>So how would we distribute the workload? We need to split the request evenly across multiple servers, with some threshold — for example, if 9 files are to be processed, we could separate the request into 3 requests, each having 3 files to process.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/0*bYkV50-dah_WGJC_" /></figure><p>Aggregation part of the process here is very simple — every worker returns the number of words in the files it was given to calculate, and the coordinator just <strong>summarizes all workers’ results</strong>. But from the request, we do not know exactly which files we need to process since we receive only file filters. So what we could do is always distribute our queries to multiple servers, additionally passing the name of the instance and all instances we distributed the request to.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*k3Fun59XvMiViuJL" /></figure><p>Now we can formalize how workers will process the query:</p><ul><li>Fetch all file metadata from metadata storage.</li><li>Filter out only the ones matching the query.</li><li>To decide whether the worker needs to process the file or not, calculate the hash of the file name and apply modulo by the number of allWorkers.</li><li>Check if the position of currentWorker in the allWorkers array matches the position selected in the previous step.</li><li>If the position matches, process the file; otherwise, skip it.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*BQc0XebLQKFRMV76" /></figure><p>It is important to mention the quality of the hash function used will decide how good the work distribution will be in the end. For example, to have one of the least possible number of hash collisions, <a href="https://xxhash.com/">xxHash</a> can be used.</p><p>Now, in theory, we can process queries containing thousands of files, but how can we improve it further?</p><p>Currently, before a worker can start counting words in a requested file, it needs to fetch it from the blob storage. To eliminate the need to download the same file twice, we need to add a local file <strong>cache to the worker</strong>. Additionally, we now want to <strong>send</strong><em> </em><strong>queries for the same file to the same workers</strong>. To achieve this in the current architecture, we need to always send all requests <strong>to all nodes</strong>. On top of it, since we use hash modulo for instance selection, every time some worker instances go up or down (which happens regularly in large clusters), we will notice full file redistribution between workers. This will cause a drastic surge in network usage and a consequent spike in response P99 while it happens.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/999/0*ocJ9FStSfO50bKzt" /><figcaption>Almost all files were moved upon addition of a new worker</figcaption></figure><p>To improve the file redistribution ratio we must use a different algorithm rather than hash modulo. The industry standards are <a href="https://en.wikipedia.org/wiki/Consistent_hashing">consistent hashing</a> and <a href="https://en.wikipedia.org/wiki/Rendezvous_hashing">rendezvous hashing</a>. The consistent hashing is preferred if you have a large number of worker nodes and a very high traffic volume since the instance selection is fast due to utilization of the hashring. On the other hand rendezvous hashing is preferred then better query distribution is preferred — it calculates the hash for each instance, sorts them and picks the highest. In our cases we will apply a <strong>rendezvous hashing approach </strong>because we want to have the most even file distribution across workers. Also with the rendezvous hashing we can pick instances for retries always in a specific order, so we could have our cache populated even on “backup” instances, maintaining the data distribution evenness.</p><p>Now we handled cache redistribution during the worker count change, but we still have more things to improve! Currently we distribute the query to all workers, which is quite wasteful because:</p><ul><li>Success of each request depends on the success of all nodes in the cluster</li><li>There can be small queries required just a few files to be read</li><li>Because of retries some instances will need to be queried twice for the same query</li></ul><p>To address these let us move the determination of files to be read for each request into the <strong>coordinator</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*kMwdBM9Xz7cWoWn-" /></figure><p>Now the coordinator will decide:</p><ul><li>How many workers must handle the request</li><li>Which workers exactly must handle it</li><li>Which workers will be used for query retries</li></ul><p>The task of processing a single large file, for example, several TBs, on a single worker within a low time limit will most likely fail as well, meaning we need to split this task further. For this, the coordinator can have a file size threshold for a single worker. Let us say if the file size is less than 500MB, it will be processed by a single worker; if it is 1GB, there will be two tasks for two workers. For this, we will include <strong>offset and length</strong> into the worker task alongside the file name — each worker will start the file processing from the <strong>offset</strong> and will limit the processed file volume by the specified <strong>length</strong>. S3 also supports offset and length, so we would not need to download the full file. Now we can easily process large files as well. It is <strong>also important to include offset and length into the hash calculation,</strong> otherwise huge files will be <strong>still processed by a single worker</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*pTTRnLNO5w3_XC5n" /></figure><p>Now our distributed query will look like this</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/0*zN0i28hbb1wUWzkv" /></figure><p>Another issue will arise when a lot of files that were never queried before are queried at once — the network might become a bottleneck and the cluster may fail to download the data before the timeout. One possible way to mitigate this is to have a way to let workers know which files they need to proactively download upon later appearance in S3 and before they are actually queried. This will help to distribute the network load. Unfortunately, this approach still has its weak sides:</p><ul><li>Ultimately, such an approach will make the total workers’ local cache size equal to the total size of the blob store. To mitigate this, we could define hot and cold data. Every file created earlier than a week ago would always be cached on workers, while cold files would be cached only after a query. This will help us to balance between response latency and the total cache size.</li><li>The addition of a new worker will result in the download of significant amounts of data, resulting in high network utilization. This can be mitigated by adding network throttling for cache population. Additionally, thanks to rendezvous hashing, we can select multiple workers “owning” the file, so we would not suffer too much from instance addition/removal.</li></ul><p>To optimize the system further, we can:</p><ul><li>Store the files words count in the metadata during the original file upload, so basic queries (without word pattern) could be executed by coordinator itself without calling workers</li><li>If there are any specific word patterns which will be called on a regular basis, it worths adding a precomputation for those as well</li><li>Add additional result cache (Memcached, Redis or something else), to not execute same queries on the same files multiple times</li><li>Finally, given that word counting is our system’s only purpose, we could de-duplicate words and store only unique words, dramatically reducing the size. On top of it we could build a reverse index, to know exactly if a specific file contains provided word patterns to not process files not containing any results</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Dhw4e6_zQFqauNQt" /></figure><h3>Summary</h3><ul><li>Separate workers and coordinators</li><li>Let coordinators decide the file list for workers to process</li><li>Cache files from the blob storage on workers</li><li>Use rendezvous hashing to avoid overloaded workers</li><li>Use good hash function for even better work distribution</li><li>Pre-download new files</li><li>Precompute common queries</li><li>Cache query results</li></ul><p>Thank you for reading and have a great day!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8512ab36429d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Grafana & GitLab — happier developers]]></title>
            <link>https://medium.com/agoda-engineering/grafana-gitlab-happier-developers-c19d686a31a0?source=rss-3a7109501dd6------2</link>
            <guid isPermaLink="false">https://medium.com/p/c19d686a31a0</guid>
            <category><![CDATA[gitlab]]></category>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[grafana]]></category>
            <category><![CDATA[grafana-loki]]></category>
            <category><![CDATA[technology]]></category>
            <dc:creator><![CDATA[Evgeniy Zuykin]]></dc:creator>
            <pubDate>Tue, 26 Dec 2023 04:01:41 GMT</pubDate>
            <atom:updated>2023-12-26T04:01:41.530Z</atom:updated>
            <content:encoded><![CDATA[<h3>Grafana &amp; GitLab — happier developers</h3><h4>Or how to achieve 90% of results with 10% of efforts</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7pbFJIQ3JhtvMrjGYb6-gQ.jpeg" /></figure><p>At Agoda, we utilize Grafana and the Grafana Loki plugins to streamline log access. This dynamic duo provides a flexible and straightforward way to explore and analyze logs, empowering our teams to troubleshoot and manage system data efficiently.</p><p>Our log storage follows a structured format, combining the core message with stack traces (for errors or warnings) and additional attributes. This approach provides a comprehensive view of each log entry, ensuring our logs carry rich contextual information. With messages, stack traces, and attributes seamlessly integrated, we’ve created a detailed and informative logging system that facilitates quick identification and resolution of issues.</p><p>Inspired by a convenient feature in my beloved IntelliJ Idea that allowed me to click on a line in a stack trace and navigate directly to the corresponding code, I questioned why a similar experience couldn’t be seamlessly integrated into Grafana for any project.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*N_hZwBW_acz30-y5" /><figcaption>The picture is taken from <a href="https://www.jetbrains.com/help/idea/analyzing-external-stacktraces.html">here</a></figcaption></figure><p>This simple yet powerful functionality can significantly enhance our debugging process, enabling users to swiftly trace the origin of issues from logs in Grafana directly to their precise locations in the codebase. Such a feature would be particularly valuable for platform and horizontal teams dealing with substantial amounts of code, often with multiple owners, streamlining their daily workflow and collaborative efforts.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*7NY79YaXREGPzqFQ" /><figcaption>Original view of stack trace in Grafana</figcaption></figure><p>Thus, we can formalize a functional requirement as follows — <strong>As a developer, I need to have a way to navigate directly to the source code for a specific line mentioned in a stack trace in any project, irrespective of the number of dependencies it has</strong>.<strong> </strong>We can make this happen since we operate our own Grafana instance.</p><h4>JVM Stack Traces</h4><p>Parsing stack traces accurately for every programming language would require a significant amount of time to implement. However, let’s explore the possibility of making compromises and limiting the functionality to a subset of languages. To achieve this, we can introduce several constraints:</p><ul><li>We will narrow our focus exclusively to JVM stack traces, given that the vast majority of services at Agoda are written in Scala and Kotlin.</li><li>We will prioritize only the code authored by Agoda developers, as, in 99% of cases, these are the lines that people are most interested in.</li><li>We will simplify the parsing of JVM stack traces as much as possible.</li></ul><h4>Implementation in Grafana</h4><p>To implement this feature in Grafana, we need to make changes to both the backend and frontend components. On the backend, the following steps are required:</p><ul><li>Identify whether a log contains a Java stack trace.</li><li>Parse the identified stack trace.</li><li>For each relevant stack trace, determine its location in GitLab.</li><li>Transmit the results to the front end.</li></ul><p>On the front end, our task is to utilize the information obtained from the backend and incorporate it into the visualization by adding clickable links.</p><p>Due to its versatility, Grafana employs <a href="https://grafana.com/developers/plugin-tools/introduction/data-frames">data frames</a> as a fundamental entity for communication between components. A data frame comprises fields; each data source typically utilizes a constant set of fields. Each field is characterized by a name and a type, and we will leverage these attributes to identify the new column we intend to add.</p><p>For each log message, our new field will include a map associating source file names with links in GitLab. Consequently, the visualization process becomes straightforward. If we have link information for a specific log message, we split it into lines. Lastly, we add links to every log line that corresponds to a file in the map. Here is an example of additional field, sent by the backend:</p><pre>{<br>    &quot;File1.scala:52&quot;: &quot;http://gitlab/team/project/-/blob/branch/filepath/File1.scala#L52&quot;,<br>    &quot;File1.scala:60&quot;: &quot;http://gitlab/team/project/-/blob/branch/filepath/File1.scala#L60&quot;,<br>    &quot;File1.scala:127&quot;: &quot;http://gitlab/team/project/-/blob/branch/filepath/File1.scala#L127&quot;,<br>    &quot;File2.scala:34&quot;: &quot;http://gitlab/team/project/-/blob/branch/filepath/File2.scala#L141&quot;,<br>}</pre><h4>Understanding JVM Stack Traces</h4><p>Before determining whether a string contains a JVM stack trace, it’s important to understand their structure. A typical stack trace would look like this:</p><pre>Exception in thread &quot;main&quot; java.lang.NullPointerException<br>   at com.example.myproject.Book.getTitle(Book.java:16)<br>   at com.example.myproject.Author.getBookTitles(Author.java:25)<br>   at com.example.myproject.Bootstrap.main(Bootstrap.java:14)</pre><p>Additionally, according to <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/StackTraceElement.html#toString()">java doc</a>, stack trace lines may contain some more information:</p><pre>    at com.foo.loader/foo@9.0/com.foo.Main.run(Main.java:101)</pre><blockquote>The first element, “com.foo.loader” is the name of the class loader. The second element “foo@9.0” is the module name and version. The third element is the method containing the execution point; “com.foo.Main”” is the fully-qualified class name, and “run” is the name of the method. “Main.java” is the source file name, and “101” is the line number.</blockquote><p>To filter only stack traces according to our constraints, we can check if a line starts with “at” and contains “com.agoda” as a primary package name within Agoda. Following this, we can apply a simple regular expression to validate that the line filtered in the previous step is indeed a Java stack trace. Initially, the regular expression served as only a filtering step, but given the significant volume of logs fetched, it evolved into a bottleneck.</p><p>Following this logic, we can simply parse filtered lines into the package, file name, and log line where it happened, keeping in mind that the logline is optional. Unfortunately, languages like Scala make parsing logic more complicated, bringing additional symbols like $ and @.</p><pre>at map @ sttp.client.impl.monix.TaskMonadAsyncError$$anon$1.run(TaskMonadAsyncError.scala:26)</pre><p>To manage this syntax, we split stack trace lines by spaces, focusing only on the last parts. Additionally, to mitigate concerns about anonymous classes, we can extract everything before the first “$” symbol and operate with that information.</p><p>Once the parsing is complete, we obtain a structured set of information including filepath, filename, and log line. With this information, we can seamlessly leverage GitLab to retrieve the corresponding source code links.</p><pre>type parsedFile struct {<br>    Path string<br>    FileName string<br>    Line uint32<br>}</pre><h4>Leveraging GitLab’s API</h4><p>Our source code is stored in GitLab. Thus, we will utilize the <a href="https://docs.gitlab.com/ee/api/search.html">search API</a> with blob scope to retrieve information regarding the code location from GitLab.</p><pre>GET https://gitlab/api/v4/search?scope=blobs&amp;search=filename:DB.scala&amp;sort=asc<br><br>Response:<br>[<br>    {<br>       &quot;path&quot;: &quot;sql/src/main/scala/com/agoda/sql/DB.scala&quot;,<br>       &quot;ref&quot;: &quot;aa6286ba8f1d3aae30f07b5ed9fa2c59d89ff595&quot;,<br>       &quot;project_id&quot;: 30932<br>    },<br>    {<br>       &quot;path&quot;: &quot;sql/src/main/scala/com/agoda/sql/DB.scala&quot;,<br>       &quot;ref&quot;: &quot;ca8329434329ccfabd0fe3589ae901df246e5b3b&quot;,<br>       &quot;project_id&quot;: 24643<br>    },<br>    …<br>]</pre><p>Response from GitLab contains a list of search results, including file path, commit hash, and project_id. Now, we need to fetch associated projects. Nothing fancy, just another GET call:</p><pre>GET http://gitlab/api/v4/projects/12345<br><br>Response<br>{<br>    &quot;id&quot;: 12345,<br>    &quot;description&quot;: &quot;Simple project&quot;,<br>    &quot;name&quot;: &quot;Project&quot;,<br>    &quot;path_with_namespace&quot;: &quot;Team/project&quot;,<br>    &quot;created_at&quot;: &quot;2023–01–01T00:00:01.000Z&quot;,<br>    &quot;default_branch&quot;: &quot;master&quot;,<br>    &quot;forks_count&quot;: 0,<br>    …<br>}</pre><p>Using this information, we can build a link to the file in GitLab by simply concatenating the project path, search result commit, and file path.</p><pre>GitlabURL + project.PathAndNamespace, &quot;-/blob/&quot;, searchResult.Commit, searchResult.Path</pre><p>While our integration is already operational, it is not flawless, primarily due to the substantial number of HTTP calls made to GitLab. Additionally, GitLab returns a considerable number of results, which means we need some heuristics to identify the best match.</p><p>To reduce the GitLab workload, we can first parse all stack trace log lines and <strong>query GitLab for each unique file only once</strong>. This approach will significantly help, given that stack traces often repeat the same file multiple times with different lines. Additionally, we will add a <strong>daily cache for project information</strong>, as projects don’t change frequently, and an <strong>hourly cache for search results</strong>.</p><p>Now, we need to reduce the number of file search results. <strong>The objective is to strike a balance between obtaining sufficient information and having too many results</strong>.</p><p>After a series of experiments, we managed to achieve the best balance possible by <strong>adding the file path along with the filename</strong>. However, a new issue arose — the file path from the stack trace doesn’t necessarily always end with “class,” for example, “com.agoda.Service.withResources.” We would naturally find nothing if we attempt to provide such a path as a filename. To address this challenge, I implemented an additional optimization. In 99% of cases, the third part of the path represents a repository or library name. Therefore, we significantly enhance search results and overall accuracy by appending “com/agoda/Service” to the search path.</p><p>Now, with significantly fewer results and higher relevance, there are still a few remaining corner cases:</p><ul><li><strong>Forked stale repositories</strong>, which people created to open PRs to the original repo. This can be mitigated by using <strong>fork_count</strong>; we are interested in projects with the highest possible count.</li><li>There could be the same<strong> files in different folders</strong>; for this, we can count the number of matches between the path from the search result and the stack trace line. The more, the better.</li><li>Last but not least, the change in the <strong>newest code is considered more relevant</strong> than stale code, so we sort results by their commit dates.</li></ul><p>After applying all the optimizations listed above, we can dramatically improve the search precision of the results.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*HXw5D69jc16ZG4Q0" /><figcaption>The result</figcaption></figure><h4>Conclusion</h4><p>With relatively low effort, we now have functionality that closely mirrors what developers experience while running applications locally. Although the file search precision is remarkable, it is still not 100% accurate. For instance, if applications use some very old libraries, which were in main several years ago, they might be excluded from the Gitlab index.</p><p>It means we will either get no results for search or results that are not relevant anymore. Regardless, after having this change deployed in the production environment for several months, we have observed the significance of this feature. Without this integration, navigating through stack traces becomes significantly more challenging.”</p><p>We would also be thrilled to contribute this change to Grafana, should the developers consent to its integration.</p><figure><a href="https://careersatagoda.com/department/technology/?utm_source=medium&amp;utm_medium=blog&amp;utm_campaign=agodaeng&amp;utm_term=Grafana&amp;utm_content=Dec2023&amp;gh_src=4a2284351"><img alt="" src="https://cdn-images-1.medium.com/max/720/1*qKAAoep6HRc8EBXkqWLK5g.jpeg" /></a></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c19d686a31a0" width="1" height="1" alt=""><hr><p><a href="https://medium.com/agoda-engineering/grafana-gitlab-happier-developers-c19d686a31a0">Grafana &amp; GitLab — happier developers</a> was originally published in <a href="https://medium.com/agoda-engineering">Agoda Engineering &amp; Design</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to index hundreds of millions of series in a time-series database]]></title>
            <link>https://medium.com/agoda-engineering/how-to-index-hundreds-of-millions-of-series-in-a-time-series-database-38e61c90c826?source=rss-3a7109501dd6------2</link>
            <guid isPermaLink="false">https://medium.com/p/38e61c90c826</guid>
            <category><![CDATA[hashset]]></category>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[bitmap]]></category>
            <category><![CDATA[time-series-database]]></category>
            <dc:creator><![CDATA[Evgeniy Zuykin]]></dc:creator>
            <pubDate>Fri, 09 Dec 2022 10:46:07 GMT</pubDate>
            <atom:updated>2023-01-25T05:35:20.344Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZGxaUhm6hRXh2dZ_wkWGdw.png" /></figure><p>In WhiteFalcon — Agoda’s in-house time-series database inspired by <a href="https://druid.apache.org/">Apache Druid</a>, we have a RealTime component, which ingests new measurements and stores the last few hours of data in memory. It’s done like that because most requests (alert systems and dashboards) use only the most recent data. Today we will discuss the index structure we use to operate with <strong>in-memory data</strong> efficiently.</p><p>Let’s start with some trivia first. Our measurement has the following format:</p><pre>{<br>  &quot;metric&quot; : &quot;service.a.request.duration&quot;<br>  &quot;value&quot; : 50,<br>  &quot;timestamp&quot;: 1661067352,<br>  &quot;tags&quot;: [<br>    &quot;server&quot;: &quot;A1&quot;,<br>    &quot;cluster&quot;: &quot;C1&quot;,<br>    &quot;status&quot; : &quot;200&quot;,<br>    ...<br>  ]<br>}</pre><p>Each measurement contains a <strong>metric</strong> name, <strong>timestamp</strong>, long or double <strong>value,</strong> and set of <strong>tags</strong> (Prometheus calls them labels). Each unique combination of metric + tags creates a new <strong>series and assigned integer id</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/0*BYlnlHFTrcnUbIRX" /><figcaption>Series into unique identifier</figcaption></figure><p>Instead of storing original values, WhiteFalcon aggregates them into data points(sum/count, quantiles, hyperLogLog, etc.), depending on granularity. Hence each series is assigned its own set of data points.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/281/0*pf2bttTkcrC1eHDg" /><figcaption>Series Id into aggregated data</figcaption></figure><p>WhiteFalcon provides an interface to query data filtering out series including(or excluding) specific tag values, for example:</p><pre>{<br>   &quot;include_tags&quot;: {<br>      &quot;server&quot;: [ &quot;A1&quot;, &quot;A2&quot;, &quot;B.*&quot; ],<br>      &quot;cluster&quot;: [ &quot;A&quot;, &quot;B&quot; ]<br>   },<br>   &quot;exclude_tags&quot;: {<br>      &quot;status&quot;: [ &quot;503&quot;, &quot;4.*&quot; ]<br>   },<br>   &quot;metric&quot;: &quot;service.a.request.duration&quot;,<br>   &quot;granularity&quot;: 60,<br>   &quot;start&quot;: &quot;2022-08-21T08:10:00&quot;,<br>   &quot;end&quot;: &quot;2022-12-21T09:11:00&quot;,<br>}</pre><p>This query means the following — give me data for the metric, with a data step of 60 seconds, between specified dates, for only series which have one of the specified values for <strong>server</strong> <strong>AND</strong> one of the specified values of <strong>cluster </strong>and <strong>don’t have </strong>any of specified values for <strong>status</strong>. To serve this request, we need first to filter out the series which apply to the request and then reaggregate the data of each series together.</p><p>So our index must support the following operations:</p><ul><li>Find specific series to aggregate new measurements into during the ingestion (or create a new one)</li><li>Find all series matching the query</li></ul><p>Our core index has the following structure:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/605/0*0oRdptm4t9qyCN6y" /><figcaption>Core index structure</figcaption></figure><p>Each metric has its map of tags to series id. This helps to efficiently search the series to aggregate new measurements using a single kv lookup.</p><p>Initially, we had a simple brute-force approach to filtering series for the query: iterate through all series for queried metrics and filter out those applicable to the query. This approach is not ideal since the complexity grows in O(N) manner (where N is a number of series for the metric), which might not work well for metrics with many series.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/604/1*PIlCuZlTh8JfnzVSPJxiBQ.png" /><figcaption>Index sequence scan</figcaption></figure><p>While the idea of using such an approach in production sounds a bit silly, it has its benefits:</p><ul><li>Simple — since it is a sequence scan</li><li>Flexible — it is easy to add new features to seq scan</li><li>Low ingestion performance impact, since it is just one kv lookup (or insert in case of new series)</li><li>Memory overhead is minimal, again, because it is just one lookup</li></ul><p>So how can we organize our data to make our search more efficient?</p><p>For each tag value, let’s store a set of series where it was seen.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/0*KUlhVwhL70iSDcdg" /><figcaption>Series set for each tag value</figcaption></figure><p>Now we can quickly find the list of series required by doing some magic on sets of each tag value from the query. <br>Let’s have a look at the example request:</p><pre>&quot;include_tags&quot;: {<br>    &quot;server&quot;: [ &quot;A1&quot;, &quot;B1&quot;],<br>},<br>&quot;exclude_tags&quot;: {<br>   &quot;cluster&quot;: [ &quot;B&quot; ]<br>}</pre><p>To find the series applicable to the query, we need to get a series set for server values <strong>A1</strong>, union them with a set for <strong>B1,</strong> and then remove all series for <strong>cluster B.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/529/0*Wvm7cejwLzLaYOWa" /><figcaption>Union of values for each tag and then intersection</figcaption></figure><p>Okay, but this query was simple, and our dataset wasn’t that complicated. Let’s see how our algorithm behaves on something more complex. Let’s throw one more tag into our series.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/745/0*Xs4WKC9xZ5L3KLP4" /><figcaption>Adding status field to series sets aggregation</figcaption></figure><p>Also, let’s make our query more complicated as well:</p><pre>&quot;include_tags&quot;: {<br>  &quot;server&quot;: [ &quot;A.*&quot;],<br>  &quot;status&quot;: [&quot;200&quot;, &quot;500&quot;]<br>},<br>&quot;exclude_tags&quot;: {<br>  &quot;server&quot;: [ &quot;A2&quot;],<br>}</pre><p>Here is how we execute this query step by step:</p><ul><li>Find all tag values of the tag server which apply to wildcard <strong>A.*</strong></li><li>Get series there these tag values are used and <strong>union</strong> these sets</li><li>Find all series where tag <strong>status</strong> values are used and <strong>union</strong> them</li><li><strong>Intersect</strong> series set from tag <strong>server</strong> with series set from tag <strong>status</strong></li><li>Find a series where <strong>server</strong> <strong>A2</strong> is used and remove these values from the set obtained by previous steps.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/726/0*6MAxiAhrdWHS1s9y" /><figcaption>∪ is a set union and ∩ is set intersection</figcaption></figure><p>We need first to find the <strong>union</strong> of all series sets for a specific tag before we can proceed to the next tag. Otherwise, we will end up having incorrect results.</p><p>There is another case we need to consider — previously, we always had a non-empty include_tags section, but if it is empty, we need to return data for all series. For that purpose, we will aggregate a set of all the series used in this metric. Let’s discuss such query:</p><pre>&quot;include_tags&quot;: {},<br>&quot;exclude_tags&quot;: {<br>  &quot;status&quot;: [ &quot;400&quot;, &quot;500&quot; ],<br>}</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/711/0*_weBEReyKqaUCWv0" /><figcaption>Discard excluded tags from all series</figcaption></figure><p>First, we get combined values to exclude tag status by unioning their series sets. Later we remove these values from the total series set.</p><p>So, did the time complexity change compared to the brute force approach? For this approach, we don’t iterate over all series for metric for each request, but instead just union and intersect series sets for those tags specified in queries; hence this algorithm should be much faster!</p><p>We have a working data structure that would work well for our case, but is it optimal? Let’s have a look at how we store series.</p><p>If we store them as simple hash sets, the addition of new values will be fast, but the main operations union, intersection, and removal of others(and not) would be slow because they will have O(N) complexity. Not mentioning we will need to create a fresh instance of such sets on every union/intersection, which will affect performance and impact GC.</p><p>Are there any better alternatives to HashSet? Our series are always positive integers, allocated continuously, starting from 0. It means we can use the BitSet data structure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/711/0*FU9e2gP6UEN0iJ0n" /><figcaption>HashSet vs BitSet structure</figcaption></figure><p>BitSet is a collection of <strong>64-bit integers(Longs)</strong> slapped on each other, creating a continuous long array. Each Long has 64 bits, meaning it can hold up to 64 boolean values. It means BitSet is a natural replacement for Array&lt;Boolean&gt; and HashMap&lt;Integer&gt;.</p><p>The hashset with 64 integers will require 64 * 4 bytes (+ some bytes for internal HashSet buckets), but bitset will need just 8 bytes for long + (several bytes for long array). Also, since it is a sequence of Longs, it’s heavily optimized for bitwise operations like AND, OR, XOR, etc. This is precisely what we need!</p><p>Suppose we use bitsets instead of hashsets for storing our series sets. In that case, we will not only improve the memory footprint but also the performance of all required operations — for example, the time complexity of intersection operation will drop from O(N), where N is a number of elements, to O(K), where K is a number of Longs required to store N elements. Sounds great!</p><p>But BitSet’s biggest advantage might also become its weakness.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/411/0*-8TVvM-_i-C4hA8k" /><figcaption>Sparse series ids</figcaption></figure><p>Previously we assumed all series ids for the same metric are continuous. However, it is true for all metrics across the index, for specific metrics, these values may be sparse.</p><p>In the case of the last series, 100260, it will require bitset to have an internal array of ~ 1567 (100260 / 64) longs, which is 100 KB, just to create a bitset and store only value in it! Since we are talking about hundreds of millions of series, this flaw will hit us even harder.</p><p>So what does it mean? Can’t we use bitsets for our purpose? Luckily, people have already figured out the solution to this problem — compressed bitsets. There are multiple implementations; we use roaring bitmap</p><blockquote>Roaring bitmaps are compressed bitmaps which tend to outperform conventional compressed bitmaps such as WAH, EWAH or Concise. In some instances, they can be hundreds of times faster and they often offer significantly better compression.</blockquote><p>Although our series is sparse, series for the same metric are often being allocated together, meaning they still can primarily benefit from compressed bitsets, so we can safely use RoaringBitmap to store our series sets.</p><h3>Conclusion</h3><p>Now about the results of this approach adoption in production:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*6LIJnMXj9odXSDnN" /><figcaption>ms per minute required for series filtering</figcaption></figure><ol><li>On average, the time required for series filtering is reduced 4–6 times — from 20 ms per minute to 3–5 ms per second.</li><li>Spikes caused by queries for metrics with large amounts of series reduced and the curve flattened.</li><li>The memory required for the index increased by 20%, which is not bad, considering the initial index was just a plain hash map.</li><li>Ingestion speed dropped by 2–3% due to the accumulation of series sets for each tag.</li></ol><figure><a href="https://careersatagoda.com/department/technology/?utm_source=medium&amp;utm_medium=blog&amp;utm_campaign=Evgeniy&amp;utm_term=timeseries&amp;utm_content=Dec2022&amp;gh_src=4a2284351"><img alt="" src="https://cdn-images-1.medium.com/max/720/1*fLx4QGK9zzDiGSTMww_G3g.jpeg" /></a></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=38e61c90c826" width="1" height="1" alt=""><hr><p><a href="https://medium.com/agoda-engineering/how-to-index-hundreds-of-millions-of-series-in-a-time-series-database-38e61c90c826">How to index hundreds of millions of series in a time-series database</a> was originally published in <a href="https://medium.com/agoda-engineering">Agoda Engineering &amp; Design</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to efficiently store and query hundreds of String Int dictionaries on one machine]]></title>
            <link>https://medium.com/agoda-engineering/how-to-efficiently-store-and-query-hundreds-of-string-int-dictionaries-on-one-machine-919ab757d362?source=rss-3a7109501dd6------2</link>
            <guid isPermaLink="false">https://medium.com/p/919ab757d362</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[jvm]]></category>
            <category><![CDATA[performance]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[engineering]]></category>
            <dc:creator><![CDATA[Evgeniy Zuykin]]></dc:creator>
            <pubDate>Tue, 19 Apr 2022 07:56:44 GMT</pubDate>
            <atom:updated>2022-04-23T09:38:01.553Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*y0pyiJY5ZbfJsGqT8j2HbQ.jpeg" /></figure><p>This article will cover the evolution of data structures that we are using while querying from the historical part of <strong>Agoda’s in-house time-series database </strong>and showcase example implementations of several on-disk database indexes<strong>.</strong></p><h3>The Problem</h3><p>During the data ingestion in the <strong>real-time </strong>part of our database, we <strong>intern</strong>(issue a stable int identifier) all incoming strings. Let’s call the result of this process a <strong>StringInt</strong> dictionary. Later, during the querying at our <strong>historical</strong> part, we first needed to determine which id was assigned to each specific string from the query to operate with ingested data. Then, the results needed to be converted back to strings.</p><p>Here is an example of a request:</p><pre>{<br>    &quot;metric&quot;: &quot;whitefalcon.messages.consumed&quot;,<br>    &quot;start&quot;: &quot;2022-04-05 11:27:21&quot;,<br>    &quot;end&quot;: &quot;2022-04-05 11:29:21&quot;,<br>    &quot;tags&quot;: {<br>        &quot;dc&quot;: [ &quot;HK&quot;, &quot;SG&quot; ],<br>        &quot;cluster&quot;: [ &quot;A&quot;, &quot;B&quot; ]<br>    },<br>    &quot;groupBy&quot; : [ &quot;messageType&quot; ]<br>}</pre><p>To intern the query, we need to do <strong>reverse(String-&gt;Int) lookup</strong>, meaning we need to find an Int id for a specific String. After interning, the request will look as follows:</p><pre>{<br>    &quot;metric&quot;: 5962,<br>    &quot;start&quot;: &quot;2022-04-05 11:27:21&quot;,<br>    &quot;end&quot;: &quot;2022-04-05 11:29:21&quot;,<br>    &quot;tags&quot;: {<br>        3: [ 12, 14 ],<br>        15: [ 52, 315 ]<br>    },<br>    &quot;groupBy&quot; : [ 411 ]<br>}</pre><p>After executing the query, we need to do <strong>forward(Int-&gt;String) lookup </strong>to get actual strings by ints before we can serve the response to the client.</p><p>To process each query, we might need to combine the results of querying multiple partitions. Each partition has its dictionary since they were created at different times and by different ingesting instances.</p><p>Hence we can formulate problem as follows — <strong>how to organize multiple dictionaries in our application to have efficient access to direct and reverse lookups</strong>?</p><p><strong>Note: </strong>potentially this problem could be solved by using some KV libraries like RocksDB/LevelDB, SQLite, or even with some separately deployed distributed systems(although network latency would dramatically reduce overall performance), today we will discuss only handcrafted solutions.</p><p>Throughout the article the following tools and languages will be used:</p><ul><li>J<strong>ava 17 + Scala 2.13</strong></li><li><a href="https://github.com/openjdk/jmh">Java Microbenchmark Harness (JMH)</a> — for java benchmarks</li><li><a href="https://www.yourkit.com/">YourKit</a> for heap dump analytics and flame graph</li></ul><p>Let’s create a contract for our data structure:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d2d35c912a0cce388dd5116d991b41e7/href">https://medium.com/media/d2d35c912a0cce388dd5116d991b41e7/href</a></iframe><p>Since ids are being issued sequentially starting from 0, our dictionary is stored in the format of string array. Here string has it’s cell index as id:</p><pre>+-------------------+----------------+---------------+------<br>| number of entries | string1 length | string1 bytes | ....<br>+-------------------+----------------+---------------+------</pre><p>The number of strings in each dictionary varies a lot depending on multiple factors (partition time, partition size, etc), as well as content of the strings themselves. For simplicity let’s imagine all dictionaries have strings containing 20 alphanumeric symbols, with around 100k strings, which sums up to ~ 2MB of raw data on disk for each dictionary.</p><p>Let’s define our constraints:</p><ul><li>App instance size — 8 cpu cores + 16 GB RAM.</li><li>Workload — 1kk direct lookups and 3k reverse lookups per second</li><li>Total number of dictionaries ~ 10k</li><li>~1.5k dictionaries are required for 90% queries</li><li>All dictionaries are immutable</li></ul><p><strong>In-memory hash-maps</strong></p><p>Let’s start with straightforward approach — load dictionary fully into memory from disk. It makes direct lookup fast since we just need to access array cell, and for reverse lookup just aggregate a Map[String,Int].</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1f1805211a6a2c159fd9b765c2585965/href">https://medium.com/media/1f1805211a6a2c159fd9b765c2585965/href</a></iframe><p>For those who are unfamiliar with Scala <strong>strings.zipWithIndex.toMap</strong> does the following:</p><ol><li>It maps string array [“hello”,”world”] into tuple sequence [(“hello”,0), (“world”,1)]</li><li><strong>toMap </strong>function aggregates created sequence with indexes into Map[String, Int]</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*D2X45K0ICuWfZn0usDqkow.png" /><figcaption>Flamegraph for dictionary creation</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wIH9jxQ0EMMp3ZiFKjMt1w.png" /></figure><p>For each request, additional array of 100k objects plus actual reverse map will be allocated. Reverse map will have boxed integers, meaning 100k more objects(we could mitigate it by increasing integer cache size, but what if our dictionary would have 5kk strings?). In total, it will sum up to several hundreds of KB of allocations just to convert our string array into queryable data structure.</p><p>We will keep our CPU busy creating our dictionary, and later <a href="https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)">GC</a>(Garbage Collector) will burn the rest of the CPU. And this all is just for one instance. What if you need to read about 100 of them for each query?</p><p>We could improve this behavior by implementing the following changes:</p><ol><li>Use primitive collections, for example<a href="https://github.com/leventov/Koloboke"> koloboke</a>, to avoid boxing of primitives.</li><li>Rewrite fancy<a href="https://en.wikipedia.org/wiki/Monad_%28functional_programming%29"> monad</a> chain into old plain for-loop which will not require excessive allocations</li></ol><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/41dcc46a401b6a209cdee1d7115945fa/href">https://medium.com/media/41dcc46a401b6a209cdee1d7115945fa/href</a></iframe><p>Although these changes improve the CPU workload, it doesn’t drastically change the picture. After looking at 80% of flame-graph busy with dictionary creations, the next idea we are coming to is simple — <strong>let’s cache them all</strong>. Sounds good; we will not burn our CPU, and we will use our RAM instead.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UWg4aCUjGTzZpWz1kde6fg.png" /></figure><p>For caching let’s use<a href="https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_%28LRU%29"> LRU</a> policy, otherwise we will run out of memory sooner or later. Considering our app instance size, we can dedicate around 10% of it to the cache. We will then start evicting the least recently used elements if our cache size exceeds 1.6GB. This will help us to store dictionaries which are used for the most of requests and invalidate the ones which are used for least popular queries.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Bcxdy5Dz-IO47-frKA9tDA.png" /></figure><p>For the current implementation, each dictionary (with our constraints) will have a size around <strong>9MB</strong>(string instances, raw strings array, reverse lookup hashmap). It means we can have just a bit more than 150 dictionaries on each instance at a time. That’s not enough — we will have a lot of repeated cache invalidation, since we need much more dictionaries to serve most of requests.</p><p>Luckily for us, we’ve observed an interesting pattern — <strong>you don’t need all strings in dictionary on each request</strong>. Usually, you need less than a hundred distinct lookups.<strong>.</strong></p><p>It changes a lot. Now we can create our Map[String,Int] lazily, saving us ~60% of RAM compared to the previous solution.</p><p>Now we can re-implement our dictionary in the following way:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a71e7ed6ebcd8b7c48a796149df46223/href">https://medium.com/media/a71e7ed6ebcd8b7c48a796149df46223/href</a></iframe><p>Here we see multiple things changed:</p><ol><li><strong>strings </strong>array is not holding String instances anymore, instead we store bytes read from disk, to not allocate memory for String instances</li><li>On reverse lookup we are using brute force search to find the required string. We aren’t really worried about O(N) search complexity because it will not be done more than once for each string.</li><li>Use <strong>TrieMap(</strong>lock-free scala analogue for java <strong>ConcurrentHashMap</strong>) for caching the results of the search and make the class thread-safe.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8KUcueB1N6h_pRQ1iV3Ihg.png" /></figure><p>Now our implementation requires ~4MB, even though we are storing raw bytes, we are storing inner arrays for each entry. It costs us 1.5 MB compared to the raw disk version. Now we can cache up to 400 dictionaries at once, which is better but still not enough, since our eviction rate still be too high.</p><p><strong>Storing strings on disk</strong></p><p>Since we can’t store raw data in memory, the only choice is to leave them on disk, and apply some indexing on top.</p><p><strong>Important</strong> — For simplicity and readability, code listings will be missing some details like caching of lookup results in TrieMap, pooling of opened RandomAccessFile instances to make them ThreadSafe, etc.</p><p>Let’s create a base class for disk based dictionaries:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5589c5663a1fad56353e60f7e4e8cae0/href">https://medium.com/media/5589c5663a1fad56353e60f7e4e8cae0/href</a></iframe><p>Upon obtaining a new array of strings, create a new file to do the following:</p><ol><li>Write bytes for all incoming strings down in a file remembering byte offset for each next string.</li><li>To get the length of the string we can subtract the offset of the next string from the offset of the current string.</li><li>Upon direct lookup, use RandomAccessFile to access a specific string, by <strong>seeking</strong> position to the start of its offset and <strong>reading</strong> its length bytes.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/822/1*W8DxfcSJ6_py3_jNIL_Sxw.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/584/1*ELMAALGf65bz-6aoqNi5Dw.jpeg" /></figure><p>Now, direct lookup looks simple and solid, but what about reverse lookup? Let’s go through multiple solutions and discuss their Pros and Cons.</p><p><strong>BruteForce</strong></p><p>The simplest idea is to perform a sequence scan on all file content upon each reverse lookup until the next string matches with the specified string or file ends.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6d4591fae3639d05b83bac844987741a/href">https://medium.com/media/6d4591fae3639d05b83bac844987741a/href</a></iframe><p>This implementation requires just about 400KB in memory, since it’s storing just a simple integer array, which means we can operate with tons of dictionaries at a time. But compared to the previous approach there is a big disadvantage — the difference between brute force search in heap and on disk is tremendous. That means we need to optimize reverse lookup somehow.</p><p><strong>Binary search</strong></p><p>One of the search techniques we could implement is a <a href="https://en.wikipedia.org/wiki/Binary_search_algorithm"><strong>binary search</strong></a>. But to use it we would need to order our strings somehow. For that purpose we will use <strong>java.util.Arrays.compare</strong> method which compares two byte arrays lexicographically. But we still need to have a way to random access our strings by their initial index in the array, so we will maintain the mapping of the sorted string index to the initial index to the string.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/942/1*Xpyc23zGelVs88d2Md-cpw.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HsN-yblKCE-T2OBU2rRJzg.jpeg" /></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3fca43a75a27f51662bec9ba940b22a0/href">https://medium.com/media/3fca43a75a27f51662bec9ba940b22a0/href</a></iframe><p>Hence our improved search complexity has increased from O(N) to O(log2N) and our memory usage is still reasonable, jumping from 400KB to 800KB since we added one O(N) space Array[Int].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G7DDEJeaQ0NKTtUs-bgHWQ.png" /></figure><p>Let’s get some numbers on performance. For each benchmark, we will run lookup by string for a random string from the initial list(id must always be present). To persist fairness of benchmarks between methods, we will use <strong>random with specific seed</strong> for it to always generate random data in the same order, meaning the same strings and ids for lookup.</p><pre>Benchmark                                   Score       Error  Units<br>bruteForceDisk                              2.582 ±     0.330  ops/s<br>diskBinarySearch                        37412.364 ±  2205.060  ops/s</pre><p>On a 1kk string, binary search is much better than brute force, but still, can we improve its performance somehow? Let’s check our flame-graph:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1mwYrhZBHrtVyE-D9vdEWQ.png" /></figure><p>We can clearly see here — <strong>RandomAccessFile.seek()</strong> is a most expensive operation. With the second most costly operation is <strong>RandomAccessFile.read()</strong>. Reading bytes from disk is less expensive than moving the current offset for file descriptors. For 1kk strings, we are doing on average log2 1000000 ~ 20 iterations, each iteration is doing 1 seek and 1 read, meaning ~ 20 disks seek calls to search one value. Is there any way we could reduce the number of seek calls?</p><p><strong>Simplified B-Tree</strong></p><p><a href="https://en.wikipedia.org/wiki/B-tree">B-Tree index</a> is one of the most common indexes in relational databases. In short, this kind of tree allows each tree node to have more than two children. Since we now have higher branching, our search complexity drops from log<strong>2</strong> N to log<strong>M</strong> N, since on each step we will drop M-1/M of possible strings to search. And the most important — we will have less disk seeks!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/984/1*TAMK2CNJt2OBu7tLt3TqWw.jpeg" /></figure><p>Sounds promising, but how do we build it? The procedure of building a balanced BTree is really sophisticated. Luckily for us, each dictionary is immutable, and we can cut corners by simply splitting our list into a multilayered tree. Here is how we do it:</p><ol><li>Define a recursive function with left (L) border and right border (R).</li><li>If <strong>L</strong> becomes bigger than <strong>R, stop</strong>.</li><li>If the number of elements between L and R is less than the branching factor, write<strong> node information</strong> about just these elements, without any children.</li><li>Else we calculate the number of children nodes for each node.</li><li>Split the L to R range into a branching factor number of ranges.</li><li>For each <strong>range </strong>run step 2.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/656/1*5dgU0EkIKOfbnHQxC3ugmQ.jpeg" /></figure><p>Now let’s discuss how we serialize node information. We will save the relationship between tree nodes (child node ids) on disk otherwise, it will take too much memory. The original string id is stored as a value in each node. Information about its disk start and total bytes length will be saved into arrays for each node.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W4QKdA2HECCUogpc-hVuQQ.jpeg" /></figure><p>First, we write the number of children the node has. For each child, we write the original string id and child node id(or -1), and then for each entry, we write string bytes. During this serialization, we fill up info about each string offset and length to maintain the ability to randomly access string bytes by id.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/aa2f1ca1358be6386719bae7797b11c1/href">https://medium.com/media/aa2f1ca1358be6386719bae7797b11c1/href</a></iframe><p>Now, we have a tree, and we need to query it somehow. The idea is pretty simple:</p><ol><li>Cache the root of the tree, since it will always be used.</li><li>Compare word bytes with each entry string. If strings are equal, return the entry’s string id.</li><li>If word bytes are lexicographically less than current entry bytes, dive into the child node of current entry.</li><li>Seek to the disk offset of the child tree node and read it fully into memory. Start from step 2 until all until all nodes will be compared or required string will be found.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/656/1*B5bKs0r6Xojrpo15KGeFcA.jpeg" /></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7af58e2fce23c366d812bf6e5a65914d/href">https://medium.com/media/7af58e2fce23c366d812bf6e5a65914d/href</a></iframe><p>Whew! That was pretty intense. Was it worth it? Yes! Memory consumption of this data structure is 820KB, which is just 20KB more than the BST approach. That’s because most of the info is stored on disk, and compared with BST, we store only 2 log M (N) arrays of space, which is very efficient.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*it7aZBMwjs2m86v75RFQOQ.png" /></figure><p>And what about performance?</p><pre>Benchmark                                   Score       Error  Units<br>bruteForceDisk                              2.582 ±     0.330  ops/s<br>diskBinarySearch                        37412.364 ±  2205.060  ops/s<br>diskBTree                              103985.625 ± 10465.966  ops/s</pre><p>On 1kk strings, BTree is about three times faster than BST — definitely worth the effort! But can we do better if we occupy a bit more memory?</p><p><strong>Hashmap</strong></p><p>Initially, we kept a HashMap String -&gt; Int, but we can’t do this since we can’t store strings in memory. Now, instead of storing string as a key, we will store its hash, and instead of string id, we will store disk offset. But since any hash function might have collisions, we will account for this as a separate map into a list of offsets. Hence for reverse lookup, we need to do the following:</p><ol><li>Calculate the hash of searched string</li><li>If we don’t have such hash, return NullId</li><li>Otherwise get dedicated string offset</li><li>Seek file position to it and read its length bytes from disk</li><li>Compare bytes from disk with bytes of searched word — if they are equal return string index, otherwise return NullId</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/996/1*Bk4PyJ7rBe0H6zF1QDfejg.jpeg" /></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/587284d1711954e8e12af94a0f88e859/href">https://medium.com/media/587284d1711954e8e12af94a0f88e859/href</a></iframe><p>That’s how we improved our search complexity from O(log N) to amortized O(1) by storing more meta info. However, we will need 2.5MB of heap space for each instance. It’s <strong>just twice as less as </strong>storing the whole dataset in memory as raw bytes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1Qku48McnybSkWYf-D-Ptw.png" /></figure><p>And how much better is performance?</p><pre>Benchmark                                   Score       Error  Units<br>bruteForceDisk                              2.582 ±     0.330  ops/s<br>diskBinarySearch                        37412.364 ±  2205.060  ops/s<br>diskBTree                              103985.625 ± 10465.966  ops/s<br>diskHash                               370910.145 ± 57589.846  ops/s</pre><p>It’s almost 4 times faster than BTree! But how can we improve memory consumption?</p><p><strong>Hash buckets</strong></p><p>What if we could create a limited number of entries in the hashmap? Instead of storing a map of hash -&gt; offset, we could split all values into buckets by modulo of their hash by the number of buckets (could be picked up heuristically depending on the total number of strings). Hence, we can group all strings into buckets by modulo from the hash of their bytes by the total number of buckets. We can also play with the expected number of elements in bucket — the bigger the number, the less buckets we will have and less memory overhead. But you will need more data to iterate through on each lookup.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/836/1*9mgTCBeqDlmv55qWLnbYyQ.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/736/1*LDVBCy8Wy5UnuLy_LRSltA.jpeg" /></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7fc076b74435a673d5e976507291b05a/href">https://medium.com/media/7fc076b74435a673d5e976507291b05a/href</a></iframe><p>Let’s measure performance and memory consumption for several different elements in the bucket:</p><pre>elements in the bucket                              Score  Memory<br>10                                             298102.291   1.4MB<br>20                                             249440.313   1.3MB<br>50                                             224918.313   1.2MB<br>100                                            165778.721   1.2MB<br>200                                            108862.231   1.1MB</pre><p>We can see that a decrease in memory consumption stops after 50 elements per bucket. Still, throughput is dropping significantly, which is happening because we are reading too many strings in one bucket lookup(read is becoming more expensive than seek). Hence the equilibrium on our workload is 20–50 elements in the bucket.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MWWaz6KP6vQ8JNBaxEMzsw.png" /></figure><p>Now we can write down the final benchmark list:</p><pre>Benchmark                                   Score       Error  Units<br>bruteForceDisk                              2.582 ±     0.330  ops/s<br>diskBinarySearch                        37412.364 ±  2205.060  ops/s<br>diskBTree                              103985.625 ± 10465.966  ops/s<br>diskBucketedHash                       224918.313 ± 42852.302  ops/s                    <br>diskHash                               370910.145 ± 57589.846  ops/s</pre><p>As we can see — all of the approaches have their Pros and Cons:</p><ul><li>In-memory map is simple but very RAM heavy.</li><li>BTree has very good memory/performance ratio but is pretty complicated.</li><li>Hash is really fast but still requires more RAM compared to other ones.</li></ul><p>Regarding the approach we chose in our system — until now it was a Binary Search approach which we might change to bucketed Hash or BTree.</p><p>I am confident that there are more efficient and more sophisticated ways to solve our problem. If you know about them, please reach out to me :)</p><p>All code is available on my<a href="https://github.com/SHaaD94/InternedStrings"> GitHub</a>, in case you want to play with it.</p><p>Also check out the article of my colleague Sergei, there he <a href="https://medium.com/agoda-engineering/deserializing-millions-of-messages-per-second-per-core-74e972ef4394">described</a> how we improved our ingestion rate in the <strong>realtime </strong>part of our database by implementing <strong>ConcurrentStringInterner</strong>.</p><p>Cheers!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=919ab757d362" width="1" height="1" alt=""><hr><p><a href="https://medium.com/agoda-engineering/how-to-efficiently-store-and-query-hundreds-of-string-int-dictionaries-on-one-machine-919ab757d362">How to efficiently store and query hundreds of String Int dictionaries on one machine</a> was originally published in <a href="https://medium.com/agoda-engineering">Agoda Engineering &amp; Design</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>