Scaling One Million Checkboxes 

Just make a microservice for each bit

Every checkbox checked spins up a docker container.

"Bytes are stored in the balls, right next to the microplastics-"

The establishment: There's no way society wouldn't crumble if we reduce working hours by 1 hour per day The world's population during work hours: checking boxes

Imagine creating a small site that hits the mainstream media. Marketing: That would be GREAT! Engineering: That would be AWFUL. All you need to know right there.

The fact that some nerd tried to DDOS the silly check box website

I really appreciate how you brainstorm how things could be done before learning how the author actually did it. Really a good way to teach and really interesting to see the different ways to approach the problem.

plot twist: brown hat hackers == cloudflare security (sales) team

Middle Management Simulator 2024

After watching through this whole thing, I can't help but be reminded of the write ups that Reddit did for r/place. The most interesting/technical one was for the 2022 version where they talk about doing a lot of these same things. "I-Frame" updates with websockets for difference updates, managing how to store the data in the backend, and even a little bit about scaling at that level. What I like about this article though, is that it's just one dude with some help from a couple of friends. It's much more of a feel good story than when a corpo does something similar.

I’m gonna be honest…. I’m feeling out of the loop because this is the first I have heard of this lol.

What I would have done. 1. Put the "entire page data" endpoint behind a CDN with a ttl of 1 second. That way your app server only gets 1 request for the entire state per second and the cdn handles scaling and distribution. 2. Perform delta updates via websocket, also sending a checksum across. If after the delta is applied the check sums don't match, fetch from cdn again.

I would like to mention something about the "bool" being 64 bits long. You are absolutely correct that it depends on which system it is, but the actual length itself depends on the implementation for the language. For example, C++ bool's are 8 bits long (a byte) because that is the smallest addressable size you can have.

The guy had a in-house server but uses a Cloud solution for DB. GENIOUS.

An easy optimization would be to just send 10k checkboxes at once. Anything not visible is not interesting to the user, so no need to send to full million to them

This kind of content from prime is gold. Explaining simple stuff like a pro

Shifting bits can be done quickly and efficiently because the ALU has a "Shift Register" which implements an extremely efficient bit shift operation.

reminds me of the one million dollar website 😂

Brother, bool is only 8 bits, not 64. The only time wastes that much space is if you're doing something like (u64, bool) which would take a total of 128 bits due to alignment and padding.

Do note that the bitset implementation requires neither divisions nor modulo. Because i / 8 == i >> 3 and i % 8 == i & 7, so the lookup would be const bit = (arr[i >> 3] >> (i & 7)) & 1; I believe.

There is also 2 million checkboxes in Elixir

The guy who made this is a genius. Almost as smart as the Banana guy.

9:48 he really just said that? Struct with 3 bools is 3 bytes in size with align of 1.

I had a feeling prime would take this and spin into an hour long video. Not complaining though :D

42:23 “he’s also probably not a furry” rookie error on his part.

Fighting the masculine urge to make 1 Billion Checkboxes

b-frames (past future frames/pixels) are just content that didn't change between 2 frames or at least didn't change too a degree where they'd be included in a p-frame. During streaming that would be your static images/banners or your mic.

"Bytes are installed in the balls right next to the micro plastic" TheOldPrimy, Ex FAANG engineer.

Server gives static webpage content. client randomly check and uncheck boxes to simulate other users. Nobody’s the wiser

14:05 - I'm unsure Redis makes sense here… if your entire app lives on 1 or 2 instances on the same machine, then all Redis does is add latency to an otherwise simple operation/sharing of data.

This might actually make a great interview question for Senior Engineers.

i know next to nothing about software engineering. this is so entertaining, i'm learning a lot

This is like listening to a junior engineer who just learned basic RLE concepts.

There is a Vector Array. It's basically an array that gets bigger and smaller as needed. Like a dynamic array . They are useful

watching prime react to anything makes it 100x better

Brown Hat! What a designation (do refrain from visually imagine that). Will adopt

@ 9:44 -> Fake news! booleans in rust don't take up 64 bits, they take up 1 byte or 8 bits. A struct of 3 bools takes up 3 bytes You can test this by inserting the following in the rust playground: struct Bools { foo: bool, bar: bool, baz: bool, } fn main() { // Returns the size of a type in bytes. let size = std::mem::size_of::(); assert_eq!(size, 3); }

When he talks about using bitset, I'm pretty sure he means something like this -- A single byte is represented by 8 bits: 0000 0000 Each bit can be represented in-place as the decimal version of the 1 byte value: 64 = 1000 0000 // 4 = 0000 1000 etc You can "set" or "get" a boolean value (represented by a single bit) from this "array" of bits using bitwise ops and that single byte value to represent the place for the bitflag. That means you can effectively store 8 boolean values with just a single byte. A checkbox is a boolean value in this case. So you can get 8 checkboxes into a single byte. Hope this clarifies.

YEeeeSsssss……. BROWN HATS! Epic

“This guy is gonna get hired” took me out. Nolen used to work for Jane Street!

6:40 I would assume that they would do something like this: u8 data[1000000 / 8] = {0}; void flip(u32 index) { u32 offset = index / 8; u8 bit = index % 8; data[offset] ^= 1 > bit) & 1; }

Every checkbox, creates the next gen javascript framework.

Prime makes a 49 minute video about scaling 1 million checkboxes. Liveview does it with no scaling at all. Elixir on top as usual.

0:32 Its the Internet equivalent of bursting bubble-wrap...? ✌🏼💕

knowing bit math should be a mandatory prerequisite for all programming jobs.

16:00 On the update channel I would just send 64 bit (or maybe 32 bit) word updates with the word index (which is just 2 byte long), so 10 bytes (or 6). And if you can batch outgoing updates then array of these index, word records. With sending just 100 bytes you can update 10 sparse bit change to 640 bit change. With just 1 bit change you can sync 63 additional nearby bit.

Hey Prime, you were partially correct on one part. In C/C++ and most other languages, a struct of 3 booleans (or 1-8 booleans) takes up 64 bits on a 64 bit machine; 8 bits per boolean + padding to fill the struct to an aligned size. I don't know about Rust, but I strongly would suspect that Rust does the same. The CPU indeed has to read from memory with 64 bits at a time, so the entire struct is read at once. Accessing members of the struct is architecture and compiler dependent and it varies wildly what optimizations are done compile-time that affect how the underlying members are accessed. Storing 64 bits per boolean regardless of the amount of booleans in the struct would be a tremendous waste and would cause significant performance issues (think cache misses etc.).

(Did not finish the video, just putting in what I think is the reasonable way to do it, if you knew you would need to scale) You could just give the initial state to the user, make the client send updated checkboxes to the server as it goes, and then every 5 seconds or smth like that giving back to every users a patch of what's been happening the last 5 seconds which you would display to the user for the next 5 seconds as if it is happening in real time, made me remember a bit how Reddit did r/place.

And people still say "No need to scale it up to thousands of users when your only going to get 1 user."

this is one big visual metaphor for companies pretending to care about safety or going green, checking boxes

9:28 "There is no such thing as a vector of bits" to this I ask, what do you thing *vectorization* on many modern desktop CPUs actually is? Theyre instructions made specifically for performing operations on **bit vectors** (and other vector types too for your add/subtract/etc) but your bitwise operations are still valid! I've seen resizable bit vector implementations specifically so these instructions can be optimally made use of!

I just checked a whole bunch of boxes in the shape of the word “GYATT” lol

"taught the client" is the official style for commit messages in the Linux kernel

myself recently dealing with processor architecture can say the smallest unit the CPU can handle is 8 bit for GPIs but there are specific x86 instructions that allow a operation on a singular bit so a vector could be posibleish but yes even that implimentation would not change the fact that pages, lines are read at a time not only a bit

Take a shot for every box checked.

10:15 Actually, no. Most archs can read down to an individual byte, including x86 Edit : Also bit shifts / mods / divs aren't done in constant time but on x86 it's done by the end of the cycle (For div i am not sure but i assume)

i dont know why i got recommended this video, i know nothing about web servers, but im enjoying every *bit* of this video.

7:40 I had to store a giant 3d grid of 1-bit cells, and I did pretty much exactly this

I recently had a personal project go semi-viral in a niche twitch community and had to deal with many of these same issues, from late night panic scaling to shit hat hackers. Thanks for covering this story.

For a bitset: you can mask the 6 (for 64 bit words, i.e. u64) lowest bits with AND (mask 0x63) to get a bit address and right shift by 6to get the array index. If the array is U8 both AND and shift would be 3 bits (mask 0x07, shift 3). You would, in a case like this, not want to address each bit individually you can use the U8 to do a lookup into an array or even a switch. You would treat the word as a block and read the all at once (8, or word size, checkboxes at a time).

I believe I will have to read this article multiple times to just understand everything fully. But that just shows how much this guy has learnt from this project

Just a side line about bitsets. In languages that support them (or at least the ones I have worked on) they are literally a pointer to the start of some assigned memory, then the bits are not set in the logical manner, but instead set up so that we can logic them out with a PEXT between the bit request index (appended to it's inverse) then an xor between the returned byte, the repeated request index, and some magic constant. It was an insane bit of dark arts maths, but it is truly static time.

I don't think brown hacking was intentional , this started to become a game for people playing a game of king of hill

bro be checking boxes

A bool is 1 byte. A cpu can 100% read and write 1 byte. Some CPUs like AVR can do bit level manipulation too, but the instructions can only execute on certain address ranges, I believe on registers.

10:00 They meant specialization of vector that bit packs many bools into single adress. It is default in C++ vector and in rust there is so called bit-vec

This was quite insighfull. Thank you

You guys are silly, firestore documents charge per read so use base 64 encoding to store checked state and index with ads to pay for the read write cost XD

World of Warcraft's user interface is written in LUA... that language is used in so many weird places.

I saw this article and started reading it, but my eyes glazed over and my brain wouldn't engage, despite being really interested i was just too tired. Reading through it with you and your commentary was so much better, thanks.

"nagle is spinning in his grave" lmao xddd

I love how I have no programming knowlage outside of basic python yet im here, listening to Prime saying magic words and pretending I'm a big boy and who understands everything 😎

I don't write Rust but I'm pretty sure a bool in Rust would be 8 bits (single chars), not 64. While yes technically you're not going to be loading a single char into a register, there's machine language instructions for manipulating individual bytes. An array of bools will be just (without extra work) an array of chars. Yes you technically have to worry about things like unaligned accesses and the like but the compiler is smart enough to handle that. So for example a struct with four bools can be packed into the same size as a regular int.

Each checkbox turns on a physical server to store the bit

9:50 I can find literally zero evidence for this assertion. Even looking online the worst case I can find people citing is that the LLVM will generally assign each boolean to an i1 and assign one byte to each boolean. I cannot find a single source corroborating that it assigns 64 bits to each boolean. C *_also_* generally assigns 1 byte to each bit as far as I'm aware but if you have a struct of several bits then they can share the same byte. I could be wrong on this, I never quite got a firm hold on packing bits, but I think this is the case. The reason Rust doesn't is (as far as I can tell) 1 : because then they can't be referenced easily. (if you use other datastructures that forego this requirement they can pack bits in together) In theory I think this could be sidestepped in the compiler, but it'd be rather complex to add. 2 : "it's complex, if you pack them like that it's slower because then to reference any individual bit you need to use bitshifts and bitmasks!" no, just, just no. This is just more "hur de hur premature opimiztion rut of ahl EVIL!" waffling. Realistically for most operations you'd only need to do a predetermined bitmask but even if you *_did_* need to do both a bitmask and a bitshift those are like the two fastest operations a CPU can possibly perform so the memory savings would dramatically overcompensate for any possible CPU slowdowns. Oh, also caching is a thing. Having them packed together would improve the spatial locality of the data thereby improving cache hits, making it faster. So, no, this is just wrong, stop saying it. What you mean by "premature optimization is the root of all evil" is "I'm too lazy and/or bad to write good code". 3 : lack of demand given how much effort it'd take to make it happen, plus how easily sidesteppable it is with dedicated bitfield crates and such.

learning a ton from this simple little project

In a DB make a state variable with 1,000,000 bits, whenever a checkbox gets toggled i.e. checked or unchecked. A request is sent to the DB about which bit to flip. Here for example if we send 34 then the 34th bit will toggle and a update would be broadcasted on all active devices giving them the data of 34. This prevents multiple read from the variable with 1,000,000 bits. This variable would only be read by the client side on initiation of the webpage or reload/refresh of it. you can duplicate the variable to attain a historical record and increment a counter for every request sent

The size of a bool in rust is 1 byte, and it can be aligned to the byte (on most archs), you can look it up, I just did

You could have easily explained it by referencing the C# BitArray struct. Bool in almost every language is at least the same size as char/u8, and BitArray is 8 of those ... 8*8 = 64 bits (8 bytes) to store 1 byte, and most programming languages do this similarly if they have a similar function. When I emulate 8bit and 16bit CPUs, I always use the relevant data type (u8 or u16) specifically for that reason - I've already got my word size available and I can just use boolean operators to get the value of the specific bit and go on from there. One thing you are missing though, is that no just because you're targeting x64 instead of something else, that doesn't automatically make the data type jump up. I target exclusively x64 in visual studio, my base int size is still 4 bytes (32 bit). And I didn't set it up to do that, it just came default that way for me. A CPU can and will pull increments of data, as long as it's not single bits (as you said), but it only pulls what it needs. An ASM instruction exists even now for grabbing 8 bits of memory in the ISA (this is why in programming languages, the smallest real data types are 8 bit - which reinforces what you were trying to say: there is no CPU instruction in any consumer ISA that pulls less than 1 byte of data), and this is what is run when your code is compiled. In both C++ and C# I have to manually use the 64 bit data types to make my ints hold that value, or change some compiler flags. Also, 64 bit CPUs can address 128bits of data. This isn't even new tech, as even the OG GameBoy, with its 8bit Z80 like cpu could address 16bit addresses, by combining two registers and treating them as one (which is, as far as I know, how current gen 64bit CPUs address 128bits). It's all dependent on what instructions are implemented at the hardware level. Edit: The C++ equivalent to C#'s BitArray is BitField. Although, instead of it being a struct of type Bool (which in C#, is itself a struct if memory serves... why I'll never know), it can be a collection of any integral type according to cppreference

I'm waiting for the Elixir rebuild of this site

Best read of the year so far.

I like brown hat hacker. But you know that's essentially what hacking started as. Breaking it because it's fun and interesting to do. Although like you said the target matters so I think brown hat is applicable for yeah just personal neat projects and stuff especially single owner sites with essentially no sec infrastructure.

5:27 wouldn`t it be better if we ignored single cases? So we would have 4W2JD or even ignore doubles, having the same lenght as 4WJJD

Wow, thats top Content. What a great rundown and so good written.

It is a set because ordering is not important. We are never going to want to loop through it in a way that depends on order, so calling it an array would be over specified. Additionally, we don't care about adjacency in memory, so it would be perfectly reasonable to separate it into chunks, and store them without hard layout constraints on them. It will be bit arrays somewhere down there, but it does make sense to hide it behind an abstraction. If you decide later that you need a specific implementation then you can build that without violating the specification of the bitset then you can do that without expecting other things to break. Also, while some of the brownhat stuff was definitely dickish (DDoSing is not clever or novel), the person that checked box 100 million might not have been. If Redis expanded that set to that size automatically with just one set, you would only need one person with QA instincts to try it once. That doesn't need malice.

x >> 4 is the same as x / 8, and x & 7 is the same as x % 8. There's no need to manipulate a bit set using any actual arithmetic operations. Also, 32-bit operations would be more efficient, so Uint32Array instead of Uint8Array.

Protobuf would go crazy here. The binary representation would be super easy and you can enable gzip compression over the wire trivially if I remember right. Protobuf with like ZeroMQ would be so fast here.

this is like cookie clicker; folk have too much time on their hands

Nginx with flask and gunicorn and redis was always my favorite.

Lithuania mentioned!!! Woop woop!

03:27 No way 😂💀

man never heard of bitsets after 10 years of programming, things happen

Wait.. I've been watching the second Channel this whole time without knowing there was the first one 😮

The part where prime is explaining architecture cpu byte chunking was hilarious to see him realize "I'm dealing with a young troll." At least you know you have some young blood in your chat. That's good -- they're in the correct place to learn programming. Good Article: I didn't know Flask + Gunicorn + React existed. I'll never use it, but at least I know its a packaged thing now. This was a real good video. Lots of reminders of stuff that I haven't touched in a while.

I can't even imagine getting any of my projects' flask server code picked apart by Prime. Zero optimization in most cases, but it works, lmao.

Division by two (or any power of two) is of course constant time it's just a bit shift. Modulo by 8 is the same it's grabbing the last 3 bits

this video showed me how little I know.

bruh we were drawing bitmap black/white images on the site, turning the 1mill checkboxes into a 1000x1000 canvas we had a discord server of a few dozen people doing this I eventually created my own infrastructure of 55 servers to quickly draw images. I spent all night from 11pm until 7am creating my own CI/CD system and checking boxes at an inhuman rate. The rate limit on OCMB was pretty tough, and it was per-ip, so I had to increase my IP count - thus the high amount of servers. Others managed to utilize about 2000 proxies which nearly nuked the site out of existence. this was fun.

Seems like a good usecase for learning how to use roaring bitmaps as well.

TLDR on the "over complicating"... Arquero's bitset get is: get(i) { return this._bits[i >> 5] & (ONE >>> i); } That offloads any math to the engine which is probably significant. If you're lucky enough to be doing this in something that compiles down to opcodes on ISA that does it, DIV is actually DIVMOD... it performs unsigned int division and stores the quotient and remainder as the result. x86: "Unsigned divide AX by r/m8, with result stored in AL := Quotient, AH := Remainder." Elsewhere? eh, no idea, You'd probably just mask and shift on ARM,