CRDTs and lockless data structures

A good five or so years ago Shevek, a friend I met while building cloud-generating appliances at the (now defunct) Nebula, spent an afternoon and evening describing the benefits of lock-free data structures to me. He went deep into the theoretical aspects of it, summarizing a lot of the research thinking at the time. While I tried to keep up to retain it all later; I really didn’t manage it. The (predictable) end result was that I got the basics of what it did, why it was valuable, and some basic examples of how it was used, but I missed a lot of the how can this be more directly useful to me. A lot of that conversation was focused on multithreaded code and making it efficient, and what could be done (or not) to avoid contention blocks.

Jumping back to today, when I’m not writing away on Using Combine, I am helping some friends with a project that includes real-time collaborative editing. The goal is the same kind of thing that you see in Google Docs where multiple people are editing a document at the same time – you see each other’s cursors, lives updates, etc.

The earliest form of this kind of functionality that I used was originally a mac program called SubEthaEdit, and a couple years later a browser-based “text editor” called EtherPad, which I used extensively when working with the open source project OpenStack. (This was also around five years ago – I haven’t been actively contributing to OpenStack in quite a while).

Google adopted this capability as a feature, and has done an outstanding job of making it work. Happily, they also talk about how they do such things. In the details I was able to find, they often used the term “operational transformation” to cover most of their recent efforts. That was also the key technology behind Google’s (now dead effort): Wave. Other systems have done the same thing: ShareJS, Atom’s Xray, and the editor Xi.

I spent some time researching how others had tackled the problem of how you enable this kind of feature. The single best cohesive document I read was a blog post by Alexei Baboulevitch (aka “Archagon“) entitled: Data Laced with History: Causal Trees and Operational CRDTs. The article describes his own code and implementation experiments, conveniently available on github as crdt-playground. It also includes a tremendously useful primer into the related topics and links to research papers. It also helped (me) that all his code was done with Swift, and readily available to try out and play with.

Data Laced with History: Causal Trees and Operational CRDTs is absolutely amazing, but not an easy read. While I highly recommend it if you want to know how CRDT works, expect to need to read through it several times before the details all sink in. Alexei writes clearly and very accurately, and it is extremely dense. I have read the whole article many times, as well as dug through all that code repeatedly, to gain an understanding of it.

While I was buried in my own learning of how this works, I had an epiphany one evening: the core of a CRDT is a lock-free data structure. Once I stepped back from the specifics of it, looking at the whole thing as a general algorithm, the pieces I picked up from Shevek clicked into place. Turns out that conversation (which I had mostly forgotten and thought I lost) had a huge amount of value for me, years later. The background I gleaned after the fact gave me some ideas to understand how and why CRDTs work, and ultimately  proved incredibly useful to understand how to effectively use them.

Human Voice

When I joined twitter, it was because my friends were talking about it. Conversations that I could normally only participate in during conferences or meetups became available to me. I tried to follow it slavishly at first, and then I had an epiphany that it was more like chatting with some friends at a restaurant or bar – people are coming and going, and you chat with whomever is around and available. Facebook was similar, but family and friend focused – keeping up with what my friends are doing after I moved 1000 miles away.

Fast forward a decade, and the human voice has been nearly extinguished in both mediums. I still have accounts in both systems, but it’s more like turning on a constant advertising stream. I ceased being able to rely on either for even slight recency of human voices, let alone the friends and conversations that I used to have. They have become the modern noise-on-the-TV that I grew up with – nothing good on. Perhaps worse, because so much of it is emotionally strident – “this one small trick”, “you’ll be shocked and amazed”, etc. So much bullshit.

Fortunately I’ve (re)found a place where I can get that human voice again:

I’ve gone back to checking my RSS feeds first for reading instead of hitting twitter or facebook, which makes a huge difference. That dopamine hit isn’t the same – RSS isn’t a never-ending stream of potentially interesting content that keeps you addicted like a manic crackhead, but the content that is there tends to be pretty darned good.

I’ve gone back to curating – looking for mentions and links, and following those back to sources. The “X Weekly” curated newsletters are equally good for finding new people to read, as well as friends of friends. It takes some effort, but that is also making it more real. If someone goes to wonky, I can easily ignore them for a bit, or drop their feed from my set – no shaming or cancel notification, just stepping away to more of what I’m interested in.

If you want to pipe up and join in the conversation, you can easily host your writing at Micro.blog, WordPress, or Medium. Micro.blog and WordPress are $5 and $8 per month and Medium is no direct cost.

Remember if you’re not paying for a service, you are likely the product…

I have used WordPress for years, so I stuck there, but honestly the easy to get started option is very much micro.blog. Write about whatever you want, as much as you want. A sentence, paragraph, or longer – there’s no limit, no “right way/wrong way”, and you don’t need to torture your words into some small number of characters.

Using Combine – reference content complete!

I’m thrilled to be announcing that an updated version of Using Combine is now available!

It has taken me nearly 6 months to draft it all, reverse engineering and writing tests for all the various publishers, operators, and pieces in between – and documenting what I found. The end result is 182 pages (in US PDF format) of reference documentation the way I’d generally like to have it.

While the live site is updated automatically, updated PDF and ePub versions are now available on Gumroad. If you purchased a copy previously, you can go to Gumroad and get an updated, DRM free, content in either PDF or ePub formats.

This updates finishes the largest swath of reference updates, creating tests to verify all the various operators and writing the documentation reference sections for the following:

There was also an update for Xcode 11.3 and associated iOS 13.3 and macOS 10.15.2, which included some subtle changes to the throttle operator behavior, which I recently wrote about in some detail.

With this update, the majority of the core content is now complete, but the work is by no means finished!

The next steps for the book are review and editing. On the to-do list are refining the descriptions of the reference sections, reviewing all the patterns now that we have had Combine for a few months, and seeing the updates as the API changes and refines. There are some diagrams now, but more are likely needed in some sections – both in the patterns and reference sections.

As before, this continues as a labor of love and for the community. Meaning that the content will continue to be free, available on the live site, with updates being made available as I make them. The work has been financially supported by 116 people as I’m writing this, as well as a number of people providing pull requests to fix typos and grammar flaws.

If you want a DRM-free digital copy in either PDF or ePub format, please consider supporting this work by purchasing a copy at gumroad.

Combine: throttle and debounce

Combine was announced and released this past summer with iOS 13. And with this recent iOS 13 update, it is still definitely settling into place. While writing Using Combine, I wrote a number of tests to verify and generally double-check my understanding of how Combine was working. With the update to iOS 13.3, the tests showed me that a few behaviors changed once again.

The operator that changed and trigged my tests was throttle. Throttle is meant to act on values being received from an upstream publisher over a sliding window. It collapses the values flowing through a pipeline over time, choosing a representative value from the set that appeared within a given time window. It also turns out that throttle has slightly different behavior when you’re working with a publisher that starts out sending down an initial value (such as a @Published property).

While I was poking at throttle to understand how it changed, I also realized that debounce was acting differently than I had originally understood, so I took some time to write some additional tests and make a more explicit timing diagram for it as well. Since debounce didn’t change behavior between 13.2 and 13.3 (that I spotted anyway), I’ll describe it first.

debounce

When you set up a debounce operator, you specify a time-window for it to react within. The operator collects all values that come in from the publisher, and most notably it resets the starting point for that sliding time window when it receives a value. It won’t send any values on until that entire window has expired without any other values appearing. In effect, it’s waiting for the value to settle. The marble diagrams show this really well.

Without a break that lets the sliding window expire, a single value is returned.
With a break that lets the sliding window expire, two values are propagated.

throttle

Throttle acts similarly to debounce, in that it collects multiple results over time and sends out a single result – but it does so with fixed time windows. Where debounce will reset the start of that window, throttle does not – so it doesn’t collapse the values entirely, but sort of “slows them down” (and that matches the name of the operator pretty well).

Which value from the set that arrive that’s chosen to be propagated is influenced by the parameter latest, which is set when you create the operator. In general, latest being set to true results in the last value appearing getting chosen, and latest being set to false results in the first value that appears. This is one of those items that is a lot easier to understand by looking at a marble diagram:

Throttle (latest=false), under iOS 13.2.2
throttle (latest=true) under iOS 13.2.2

The notable behavior change is how it handles initial values. Initial value seems to be a bit “flexible” in what is specifically initial though. When I first wrote my tests, I was using a class with a @Published variable, which sends a value upon subscription, and then updates when it is changed. To illustrate the 13.3 behavior change better, I re-wrote and expanded those tests to use a PassthroughSubject, so there wasn’t an automatic initial value.

throttle (latest=false) under iOS 13.3
throttle (latest=true) under iOS 13.3

So under iOS 13.3, the initial value (which is sent out roughly 100ms after the creation of the pipeline in my test), is always propagated, and then the sliding window effect begins immediately after that.

If you want to see the underlying tests that illustrate this, check out the following bits of code from the Using Combine project:

Using Combine (v0.8) update available!

A new version of Using Combine (v0.8) is now available.

The live HTML site for Using Combine is updated automatically, and the PDF and ePub versions are now available on Gumroad.

This version has a number of additional notes and changes, primarily from reader feedback, and some references to Combine’s changes with the release of IOS 13.2. A few more issues have been noted in the book, along with references to feedback reports sent to Apple where they may represent bugs or unexpected behavior in the current implementation.

This release also includes SVG based diagrams – so the original ASCII art diagrams are now gone, which should make that content far more accessible in the ePub format.

In addition, I added a section on marble diagrams, specifically in how to read them and how they apply to the code and examples illustrated in this book. I originally planned on generating all the marble diagrams, but after repeated efforts at that I backed off that idea and am creating them by hand, with the help of OmniGroup‘s wonderful tool OmniGraffle. And yes, the source for this is also in the github repository.

For the next release, I am planning on getting back to detailing out the as-yet-unwritten section on a number of operators. 

The project board at https://github.com/heckj/swiftui-notes/projects/1 also reflects all the various updates still remaining to be written.

A huge thank you to all who have supported this book and my efforts to provide it!

Japan

A torii gate at Danjo Garan in Koyosan

We recently returned from our first visit to Japan. Karen and I have been wanting to go for quite a while, and the time was right – so most of the month of October was dedicated to that endeavor.

I loved our trip, and we were fortunate enough to even be in Kyoto during on of the festivals – Jidai Matsuri.

Our trip and tour included Kushiro, Tokyo, Nagoya, Hiroshima, Meijima Island, and Kyoto – as well as a number of places in between that will take a while to unblur in my memory.

Hiroshima Memorial

We took a tour through Samurai ToursBest of Japan, which I highly recommend if you want a good sampling of a wide swath of Japan. Their guides were excellent and informative, and I can’t thank Charlie enough for his instruction in how to navigate the signage for the Tokyo trains and subways, which more or less held us in stead through the entire trip. I do wish we could have stayed longer in some areas, but another trip in the future will have to do.

Yours truly, visiting a Studio Ghibli store in Kyoto
The Golden Shrine, in Kyoto
Looking around from the top of Miyajima Island, near Hiroshima

Tokyo subway map – yep, it’s complicated – but amazing!
Pigment, a dangerous store for artists…
giant buddha at Kamakura Daibatsu
The ryokan we stayed at in Takayama

The sheer artistry in every day life in Japan was amazing, and I miss it already being back in the US. Another trip in the future, I tell myself…

It is OK to test the framework

When I started to write the book Using Combine, I was learning the Combine framework as I went. There was a lot I was unsure about, and especially given that it was released with the beta of the operating system, the implementation was changing between beta releases as it firmed up. I chose to use a technique that I picked up years ago from Mike Clark – write unit tests against the framework to verify my understanding of it – while writing the book. (yes, I’m still working on it – it’s a very lengthy process)

While listening to a few episodes of the Under the Radar podcast, I heard a number of references to the idea of “make sure you’re not testing the framework”. It is generally good advice, in the vein of “make sure you’re testing your code first and foremost”, but as a snippet out of context and taken as a rule – I think it’s faulty. Don’t confuse what you are testing, but reliably testing underlying frameworks or libraries, especially while learning them or they evolve, can easily be worth the effort.

I have received a huge amount of value from testing frameworks – first in verifying that I understand what the library is doing and how it works. More over, it has been a very clear signal when regressions do happen, or intentional functionality changes.

If you do add tests of a framework or library into your codebase, I recommend you break them out into their own set of tests. If something does change in the library, it will be far more clear that it is a change from the library and not a cascading side effect in your code.

Most recently, this effort paid off when I stumbled across a regression in the Combine framework functionality with the GM release of Xcode 11.2. While I’ve been coming up to speed with the various operators, I’ve written unit tests that work the operators. In this case, the throttle operator – which has an option parameter latest – changed in how it operates with this release.

Throttle is very similar to the debounce operator, and in fact it operates the same if you use the option latest=true. They both take in values over time and return a single value for a specific time window. If you want the first value that’s sent within the timeframe, theoretically you should use latest=false with the throttle operator. This worked in earlier releases of Combine and Xcode – but in the latest release, it’s now disregarding that path and sending only the latest value.

You can see the tests I wrote to verify the functionality at https://github.com/heckj/swiftui-notes/blob/master/UsingCombineTests/DebounceAndRemoveDuplicatesPublisherTests.swift, and right now I’m working on a pull request to merge in the change reflecting the current release and illustrating the regression. And before you ask, yes – I have submitted this as a bug to Apple (FB7424221). If you are relying on the specific functionality of throttle with latest=false, be aware that the latest release of Xcode & Combine is likely going to mess with it.

If you are more curious about all the other tests that were created to support Using Combine, then feel free to check out the github repository heckj/swiftui-notes – the tests are in the UsingCombineTests directory, and set up as they’re own test target in the Xcode project. There are more to write, as I drive down into the various operators, so I do expect more will appear. I won’t assert that they’re all amazing, well constructed tests – but they’re getting the job done in terms of helping me understand how they work – and how they don’t work.

Sharp Knives

After writing extensively with the Swift programming language, I recently spent time writing code in C++11. The experience has been very instructional, and I know have a much deeper appreciation for the guard rails that the language Swift has constructed. To my surprise, it has also left me with a renewed appreciation of the compiler tooling – LLVM, specifically the relative clarity of error messages.

C++ as a language was significantly more approachable to me after working on code using Swift for a while. There are a lot of parallels and similarities, which was particularly nice since I was porting code (re-writing the algorithms in another programming language). I think porting between programming languages is the rough equivalent of translating between human languages. In really comparing to allow you to move between the two, you become far more aware of the idiomatic conveniences and conventions.

One of the surprisingly pieces is my realization that I am far more attached to the swift concept of protocols than I had realized. C++ has a concept of interfaces, which is close – but definitely not the same in it’s breadth.

When combined with generic algorithms, the swift language feels far more capable and specific to me. In the swift programming language, you can constrain the implementation of your generic algorithms to only apply to specific protocols, which appears to be something you can’t easily do in C++ – or at least in C++11, which was the version I was working within. I found that programming with generics in C++ is far more reliant on convention, or possibly using subclasses – examples were a bit hard to come by for me.

My limited experience with C++ also leads me to think that the conventions followed between different groups of programmers is more diverse than Swift. The idiomatic patterns I found while reading other groups code had dramatically different patterns included within them. So much so that it was often hard to identify those patterns, and understand what was a team’s convention.

My time with the C++ components also makes me appreciate all the more the tendency of languages these days (to borrow from Python) to come “batteries included” with standard libraries. C++ standard library is more like tools to make tools, and some of the things commonly included with other languages (python, swift, etc) just have to be found individually and assembled.

While I have a bit more to do with C++ before I’ll be done with my project, I relish shifting back to the guard rails of swift. (I must admit, I’m now significantly more curious about the language Rust as well).

iPad Lost Mode

This past Saturday, I was on a 7am EDT flight from Orlando, FL to Seattle, WA – which means I was up at 3:30am east-coast-time to make the flight. That would be pretty harsh, except that my normal timezone is 4 hours later than that. The flight was smooth, and I half-slept most of the time. I took out my iPad and put it into the seat back pocket to work on it or read a bit during the flight, but never used it.

The following day after we were home, I went to get the iPad – and realized to my horror that I’d never pulled it from the seat-back pocket. The data was fortunately backed up, but loosing the hardware – a gift last Christmas – wasn’t a hit I wanted to take. We called the airlines baggage team, and they put in a lost report. I was pretty sure it was gone and resigned myself that I’d have to replace it some months down the road. I could simply make do until then, feeling foolish for leaving it in the seat pocket when I was half-asleep.

I logged into the Find my iPhone app on my iPhone, and marked the iPad in “lost mode”. I wanted it found, and had never used this feature previously. I set up the message that it was lost, and included my phone number – which shows on the lock screen. It hadn’t been able to connect to any networks where it already knew the wifi, so it was just “missing” from that system, but if and when it did connect – it would drop into “locked/lost” mode.

On Tuesday, the airlines called me and let me know they’d found an iPad matching my description. After a brief discussion, we verified that it was indeed mine. Within an hour I had several options for getting it back; choosing to have it delivered. I was expecting it to arrive “some time before 8pm on Wednesday”.

On Wednesday, I was at my usual coffee-house haunt, and saw a notification in email – “Your iPad has been found”! I checked the location, and it was my home address! Wait – the email notification was from 30 minutes ago.. So I called my sweetie and she ran downstairs and found… nothing!

She ran around the outside of the house three times, looking for any place where the box might have been left, but nothing. We immediately thought “OMG, it’s been stolen from our front porch” – as there’s a thing in our neighborhood where package theft is pretty common.

After looking again at the Find My Phone app, I realized that while it was “found” – it reported as being on the street in front of our house – and only for a minute, before disappearing again into the mists of who-knows-where. In hindsight, I imagine that the Fedex driver simply happened to be passing near our house at 9:17a. It was going slowly enough that the iPad was able to finally make a wifi connection it knew and register itself. Fedex, who was delivering it, reported that it was still undelivered, so after an hour or so of “theft panic”, that faded into a vague concern and hope that it really was still out for delivery. Fortunately updates from Fedex are nearly real-time, so if they’re reporting it is still in transit, there can be a reasonable amount of confidence that it is.

Over the course of the day, the Fedex delivery driver wandered around our neighborhood, delivering all their various packages. I got 2 more pings from the iPad, which also reported that it was “playing a noise” since it was lost. In both cases, it was near wifi networks that I’d previously connected with, and it was in those locations for only a minute or two. I can only imagine the driver being confused, if they heard the sound at all, coming from the back of their truck.

It was finally delivered home, around 6pm – nearly nine hours after first reporting itself in the area. It was in lost mode, and I was able to log in and recover it – everything intact. I felt extremely relieved, and even more that fortune had sided with me that day. Many friends have done or reported something similar, and devices forever disappear after that scenario.

I should mention that the Alaska Airlines team was fantastic through out this whole nerve-wracking scenario. They were super understanding when I called in panic, thorough about verifying the device was indeed mine when the found it, and efficient after getting the reports filed, made available online to me, and really flexible delivery options – including allowing me to come pick it up if I wanted.

The “lost device” feature was lovely, except when it wasn’t. It was like hearing distant calls for help that you can reach in time; sort of like the terrible dream where you can never make it to the end of the hallway to escape whatever dread it coming. I don’t know that any capability or feature of the iPad that would have made that better, it was just hellishly nerve-wracking to wait while it yelped in the back of that truck, wandering our my neighborhood.

A Using Combine update now available!

A new version of Using Combine (v0.7) is now available! 

The free HTML site of Using Combine has been updated automatically, and the PDF and ePub versions are available on Gumroad.

This version has relatively few updates, primarily focused on some of the missing publishers and resolving the some of the egregious flaws in ePub rendering. No significant changes have come with the later Xcode and IOS betas, and with Xcode 11 now in GM release, it was a good time for another update to be made available.

For the next release, I am focusing on fleshing out a number of the not-yet-written reference sections on operators, most of which are more specialized than the more generally used ones that have already been covered.

The project board at https://github.com/heckj/swiftui-notes/projects/1 also reflects all the various updates still remaining to be written.