Diacode team here. Thank you for sharing the post. This article is part of an ongoing series of blog posts that covers the whole Trello clone / tribute that our colleague @bigardone did.
We didn't submitted it to HN before because we were waiting to complete the whole thing and create a proper index for all the articles. The part 6 will be published tomorrow and you can expect a few more articles in the next weeks.
I'd like to clarify that this is not a product, it doesn't cover all the awesome features that Trello has. It's just a learning experiment that we're sharing with the rest of the world.
Finally, to give you some background, we're a small Rails dev shop (5 guys) who works remotely. We're now playing with Elixir and Phoenix and having a lot of fun with it. I'd totally recommend any dev to play with Elixir, specially if you come from a Rails background.
Kudos to our colleague @bigardone for putting all of this together.
It would be good to add a "Next" link at the bottom of each part to go to the next part so people can click through instead of having to scroll to the top after reading each time.
I'm interested in learning React, but brand new to front-end tooling (npm/webpack/etc). When doing this tutorial I got derailed by npm start, and the host of errors it led me through.
Does anyone have any advice for learning the tooling pre-requisites that go along with React development? I'm happy to buy books, pay for courses, whatever it takes.
By the way, our whole site and blog is on GitHub, so if any of you guys want to contribute to any of the articles feel free to drop us a PR :)
https://github.com/diacode/diacode-website
I'm trying to work out how apps like this and trello calculate and store card poisition with as little overhead as possible.
It seems obvious that every time you move a card to a column, you recalculate the order of every card, however that has overhead because you have to send the new order of every card to the server.
Is there a more efficient way to solve this problem? It seems to me it would be more efficient to assign a position value for only the card you are moving relative to those before and after it.
Trello gives each card a `pos` attribute, which is simply a double (64-bit float). When the first card in a list is created, it is given a `pos` of 16384. When a card is added to the end of a list it is given <pos of last card> + 16384. If added to the beginning, it is given <pos of first card> / 2. If inserted between two cards, it is simply the average of the two neighbors.
Finally, if two cards end up with values too close together (just some magic number - .0001 apart or something) then those cards and some nearby are all re-numbered.
This means that most of the time you only have to update a single card. In degenerate movement cases, you might update up to an entire list, but that can only happen every so many moves (~20 or so, but depends on exact values) even in the worst case.
You can get much farther by storing a fraction. Still, a midpoint is not the most effective point to chose. One solution I've explored is in the form of fractions generated by the Stern-Brocot tree. The continued fraction representation is easy to work with and can easily be turned into other representations.
With that, you could pick ideal points between bounds very cheaply:
In languages with large integers, it's quite easy to store two numbers. In a language like JavaScript, 53 bits of the mantissa in a double floating point number give 70+ moves [1] before you'd have to worry about losing precision, and if that were a deal breaker, a continued fraction is very cheap to store instead.
If people are interested, I'd be happy to share some implementations I've got in a number of languages including Erlang and JavaScript (I'm rewriting these from a prior version I did which used a slightly less optimal path representation).
[1] These are worst case. Most interactions could survive 1000+ resorts in practice. I've yet to see any of the components outgrow the 53bit mantissa of a double in JavaScript. The worse case grows with the Fibonacci sequence which is easy to see once you learn more about the Stern-Brocot tree structure. Even when they do grow large though, it's easy to switch to the continued fraction representation which solves this problem.
Thank you very much. That problem was bothering me for quite a long time, but I couldn't figure out correct term for googling.
Another solution I made myself is just to use string as a key. If you need to insert something between "a" and "b", it'll become "an". If you need to insert something between "an" and "am", it'll become "ann", etc. It uses 26 letters but probably should use 64 different characters. This way you'll manipulate strings, they could be easily sorted and you'll figure out next string quite fast. But they could grow long, so entire recalculation should be done from time to time.
Yes. This is very similar if you consider the path on the b-tree with the alphabet L, R. It doesn't follow traditional lexical sorting though since RRL (5/2) comes before RR (3/1).
This is handy though. Consider having something at index 'a'. Now find something that comes right before it. You can't if you use traditional alphabetical ordering.
So, the problem with your approach is that Trello has an open API. This means that they don't control the clients, and also that the API needs to be reasonably easy to understand. "Sort by this attribute" for displaying and "pick literally any floating point number that sorts it into the right position" for moving cards is much easier to get across than what you're describing.
Sure, you'd need a library but the problem with integral sorting is that operations must be totally ordered. This starts showing limits under stress of heavy collaboration. There is more than one way to solve this but most solutions either have unstable merges or involve the same point on a number line concept.
The above might seem odd but is much more reliable than midpoints and not hard to implement. The representation of the index can use multiple formats, one of the easiest is just a pair of numbers in a fraction.
The problem with floating point numbers is that you'lol lose precision faster than you might expect. See my gist for an example of 40 fractions from a production database where there is no double precision floating point number between them.
Like I said, Trello re-numbers when things get to close together, so you never see something like that. Obviously there are trade-offs, but very occasional re-numbering vs. a ton more complexity seems like an easy decision.
"you'd need a library" is not a solution when you have API consumers in dozens of languages.
If you can sort fractions and call a function to get something between two points, then that's the entirety of the complexity. The "library" is about a hundred lines in JS and less in Erlang. The logic, which I have written in the past to do conditional reindexing has a worse interface and ends up with about the same LOC burden.
Seriously, I've done both of these and the complexity is about the same. One route just ends up with a much better separation of concerns where the other has surprising edge cases which I see hit far more often than I would have imagined.
The complexity sounds fairly similar, but my point is that there's a world of difference between server-side complexity (implement once) and client side (implement 3 dozen or so times).
Fair enough. Getting a usable API that works reliably here is tricky though. I've often fallen back to a sort of indirection like "move this card right after that one" ... this only works if you can calculate that right away since that card can be moved by some other agent.
I'll wrap up a new version of the library that's independent of what I have it hooked up to and upload it to npm and hex.pm respectively.
When I first wrote it, I started with midpoints but it doesn't take long to see that it gets messy to optimize. I eventually stumbled on the b-tree representation of all positive rational numbers (Stern-Brocot) and the optimization became obvious.
I'm dense. Why is it less effective to choose the midpoint fraction and more effective to choose with the Stern-Brocot tree? Is it just the growth/storage or are there other issues too?
Growth is one, the average term will be smaller. The real reason to pick this is that the tree is a b-tree so you can pick terms above and bellow, so you can end up with simpler terms, not just more complex ones.
Not sure why this got down voted. It's easy to see that points can be selected between two others that are parents in some cases. With mid-points, it usually mixes a fractional part like taking a midpoint 1/2 and then moving the upper bound so the next card is 2 and then moving something between 0.5 and 2. This ends up being a messier fraction.
Adding logic to pick 1 instead of 1.25 seems easy but there are a lot of edge cases and ends up creating something that is at least as complex as this simple binary tree that generates all positive rational numbers.
While interesting, I wonder if this makes any sense in terms of performance vs simply using a linked-list (or some kind of built-in equivalent, maybe backed by a binary tree, or something)? How many cards are you going to have in a given stack anyway? All you need is a list of card-ids (integers?) -- It's not like this has to run on a micro-controller...
I'm not sure if those are the meassures that guide the decision: Searching in linked lists is suboptimal (was it O(n)?), as is their cache performance. Sure, with small lists, that doesn;t matter, but how small is small enough?
Incredible. I'm actually scrolling HN during a break from 3 hours of trying to optimize a solution to this problem.
Came up with something like this but wanted to avoid ever having to update the entire list. A combo of Rubaxa Sortable's 'onEnd' option and Vue to render card properties in HTML attributes make it easy.
It's a bit more efficient than traditional ordering...
From the readme:
ranked-model is also optimized to write to the database as little as possible: ranks are stored as a number between -8388607 and 8388607 (the MEDIUMINT range in MySQL)
You might be able to watch the network tab in the chrome developer tools to see what they send back and forth. Trello also has an api that may prove illustrative.
A tip to everyone checking the codebase (JS parts) to learn about building a Trello-like application, there isn't any optimistic UI updates in this tutorial app. (eg. after dragging a card to another list, displaying the card at the dragged position before receiving confirmation from the server.)
When you add optimistic updates to the mix with real time updates, things get much more complicated. Tracking pending updates, rolling back when something goes wrong, ordering of updates, reconciliation with server when the client is missing some updates etc.
I'm building something similar, and these have been most time consuming parts to build in a reliable way.
Thats one of the really nice things about react: you can update the state on the clients copy of the board data, let react change the UI as required, then let the server send over the new state once it has one, update the clients state as required and let react deal with the ui updates.
As for reconcillation I would probably just have the server send over the entire current state of the board when the client connects. It is much easier and doesn't waste that much bandwidth, which is cheap anyhow.
The 'happy path' (everything goes right) is easy, as you said.
The hard part for me was making sure the state in the client is always in sync with server, in a valid state, even when things go wrong.
On a slow connection, another update made by someone else to board may arrive between the optimistic client update and the server confirmation, which can lead to a broken state on client.
Or, user may do an update on the optimistically added card, like editing, while the first action is not confirmed by the server yet. You either need to queue these actions, or generate the id of the card on client side. And you need to have reliable 'rollbacks' on the client when server rejects the action for some reason.
There are many more edge cases like that. I've solved all these problems eventually, but it took much more time for me than building the happy path.
> And you need to have reliable 'rollbacks' on the client when server rejects the action for some reason....'ve solved all these problems eventually, but it took much more time for me than building the happy path.
I'm sure you figured this out, but having an immutable data structure at the root of your React application is great for rollbacks. And then maintain an array with a reference to the various data structures, however deep you need (within reason), and pop or push them as needed to rollback/roll forward.
Yes, I'm using Redux, and never modify the state. But I also needed to rollback only the rejected action, and keep the rest of the actions that user did after the rejected action intact. That presented a whole lot of different edge cases.
I created a solution based on redux-optimist[1], modified to my apps specific needs.
Looks really cool except Part 2 where the ceremonious setup for the front-end part really point out the issue with JS right now. Other than that, great work!
"Need" is always such a strong word, but Phoenix is particularly well-suited to real-time applications, and can scale pretty ridiculously off of them.
Not to mention, Elixir is a joy to code in, and a lot of us are still experimenting with it, trying to figure out where it's going. So projects like this are a good outlet.
I haven't hit their site yet, but I don't think they're saying you need Elixir to build this kind of project. I think it's more along the lines of needing Elixir to build a tutorial series for Elixir.
As for the benefits of using Elixir, I'm not qualified to answer that since I've only skimmed the surface of what Elixir is (but it looks intriguing!).
Trello has a certain real-time aspect to it that lends itself very well with Elixir channels. (At least I assume this tutorial is going to use that for the realtime bit). Rails is coming out with something as well, called ActionCable.
And finally Meteor has it with utmost simplicity as well. Just save to the database and Meteor updates the data to everyone, automatically.
This use of "need" makes me wonder what the earliest tech is that you could use to build a trello-ish. I'm thinking it's doable with C, CGI, and xmlhttprequest....
Or a more closer-to-the-metal solution like Node.js?
Joking aside, I wonder if it's possible to write a real-time webapp with C and CGI. Ok, 'possible' is a strong word; but I'd really like to hear from someone who'd given this a try.
Back in the mists of time, there was a thing called CGI-IRC written in perl that you deployed as an nph CGI script and would then do real time comms; I think (vague memory) the original authors an ircatwork.com using it and then eventually started mibbit.
I don't recall seeing one written in C, I think the last time I saw a CGI script written in C was a some years ago version of Nagios
I'm more interested in the React part of this tutorial. If the backend was swapped with another framework. can the tutorial still be followed to learn React?
I just finished going through this http://survivejs.com/webpack_react/introduction/ whole thing building a kanban board using react and altjs. It was really interesting, though a much simpler version of what was posted in the OP I learned a lot about webpack and react, and got to try a different flavor of flux I hadn't experimented with before (alt.js).
I'm excited to dive into the OPs tutorial however. It looks really interesting.
We didn't submitted it to HN before because we were waiting to complete the whole thing and create a proper index for all the articles. The part 6 will be published tomorrow and you can expect a few more articles in the next weeks.
I'd like to clarify that this is not a product, it doesn't cover all the awesome features that Trello has. It's just a learning experiment that we're sharing with the rest of the world.
Finally, to give you some background, we're a small Rails dev shop (5 guys) who works remotely. We're now playing with Elixir and Phoenix and having a lot of fun with it. I'd totally recommend any dev to play with Elixir, specially if you come from a Rails background.
Kudos to our colleague @bigardone for putting all of this together.