Bigcanvas
Ladies and gentlemen, Frozen Fractal presents… Bigcanvas! It’s an infinite online canvas that anyone can draw on. The ‘why’ is described within the app itself, so have a look! This blogpost focuses on the technical aspects, i.e. the ‘how’.
Just for fun and challenge, efficiency was one of the main design goals. This mainly manifests itself in the design of the server, storage format and the wire protocol. But to understand those, you first need to know how things fit together in the web browser.
Client
The canvas is broken up into blocks of 512×512 pixels, each with base 64 integer coordinates. We indicate the particular point within a block with another pair of integer coordinates, in regular decimal notation this time. Each block is drawn on screen using a HTML5 canvas element. Scrolling means simply moving the canvases around, and adding and removing them as needed.
Drawing is a bit trickier. Because the canvas is broken up into blocks, a single line segment may overlap multiple blocks. We could simply draw it in all of the blocks that it overlaps, and rely on the canvas to clip it correctly. The problem is that the coordinate range within a block is limited (by the wire protocol, see below), so not every segment can be represented within each block. We therefore need to clip the line segment manually to fall within a small margin around each block. That’s all done on the client side.
Wire protocol
At no point do we send or store pixel data. Instead, we work with ‘strokes’, i.e. a series of points that together make up a squiggle that the user drew.
Strokes are sent to the server via HTML5 WebSockets. This was a challenge, because the WebSockets standard does not (yet?) allow transmission of binary data, and mandates the use of UTF-8 strings. Invalid UTF-8 causes the connection to close. Note that UTF-8 may not contain null ('\0') bytes. Code points between 1 and 127 (inclusive) are encoded as themselves. Code points of 128 and up require more than one byte to encode and are therefore quite wasteful. So the wire protocol was designed to use only bytes in the range 1–127.
By far most data sent across the wire will consist of strokes, so it is important to represent these efficiently. I started out with 127×127 blocks, so that each coordinate within a block would fit in a byte. A stroke would thus look like xyxyxy.... But I soon discovered that this block size was too small, causing things to work slowly on Firefox and to a lesser extent on Chrome. So I switched to 512×512 blocks. Now this requires 9 bits per coordinate. The trick I use is to break each coordinate (x and y) up in a part modulo 127 and a part divided (rounding down) by 127. The modulo part fits in one character; the other part is at most 4 so it fits in 3 bits. Those 3 bits from x and y combine into 6 bits, which fit into another character. So each point is now three characters:
x%127 + 1y%127 + 1(((x/127) << 3) | (y/127)) + 1
It’s ugly, but it works well. All the encoding and decoding is done on the client side; the server is just a dumb data switch and does not need to know the format, except to the extent that it can check it is valid (which is easy and fast).
For extensibility, the string with coordinates is wrapped inside a JSON object. Later on, I might add stroke properties such as width and colour.
Subscriptions
Of course, we wouldn’t want to send the entire canvas contents to a client when they connect. Therefore, a client sends ‘subscription’ messages to the server, requesting to be kept up to date on the contents of particular blocks. When one of these blocks changes, the server pushes out the new strokes (but not the existing ones) to all subscribed clients. When a block scrolls out of view, the client sends an ‘unsubscribe’ message so it no longer receives updates.
Server architecture
The server is written in Google’s Go. This entire project was in part an excuse for me to become familiar with that language. If you’ve never seen Go before, you can think of it as high-level C with garbage collection and very powerful and easy to use parallelization primitives.
Currently, the server is not distributed in any way; it just runs on a single machine. I did design it so that it can easily be sharded if the need arises. This could be done by region in the canvas (each server serves a particular area) but this would create hotspots if many users are active in the same area. It could also be done by hash (each server serves a set of blocks based on a hash of their coordinates), but this requires a client to have connections to many more servers, and open and close them as they move around. Neither solution is ideal; probably some area-based approach combined with splitting/combining of areas is most scalable. But that’s for another day.
Storage
Blocks are stored on the filesystem in flat files, one file per block. For small blocks (< 1 kB) this is a bit wasteful, but it will have to do for now. Of course, empty blocks are not stored at all, which is part of the secret ‘infinity’ sauce.
To avoid filesystem limits on the number of files per directory, we compute the SHA1 hash of the block’s coordinates, take the first three and second three characters, and create a directory structure out of that. As an example, block 3,5 would be stored in the file 95a/c05/3,5. If we conservatively assume a maximum of 4096 files per directory, this allows for 2³⁶ files. If each block is 4 kB, this takes 256 TB of disk space, so the directory structure is not going to be the limiting factor.
Inside each block file, the strokes are concatenated as a series of strings, each prefixed with a header specifying the length. This format is exactly the same as the wire format, which means that if a client requests a block, the server can simply and brainlessly stream out the entire file.
The advantage of flat files is that we can trivially append to them. If someone draws a new stroke, we simply append it verbatim to the existing file. This is implemented in the server code by storing the stroke in a Go ‘channel’. A single goroutine runs an infinite loop that takes strokes from the channel and writes them to disk. This prevents problems with concurrent writes, and ensures the least amount of disk thrashing (although I still expect disk seeks to become the first performance bottleneck).
This storage format is far from efficient, but it was easy to implement. The server currently caches all data into memory anyway, so as long as that still fits, it doesn’t really matter.
Limitations
Of course, a truly infinite canvas is impossible, because computers have limited memory. Even if we don’t store the actual contents, even the coordinates themselves can become arbitrarily large. But I’ve given it my best shot, storing coordinates as strings in base 64. Assuming that we’ll hit some limit at 256 characters (be it URL length or filename length), this gives 64²⁵⁶ different coordinates. This number is so large that even Google’s built-in calculator refuses to compute it. But we need two of these babies, an x and a y coordinate, so that leaves ‘only’ 128 characters each. On an 80ppi screen, this comes down to 2.5 × 10²³⁰ metres. For reference: the size of the visible universe is only about 10²⁴ metres.
Social aspects
Frankly, this is a bit scary. I intentionally did not add an erase option, and this thing is open to the entire internet, entirely anonymously. I have no idea what this will lead to. Will it bring out people’s inner artist and allow beauty to be created? Will people find a use for it, such as online collaborative sketching? Will it become a display of love, like when people carve hearts into tree barks? Will the immature insist on drawing penises all over the place? Will griefers paint everything black and ruin it for everyone? I have no idea, and that’s exciting!