Reddit opened a self-expression page in honor of April Fools, but the project, created as a joke, has become a kind of wall for collective graffiti from participants from around the world, showing what mark they want to leave in history.
On April 1, Reddit launched the Place project, a page with a blank canvas on which each forum user could draw any image. The artists had limitations: they could only draw one pixel of one of the 16 colors every five minutes, and the size of the canvas was also limited. On top of the drawn pixels, you can draw others (and then the first author can again draw his own pixel on top of the opponent's pixel), which is why the authors of the images a priori conflict. As indicated in the description of the canvas, the project is designed for joint creativity - “Each of you can create something individual. Together you can create something more.”
At the start of the project, everyone literally pounced on the canvas - every pixel on it was filled. At first, users simply poked color into free pixels, but then teams began to form, which began to draw one of the simplest possible ideas that finds like-minded people - state flags. The more users worked on the canvas, the more interesting and complex ideas came to their minds. And "The Place" has evolved from an April Fool's project to a place where users from all over the world come together in real communities to show something to the world and support their creation from groups of raiders who really just also want to draw some kind of their own drawing.
Place during the first hours of operation
"The Place" has become an online sticker board, but each of them is created with great difficulty. For example, to draw a 48 x 68 pixel Linux logo and protect it from squatters requires 3,264 people to draw at the same time.
Users come together to implement ideas that are smaller and simpler, but still very team-oriented, like this row of hearts with flags different countries(and not only): everyone is responsible for "their" heart, but all together people unwittingly form one team.
And others write whole canvases of text, for example, like this group of fans " Star Wars", who wrote and maintains Supreme Chancellor Palpatine's famous monologue about the Sith Darth Plagueis from the third episode of the space saga.
However, some users complained that the project participants "planted" bots instead of themselves, which automatically update the pixel occupied by the author every five minutes. Despite the fact that when drawing each pixel, the user needs to repeat a set of actions (for example, choosing a certain color), some have been able to bypass the protection mechanism and create bots that draw pictures for them.
However, there are those who still create special threads, trying to call on like-minded people who will help draw and leave for future generations something like ... puke Rick Sanchez from the Rick and Morty cartoon. Seriously? Are they really not bots?
After 72 hours of work, the project was closed. The administration of the resource thanked everyone for their participation and for the fact that people united "to create something more."
Reddit often becomes a place for various social activities. For example, recently sad users of the resource decided to ask what it's like to wake up every day with a smile. And before that, Reddit readers shared stories about girls with each other. Not only anonymous people are sitting on the popular resource: recently the actor answered questions from users about the film “Trainspotting” for several hours.
To begin with, it was extremely important to determine the requirements for the April Fools project, because it had to be launched without “overclocking” so that all Reddit users would immediately have access to it. If it had not worked perfectly from the very beginning, it would hardly have attracted the attention of a large number of people.
The "board" needs to be 1000x1000 tiles in order to look very large.
All clients must be in sync and display the same board state. After all, if different users have different versions, it will be difficult for them to interact.
You need to support at least 100,000 users at the same time.
Users can place one tile every five minutes. Therefore, it is necessary to maintain an average update rate of 100,000 tiles per five minutes (333 updates per second).
The project should not negatively affect the work of other parts and functions of the site (even if there is high traffic on r/Place).
- In case of unexpected bottlenecks or failures, flexible configuration must be provided. That is, you need to be able to adjust the size of the board and the allowed drawing frequency on the fly if the amount of data is too large or the refresh rate is too high.
Backend
Implementation decisions
The main difficulty in creating the backend was to synchronize the display of the state of the board for all clients. It was decided to have clients listen for tile placement events in real time and immediately request the state of the entire board. It is acceptable to have a slightly outdated full state if you subscribe to updates before the full state was generated. When the client receives the full state, it displays all the tiles it received while waiting; all subsequent tiles must be displayed on the board as soon as they are received.
For this scheme to work, querying the full state of the board must be done as quickly as possible. At first, we wanted to store the entire board on one line in Cassandra, and have each request just read that line. The format for each column in this row was:
(x, y): ('timestamp': epochms, 'author': user_name, 'color': color)
But since the board contains a million tiles, we needed to read a million columns. On our production cluster, this took up to 30 seconds, which was unacceptable and could lead to excessive load on Cassandra.
Then we decided to store the entire board in Redis. We took a bit field of a million four-bit numbers, each of which could encode a four-bit color, and the x and y coordinates were determined by the offset (offset = x + 1000y) in the bit field. To get the full state of the board, it was necessary to read the entire bit field.
Tiles could be updated by updating values at specific offsets (no need to block or do the whole read/update/write procedure). But all the details still need to be stored in Cassandra so that users can find out who posted each of the tiles and when. We also planned to use Cassandra to restore the board when Redis crashed. Reading the entire board from it took less than 100 ms, which was quite fast.
Here's how we stored colors in Redis using a 2x2 board as an example:
We were worried that we might run into read throughput on Redis. If many clients were connecting or updating at the same time, then all of them simultaneously sent requests to get the full state of the board. Since the board was a shared global state, the obvious solution was to use caching. We decided to cache at the CDN level (Fastly), because it was easier to implement, and the cache was closest to the clients, which reduced the response time.
Full board state requests were cached by Fastly with a timeout per second. To prevent a large number of requests when the timeout expires, we used the stale-while-revalidate header. Fastly supports about 33 POPs that cache independently, so we expected to receive up to 33 full board state requests per second.
To publish updates to all clients, we used our websocket service. We have previously used it successfully to power Reddit.Live with over 100,000 concurrent users for live private message notifications and other features. The service was also cornerstone our past April Fools' projects - The Button and Robin. In the case of r/Place, clients supported websocket connections to receive real-time updates on tile placements.
API
Getting the full state of the board
At first requests got to Fastly. If it had a valid copy of the board, then it immediately returned it without contacting the Reddit application servers. If not, or the copy was too old, then the Reddit application read the full board from Redis and returned it to Fastly to be cached and returned to the client.
Please note that the request rate never reached 33 per second, i.e. caching with Fastly was very effective tool protecting the Reddit app from most requests.
And when requests did reach the application, Redis responded very quickly.
Tile drawing
Stages of drawing a tile:
- The timestamp of the last tile placed by the user is read from Cassandra. If it was less than five minutes ago, then we do nothing and an error is returned to the user.
- Tile details are written to Redis and Cassandra.
- The current time is recorded in Cassandra as the last time the user placed a tile.
- The websocket service sends a message about the new tile to all connected clients.
In order to maintain strict consistency, all writes and reads in Cassandra were performed using the consistent level QUORUM .
In fact, we had a race here whereby users could place multiple tiles at once. There was no blocking in stages 1-3, so simultaneous attempts to draw tiles could pass the test in the first stage and be drawn in the second. It seems that some users found this bug (or they used bots that ignored the limit on the frequency of sending requests) - and as a result, about 15,000 tiles were placed using it (~0.09% of the total).
Request rate and response time as measured by the Reddit app:
The peak tile placement rate was almost 200 per second. This is below our calculated limit of 333 tiles/s (average assuming 100,000 users place their tiles every five minutes).
Getting details on a specific tile
When requesting specific tiles, data was read directly from Cassandra.
Request rate and response time as measured by the Reddit app:
This request proved to be very popular. In addition to regular client requests, people have written scripts to retrieve the entire board one tile at a time. Since this request was not cached in the CDN, all requests were served by the Reddit application.
The response time to these requests was quite short and kept at the same level throughout the life of the project.
Websockets
We don't have separate metrics showing how r/Place has affected the performance of the websocket service. But we can estimate the values by comparing the data before the start of the project and after its completion.
Total number of connections to the websocket service:
The base load before the launch of r/Place was about 20,000 connections, the peak was 100,000 connections. So at the peak we probably had about 80,000 users connected to r/Place at the same time.
Throughput of the websocket service:
At peak load on r/Place, the websocket service was transmitting over 4 Gbps (150 Mbps per instance, 24 instances in total).
Frontend: web and mobile clients
In the process of creating the front-end for Place, we had to solve many complex tasks related to cross-platform development. We wanted the project to work the same on all major platforms, including desktop PCs and mobile devices on iOS and Android.
The user interface had to perform three important functions:
- Display board status in real time.
- Allow users to interact with the board.
- Work on all platforms, including mobile applications.
The main object of the interface was the canvas, and the Canvas API was perfect for it. We have used the element
Canvas drawing
The canvas had to reflect the state of the board in real time. It was necessary to draw the entire board when the page loaded and finish drawing updates coming through web sockets. A canvas element that uses the CanvasRenderingContext2D interface can be updated in three ways:
- Draw an existing image on the canvas with drawImage() .
- Draw shapes with different methods drawing forms. For example, fillRect() fills a rectangle with some color.
- Construct an ImageData object and draw it on the canvas with putImageData() .
The first option did not suit us, because we did not have a board in the form of a finished image. There were options 2 and 3. The easiest way was to update individual tiles using fillRect() : when an update comes through the websocket, just draw a 1x1 rectangle at position (x, y). In general, the method worked, but was not very convenient for drawing initial state boards. The putImageData() method was much better: we could determine the color of each pixel in a single ImageData object and draw the entire canvas at once.
Drawing the initial state of the board
Using putImageData() requires defining the state of the board as a Uint8ClampedArray , where each value is an eight-bit unsigned number between 0 and 255. Each value represents some color channel (red, green, blue, alpha), and each pixel needs four element in the array. A 2x2 canvas requires a 16-byte array where the first four bytes represent the top left pixel of the canvas and the last four bytes represent the bottom right.
Here's how the canvas pixels are associated with their Uint8ClampedArray representations:
For the canvas of our project, we needed an array of four million bytes - 4 MB.
In the backend, the state of the board is stored as a four-bit bit field. Each color is represented by a number between 0 and 15, which allowed us to pack two pixels into each byte. To use this on a client device, you need to do three things:
- Pass binary data from our API to the client.
- Unpack data.
- Convert 4-bit colors to 32-bit.
To transfer binary data, we used the Fetch API in those browsers that support it. And in those that do not support, used XMLHttpRequest with responseType set to "arraybuffer" .
The binary data received from the API contains two pixels in each byte. The smallest TypedArray constructor we had allows us to work with binary data in the form of one-byte units. But they are awkward to use on client devices, so we unpacked the data to make it easier to work with. The process is simple: we iterate over the packed data, pull out the high and low bits, and then copy them into separate bytes in another array.
Finally, four-bit colors had to be converted to 32-bit.
The ImageData structure we needed to use putImageData() requires that final result was in the form of Uint8ClampedArray with bytes encoding color channels in RGBA order. This means that we had to do one more unpacking, splitting each color into component channel bytes and putting them in the correct index. It's not very convenient to do four writes per pixel. Fortunately, there was another option.
TypedArray objects are essentially array representations of ArrayBuffer. There is one caveat here: multiple TypedArray instances can read from and write to the same ArrayBuffer instance. Instead of writing four values in an eight-bit array, we can write one value to a 32-bit one! By using a Uint32Array to write, we were able to easily update tile colors by simply updating one index of the array. True, we had to save our color palette in byte-reversed-byte order (ABGR) so that the bytes automatically fall into the correct places when read using Uint8ClampedArray .
Handling updates received via websocket
The drawRect() method was well-suited for drawing pixel-by-pixel updates as they were received, but there was one weakness: Large chunks of updates coming at the same time could lead to stuttering in browsers. And we understood that updates to the state of the board can come very often, so the problem had to be solved somehow.
Instead of immediately re-rendering the canvas every time we receive an update via websocket, we decided to make it so that websocket updates that arrive at the same time can be bundled and rendered in bulk at once. To achieve this, two changes were made:
- Stop using drawRect() - we found convenient way update many pixels at a time with putImageData() .
- Transferring canvas rendering to the requestAnimationFrame loop.
By wrapping the render in the animation loop, we were able to immediately write websocket updates to the ArrayBuffer while deferring the actual rendering. All websocket updates arriving between frames (about 16 ms) were bundled and rendered at the same time. Thanks to the use of requestAnimationFrame , if the rendering took too long (longer than 16ms), it would only affect the refresh rate of the canvas (rather than degrade the performance of the entire browser).
Interaction with canvas
It is important to note that the canvas was needed in order to make it more convenient for users to interact with the system. The main interaction scenario is the placement of tiles on the canvas.
But rendering each pixel accurately at a 1:1 scale would be extremely difficult, and we would not avoid mistakes. So we needed zoom (big!). In addition, users needed to be able to easily navigate the canvas, as it was too large for most screens (especially when using zoom).
zoom
Since users could place tiles once every five minutes, placement errors would be especially frustrating for them. It was necessary to implement a zoom of such a multiplicity that the tile would be large enough, and it could be easily placed in Right place. This was especially important on touchscreen devices.
We implemented a 40x zoom, that is, each tile had a size of 40x40. We wrapped the element