12 ms·
A 1.5GB string
- Vecr 4y agoThe formula to calculate the numbers of needed servers is wrong, as you can't have fractional servers. You should use the pigeonhole principle[0] [0]: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle
- sd9 4y agoThe only difference in this case is to take the ceiling. The formula seems fine as an approximation.
- nmilo 4y agoSo round it, this is engineering, not math. The safety buffer factor accounts for any rounding errors anyways.
- deleted 4y ago[deleted]
- sweettea 4y agoThe formula for number of needed servers seems like a fine approximation; I'm very confused how you could use the pigeonhole principle. Perhaps to say that if you have N servers, one of them has at least total_users/N users? But assuming you have a decent methodology for balancing users across servers, and can rebalance to use a new server when added, this has basically the same effects as the formula given so I'm clearly missing why you pointed this out.
- cowthulhu 4y agoThe formula/metric is clearly an approximation?
- Dylan16807 4y agoUse it how? The actual pigeonhole principle would conclude that you have multiple users on at least one server, and nothing else. And anything that calculates individual users is the wrong way to do this math.
- tiler2915072 4y agoAs others have pointed out for the authors discussion this fact doesn’t really matter. However what does matter is that the authors probably is not estimating the average correctly partially due to this bug. If they scaled without fixing their excessive string storage, they would probably find their estimate to be off. Even with the fix I’d be surprised if the underlying distribution of data per user is normally distributed.
- IncRnd 4y agoThat can obviously be rounded. Nobody will really try to purchase 27% of a server. A different issue is that the formula should include "1+Safety Buffer". Otherwise it needs to be run twice, once with the safety buffer and once without. Even so, I didn't take the formulae on this page to be accurate so much as representational.
- ilyt 4y agoIt relies on common sense, thing that you lack.
- Backslasher 4y agoThe real formula we used to order servers was more complex than this, and included regional distribution, requirement peaks etc. I can expand more on that process if this is interesting. However, for the context of this post, this crude approximation suffices IMO
- wadefletch 4y agoWhat is the CSS effect as you enter the page? Are they streaming the CSS itself, or just an animation in the browser? Very cool effect.
- pkage 4y agoIt's a CSS animation from the Jekyll theme. Pulled from the minified CSS: @keyframes intro { 0% { opacity: 0 } 100% { opacity: 1 } } Applied via: animation: intro 0.3s both; animation-delay: 0.15s;
- tgsovlerkhgsel 4y agoA better fix could have been switching to some other (binary) serialization protocol (BSON or similar) - the problem here doesn't seem to have been the size of the history itself, but the exponential growth of the escaping.
- crdrost 4y agoOr, y'know, just jo.put("previous", previous); Rather than jo.put("previous", previous.toJson()); Presumably the reason they didn't do this is because they couldn't handle a recursive schema?
- alephaleph 4y agoIn the post they say they didn’t do this bc they’d just be trading long strings for deeply nested objects.
- lalaithion 4y agoDeeply nested objects grow linearly with the size of history, not exponentially.
- NegativeLatency 4y agoAgreed, I'd take deeply nested objects, over deeply nested strings (of strings...) of objects.
- crdrost 4y agoFor the record I do agree that the schema data Screen = Screen { previous :: Maybe Screen, ... } is inferior to what they eventually had, data ScreenHistory = ScreenHistory { previous10 :: [Screen], current :: Screen } -- Screen itself is nonrecursive But I do think that storing JSON as a string was a weird antipattern in the first case, smacking of a premature optimization.
- btown 4y ago
- usr1106 4y agoDid they buy this domain just for this blog posting about backslashes? No, the first HN submission is from 2017. Coincidence or an agenda?
- ehPReth 4y agowhat?
- stingraycharles 4y agoThe story is about backslashes. The domain is backslasher.net. Seems like a fun coincidence to mention.
- augusto-moura 4y agoMaybe the story is not that recent? I will bet on a coincidence though, pretty interesting nonetheless
- rsstack 4y agoCoincidence :) I know him in real life and he has used that nickname for a decade+.
- Backslasher 4y agoHa, this is a nice coincidence. I was looking for a cool domain name a billion years ago and came up with Backslasher since I was just learning text processing in Bash/Perl. My lifelong goal is beating the same-named horror film in search results.
- ww520 4y agoGood analysis. The previous session data probably needs to be deserialized from json to objects first before adding in the new session object. The whole container can then be serialized to json at one shot. This avoids the recursive escape encoding.
- IncRnd 4y agoThat's a case of not solving the problem. Leaving aside the need to send a massive set of screen images for the moment, a severe issue with that protocol is the lack of compression. It doesn't need to use a quadtree[1], although that will significantly speed up the interface when sliding the tree depth to the screen action being taken. Even RLE[2], Huffman[3], or any other standard string compression[4][5] would solve this issue shown in the blog. [1] https://en.wikipedia.org/wiki/Quadtree#Compressed_quadtrees https://en.wikipedia.org/wiki/Quadtree#Compressed_quadtrees [2] https://en.wikipedia.org/wiki/Run-length_encoding https://en.wikipedia.org/wiki/Run-length_encoding [3] https://en.wikipedia.org/wiki/Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding [4] https://en.wikipedia.org/wiki/Data_compression#Image https://en.wikipedia.org/wiki/Data_compression#Image [5] https://en.wikipedia.org/wiki/Lossless_compression#General_purpose https://en.wikipedia.org/wiki/Lossless_compression#General_p...
- Genbox 4y agoEfficient data handling is better than spending cycles on generating a lot of backslashes and then burn cycles on compressing it.
- IncRnd 4y agoIt's also good to properly manage transmission of that list of screens, even after you've fixed the backslashes. The article stated that they degraded the user experience by artificially limiting the string length instead of fixing the issue.
- thfuran 4y agoAs an immediate stopgap before the proper fix was in place.
- duskwuff 4y ago"Screens" is referring to the state of a multi-step UI (similar to the back/forward cache in a browser), not a bitmapped image.
- missblit 4y ago> Understanding we are memory-bound is crucial, as it directs our efforts towards reducing memory consumption in order to accommodate more users on the server. While this is true, it bears mentioning that in a service handling many requests they all smear together memory-wise, so _any_ latency savings can also ease memory pressure (a memory allocation has an area: bytes × time). So for instance it can make sense to minimize memory held across an RPC boundary, or even to perform CPU optimizations if they would improve the latency, > e.g. examining a memdump rather than just measuring overall memory utilization A flame graph also would have highlighted this (without the need to look at what might be user data), and is usually where I start looking for memory optimization. I mean if you don't know what code is allocating lots of memory where would you even start anyway? Additionally I've found that looking at outliers, while a good idea, can sometimes lead to wild goose chases if you're not careful. There can be pathological edges cases which are rare enough to not actually matter in practice.
- thedufer 4y agoThis service keeps around a lot of long-lived per-session state, which leads to a very different memory profile from a typical web service, like what you're describing. Your point is valid in general, but doesn't seem to be relevant here.
- missblit 4y agoYeah, but any excuse to talk about memory profiling! It's one of my favorite past-times.
- Dwedit 4y agoMeanwhile, Firefox has big problems when you give it a 6MB Data URL, you get crashes or graphical glitches throughout the browser while it tries to draw the URL bar.
- TechBro8615 4y agoThat seems like a weird oversight, since Firefox is normally quite good at rendering large assets. For example, I prefer viewing large SVG images (like those generated by dependency graphing tools) in Firefox, because unlike Chrome, it allows me to pan and zoom within the image.
- chrisweekly 4y agoMy kneejerk rxn is, this seems more about URL length than asset rendering.
- jfk13 3y agoAs it happens, Firefox 112 has some improvements in this area, although it's still true that handling a multi-megabyte URL will be a bit painful.
- Phelinofist 4y agoWhy not just restrict the history to a configurable number of entries? Having like 20-50 is probably enough. It might no be 100% correct but the effort:use ratio seems good.
- Backslasher 4y agoWe ended up doing that. We decided that while we have to store the stack, it can't hold 20 years of history. > creating a dedicated real stack with self-imposed size limits and reporting.
- scotty79 4y agoWith this escaping of escaped strings they are doubling the number of escapes each time which means they can reach 1GB with just 30 steps.
- NegativeLatency 4y ago> Since JSON fields have quotes, and those quotes need to be escaped when stored in a string, they are stored as \" I don't think they do though?
- andrewmackrodt 4y agoThey were serialising the previous object as a string (which may also contain a key called previous which is a string) so quoted values, backslashes and any other escape characters would be escaped. Over multiple screens this grows quickly, e.g. this simple struct which has only an id column grows to 2KB in only 9 steps: let obj = { id: 1 } for (let id = 2; id <= 10; id++) { obj = { id, previous: JSON.stringify(obj) } }
- NegativeLatency 4y agoRight, I was suggesting something like this (since we're already in JSON land, why leave it for string land): let obj = { id: 1 } for (let id = 2; id <= 10; id++) { obj = { id, previous: obj } }
- eyelidlessness 4y agoThe problem as stated is more complicated than it needs to be, due to forcing the serialized structure to match the in memory structure. Their in memory structure is a singly linked list. With JSON as a serialization format, that’s probably better modeled as an array with the “previous” link stored as the head (history[0]), and its “previous” stored as the tail (history[1]). If this sounds like a cons cell, that’s what it is! It’s also a linked list. The laziness they want to achieve (only de/serialize one screen at a time per navigation forward or back) is also straightforward. - forward: serialize the current screen, trim the leading/trailing quote off the previous serialization, insert with a comma before the new trailing bracket - back: parse history, head is your desired “previous” screen, tail is your now-“previous” screen’s history There’s a tiny amount of overhead to this approach, but not nearly as much as repeatedly reserializing the same string to shoehorn it into a serialized structure that doesn’t let you cheat a little bit with well known start/end characters.
- IngvarLynn 4y agoAssuming 3 backslashes per iteration, one iteration per second - it would take 16 years to get to 1.5GB. This code problem looks deeper to me.
- cyanydeez 4y agoEvery quote in a jsonstring requires backslashes. This is geometric explosion. You're assuming very simple state objects.
- NieDzejkob 4y agoThe growth is exponential - each backslash becomes two in the next iteration. Thus after n iterations we have 2^n - 1 backslashes, and we only need 30 iterations to hit a gigabyte (and that's assuming only one quotation mark in the original JSON).
- ben0x539 4y agoWonder if it's worth putting special logic into json serialization libraries that politely raises some alarms when writing like a few hundred \ in a row.
- dan-robertson 4y agoHow does the number of backslashes grow as the string is repeatedly escaped? 1 \ 2 \\ 4 \\\\ 8 \\\\\\\\ We see it grows exponentially: to escape each backslash, you need two. So I guess I’m surprised that this is a post about a 1.5GB string and not the exponentially increasing work on each navigation causing performance problems, or the session crashing from running out of memory when a user navigates too far. Maybe the service wasn’t being used much yet or there’s some other reason that strings only grew to ridiculous sizes and not oom sizes. I’m curious why it didn’t exhibit sooner. (I saw a somewhat similar problem long ago but then it was more like doing ‘this.json = this.messages_array.to_json()’ on every new message, so merely quadratic. I think it was noticed not long after we first had a lot of messages added to one of the objects)
- MBCook 4y agoIt only takes about 30 doublings to get to 1.5 billion from an initial \\ if I have my math right. I guess the history wasn’t that deep.
- MichaelZuo 4y agoI don't understand how this made it into production without anyone noticing the exponential if it's really a straight doubling each time.
- Xorlev 4y agoComputers are fast. I once worked on a service sitting at the top of a deep RPC stack. Stack traces were often folded into RPC error messages to help diagnostics. Well, if you have a failure at one layer, propagated to the next layer, and the next layer, and sometimes replicated for each looked up item (to support partial failure semantics), then you can end up with gigabytes of stack traces in memory for some fraction of time. Very hard to figure out until tasks started dying and leaving behind heap dumps during a wide-spread incident at a lower layer of the stack.
- 3y ago
- anonymoushn 4y agoIt seems like the memory used will grow only linearly if you escape " and \ as "\u0022" and "\u005c" respectively.
- preseinger 4y ago> So each screen has the previous screen the user visited, to allow the user to go “back” and get the exact screen they were in before (state, scrolling position, validation notices etc). this is the actual problem, a clear design error if the entire screen "stack" is part of per-request or per-session state while also being unbounded the backslashes encoding stuff is a symptom
- preseinger 4y agodownvotes? what? nothing i wrote is in any way controversial? obviously you can't embed unbounded history in session state directly?
- mkl 4y agoYou can store a heck of a lot more states if you don't double the storage required with each additional state. That's the actual problem.
- cratermoon 4y agoI'm currently consulting with a company in the aviation industry that is struggling to adapt a legacy-bound culture to modern software engineering techniques. Among other things they have no sense of systems-level concerns. I've recently identified one of the most common user activities ends up executing the same expensive end-to-end query at least 4 times for each interaction, never bothering to memoize the results. While there is a rudimentary cache in place, the lack of awareness that the same interaction involving at least 3 network requests per query even when the cache is warm has not yet struck them as a problem. As this system is currently only handling a fraction of the total traffic it will be expected to manage when it's fully live, it's clearly a slow-burning fuse that will explode in their faces when they try to make the switchover complete.
- nayuki 4y agoI wrote some stress-test cases for a Java library recently which involved 1-GB and 2-GB strings. On the surface, a java.lang.String should be a wrapper around a char[], whose maximum length is Integer.MAX_VALUE = 2 147 483 647. This is roughly how older implementations of JDK did things. But as of JDK 9 and JEP 254, String's private field has type byte[], and each character uses either 1 byte if it's encodable in ISO 8859-1 or 2 bytes if it requires UTF-16. This means that strings containing only ASCII characters can be up to about 2 billion in length, whereas strings with real Unicode content can only be up to about 1 billion in length. This is a bit of an unfortunate regression in functionality.
- ungamedplayer 4y agoNaive question, why not just do the java equivalent of mmap and read the data from storage? Seems like somewhere along the line reality outgrew the original requirements.
- nayuki 3y agohttps://docs.oracle.com/javase/8/docs/api/java/nio/MappedByteBuffer.html https://docs.oracle.com/javase/8/docs/api/java/nio/MappedByt...
- ungamedplayer 3y agoWas the link to show me that mmap existed, or did that doc show some reason it could not be used.
- userbinator 4y agoIronically, not long ago there was an article about how hard string handling is in C, so programs tend to be written to avoid manipulating strings as much as possible. In other languages, where strings are easy to use, it encourages inefficiency like this. The term "stringly typed" also comes to mind. JSON truly is the new XML, both in terms of advantages and disadvantages. I wish people would stop using it for everything and realise that using a "human-readable" format for data that is 99.999999% not going to be seen by a human is absolute insanity in terms of inefficiency.
- Culonavirus 4y ago> using a "human-readable" format for data that is 99.999999% not going to be seen by a human is absolute insanity in terms of inefficiency. Database dumps say hello. :)
- alex_sf 4y agoIf you want human-readable dumps, there's no reason you can't convert the more-efficient format into something human-readable.
- smittywerben 4y agoI just drag my Windows XML script driver into SYSTEM32 folder (for my HP indigo 7000 series ink press) then I press the rest.
- flandish 4y agoIf you want human readable db output, I might introduce you to what I’ve spent most of my career doing: etl. :)
- afloyd 4y agoHuman readable formats should exist for more or less one purpose, interfacing with a human, eg configuration.
- 4y ago
- sxv 4y ago| 1.5GB string Genomics data has entered the chat.
- gumby 4y agoWhy are they saving the JSON as a string in the first place, and not as a datastructure?
- Scarbutt 4y agoIt's a networked application.
- iudqnolq 4y agoBut they still have to serialize the JSON object containing the string. I wonder if it was an "optimization" to avoid serializing full object every time it was transferred?
- Backslasher 4y agoI do not know why this is a JSON object. It might have been for debuggability, although I don't agree with this choice.
- sour-taste 4y agoIt seems like just using the browser to store forward/backwards state with window.history would be easier than worrying about this server side. Maybe it was a legacy site that didn't work well with forward/back or a native app?
- fake-name 4y agoNothing in the article indicates that the client here is a browser. I read it as some service with a custom client application.
- Backslasher 4y agoThis is correct :)
- YouWhy 4y agoWow! So this is actually a drama I had a secondary role in. A few remarks: 1. Team: Nitzan (the blog author, and an awesome dude!) was at the time the Production Engineer monitoring the top-line capacity metrics. The Java heapdump tooling was hacked together by E.A., with some tough bits by A.S., who's a force of nature. The bulk of the mitigation was carried out by Y.B. over several months. I was the person who analyzed a couple of memory dumps and framed URL strings as a worthwhile 80/20 goal. 2. The main difficulty in the mitigation project was that the pathological strings were accessed over hundreds of callsites using some semantics like semanticallyUsefulURL = decodeURLString(urlStoredInStringForm) What Y.B. ended up doing was 2.1. A lengthy build-up very carefully constructing an API to represent URLs in as compact a way as possible, and plugging it in where convenient, 2.2. Carrying out a massive automated rewrite at the source level ("codemod"), which is possible in Java but not for the faint of heart. I think he used some JetBrains tooling to get that going. I consider his work a tour de force. I vaguely recall there being some modest CPU improvements in the process. 3. Organizational dynamics: the codebase was originally written by very competent people who did not work through that specific detail because it was not important for their original use case. However subsequently the code underwent several years of almost solely rewarding improvement in end-user metrics, leading to an overall inadequate state that was hurting the organization as it was hitting hard scaling limits. In fact, "engineering excellence" was not even a category for recognition at that time. In this climate I could not find my own voice as a SW professional and chose to quit after a little bit more than a year. I have a pretty good memory, I'd be happy to give more context if appropriate, just ping me. (Edited - added one more due prop!)
- Backslasher 4y agoA.S --> E.A, no? :) I decided to abstract away the URL part as it wasn't easily explainable and not important to the story. I figured the JSON-in-JSON part is interesting enough. Anyway, the resulting memdump with many \\s remains my most audience-engaging slide to date, and figured out the non-company audience deserves to know. Good times.
- YouWhy 4y agoYou're fully right! I added them both - E.A. was the original toolmaker, and A.S. worked more down the chain. He definitely was the person who walked me through the finer points of retrieving the data.
- jldugger 3y agohttps://rachelbythebay.com/w/2023/04/09/note/ https://rachelbythebay.com/w/2023/04/09/note/ > I read a post about someone who found that their system had something like 1.2 GB strings full of backslashes because they were using JSON for internal state, and it kept escaping the " characters, so it turned into \\\\\\\\\\\\\\\\\\\\\\\\\" type of crap. That part was new to me, but the description of the rest of it seemed far too familiar. > And I went... hey, I think I know that particular circus!