<?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 Nikita Chizhov on Medium]]></title>
        <description><![CDATA[Stories by Nikita Chizhov on Medium]]></description>
        <link>https://medium.com/@nik96a?source=rss-52b1a0a59bb3------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*7sSvt-KC4cKKULJA.jpg</url>
            <title>Stories by Nikita Chizhov on Medium</title>
            <link>https://medium.com/@nik96a?source=rss-52b1a0a59bb3------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 23:05:19 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@nik96a/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[Optimised ObservedRemove Set in depth]]></title>
            <link>https://medium.com/@nik96a/optimised-observedremove-set-in-depth-60770103a650?source=rss-52b1a0a59bb3------2</link>
            <guid isPermaLink="false">https://medium.com/p/60770103a650</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[crdt]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[backend]]></category>
            <dc:creator><![CDATA[Nikita Chizhov]]></dc:creator>
            <pubDate>Mon, 31 Oct 2022 17:11:07 GMT</pubDate>
            <atom:updated>2022-10-31T17:11:07.860Z</atom:updated>
            <content:encoded><![CDATA[<h4>Or trying to compress several months of exploring CRDTs for a real distributed system by a backend software engineer</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/559/0*P6f7jYZE04NNf2Ok.jpg" /></figure><p>I set 2 goals in this article:</p><ol><li>Explain how optimised Observed-Remove Set works in simpler terms than it is done in the original paper — “<a href="https://doi.org/10.48550/arXiv.1210.3368">An Optimized Conflict-free Replicated Set</a>”</li><li>Explore how it should be implemented to be useful in production environment — including turning it into a Delta State CRDT + all data structures involved</li></ol><p>I assume that you are:</p><ul><li>Familiar with a concept of CRDTs and understand difference between state and operation-based CRDTs</li><li><em>Maybe</em> you have heard about Optimised Observed-Remove semantic — actors, dots, version vectors and so on.</li><li>Not entirely comfortable reading papers that use words like <em>lattice</em> and <em>join-semilattice</em> and these kind of notations:</li></ul><blockquote>(m, c) ⊔ (m ′ , c ′ ) = ({k 7→ v(k) | k ∈ dom m ∪ dom m ′ ∧ v(k) 6= ⊥}, c ∪ c ′ ) where v(k) = fst((m(k), c) ⊔ (m ′ (k), c ′ ))</blockquote><p>You get additional points for being comfortable with c#, as all the examples will be done using it. Though there will be plenty of language-independent pictures and diagrams as well.</p><p>It’s fair to point out that this is not the first article about the topic. Huge shout-out to <a href="https://bartoszsypytkowski.com/">Bartosz Sypytkowski</a> with his series of articles about CRDTs. The closest one to what I am trying to do is <a href="https://bartoszsypytkowski.com/optimizing-state-based-crdts-part-2/">Optimizing state-based CRDTs (part 2)</a> — check it out if you somehow have not seen it yet. My hope is that my attempt will be sufficiently different to be useful, even if only by the virtue of a different writing style.</p><p>Let’s get started.</p><h3>From classic to optimised Observed Remove set</h3><p>If you were to <a href="https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#OR-Set_(Observed-Remove_Set)">open wikipedia</a> at the time of writing this article, Observed Remove Set will not be particularly exciting concept. It achieves being a CRDT by tagging each element. Every time element is added, a unique tag is generated and saved. Every time element is removed, its tags are moved to a list of tombstones. On merge, (1) join (union) tombstone sets, (2) for each item, join all item tags and (3) for each item, remove all tags that are present in the combined tombstone set. If item no longer have any tags, drop it.</p><p>If you are a diagram person like me, here is the same explanation with 100% more squares and arrows:</p><p>Concurrent addition, then merge:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*klWWuzB1YakJzPoN6qDOFQ.png" /></figure><p>Concurrent addition and removal, then merge:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*X1pggJansyuwf9J-xDEteA.png" /></figure><p>The problem is, of course, tombstones. With this design we are required to store tombstones indefinitely. Even several bytes of data, which is added every time we add elements to a set and never removed, will result in problems sooner or later. If you can think of a use-case where this is not an issue, then chances are - you will be better off just using a central point, without trying to go into convergent data structures.</p><p>At the very least — this was not enough for me. I needed a set, that can be safely modified concurrently, supported additions and removals, and would not have a permanently growing metadata.</p><p>At the very end of wikipedia article I linked, there are 3 sentences starting with “An optimization that eliminates the need for maintaining a tombstone set is possible”. It in turn links a great paper by M.Shapiro et al: “<a href="https://doi.org/10.48550/arXiv.1210.3368">An Optimized Conflict-free Replicated Set</a>”.</p><p>The optimisation promises several things:</p><ol><li>No tombstones</li><li>Set is still a state-based CRDT that supports additions and removal</li><li>Size is upper-bounded in size</li></ol><p>Great! However, I have to admit — I had to spend weeks and implement it 2 times before I completely understood how it works. Let me try and shorten this journey for you.</p><h4>Step 1 — change tags a bit</h4><p>The first thing we need — is to remember that in most systems we have a limited number of “actors” making an update to a data structure. You can think about them as users. More likely though — they can be different nodes in a distributed system, each with their own identity.</p><p>Let’s say that we can assign each such actor an <strong>ActorId</strong>. Some unique identifier that actor uses — can be Guid, can be some unique string — it does not matter.</p><p>Let’s further assume, that each actor can be trusted with executing its own actions sequentially. What I mean is — each addition and removal should not be done concurrently if they are done by the same actor. This is not particularly hard to achieve if actors are nodes or processes — each node can have their own local locking mechanism.</p><p>Given those 2 assumptions, we can use pairs (ActorId, local version) instead of tags. Local version will be a simple integer counter that is incremented every time an actor operates on the set. Call this pair a <strong>Dot</strong>.</p><p>By definition — dots are unique, as each ActorId is unique and each operation by the actor have a unique local version. So we can use them instead of tags.</p><p>The following diagram is the same Observed-Remove set with tombstones. We simply added a dictionary of counters to remember local version of each actor.</p><p>Concurrent addition, then merge. Top line — actor “A1”, bottom — actor “A2”:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iqFV2lIlEChV-c7DEEyeAA.png" /></figure><p>Concurrent addition and removal, then merge:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*R5vOrD2M1sfu142e5TLtsQ.png" /></figure><p>Notice that if we were to add elements concurrently with same ActorId, we will encounter issues after removal — concurrently added element will be lost:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1k2yk_TCkbNm2oNWodODew.png" /></figure><h4>Step 2— removing tombstones</h4><p>Notice that tombstones are now a set of Dots — each is (ActorId, local version). If we have tombstones that are sequential — for example (A1, 5), (A1, 6), (A1, 7), (A1, 8) — we don’t need to store all of them. It will be enough to have a tombstone “range” — (A1, [5, 8]). Now we don’t have to store <em>all</em> tombstones, but we still have them.</p><p>Let’s take a close look at a possible state of such a set:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dCsxfdPLXrE8rK-Ytlsjqg.png" /></figure><p>Do you see it? We have a duplicate information! Let’s say we want to merge the above set with another set:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-G8v6YDYgAKqk84MIlT4Xw.png" /></figure><p>Look at the -6 in the right set. It has a Dot (A2, 1). We can see from the tombstones on the left that it must be removed. BUT! We can also infer the same thing, by the following 2 facts:</p><ol><li>Dot (A2, 1) is nowhere in the Items</li><li>Local version for A2 is 2.</li></ol><p>Both tombstones and Items+Counters, independently tell us a story — “left set <em>observed</em> some value added with dot (A2, 1), but it was since removed”.</p><p>Either one is enough to tell that item -6 from the right set must be ignored when merging.</p><p>Finally, let’s rename Counters to <strong>VersionVector</strong> (to have a universally understood name) and drop tombstones. Resulting data structure looks something like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f7dba4606a9c610daf887d25382e4da1/href">https://medium.com/media/f7dba4606a9c610daf887d25382e4da1/href</a></iframe><p>In the paper, authors operate with a set of triples — (Item, ActorId, Version). While we could work with them in code the same way (i.e. by having a HashSet&lt;(TItem, TActorId, int)&gt;), it would not be efficient at all. Having a dictionary of dictionaries is completely equivalent mathematically, but allows us to have many useful operations in constant time.</p><p>Let’s try to implement all operations we need:</p><h4>Add</h4><p>For addition we start with <em>item</em> and <em>actorId</em>. We need:</p><ol><li>Get the current version of a given actor and increment it.</li><li>Save item with resulted dot to the _items if it does not exist there</li><li>If it does exist, add our new dot to already stored dots</li></ol><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/59178370d9526a1d99674012096ff622/href">https://medium.com/media/59178370d9526a1d99674012096ff622/href</a></iframe><h4>Contains + Remove</h4><p>In order to check if item is in the set, it’s enough to check keys of _items.</p><p>To remove, we simply drop the item! Remember, we got rid of tombstones and infer “observed-removal” by a lack of dot in the Items.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/15edb4be7abb11e3c858c76bab1d2084/href">https://medium.com/media/15edb4be7abb11e3c858c76bab1d2084/href</a></iframe><h4>Merge</h4><p>The most interesting operation.</p><p>If you want to follow both this article and the paper, here is a breakdown. If you don’t, skip until the next code section and just roll with it.</p><p>In the paper, we are presented with the following algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_u2v6h10KoeIMzV7ggfzUw.png" /></figure><p>“B” is the other set — the one we merge with. I will call it <em>other</em>. “E” here is a set of triples (e, c, i), where e = Item, c = ActorId, i = Version. That is — it is our _items field (remember dictionary of dictionaries is equivalent to a set of triples). Then in plain english:</p><ul><li>M = All triples that are both in our set and in <em>other</em> set</li><li>M’ = All triples that exist in our set and have version higher than highest version in <em>other</em> set. In other words — those items that are “new” to <em>other </em>set.</li><li>M’’ = exact mirror of M’ — all triples that <em>other</em> set have, but our set have not yet observed</li><li>U = combined triples from M, M’ and M’. From U we remove O - all triplets (Item, ActorId, Version), such that there exists another triplet with same items and actorId, but higher version.</li></ul><p>Now, a couple of observations which does not impact the math, but impact the implementation:</p><ol><li>M, M’ and M’’, by construction, <em>do not intersect</em>. Which means unions are equivalent to concatenations.</li><li>During construction of M’ and M’’, authors use set difference (E \ B.E). This operation is useless because we later apply stronger filter: c &gt; b.v[i] (or Version &gt; other._versionVector[actorId]). There can be no triples in <em>other </em>(B),<em> </em>that have version larger than _versionVector of <em>other</em>.</li><li>Instead of constructing M and M’ separately, we can construct their union by removing from _items all dots, that have version that is less or equal to version from <em>other</em>._versionVector and do not exist in <em>other</em>._items</li></ol><p>The last part is admittedly hard to digest, so let’s break it down. We take one of our dots — (actor, version). Let’s say its from element -6 from the right set in last example, with dot (A2, 1). We then check 2 things :</p><ol><li>Is version (in this example — 1) less or equal to corresponding version in <em>other</em> version vector? In the example, <em>other</em> will be a set on the left, and its version vector is {A1: 2, A2: 5} (it was called Counters, remember?). So first check succeeds — 1 is less or equal to 5.</li><li>Does dot exist in <em>other</em>? In the example we took item -6 with dot (A2, 1). This dot does not exist on the left. (heck, the entire item does not exist)</li></ol><p>With 2 conditions met, we can safely say — dot (A2, 1) was removed at some point in the past of left set. So if we were merging it into the right set, we could drop item -6.</p><p>Taking all this into account, let’s code (don’t worry about efficiency just yet, for now I focus on how easy it is to understand).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b2a17085a2eb0c4479b89409ca197b7f/href">https://medium.com/media/b2a17085a2eb0c4479b89409ca197b7f/href</a></iframe><p>We merge in 3 steps:</p><ol><li>Remove all local dots that should not be present anymore (because <em>other already </em>observed their removal)</li><li>Add all dots from other that we have not seen.</li><li>Merge version vectors by simply taking actor-wise max.</li></ol><p>And… thats it. We implemented an Optimised Observed-Remove Set.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/476/0*hm7yHPXI2mOjjk8y.jpg" /></figure><h4>Ok, just kidding. Of course we can do better.</h4><p>Before talking about implementation specific optimisations, how about algorithmic complexity?</p><p><strong>Addition</strong> — total complexity O(1). Line-by-line view:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/652077297147616154cfe197e3bf9908/href">https://medium.com/media/652077297147616154cfe197e3bf9908/href</a></iframe><p><strong>Removal</strong> and <strong>Contains — </strong>O(1) total. They are both one-liners with a single operation on a dictionary key.</p><p><strong>Merge </strong>— total worst case complexity is O(A*N + A). “A” here is a number of actors operating on a set, “N” — number of items in the set (max of this and <em>other</em>). Although most of the time you would not have a situation where every actor adds every element. I think a more realistic situation — most of the items are added by just a single actor. Under this assumption complexity essentially becomes O(N+A). If we can’t make this assumption, then we are stuck with O(A * N). Line-by-line:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a3dfbed207d1227883c0a90e9c50b8aa/href">https://medium.com/media/a3dfbed207d1227883c0a90e9c50b8aa/href</a></iframe><p>We actually did pretty good. All the set methods are optimal — can’t do better than O(1). Merge also looks alright — we visit all data just once.</p><h4>What can we improve?</h4><p>There are a number of simple things, that any experienced c# dev with efficiency kink probably already screamed in my direction. We can avoid using LINQ. We can also remove ToList() calls and do removal outside foreach enumeration (by saving “toRemove” items into arrays, preferably rented from ArrayPool). How much can we win with this?</p><p>Well, not an insane amount. Depending on various parameters, such as size of the sets before merge, number of actors involved and so on, we can make things anywhere between 0 to 50% faster. We also remove all unnecessary allocations, leaving only those required for data. For this we, of course, sacrifice a bit of readability. You be the judge what’s worth more. You can check the updated code and benchmarks I used <a href="https://gist.github.com/NikitaChizhov/0b478a550ca5453ea3c02cc44f4d8cc2">here</a>.</p><p>Another trick we could do depends on assumptions about the data. How many actors do we expect? Chances are, not that many. Even if there are a lot of actors in total, chances are — only a few actors add any given item (and therefore — only a few dots exist per item). In this case, using a Dictionary to store dots is not efficient in either memory or speed. You will be better off using Array or List, where cost of iterating several items is less than 1 dictionary lookup. There even exists a special <a href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.specialized.listdictionary">ListDictionary</a> for this, although you might want to implementing your own anyway.</p><p>Third possibility is to change _items data structure in another way. Remember that the data structure we store items in — Dictionary&lt;TItem, Dictionary&lt;TActorId, int&gt;&gt; — is not the only possible hierarchy. We can use any data structure that encodes triples of (Item, Actor, version). What if we used Dictionary&lt;TActorId, Dictionary&lt;TItem, int&gt;&gt;?</p><p>If we were to use it, we get both positive and negative change in performance. <strong>Remove</strong> and <strong>Contains</strong> operations now need to iterate over Actors and do a their thing within a loop:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0660c90cc5aeea37204cce9a087e2bfd/href">https://medium.com/media/0660c90cc5aeea37204cce9a087e2bfd/href</a></iframe><p>Instead of O(1) they are now both O(A).</p><p><strong>Add</strong> operation did not really change — we still do constant times dictionary inserts, just in the different order.</p><p><strong>Merge</strong> however, now have a possibility to cheat. What if <em>other</em> set we are merging with contains actor that is completely new to us? In such a case, we don’t even need to iterate them — all of them, with all their dots can be inserted straight away. How common is such a situation depends heavily on your use-case. But this structure provides another intuition to how optimised observed-remove set works. Not going to lie — after I visualised the following picture in my head, the reverence I held for Observed-Remove set completely disappeared:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*x0rOkLCU6iU6_N1iR-K__w.png" /></figure><p>If you are like I was — a little bit disappointed — don’t be. It’s still an awesome data structure with its fair share of complexity.</p><p>Speaking of — let’s add some and speak about the elephant in the room.</p><h4>Network makes things more complicated</h4><p>I promised to talk about real production environment, haven’t I? Well, if you are building a real distributed system and you have to exchange over the network <em>the</em> <em>entire state of a data structure</em> in order for it to be useful, you are — pardon my language — weird. Maybe you can find such a use-case if you squint hard enough. But wouldn’t it be nice to be able to exchange only the necessary amount?</p><h3>Meet delta state CRDTs</h3><p>Presumably originally introduced in paper “<a href="https://doi.org/10.48550/arXiv.1410.2803">Efficient State-based CRDTs by Delta-Mutation</a>” by Paulo Sérgio Almeida et al. and expended upon by the same team in “<a href="https://doi.org/10.48550/arXiv.1603.01529">Delta State Replicated Data Types</a>”, delta state CRDTs are awesome. But God damn are those papers are hard to read.</p><p>The core idea is very simple though. We have a state-based CRDTs, that don’t have any network requirements, but message size is the entire data structure. And we have operation-based CRDTs that have small messages, but network must support exactly-once causal delivery. Delta state CRDTs should allow us to have the best combination — small messages which can be delivered over unreliable network (at least once delivery without ordering guarantees).</p><p>Over the next section I will try to explain how one can arrive to a Delta State design for ObservedRemove set. If you are not interested in the journey and simply want the design, skip until the next section.</p><h4>Journey to the delta state ObservedRemove set</h4><p>To construct a delta-state ObservedRemove set we need to start with answering 3 questions:</p><ol><li>How does a single delta look like?</li><li>How does a single delta get merged into a set?</li><li>How do we decompose a set into a collection of deltas?</li></ol><p>Well, let’s start with examining Add operation. What is the data that’s get added to the set? Its a triple — (Item, Actor, Version). Similar story with Remove — we start with Item, but what we actually end up removing is a collection of triples (Items, Actor, Version) — however many dots an items happened to have. So what if we were to try and use a triple + add/remove flag as a Delta?</p><p>Merge then seems relatively simple. For deltas with “add” flag — if Version in Delta is less or equal to the one stored in VersionVector, ignore it (because we already observed this addition). For “remove” flag try to remove received dot if it is stored.</p><p>Unfortunately it’s not as straightforward. There are 2 problems that come up:</p><ol><li><strong>After Remove operation is done, we can’t produce the full triple of removed elements</strong>. Because, well, item is removed at this point. But Merge needs to happen independently of Remove and we don’t want to store removed items indefinitely. However, notice that once we know the Dot (Actor, version), we don’t really need to know the item to remove it. After all, Dot is unique — it always corresponds to one and only one item. So the first problem is solved pretty easily — to transfer the effects of a Remove we simply use dot as a delta, without an item.</li><li><strong>Version vector is insufficient to make merge work.</strong></li></ol><p>To unpack the second one we need an example. Let’s say that we have 2 replicas of ObservedRemove set that are exchanging deltas. Don’t worry about exact implementation for now, just roll with intuition:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LIgS3DytUktIRg-uv0iyEw.png" /></figure><p>Here we have a diagram with 3 operations. The goal is to transfer effect of each operation to another set. We have no algorithm for Merge yet, but we can try to describe its properties based on our expectation of the result.</p><ul><li>We know, that after merging all deltas, the bottom set must have the same internal state as set above. If that property does not hold, Merge doesn’t do its job properly. Then, just looking at the first operation and its delta — Merge should: (1) update VersionVector to contain {A1: 1} and (2) add {-1: {A1: 1} to items. This seems trivial enough — just take values from AddDelta and insert them.</li><li>We know, that deltas should work under delays and duplications. So if we were to deliver first AddDelta(-1, A1, 1) again after 3 operations, it should have no effect. Well, we do have a VersionVector, which job is to reflect which dots we already observed. Intuitive thing to do — only apply addition if version from AddDelta is greater than value in VersionVector.</li><li>We know, that we want to be able to merge deltas in different order and still expect to get the same result. And here is the point when it’s not obvious how to make things work. Let’s say that we reorder the delta arrival from example — first we receive second delta — AddDelta(-3, A1, 2) and only then we receive AddDelta(-1, A1, 1). How do we do the first update?</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Cnxu-8nfNUAgfLaVkZc6ew.png" /></figure><p>At the moment of merging AddDelta(-3, A1, 2) we don’t know anything about the future. We <em>can</em> say that something is wrong — we get the version 2 without ever seeing version 1. But we can not have any guarantees when version 1 will arrive. Any attempt of “saving” AddDelta(-3, A1, 2) until we receive delta with version 1 plant us firmly into a Causal delivery network constrain (and it is operation based CRDTs territory).</p><p>So — we have to merge AddDelta(-3, A1, 2) immediately. Which means we have to update the version vector. But whatever value we were to insert, we get problems down the line. Any integer number added into VersionVector with A1 key (the most natural choice is 2, as it’s the received version) will result in inability to add the next delta. Think about it — by our design, state after merging AddDelta(-3, A1, 2) tells us that the set already observed dot (A1, 1) and removed it.</p><p>The solution is — change the VersionVector. We need to be able to reflect the fact, that set <em>observed</em> not a continuous range of versions from 1 to a number, but a set of versions with possible gaps.</p><h4>VersionContext or VersionRanges</h4><p>Now, <a href="https://doi.org/10.48550/arXiv.1603.01529">the paper</a> proposes to modify VersionVector into a VersionContext. VersionContext contains a VersionVector plus a collection of dots that we can’t yet add to a version vector, which Sypytkowski in his blog called a DotCloud. Here is a visualisation how such structure is updated:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8CHr_7aNAg8M-6nJGBCUVQ.png" /></figure><p>I felt adventurous and tried a slightly different option — VersionRanges. The idea is — instead of having separate VersionVector + DotCloud, we can have a single list of Ranges. We keep it in sorted order and merge overlapping ranges when inserting new version. I defined Range as inclusive from the left, but exclusive on the right. So, for example, Range [1, 4) contains 1, 2 and 3 and does not contain 4.</p><p>Here is how inserting would look like with the same order of dots as in the last picture:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fobRJ1Z64Lx-h-x0T5IwJQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/0*nOjAjmd3Xm29YaRf.jpg" /></figure><p>If you like idea of VersionRanges, <strong>allow me to advise against it</strong>. First, it is much, <strong>much</strong> harder to implement — just think about all the edge cases you need to consider when inserting a new version (it’s not like there is a standard data structure for sorted list of disjoint intervals). Second, it’s not even faster. In fact, across a variety of orders of insertion, inserting a Version into a list of ranges is <em>several times</em> slower than into a VersionContext.</p><p>Omitting my failed attempt, here is how a VersionContext for a single Actor can look like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6dfffcad3c8b3a887a355dfba6cbecf8/href">https://medium.com/media/6dfffcad3c8b3a887a355dfba6cbecf8/href</a></iframe><p>Notice that we have a choice here — we can construct a single VersionContext which works for all actors. It would contain the VersionVector + a set of <strong>dots </strong>(i.e. a set of (Actor, Version) pairs). Or, and I think this is easier — make a VersionContext for a single item, that contains a single entry from VersionVector + a set of <strong>versions</strong>.</p><p>We really only need 2 operations from VersionContext: (1) getting a new version, (2) adding a version that came from another instance.</p><p>To get a new version, we don’t even need to touch the dot/version cloud. Think about it — the actor that is making an update should never have any of its versions detached. If id did, it would mean we broke the rule we started with for OptimisedObservedRemove set — an actor had concurrent updates (which were delivered out of order).</p><p>We also design VersionContexts Add method so that it returns true if context was updated and false if nothing changed (which will be useful later).</p><h4>Time to start coding DeltaObservedRemoveSet</h4><p>We begin by defining Delta classes and modifying Add and Remove methods to return resulting deltas, which can be then propagated to other instances. I use a couple of simple extension methods which you can see <a href="https://gist.github.com/NikitaChizhov/0e9cb6277ace5e4cfa4dc385d1a7d568">here</a> if curious.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d11a172e8bfbc69183a5cfe90da6d138/href">https://medium.com/media/d11a172e8bfbc69183a5cfe90da6d138/href</a></iframe><p>Once we have that, we can focus on a new Merge method:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ab75e789b22c715c72eba38f5d9ddc5c/href">https://medium.com/media/ab75e789b22c715c72eba38f5d9ddc5c/href</a></iframe><p>Notice a similar, but slightly different behaviour for Add and Remove deltas. The first step for each — call TryAdd on context for incoming version.</p><p>Add delta will return immediately if TryAdd failed. This is because, if TryAdd returned false, it means we already observed the dot. We don’t know if we still have the item — it might have been removed already — but it does not matter. We either have the item and adding it again will do nothing, or we don’t have the item anymore because it was removed and we should not add it again.</p><p>RemoveDelta is the opposite — it will return immediately if TryAdd succeeds. Think about it — TryAdd returning true means we have not seen this dot before. Which means a corresponding item can not be in the set. Only if it’s false we need to try and find the dot and corresponding item.</p><p>If you read the code carefully, you noticed that in Merge, in RemoveDelta case-branch, I use a RemoveItemDot method which I have not shown. That is not by accident, it just needs a separate discussion.</p><h4>Finding an item by dot</h4><p>RemoveItemDot is currently the most annoying method in our implementation. The problem is — in order to find an item, we have no choice but to iterate all _items. This operation alone makes Merge at least O(N) in complexity, if not O(N * A):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bd9f90c3c530c342104670f64d6589fb/href">https://medium.com/media/bd9f90c3c530c342104670f64d6589fb/href</a></iframe><p>The natural solution to this — keep a secondary data structure, that is able to map dot to item. This mapping is unique, so it can be as simple as Dictionary&lt;Dot&lt;TActor&gt;, TItem&gt;. It requires more memory and updating it does slow us down, but it’s not a huge cost for a big speed-up in Merge.</p><p>Let’s name this structure <strong>Inverse </strong>and for the moment move forward to another questions — we will come back to it soon.</p><h4>Enumerating deltas for a set</h4><p>Why do we even need this? Well, strictly speaking it’s not <em>necessary</em>. Any scenario I could come up with can be solved with functionality we already have.</p><ul><li>You need to make a local update and propagate it to a number of other replicas? Take the deltas produced by update and save it until propagation is successful</li><li>You need to transfer the existing state to a new location? Ignore CRDT semantics entirely, just transfer the whole data as a single stream with appropriate checksum mechanism.</li></ul><p>While those get the job done, there are side-effects. If you store deltas until they are fully propagated to all replicas, how do you keep track of different replicas? If a replica is on the node that goes down, do you wait for it to go back up? How long? What if replica exists on a client, that connects to the overall system infrequently? What if there are thousands of copies that need to be synchronised — how do you keep track of which one received which deltas?</p><p>Instead of solving those questions, it would be nice if a set could provide some small indicator of what deltas it have and another set would then produce only deltas that would be new to the first set. I call this “small indicator” a <strong>CausalTimestamp</strong>. Without thinking about how it is implemented, this is the overall picture we want:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QFw3_nlpFG1B8mC6yPYbag.png" /></figure><p>And from the code perspective, here is the same thing as an interface we want our set to implement:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/80b19b292a3e8a873ffcc62c0f90fddc/href">https://medium.com/media/80b19b292a3e8a873ffcc62c0f90fddc/href</a></iframe><p>So how does this <strong>CausalTimestamp</strong> look like?</p><p>Our set always had an Add-Remove duality, perhaps it will help us here as well. Lets think about two questions separately:</p><ol><li>How can we tell, which items were already added to a set without looking at items?</li><li>How can we tell, which items were removed from the set?</li></ol><p>The first question is easy — we have a special data structure just for this — its our VersionContext. Just by having a VersionContext of another set, we can tell which items we need to send to it and which items it already observed.</p><p>The second one is more involved. We know that dot was removed if it exists in VersionContext but there are no items containing that dot. But checking it for all dots in the context is long and complicated, how can we make it efficient?</p><p>Now is the time we come back to <strong>Inverse.</strong> As a quick reminder — we decided that we will benefit from a dot -&gt; item mapping for merging RemoveDeltas and called it Inverse. How can it help?</p><p>Picture time. For any actor in the set, we have a context that looks something like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4nLv1hb6pZSLk-24Z8TLww.png" /></figure><p>Let’s add an Inverse visualisation here as well. Here I visualise the set that for this Actor contains items -24, -11, 34, 78 and -8. It also had 6 other items we know was removed (versions 1, 2, 4, 5, 8, 11) and 2 versions that are yet to be received (versions 9 and 12).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VWlQusRjTjadjcXniL-m5g.png" /></figure><p>If we focus only on the keys of the inverse, we can immediately see how a set can communicate which dots were removed:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZqoejQg4Jh9XqYcYjjk8Lw.png" /></figure><p>Those blocks coloured red are gaps — versions that exist in version context, but not in Inverse. They correspond to all dots that we know have been removed. In order to extract them easily, we need Inverse to not be a simple dictionary, but an ordered map of some kind.</p><p>How can we communicate to another replica which “gaps” we have? I can think of 3 options:</p><ol><li><strong>Don’t include this into CausalTimestamp at all</strong>. This would mean that we have to produce all RemoveDeltas every time EnumerateDeltas is called, regardless of causal timestamp provided. This is, obviously, simpler to code, but results in unnecessary network utilisation. And if you have a lot of non-sequential removals, this can be costly. (RemoveDeltas with sequential versions can be easily compressed into few RemoveRangeDeltas).</li><li><strong>Send all the gaps as part of CausalTimestamp</strong>. This may seem like it leads to less network load, but on average it’s actually pretty much the same. The only difference is whether we send gaps as part of CausalTimestamp or as part of response to CausalTimestamp.</li><li><strong>Remember that this is not at all a new problem and use hashing</strong>. Really, if we formulate this as “how do I efficiently check if another server has the same set of <em>things</em> as I?”, we immediately realise that this is nothing new. One of the common solution being — use a Merkle tree. Its probably possible to make it even more efficient than standard Merkle tree by using the fact that’s our objects are non-overlapping integer intervals, but I have yet to explore in this direction.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yP7_LfyaRfK_KqbpGetlRg.png" /></figure><p>How Merkle tree works and synchronised is outside our discussion — it’s a known problem with a lot of reference implementations. Here is a <a href="https://jack-vanlightly.com/blog/2016/10/24/exploring-the-use-of-hash-trees-for-data-synchronization-part-1">random blogpost</a> about it.</p><p>Let’s talk instead about Inverse. I said that we need a sorted map, right? But which one? Because we do have options:</p><ol><li><strong>A sorted map based on self-balanced binary search tree</strong>. This is how SortedDictionary is implemented in .NET</li><li><strong>A sorted map based on SkipList</strong>. This may or may not be a better option under heavy concurrency — depending on the implementation and who you ask. .NET does not have a skip list implementation, but, for example, <a href="https://stackoverflow.com/questions/1811782/when-should-i-use-concurrentskiplistmap/1811810">Java does</a> and seem to prefer it for concurrent scenario.</li><li><strong>Use a regular list and preserve sorting by inserting into a correct place</strong>. This is what .NETs SortedList does (don’t be fooled by its name, it is actually a key-value map, not just a list).</li></ol><p>On the surface this last one seems like a bad idea. After all, first two options promise logarithmic time for all operations, while SortedList have a worst case O(N) for both Add and Remove. But thats only for random data. While in our case, depending on the network, insertion can be anywhere from “slightly random order” to a pure increasing order. Remember, every Add to our set increases the Version. Which in turn means, that adds to Inverse also usually happen with greater and greater versions. Which means average complexity for inserting into SortedList around O(1) (same as appending to normal list).</p><p>We can’t promise the same about removals, but it’s still enough to make us weigh our options:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zWQ3zOsToS3zGUs2VuFTUg.png" /></figure><p>So, how do we code our delta enumeration? And how do we extend the set to be a map? Coming up in part 2!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*WgKNK8tzsOy3kQR5.jpg" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=60770103a650" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Thoughts on a train- Part 1, Number’s journey]]></title>
            <link>https://medium.com/@nik96a/thoughts-on-a-train-part-1-numbers-journey-f8333eaa52a7?source=rss-52b1a0a59bb3------2</link>
            <guid isPermaLink="false">https://medium.com/p/f8333eaa52a7</guid>
            <category><![CDATA[appreciation]]></category>
            <category><![CDATA[rant]]></category>
            <category><![CDATA[network]]></category>
            <category><![CDATA[physics]]></category>
            <dc:creator><![CDATA[Nikita Chizhov]]></dc:creator>
            <pubDate>Sun, 15 Aug 2021 14:30:36 GMT</pubDate>
            <atom:updated>2021-08-15T14:30:36.713Z</atom:updated>
            <content:encoded><![CDATA[<p>Every time I ride a train, every time I have a moment to relax and watch trees and plains and electric poles fly by, I marvel at the enormous hidden complexity that allows for that moment to happen.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*0XuanW2MOm92kzPHssjiNw.jpeg" /><figcaption>A random photo from a window of my train. Somewhere close to Berlin</figcaption></figure><p>I start imagining all the interactions, all the processes, all the effort required. I am, of course, never fully successful. Understanding everything around you — how it works, how it’s made, what is it’s history — is a hopeless quest. But step by step, year after year, I am understanding better.</p><p>The thought process usually starts right after my ticket is checked by a nice person in the train company uniform. She takes out some electronic device unknown to me, I take out my phone and open an app with a QR code — my ticket. The validation takes just a couple of seconds.</p><p>At that time, light emitted by a validation device hits the screen of my phone. In there, there are miniscule containers with polymer solution, fractions of millimeters in size — pixels. By applying an electric field, my phone forces them to change. To bend light differently. Some start to block all light and become black to the eye. Some allow a particular wavelength to pass and in conjunction with their neighbors become white. The reflected light is then received back by the validation device. Somehow it makes sense of it and is able to reconstruct the information behind the QR code. A number.</p><p>So much happened and so far only a single number was passed from one device to another! From an arrangement of electric charges in RAM in the phone, to the arrangement of light bending polymers in the pixels, to the very specifically reflected light, to the activations in a light sensitive matrix, to another arrangement of electric charges in RAM of a validation device.</p><p>This number’s journey has only just begun. To complete its purpose it needs to travel far. Every step will require it to change completely, while staying the same.</p><p>First, it “travels” to an antenna. Or rather, electrons inside this tiny piece of conductive metal dance a certain way — forward and backward, forward and backwards. They do that approximately 5 billion times per second. And their dance does not go unnoticed. They create a literal wave around them, which expands in all directions at the speed of light. Somewhere in the train (you still remember we are in the train, right?) there is another antenna with it’s own electrons in it. And those electrons are excited about their dancing brothers. So much so, they start mimicking them. After a millisecond or so of this coordinated dancing, our number’s journey through WI-FI connection is complete.</p><p>A very similar thing happens next. But this time electrons need more space. They again dance forward and backward, but they go further each time. Thanks to that the signal can travel much further — kilometers instead of meters. It’s picked up by a tower and translated again. This time — electrons dance in a line inside a copper wire.</p><p>Multiple times in this journey, our Number has to ask for directions. You see, it knows only the final destination — an address somewhere in the internet. But it does not know how to get there. So first, it asks a router in the train if it knows how to get there. The router, unfortunately, does not. But it knows who to ask. So the message with Number goes to another, bigger router that belongs to an Internet Service Provider. And then, most likely, to another ISP. It’s journey is without a doubt, epic. A person with imagination might even see elements of a Campbell’s “Hero’s Journey” — a wise DNS server, which helps to see the truth about the destination, many routers that share their knowledge of the way, perhaps one or two firewalls, which add tension.</p><p>After what feels like ages, but actually is just a dozen or so milliseconds, Number arrives to it’s destination. Now it’s time to complete its purpose. It is briskly compared to several others. Bigger than this one, ok. But smaller than this one, good. Bigger again, smaller, bigger, bigger, bigger. Equal! Number found its twin. There was exactly the same number waiting for it here, inside the server of a train company. A small message containing a status code “200 OK” traces Number’s journey back to the validation device. An entire process taking less than 100 ms.</p><p>After thrice as long of human brain processing what it sees, I hear “Thank you” and the lady moves on to the next passenger. While my mind moves on to looking at the glass and rubber and metal around me, thinking what insane effort was required to make them the way they are.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f8333eaa52a7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Using DI with DispatchProxy based decorators in C# .NET Core]]></title>
            <link>https://medium.com/@nik96a/using-di-with-dispatchproxy-based-decorators-in-c-net-core-ac02f02c5fe5?source=rss-52b1a0a59bb3------2</link>
            <guid isPermaLink="false">https://medium.com/p/ac02f02c5fe5</guid>
            <category><![CDATA[dot-net-core]]></category>
            <category><![CDATA[net-core]]></category>
            <category><![CDATA[decorator-pattern]]></category>
            <category><![CDATA[c-sharp-programming]]></category>
            <category><![CDATA[dependency-injection]]></category>
            <dc:creator><![CDATA[Nikita Chizhov]]></dc:creator>
            <pubDate>Tue, 11 Feb 2020 21:57:23 GMT</pubDate>
            <atom:updated>2020-02-11T21:57:23.189Z</atom:updated>
            <content:encoded><![CDATA[<h3>Using DI with DispatchProxy based decorators in C# .NET Core</h3><p>Can we all agree that decorators are awesome? There are good reasons why decorator pattern is a part of best practices of software design (<a href="https://en.wikipedia.org/wiki/Decorator_pattern">Wikipedia sums it up reasonably well</a>):</p><blockquote>In <a href="https://en.wikipedia.org/wiki/Object-oriented_programming">object-oriented programming</a>, the <strong>decorator pattern</strong> is a <a href="https://en.wikipedia.org/wiki/Design_pattern_(computer_science)">design pattern</a> that allows behavior to be added to an individual <a href="https://en.wikipedia.org/wiki/Object_(computer_science)">object</a>, dynamically, without affecting the behavior of other objects from the same <a href="https://en.wikipedia.org/wiki/Class_(computer_science)">class</a>.<a href="https://en.wikipedia.org/wiki/Decorator_pattern#cite_note-1">[1]</a> The decorator pattern is often useful for adhering to the <a href="https://en.wikipedia.org/wiki/Single_responsibility_principle">Single Responsibility Principle</a>, as it allows functionality to be divided between classes with unique areas of concern.</blockquote><p>However, if you attempted to use decorator pattern in .NET alongside default Microsoft.Extensions.DependencyInjection, there is a good chance you found it rather frustrating. There seems to be no way to elegantly use them together.</p><p>Well, allow me to showcase a couple of tricks to help with that.</p><p><em>All the code snippeted below </em><a href="https://github.com/NikitaChizhov/DispatchProxyWithDependencyInjection"><em>can be found here</em></a><em> as a single ConsoleApplication project you can run.</em></p><h3>Setting the scene</h3><p>Before we come to decorators, let’s define an example class we will decorate. There is nothing interesting in it — a method <strong>VeryImportantWorkAsync</strong> will call <strong>await Task.Delay</strong> — nothing you haven’t seen.</p><p>Just to be fancy, let’s inject another service in our ExampleService. We will call it <strong>ImportantDataProvider</strong>. It’s job will be to supply TimeSpan for our Task.Delay</p><p>Here are interfaces and implementations for both:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/61a17e284ce29706e9eb9060bac8eb96/href">https://medium.com/media/61a17e284ce29706e9eb9060bac8eb96/href</a></iframe><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1d182062b99b9b4b30c69aa89f945714/href">https://medium.com/media/1d182062b99b9b4b30c69aa89f945714/href</a></iframe><h3>Classic decorators</h3><p>Alright, the scene is set, let’s talk decorators. Usual way to implement this pattern would look something like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9b18966035c5edb8f18a74b6d0706596/href">https://medium.com/media/9b18966035c5edb8f18a74b6d0706596/href</a></iframe><p>It’s clean and simple.</p><p>However, if you need decorators for a lot of classes, it is not hard to see how this can become repetitive. Even in below-medium-sized project you may want to use basically the same decorator for several classes with multiple methods in each. IDEs like JetBrains Rider or Visual Studio provide great code generation capabilities, but it still gets boring soon.</p><p>It is also definitely not obvious how to use DI with it. Most articles i found recommend the following:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5d99bc6e768bb9be4b256143c2141046/href">https://medium.com/media/5d99bc6e768bb9be4b256143c2141046/href</a></iframe><p>Main reason i don’t like this — it look kind of ugly. It does not really utilizes DI and requires a lot of effort to change if you want to add other constructor arguments to any of classes involved.</p><p>After some stubborn searching, i was able to find a very nice solution. Most of the credit goes to <a href="https://greatrexpectations.com/2018/10/25/decorators-in-net-core-with-dependency-injection">this marvelous article</a>. The only addition from me — ability to decorate every registered service instead of only the first found (which is something like 1% of inventive work here):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fb56f515ebe591e5e4be8cc2b5c7ad36/href">https://medium.com/media/fb56f515ebe591e5e4be8cc2b5c7ad36/href</a></iframe><p>The use of this extension method looks much nicer, isn’t it?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5272ac9d20452739299de25d9c15234d/href">https://medium.com/media/5272ac9d20452739299de25d9c15234d/href</a></iframe><h3>DispatchProxy-based decorators</h3><p>As I mentioned before, the drawback of classic decorators is their repetitiveness. How much nicer would it be to be able to just do some work before and after an arbitrary method? (python people, please hide your smirks)</p><p>Well, we can do just that using <strong>DispatchProxy</strong> class.</p><p>Again, all the credits goes to, first, <a href="https://www.c-sharpcorner.com/article/aspect-oriented-programming-in-c-sharp-using-dispatchproxy/">this very extensive article</a>. There you can find a much more detailed example. And second — to <a href="https://stackoverflow.com/a/48150664">this StackOverflow answer</a>.</p><p>Decorators with DispatchProxy are a bit more advanced, so let’s go over how they work slowly.</p><h4>What is a DispatchProxy?</h4><p>It’s an abstract class in <strong>System.Reflection</strong> namespace, with only a couple of methods inside:</p><p>It defines an abstract method <strong>Invoke</strong>:</p><pre>protected abstract object Invoke(MethodInfo targetMethod, object[] args);</pre><p>And implements generic method <strong>Create</strong>:</p><pre>public static T Create&lt;T, TProxy&gt;()<br>    where TProxy : DispatchProxy</pre><p>Calling <strong>Create</strong> method will actually create <em>a new class</em> with two properties:</p><ol><li>This new class will inherit from supplied type <strong>TProxy</strong></li><li>It will also implement everything defined in <strong>T</strong> interface (and all interfaces <strong>T</strong> inherits from).</li></ol><p>How the hell does it implements methods it doesn’t know anything about? That’s what <strong>Invoke</strong> is for. All implemented methods will do the same thing — call Invoke, supplying information about called method as <strong>MethodInfo</strong> and all the arguments as array of objects.</p><h4>So how do i use this?</h4><p>Let’s try a minimal example:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9904996f1de201fa06ccf063dc7423a7/href">https://medium.com/media/9904996f1de201fa06ccf063dc7423a7/href</a></iframe><p>This is a decorator! It does absolutely nothing, but we will add functionality in a minute.</p><p>First, notice that this class can not be <em>sealed</em>. This should not be surprising — after all, DispatchProxy will attempt to create a new class which inherits from our <strong>DispatchProxyEmptyDecorator.</strong></p><p>Second, this is generic class with type parameter <strong>TDecorated</strong>. This will be an interface we want to decorate. Any interface!</p><p>Third, due to the way DispatchProxy works, there has to be a constructor with no parameters. (We didn’t need to define it explicitly because DispatchProxy already have one)</p><p>In the public <strong>Create</strong> method we defined we do two things:</p><ol><li>Call private Create method (don’t confuse these two overloads) defined in DispatchProxy</li><li>Save supplied instance of class we want to decorate</li></ol><p>In the <strong>Invoke</strong> method we just invoke method saved _decorated instance with a signature of MethodInfo argument.</p><p>If you understood this example, it should not be hard to extend any functionality you want. For example, here is simplest logging decorator:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/292923e21aa5f37f99442f4fd22b840b/href">https://medium.com/media/292923e21aa5f37f99442f4fd22b840b/href</a></iframe><p>Example above will, of course, work poorly in case of async methods. So let’s fix that:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/043b423977047ce2f522f1edffdca85f/href">https://medium.com/media/043b423977047ce2f522f1edffdca85f/href</a></iframe><h3>Finally, DispatchProxy decorators with DI</h3><p>Finally, here is an extension method i came up with. If you ever saw (or can come up with) better solution, please fill free to share it in the comments :)</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e638558161945573505a972de70e8830/href">https://medium.com/media/e638558161945573505a972de70e8830/href</a></iframe><p>Use of extension is the same as with classic decorators:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/43bc74b3baa2d9805b671a1729539b39/href">https://medium.com/media/43bc74b3baa2d9805b671a1729539b39/href</a></iframe><h3>Bonus: isn’t it slower? Is it even worth it?</h3><p>That’s good questions. Since DispatchProxy uses Reflections, there can be performance concerns. And not only in terms of code running time — development can also be faster or slower depending on level of proficiency and amount of decorators involved. Here are some thoughts on the matter:</p><ol><li><strong>Application performance</strong>. Both decorator implementation will add an overhead compared to running naked, non-decorated service. Overhead introduced by DispatchProxy may be several times higher. However, in my <em>non-exhaustive</em> testing i saw overhead of 1–5 microseconds compared to non-decorated method. (Classic decorator closer to 1, DispatchProxy — closer to 5). <em>Most of methods i usually decorate do not care about this overhead</em></li><li><strong>Development speed</strong>. It’s true that DispatchProxy makes decorators less repetitive. <em>However, it also does not allow a lot of code generation benefits from IDEs</em>. So if i were to need just a couple of decorated methods, i likely won’t bother with making them with DispatchProxy.</li><li><strong>Code can be convoluted</strong>. Examples i showed are simple. But most of times you would want more complex logic in you decorators. Async methods, desire to process method result and other needs can add complexity to DispatchProxy decorators quickly. And <em>sometimes you may prefer to have repetitive, but easy to understand</em> <em>code.</em></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ac02f02c5fe5" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>