Circular Dictionary, where are you?

It is surprisingly hard to find a .NET implementation of a "circular dictionary".

(At least not in the 15 minutes that I looked for one)

In my definition, it's a dictionary for key-based lookups that won't exceed a set capacity. It does this by removing oldest entries to make room for new ones. My use case for this to keep a limited history of the last ??? IDs which have been issued. That way, if a client has a transient network failure, they can just retry with the same request ID, and I will provide the same answer back. I could even save the history periodically so it could be loaded on startup if the failure was server-side. However, the capacity limit is needed so that memory usage doesn't grow unbounded over time.

I originally looked at using an OrderedDictionary for this purpose, but it's implementation is such that a Remove operation is O(n), because it copies all the elements of the array down when one is removed.

The way around that is to use a circular buffer instead of an array that is always strictly ordered. In other words, when the array fills up, it just loops back around to the beginning and starts replacing existing entries.

However, it took me a surprising amount of thought to come up with a solution. And after all that mind churn, the implementation isn't even complicated. You will have to forgive the very OO-centric F#, though.

namespace Xe.DataStructures

open System.Collections.Generic

type CircularDictionary<'key, 'value when 'key : equality>(capacity: int) =
    inherit Dictionary<'key, 'value>(capacity)

    let maxIndex = capacity - 1
    let buffer = Array.zeroCreate<'key> capacity
    let mutable isFull : bool = false
    let mutable next : int = 0

    member me.CircularAdd(key:'key, value:'value) =
        let put () =
            me.Add(key, value)
            buffer.[next] <- key
        
        let moveNext () =
            if next = maxIndex then
                isFull <- true
                next <- 0
            else
                next <- next + 1

        let clear () =
            me.Remove(buffer.[next])
            |> ignore

        if isFull then clear()
        put()
        moveNext()

The unit tests for this are stupid -- too long and boring to post. It's akin to calling CircularAdd, then verifying the count, verifying the last X items are still in the dictionary, and verifying that ones added before that are not.

Obviously things: Not thread safe. Call CircularAdd after checking that the key doesn't already exist. Initialize with positive capacity. At least my use case obviates all these things, so I didn't bother with them. Feel free to use, but I'm not responsible for it breaking when you use it. :)

F# dependency wrangling, interop, nancy

Defining dependencies, C# vs F#

One of the advantages of using F# is the ability to define things as functions rather than extra types. For instance, let's say I wanted to define a dependency (I like the term resource) that generates an ID.

In C#

I would likely do something like this:

 public interface IGenerateIds  
 {  
   string GenerateId(string entityPrefix);  
 }  

Then I would have to make different concrete implementations for testing, and also a production one:

 public class TestGeneratorOf1 : IGenerateIds  
 {  
   public string GenerateId(string entityPrefix)  
     { return "1";}  
 }  
 // you are testing this right?  
 public class TestGeneratorFails : IGenerateIds  
 {  
   public string GenerateId(string entityPrefix)  
   { throw new Exception("died"); }  
 }  
 public class RealGenerator : IGenerateIds  
 {  
   public string GenerateId(string entityPrefix)  
   { /* real implementation */ }  
 }  

In F#

I can directly define function signatures (called a type abbreviation):

 type GenerateId = string -> string  

This says given a string, return a string. This is a bit obtuse, so I can actually use aliases to give my signature more meaning when I look at it later:

 // aliases  
 type EntityPrefix = string  
 type CreatedId = string  
 // same signature, string -> string, but more descriptive  
 type GenerateId = EntityPrefix -> CreatedId  

This works a treat, and later I can easily define functions that implement this signature for whatever I need to test:

 let generateId1 prefix = "1"  
 let generateFail prefix : string = failwith "died"  
 let realGenerator prefix =  
   // real implementation  

The first two functions are so simple, they don't even need their own class file, and I will likely create them inline with the tests. The dependency signatures are small enough that they can all go in one centralized file and still be easily understood.

Compare the cognitive and organizational burden of the number of files. C# has at least 4 files for every dependency: interface, test pass, test fail, real. F# really only needs 1 file per dependency for the real implementation.

In my estimation, the F# version has a lot better signal-to-noise than the traditional OO dependency management!

That's great and all, but then there's interop...

So, I went to put this into practice... creating a REST endpoint using Nancy. Now Nancy is a brilliant framework, but it is quite OO-centric. Modules require inheriting a base class. DI requires interfaces and concrete classes. Fortunately, F# has these bits in it. You pretty much have to use the inheritance to use Nancy. But I wanted to continue to use functional dependencies. I also wanted to be able to unit test the endpoint with its dependencies in various conditions (good and bad) without using the real dependencies (i.e. database calls). But then have the option to deploy the same service with real dependencies and no change to the endpoint itself.

In Nancy, the way to do that is with a bootstrapper. I created bootstrappers for different dependency combinations that I wanted to test. These put the appropriate dependency in every request context.

 type IdGenGoodBootstrapper() =  
   inherit DefaultNancyBootstrapper()  
   override this.RequestStartup(container, pipelines, context) =  
      context.Items.["somekey"] <- box generateId1  

 type IdGenBadBootstrapper() =  
   inherit DefaultNancyBootstrapper()  
   override this.RequestStartup(container, pipelines, context) =  
      context.Items.["somekey"] <- box generateFail  

And I can setup my Nancy tests (nuget Nancy.Testing) to use those bootstrappers.

 let browser = new Browser(new IdGenGoodBootstrapper())  

Then my endpoint can pull the dependency function out of the request context...

 let gen = unbox<GenerateId> x.Context.Items.["somekey"]  
 // KABOOM  

... except that it crashes

It appears that the way F# works, these function signatures only work for the IDE. But at run time they compile to some core F# types (e.g. FSharpFunc). Not only that, but it appeared to me that they could be more generically typed than the defined abbreviation: e.g. a FSharpFunc<String, String> could be replaced with FSharpFunc<object, String> if you don't actually do something String-specific in the function. Combine that with the fact that at run-time, you can't get the real type definition of an abbreviated type (e.g. typedefof<GenerateId> will be a single FSharpFunc with no type parameters given). As a result, I found no way to pull a pure function back out of the dictionary and use it.

Coming from C#, this was completely unexpected to me. And I suppose it speaks to the very OO-ingrained nature of the CLR. However, just before posting a well-developed Stack Overflow question on the subject, I discovered a work-around.

Taking advantage of the OO nature, I can wrap the function signature in a record type (which ultimately gets emitted as a class, I think), and the run time can apparently cast that back to something that works.

 type GenerateId = { GenerateId: EntityPrefix -> CreatedId; }  

Then the code has to be changed to wrap the function in a record.

In the bootstrappers

 type IdGenGoodBootstrapper() =  
   inherit DefaultNancyBootstrapper()  
   override this.RequestStartup(container, pipelines, context) =  
      context.Items.["somekey"] <- box { GenerateId = generateId1 }

 type IdGenBadBootstrapper() =  
   inherit DefaultNancyBootstrapper()  
   override this.RequestStartup(container, pipelines, context) =  
      context.Items.["somekey"] <- box { GenerateId = generateFail }  

In the endpoint

 let gen = unbox<GenerateId> x.Context.Items.["somekey"]  
 let result = gen.GenerateId "asdf"  

And now it works!

Discovering this was quite the process. It was a bit of a letdown that function signatures are so limited at runtime, but the work-around is quite minimal. Overall, I am very happy at the way this works.

ID Generation Strategies

The theories

Historically, common practice is to let the database decide the next ID for a new entity. The database is THE place where consistency was maintained and therefore the best source of truth for what's available next.

Things can go wonky from there when you get into systems with eventual consistency between writes and reads. As a result, I have been investigating other ID generation strategies.

One that has become popular is to use UUIDs for entity IDs. Clients can generate UUIDs at will and they are reasonably guaranteed to be unique. Initially, I thought I would switch to this, but further research brought up 2 problems. One, various platforms have differing capabilities at generating UUIDs, especially looking at HTML5. More importantly, GUIDs are hard to remember, to communicate, to type. Even if they aren't exposed to the users, *I* still have to deal with them when debugging, querying, etc.

So the next idea was to use an ID issuance service, where the client first requests a new ID. This can be retried as necessary until one is obtained. Once obtained, the client makes requests against the ID. The downside here is the risk of unused IDs due to transient failure. I could also imagine misbehaving retries creating swathes of unused IDs.

Then you can diverge into ID request tracking -- clients send a UUID, then poll another resource by UUID to watch for the ID to be generated... or at the very least the UUID can enable retries on creating the same ID. Or you can use a HiLo type algorithm so the client itself reserves a block of IDs ahead of time that it can use until it runs out. Again, with non-sequential IDs (across different clients) and (blocks of) unused IDs as minor drawbacks.

An Implementation

My first attempt at ID generation used the conventional model of creating an ID when an entity is created, based on the next available ID from the database. Then returning that ID to the caller (e.g. a Location header for REST-oriented folks). The client is also sending me a GUID (or UUID) with the request so I can trap retries (... or can I?). Ultimately the next important decision point was:

What do I do if a client sends me the same Request UUID more than once? Then to my horror, the answer is predictably: "That depends." If the client initially failed to receive a response and is retrying the entity creation, (and assuming the server can query generated IDs by UUID), then the correct response would be give them back the same previously generated ID for that UUID. However, if it's months later and due to bad pseudo-RNG the same UUID is generated for a fresh request, then the correct response would be to error. Or perhaps better, I could still return the previously generated ID and depend on the POST itself to fail because the entity had already been created. This is essentially a concurrency error where I expected entity version -1 (not created), but actual version was >= 0.

Implementing ID generation tracking in order to allow at most once creation semantics has its own challenges. Tracking means storing the request ID/entity ID and then either querying or caching this store. Querying can be a problem depending on your ID store. I'm using EventStore so as to avoid adding another database into the mix, and querying each time is essentially like a table scan -- not ideal. Caching is a brand of musical chairs that can work, but can get complicated if "done right". The sticking point on caching for me is expiring least-recently-used entity ID sets (each entity has its own incrementing set of IDs) so that memory usage doesn't grow unbounded. Maybe in 5 years every RequestID/EntityID fits in memory just fine, but maybe it doesn't! Cache miss loading performance is also likely going to be an issue over time.

Current Conclusions

Should I try to guarantee at-most-once creation? Well the record-keeping requirements on the back-end certainly makes me question that!

For a separate ID issuance service, is issuing an ID that never gets used really so bad? (Let's say due to a transient network failure and retry) Having gaps in ID issuance appears to be psychologically damaging to certain personality types, and it *is* good to be conscientious about things "falling through the cracks". What can we do to sate that? I suppose a report could suffice to satisfy that curiosity. Maybe even a follow-up procedure to officially tombstone issued but unused IDs after a certain time period if it's important that every one be accounted for.

That actually wouldn't be procedurally much different from allowing a client to double-post the same customer, causing two different customer IDs with the same data, and then having to administratively go back and delete one. Although the issued-but-unused-ID method leaves your data in potentially better shape in the interim.

For the ID issuance service, there is still an itch that I want to scratch: misbehaving clients (let's say a bug) requesting lots of IDs. You could just say "Who cares if 10 million IDs were issued but unused before we fixed the problem?" and go on about your day. But in principle, I'm unlikely to say that. And I haven't thought through options to determine a good remedy. A throttle is the immediate answer to mind, but that's terribly boring and makes me think that I really need to look at the problem differently to illuminate better options.

Oh, and by the way...

And finally, I want to say that exploring ID generation has brought up a very important shift in the line of thinking about IDs -- that is, an ID is metadata about an object rather than part of its content. When you look at most existing code, you see the entity ID being part of the entity itself. But ID issuance begs to differ because the ID must be known ahead of time before the entity can even be created. The client-generated GUID (which is also ID issuance, but from the client instead of server) also takes this tact. In fact, the SQL database itself also takes this tact in that it has to know what the next available ID is before it inserts the data. But our code has been so tightly integrated with SQL implementation details up to now that it was taken as a given that ID needs to be part of the data itself. When really, that is just what SQL requires - ID being part of the data row.

Functionally, the data itself doesn't usually give a flying rip about its own ID number when actually doing work. The important part is that the infrastructure knows about identity and can appropriately provision work and load data when given an ID. NOTE: In the relational DB world, an entity may care about the ID number of a *separate* entity insofar as it needs to ask the infrastructure to load that other entity's data.

Anyway, this realization has affected the how I model entities (e.g. in DDD, no more aggregate IDs on the aggregates themselves), and so I thought it was worth mentioning.

Install EventStore as a service in Windows

Install Chocolatey

(optional, you can manually download NSSM)

Start a command prompt as administrator and run (copied from the website):

@powershell -NoProfile -ExecutionPolicy unrestricted -Command "iex ((new-object net.webclient).DownloadString('https://chocolatey.org/install.ps1'))" && SET PATH=%PATH%;%ALLUSERSPROFILE%\chocolatey\bin

Install NSSM

From command prompt:

choco install NSSM

Download EventStore

http://geteventstore.com/downloads/

Get Event Store for Windows

Unzip and copy to C:\EventStore (or a location you prefer)

Note: EventStore is available from Chocolatey as well, but as of this writing it wouldn't install for me, and it’s slightly behind current version.

Install EventStore as a service

From command prompt:

nssm install EventStore C:\EventStore\EventStore.ClusterNode.exe --db ./db --log ./logs

Note: This uses the default ports and runs single node. The db and logs directories will be automatically created on startup if they don't exist.

Video encoding

I was reading about VP8 and H.264 because my application will have to handle video, and I wanted to be familiar with what's going on. As part of that, I considered a method to "encode" a video in a way that is highly parallel, maybe low on space, and with little-to-no loss. Being just a simple man from the South, I'm sure someone a lot smarter than me has already thought of this, but here are my ideas.

Moving pictures

In simplest terms (at least in my limited knowledge of the video industry), raw video is an ordered sequence of pictures (frames). So each frame is a 2-dimensional grid of pixels. From video gaming, at least 60 frames per second is considered roughly optimal to make the human eye unable to perceive frame changes (it just looks like motion). 30 fps and up actually works for this, but an occasional frame change is still observable. At 1080p (1920x1080 resolution) there are 2,073,600 pixels in each frame if you look at it as an individual picture. A pixel's color is represented by a combination of color values. From the web, I know that one way to represent RGB colors is by using 6 hexadecimal digits; 2 for red, 2 for green, and 2 for blue. 6 hex digits takes up roughly 3 bytes. So that adds up to 5.9MB per frame to represent all the pixels. At 60 frames per second, that's 355MB per second of space. A 2 hr movie would be 42.7GB in raw form, not counting audio, delimiters, and format info.

Maths

If you look at an RBG color as a vector, then each frame is vector field. Though not quite, because RGB coordinates would always be integers. It'd be more like a vector ring, but probably assuming it's a real number would be sufficient. So anyway, if we extend that further, we could theoretically find a formula to exactly fit the changes of one pixel over time. (A small part of me wishes I had not dropped Vector Analysis in college.)

With the way most movies are actually edited, a single function would probably be pretty hairy, take a long time to generate, and take a lot of calculation to get the value for each pixel. But inside of a single shot, the function would probably look pretty smooth and have a fairly easy formula. Some exceptions are likely (like a night scene with gunshots, causing wide swings of color and intensity). So the one end of the spectrum you have one monolithic formula per pixel, and on the other end is a piece-wise function, with formulas for each shot.

Formula-fitting each pixel is an inherently parallel process, with each pixel considered separately. Optimization can occur afterwards. Video cards could be used (both encode and decode) for this since their computational power is all about parallelization.

Considering there are over 2 million pixels at 1080p, would this method actually save any space? A movie like The Matrix with over 2300 shots and using an accurate piece-wise function could be 10x larger than the original (my rough guesstimate based on a 50 ASCII character formula per shot per pixel). However, there are some "nerd knobs" that can be tweaked to make it theoretically small enough to be consumable. For one you can always increase the margin of error on the function, which will generally make the functions smaller and simpler while sacrificing accuracy. There are also optimizations you could make like sharing a particular formula across multiple pixels. Consider a night shot where many of the pixels will be the same shade of grey. Or consider that many pixels for a given scene will share a similar intensity, but will just be color shifted from one another. Or vice versa, same color, but different intensities (black and white film, for instance). By identifying those formulas which are simple transformations of others, there is an opportunity to conserve space. Although the sheer number of addressable pixels creates a lot of overhead for such optimizations. This volume of data is as much an exercise in organizational efficiency as anything.

Anyway, it is an interesting though experiment. Looking at a video as a series of vector fields is something I hadn't considered before.

Picking a client platform for a new system

What follows is my journey to picking a platform for a particular client in a new software system. It may not be the best answer for your case, but the considerations may still be relevant.

When tasked to develop a new business system one of the (many) choices to be made is the platform internal clients will run on. It is an important decision that will have impact for years to come.

The Desktop

Our first inclination was to create a Windows desktop app. All workstations are Windows machines, our team skillset is the .NET platform, and there were a number of local resources that need to be accessed (specialized printing, camera access, signature pad, and accounting software integration). So then I began to look at .NET desktop platforms: WinForms, WPF, and WinRT. WinForms was dismissed right away because of it's lack of extensibility and modern feature support (hardware acceleration, data binding, and flexible controls to name a few).

WPF

The harder decision was between WPF and WinRT. As near as I can tell from my research, WPF and WinRT apps are not all that different to develop (XAML/.NET, although WinRT has other options too). I even started a prototype app using MahApps.Metro and began digging into learning WPF. However, there is a cloud of doubt surrounding the future of WPF. There were some new WPF bits in .NET 4.5, but overall there has been very little activity or advancement in WPF for many years. Things that were tedious generations ago (that is, computer generations) are still tedious, with no official sign that it will improve. Considering it's age and stagnation, it's hard to pick this as the platform of the future for the new clients.

WinRT

I also did some research on WinRT. As far as I've found, you can make a .NET desktop app by starting with a Windows Store project template and manually modifying the project to enable desktop usage. You can also manually add references to WinRT libraries from other project types. My main issue with WinRT is that much of its design revolves around "metro" and the Windows Store, which is generally not being embraced by the industry. To me this makes WinRT's future speculative at best. Not to mention that WinRT will only run on Windows 8 right now, which the IT department is skipping. The impending Windows 10 release probably next year and a cooperative IT department willing to upgrade would ordinarily make this choice not so bad. But the larger question of whether the Windows Store underpinning will make it as a desktop app platform (which doesn't seem to be WinRT's primary consideration) gives me great pause. Microsoft has managed to leave an unstable vacuum in desktop development, which makes me concerned about significantly investing in that space.

Now what?

So where does that leave me? Well, my background is the web, and although I was looking forward to broadening my skill set to a desktop technology, it doesn't appear (from a platform perspective) that there is an good one to pick. I was also not very encouraged by my foray into WPF. It felt like almost a backwards step from HTML5 as a front-end technology. Don't get me wrong, HTML5 has a lot of room for improvement. I always like to say (with some embellishment) that Javascript is the worst possible tool for the job, but it is the only tool that can do its job. (This is sortof a twist on the Python creator's comments about PERL.) But I will say that XAML markup is quite verbose, especially since a lot of the changes I wanted to make required custom implementations of the entire control (even if mostly pasted from the default template). And the code required for data binding is crazy verbose compared to something like knockoutjs's ko.observable(). A lot of styling that is pretty straightforward in CSS feels weird in XAML... e.g. hover/active color changes. CSS3 animations are also amazingly simple. And considering that HTML5 is actually experiencing a LOT of improvement of late, and more in the future, it seems like a good client platform choice for moving data.

Web Issues

However, there are a couple of problems with this choice. Firstly, let's talk about browser compatibility. This is the main thing which holds back HTML5/CSS3 as a platform, but that mainly concerns web pages out in the wild. Consider that with a desktop app, IT would be required to install my app on machines. Now instead of that, IT will be required to install a different app on machines -- a modern/HTML5 browser. And there's more than one to choose from. What about cross-platform compatibility? You can install recent versions of Chrome of Firefox on a broad range of OSs and versions, probably on any workstation your enterprise runs.

Signatures

Then there is local resource access, the primary reason we wanted a desktop app. With some changes to our workflow, we are able to simplify the process for customers and also get rid of the need to interface with a signature pad -- its function will be integrated into a tablet which will be used for other parts of the process. Using a browser that supports getUserMedia, our app can also access the web cam. So the main difficulties left are the specialized printing and integration with accounting, which do require local resource access that browsers cannot provide.

Direct Printing

Normal printing is not really a problem from the browser, but we must print to specialized devices that may use their own printing languages (like zebra printers). Before the HTML5 discussions, we had already decided to make a Windows service for printing which would directly talk to the printer so prints can be automatically triggered based on system events. Since the service will already be directly talking to the printer, it can handle manually triggered printing from the web app as well. So that problem was already solved.

Accounting integration

I don't have a solution designed for the accounting software, because we don't even know what we will be using yet. (They are extremely unhappy with their current accounting software and want to change away from it regardless of my effort.) In any case, all the client will be able to do is make the request (e.g. to create invoices), and the server will take the process from there; running it directly if the accounting software supports it, or delegating it to a custom service on the accountant's machine in the worst case.

Chrome app?

I also looked at developing this as a Chrome app, which provides limited access to local resources. However, I really didn't like the idea of making proprietary modifications that make my HTML5 app not run elsewhere. It also seemed like for every local access I got, some normal web access was restricted due to sandboxing. That, and really the only benefit I would get is printing, which I had already resolved. The accounting software would probably still not be accessible from the Chrome app.

So anyway, that was my decision process. Going forward, we are looking at using Angular as our UI technology, and Bootstrap as a front-end (wanted to use Foundation, but Bootstrap was easier to integrate). On the server side, it's .NET Web API.

Disabling Text Selection / Right click on Websites is Stupid

So, I run into this every once in a while, and it is a minor thing that majorly irritates me: Websites who attempt to disable text selection or right-click.

First of all, this is utterly futile. HTML on a web page can't reasonably be protected from copying. The source of a web page can be viewed and manipulated (client side) at any time, even without right-click. Rather than just copying your text anyone can completely grab layout, style, script, etc. To illustrate this point to co-workers, I will go to a well-known website and change the main page by adding their name to it, for instance. It only shows up on their local browser until they reload the page, but it makes the point that HTML content is not readily securable and wasn't designed to be. If you want that control, use another format.

Second, there are valid use cases for highlighting text, as it has become a normal and expected thing in browsers. One such case is citation where you include the link, but the page's text is lengthy, and you want to block quote a passage to highlight it. There is also reporting a problem with the website. There are also accessibility/usability cases for text selection (e.g. text clipped in container). Personally, I sometimes highlight text subconsciously as I read, which is actually what led to this blog post when I found I could not do that.

Thirdly, I respect people's copyrighted / licensed work, but that respect ends with trying to hijack/disable basic functionality on my browser. Sorry, but find another way. Maybe inject a page link when someone copies text so they get a proper citation with no extra steps?

So, I made this post (where you can freely select the text if you like) to document the ways I have found to defeat this asinine infringement of browser functionality.

Javascript Selection disabling

The one I ran into most recently was a WordPress plugin called "Blog Protector". This style is very easy to disable. This should cover text selection on most browsers (not fully tested). On Chrome, the only line I needed to run was the first one.

Open a Javascript console (Chrome is Ctrl-Shift-J, IE is F12 then Console) and run this:

if(document.body.onselectstart) document.body.onselectstart = null;

if(document.body.style.MozUserSelect) document.body.style.MozUserSelect = null;

if(document.body.onmousedown) document.body.onmousedown = null;

I'll update this post if I run into more. This is mainly for my own reference, so I won't be taking requests, sorry.