by Oren Eini

posted on: July 03, 2024

In my previous post, I explained what we are trying to do. Create a way to carry a dictionary between transactions in RavenDB, allowing one write transaction to modify it while all other read transactions only observe the state of the dictionary as it was at the publication time.I want to show a couple of ways I tried solving this problem using the built-in tools in the Base Class Library. Here is roughly what I’m trying to do:IEnumerable<object> SingleDictionary() { var dic = new Dictionary<long, object>(); var random = new Random(932); var v = new object(); // number of transactions for (var txCount = 0; txCount < 1000; txCount++) { // operations in transaction for (int opCount = 0; opCount < 10_000; opCount++) { dic[random.NextInt64(0, 1024 * 1024 * 1024)] = v; } yield return dic;// publish the dictionary } }As you can see, we are running a thousand transactions, each of which performs 10,000 operations. We “publish” the state of the transaction after each time. This is just to set up a baseline for what I’m trying to do. I’m focusing solely on this one aspect of the table that is published. Note that I cannot actually use this particular code. The issue is that the dictionary is both mutable and shared (across threads), I cannot do that. The easiest way to go about this is to just clone the dictionary. Here is what this would look like:IEnumerable<object> ClonedDictionary() { var dic = new Dictionary<long, object>(); var random = new Random(932); var v = new object(); // number of transactions for (var txCount = 0; txCount < 1000; txCount++) { // operations in transaction for (int opCount = 0; opCount < 10_000; opCount++) { dic[random.NextInt64(0, 1024 * 1024 * 1024)] = v; } // publish the dictionary yield return new Dictionary<long, object>(dic); } }This is basically the same code, but when I publish the dictionary, I’m going to create a new instance (which will be read-only). This is exactly what I want: to have a cloned, read-only copy that the read transactions can use while I get to keep on modifying the write copy.The downside of this approach is twofold. First, there are a lot of allocations because of this, and the more items in the table, the more expensive it is to copy.I can try using the ImmutableDictionary in the Base Class Library, however. Here is what this would look like:IEnumerable<object> ClonedImmutableDictionary() { var dic = ImmutableDictionary.Create<long, object>(); var random = new Random(932); var v = new object(); // number of transactions for (var txCount = 0; txCount < 1000; txCount++) { // operations in transaction for (int opCount = 0; opCount < 10_000; opCount++) { dic = dic.Add(random.NextInt64(0, 1024 * 1024 * 1024), v); } // publish the dictionary yield return dic; } }The benefit here is that the act of publishing is effectively a no-op. Just send the immutable value out to the world. The downside of using immutable dictionaries is that each operation involves an allocation, and the actual underlying implementation is far less efficient as a hash table than the regular dictionary.I can try to optimize this a bit by using the builder pattern, as shown here:IEnumerable<object> BuilderImmutableDictionary() { var builder = ImmutableDictionary.CreateBuilder<long, object>(); var random = new Random(932); var v = new object(); ; // number of transactions for (var txCount = 0; txCount < 1000; txCount++) { // operations in transaction for (int opCount = 0; opCount < 10_000; opCount++) { builder[random.NextInt64(0, 1024 * 1024 * 1024)] = v; } // publish the dictionary yield return builder.ToImmutable(); } }Now we only pay the immutable cost one per transaction, right? However, the underlying implementation is still an AVL tree, not a proper hash table. This means that not only is it more expensive for publishing the state, but we are now slower for reads as well. That is not something that we want.The BCL recently introduced a FrozenDictionary, which is meant to be super efficient for a really common case of dictionaries that are accessed a lot but rarely written to. I delved into its implementation and was impressed by the amount of work invested into ensuring that this will be really fast.Let’s see how that would look like for our scenario, shall we?IEnumerable<object> FrozenDictionary() { var dic = new Dictionary<long, object>(); var random = new Random(932); var v = new object(); // number of transactions for (var txCount = 0; txCount < 1000; txCount++) { // operations in transaction for (int opCount = 0; opCount < 10_000; opCount++) { dic[random.NextInt64(0, 1024 * 1024 * 1024)] = v; } // publish the dictionary yield return dic.ToFrozenDictionary(); } }The good thing is that we are using a standard dictionary on the write side and publishing it once per transaction. The downside is that we need to pay a cost to create the frozen dictionary that is proportional to the number of items in the dictionary. That can get expensive fast.After seeing all of those options, let’s check the numbers. The full code is in this gist.I executed all of those using Benchmark.NET, let’s see the results. MethodMeanRatioSingleDictionaryBench7.768 ms1.00BuilderImmutableDictionaryBench122.508 ms15.82ClonedImmutableDictionaryBench176.041 ms21.95ClonedDictionaryBench1,489.614 ms195.04FrozenDictionaryBench6,279.542 ms807.36ImmutableDictionaryFromDicBench46,906.047 ms6,029.69Note that the difference in speed is absolutely staggering. The SingleDictionaryBench is a bad example. It is just filling a dictionary directly, with no additional cost. The cost for the BuilderImmutableDictionaryBench is more reasonable, given what it has to do. Just looking at the benchmark result isn’t sufficient. I implemented every one of those options in RavenDB and ran them under a profiler. The results are quite interesting.Here is the version I started with, using a frozen dictionary. That is the right data structure for what I want. I have one thread that is mutating data, then publish the frozen results for others to use.However, take a look at the profiler results! Don’t focus on the duration values, look at the percentage of time spent creating the frozen dictionary. That is 60%(!) of the total transaction time. That is… an absolutely insane number.Note that it is clear that the frozen dictionary isn’t suitable for our needs here. The ratio between reading and writing isn’t sufficient to justify the cost. One of the benefits of FrozenDictionary is that it is more expensive to create than normal since it is trying hard to optimize for reading performance.What about the ImmutableDictionary? Well, that is a complete non-starter. It is taking close to 90%(!!) of the total transaction runtime. I know that I called the frozen numbers insane, I should have chosen something else, because now I have no words to describe this. Remember that one problem here is that we cannot just use the regular dictionary or a concurrent dictionary. We need to have a fixed state of the dictionary when we publish it. What if we use a normal dictionary, cloned?This is far better, at about 40%, instead of 60% or 90%.You have to understand, better doesn’t mean good. Spending those numbers on just publishing the state of the transaction is beyond ridiculous. We need to find another way to do this. Remember where we started? The PageTable in RavenDB that currently handles this is really complex. I looked into my records and found this blog post from over a decade ago, discussing this exact problem. It certainly looks like this complexity is at least semi-justified. I still want to be able to fix this… but it won’t be as easy as reaching out to a built-in type in the BCL, it seems.

by Andrew Lock

posted on: July 02, 2024

Behind the scenes of collection expressions - Part 4

by Oren Eini

posted on: July 01, 2024

At the heart of RavenDB, there is a data structure that we call the Page Translation Table. It is one of the most important pieces inside RavenDB.The page translation table is basically a Dictionary<long, Page>, mapping between a page number and the actual page. The critical aspect of this data structure is that it is both concurrent and multi-version. That is, at a single point, there may be multiple versions of the table, representing different versions of the table at given points in time.The way it works, a transaction in RavenDB generates a page translation table as part of its execution and publishes the table on commit. However, each subsequent table builds upon the previous one, so things become more complex. Here is a usage example (in Python pseudo-code):table = {} with wtx1 = write_tx(table): wtx1.put(2, 'v1') wtx1.put(3, 'v1') wtx1.publish(table) # table has (2 => v1, 3 => v1) with wtx2 = write_tx(table): wtx2.put(2, 'v2') wtx2.put(4, 'v2') wtx2.publish(table) # table has (2 => v2, 3 => v1, 4 => v2)This is pretty easy to follow, I think. The table is a simple hash table at this point in time.The catch is when we mix read transactions as well, like so:# table has (2 => v2, 3 => v1, 4 => v2) with rtx1 = read_tx(table): with wtx3 = write_tx(table): wtx3.put(2, 'v3') wtx3.put(3, 'v3') wtx3.put(5, 'v3') with rtx2 = read_tx(table): rtx2.read(2) # => gives, v2 rtx2.read(3) # => gives, v1 rtx2.read(5) # => gives, None wtx3.publish(table) # table has (2 => v3, 3 => v3, 4 => v2, 5 => v3) # but rtx2 still observe the value as they were when # rtx2 was created rtx2.read(2) # => gives, v2 rtx2.read(3) # => gives, v1 rtx2.read(5) # => gives, NoneIn other words, until we publish a transaction, its changes don’t take effect. And any read translation that was already started isn’t impacted. We also need this to be concurrent, so we can use the table in multiple threads (a single write transaction at a time, but potentially many read transactions). Each transaction may modify hundreds or thousands of pages, and we’ll only clear the table of old values once in a while (so it isn’t infinite growth, but may certainly reach respectable numbers of items).The implementation we have inside of RavenDB for this is complex! I tried drawing that on the whiteboard to explain what was going on, and I needed both the third and fourth dimensions to illustrate the concept. Given these requirements, how would you implement this sort of data structure?

by

posted on: July 01, 2024

SARIF (Static Analysis Results Interchange Format) is an OASIS Standard that defines an output file format. The SARIF standard is used to streamline how static analysis tools share their results. SARIF is a JSON-based format that is easy to parse. Lots of tools support it, including Visual studio C

by Oren Eini

posted on: June 28, 2024

We recently published an article on Getting started with GraphQL and RavenDB, it will walk you through setting up Hot Chocolate to create a RavenDB-based GraphQL endpoint in your system.Here is what this looks like:Another new feature is the New Database Wizard, which was completely redesigned and made much simpler. We have a great number of features & options, and the idea is that we want to give you better insight into what you can do with your system. Here is a quick peek, but take a look at the link. I’m biased, of course, but I think the team did a really great job in exposing a really complex set of options in a very clear manner.The About Page of RavenDB Studio has undergone major updates. In particular, we have made it easier to see that new versions are available, what changes are included in each version, and check for updates. Additionally, you can now review your license details and compare features available in different editions. Furthermore, we pushed an update to the About Page of RavenDBitself. Here we try to tell the story of RavenDB and how it came about. Beyond the narrative, our goal is to explain the design philosophy of RavenDB.The idea is quite simple, we aim to be the database that you don’t have to think about. The one component in your system that you don’t need to worry about, the cog that just keeps on working. If we do our job right, we are a very boring database. Amusingly enough, the actual story behind it is quite interesting, and I would love to get your feedback on it.We also published our new roadmap, which has a bunch of new goodies for you. I’m quite excited about this, and I hope you’ll too (in a boring manner 🙂). Upcoming features include data governance features, Open Telemetry integration, extremely large clusters, and more.One of our stated goals in the roadmap is better performance, with a focus on ARM hardware, which is taking the server / cloud world by storm. To that end, we are performing many “crimes against code” to squeeze every last erg of performance from the system. Initial results are promising, but we still have some way to go before we can publicly disclose numbers. As usual, I would appreciate your feedback about the roadmap and the new features in general.

by Oren Eini

posted on: June 26, 2024

Today I got in my car to drive to work and realized that Waze suggested “Work” as the primary destination to select. I had noticed that before, and it is a really nice feature. Today, I got to thinking about how I would implement something like that. That was a nice drive since I kept thinking about algorithms and data flow. When I got to the office, I decided to write about how we can implement something like that. Based on historical information, let’s suggest the likely destinations. Here is the information we have:The Lat & Lng coordinates represent the start location, the time is the start time for the trip, and the destination is obvious. In the data set above, we have trips to and from work, to the gym once a week, and to our parents over the weekends.Based on this data, I would like to build recommendations for destinations. I could try to analyze the data and figure out all sorts of details. The prediction that I want to make is, given a location & time, to find where my likely destination is going to be.I could try to analyze the data on a deep level, drawings on patterns, etc. Or I can take a very different approach and just throw some computing power at the problem. Let’s talk in code since this is easier. I have a list of trips that look like this:public record Trip(double Lat, double Lng, string Destination, DateTime Time); Trip[] trips = RecentTrips(TimeSpan.FromDays(90));Given that, I want to be able to write this function:string[] SuggestDestination((double Lat, double Lng) location, DateTime now)I’m going to start by processing the trips data, to extract the relevant information:var historyByDest = new Dictionary<string, List<double[]>>(); foreach (var trip in trips) { if (historyByDest.TryGetValue(trip.Destination, out var list) is false) { historyByDest[trip.Destination] = list = new(); } list.Add([ trip.Lat, trip.Lng, trip.Time.Hour * 100 + trip.Time.Minute, // minutes after midnight trip.Time.DayOfYear, (int)trip.Time.DayOfWeek ]); }What this code does is extract details (location, day of the week, time of day, etc.) from the trip information and store them in an array. For each trip, we basically break apart the trip across multiple dimensions. The next step is to make the actual prediction we want, which will begin by extracting the same dimensions from the inputs we get, like so:double[] compare = [ location.Lat, location.Lng, now.Hour * 100 + now.Minute, now.DayOfYear, (int)now.DayOfWeek ];Now we basically have an array of values from which we want to predict, and for each destination, an array that represents the same dimensions of historical trips. Here is the actual computation:List<(string Dest, double Score)> scores = new(); foreach (var (dest, items) in historyByDest) { double score = 0; foreach (var cur in items) { for (var i = 0; i < cur.Length; i++) { score += Math.Abs(cur[i] - compare[i]); } } score /= items.Count; scores.Add((dest, score)); } scores.Sort((x, y) => x.Score.CompareTo(y.Score));What we do here is compute the difference between the two arrays: the current start location & time compared to the start location & time of historical trips. We do that not only on the raw data but also extract additional features from the information.For example, one dimension is the day of the week, and the other is the time of day. It is not sufficient to compare just the date itself. The end result is the distance between the current trip start and previous trips for each of the destinations I have. Then I can return the destinations that most closely match my current location & time.Running this over a few tests shows that this is remarkably effective. For example, if I’m at home on a Saturday, I’m very likely to visit either set of grandparents. On Sunday morning, I head to the Gym or Work, but on Monday morning, it is more likely to be Work.All of those were mostly fixed, with the day of the week and the time being different. But If I’m at my parents’ house on a weekday (which is unusual), the location would have a far greater weight on the decision, etc. Note that the code is really trivial (I spent more time generating the actual data), but we can extract some nice information from this. The entire code is here, admittedly it’s pretty dirty code since I wanted to test how this would actually work. At this point, I’m going to update my Curriculum Vitae and call myself a senior AI developer. Joking aside, this approach provides a good (although highly simplified) overview of how modern AI systems work. Given a data item (image, text, etc.), you run that through the engine that outputs the embedding (those arrays we saw earlier, with values for each dimension) and then try to find its nearest neighbors across multiple dimensions. In the example above, I explicitly defined the dimensions to use, whereas LLMs would have their“secret sauce” for this. The concept, at a sufficiently high level, is the same.

by Mehul Harry

posted on: June 26, 2024

Join us on July 23, 2024, for .NET Aspire Developers Day, a livestream event to elevate your .NET skills with keynotes, deep dives, and interactive sessions. Connect with experts and the community.

by Andrew Lock

posted on: June 25, 2024

Behind the scenes of collection expressions - Part 3

by James Montemagno

posted on: June 24, 2024

Join us for Let's Learn .NET Aspire, a global live stream workshop where you can learn all about what .NET Aspire is, why you would use it, and see how to integrate .NET Aspire into your apps with a hands on workshop.

by

posted on: June 24, 2024

I think the default settings for the tree view in Visual Studio Code are not very good. The indentation is too small, and the indentation guides are not visible enough. Here's how to improve the tree view settings:Open the VS Code settingsAdd the following json content to the settings:JSONcopy{