21 ms·
Tell HN: The site was offline. What changed?
Obviously things took longer than intended and expected, but in the end:
Items moved from /12345 to /12/34/12345. HN now starts in one fifth the time, and better utilizes the filesystem cache. Backup speeds are also improved.
Profiles moved from /kogir to /ko/gi/kogir, and from /KogIr to /%k/og/%kog%ir, which works on case-insensitive filesystems. Similar performance improvements were observed.
Passwords moved from a 45MB user->hash mapping file into user profiles themselves. Previously, this mapping file was re-written in its entirety every time a new account was created, and is why the site went down on May 18th. New account creation is now incredibly lightweight, and should allow us to further limit and possibly eliminate our use of captchas.
There were additional changes to support new features currently in the pipeline, but which we're not yet ready to announce.
I'm sorry that we were offline for so long. Nothing else we currently have planned should require anything more than a simple restart, so with any luck this will be the last major disruption the quarter, and maybe even this year.
- yiedyie 12y agoAnd the question for this answer: https://news.ycombinator.com/item?id=7872121 https://news.ycombinator.com/item?id=7872121
- bndr 12y agoCan someone explain why "Items moved from /12345 to /12/34/12345. HN now starts in one fifth the time" that increases performance? why is it better?
- fennecfoxen 12y agoThis is a common technique to limit the number of files in any single directory when you store your date in many many files on disk. You will also see this in things like web cache software and the like.
- VLM 12y agoThats what it is. The specific "why" is there aren't many O(1) directory traverses. So a million files in a dir is going to take longer to access any individual file than if there's only 3 files to pick from. And if it scales worse than linear, a tree structure, although hitting the FS multiple times once at each level, in total can take less time. Finally if you can avoid a smooth distribution hash and intentionally order by something important (time?) then you only need a cache the most recent directories in memory and the deep historical archive can fend for itself rarely accessed without getting in the way of the busy files. If you rarely if ever leave /stuff/thisYear/today/ then whatever is in /stuff/2011/dec25 will never slow today down or get in the way.
- oneeyedpigeon 12y agoSomeone will explain this better but, as I understand it, having a huge number of files in a single directory becomes inefficient at a certain number; organising those files hierarchically brings an improvement. If HN really stores each item as a file in one big directory, that directory used to contain almost 8 million files ...
- leephillips 12y agoNot only inefficient; some linux commands fail when they're used on more than a few million files at a time - there is a maximum number of arguments that they can handle. EDIT: bzbarsky's explanation below is more accurate.
- bzbarsky 12y agoTypically the issue is not the commands themselves but the shell. Trying to do "something *" on the shell command line will expand out the glob, and if the resulting string is too long (e.g. you fail to malloc() it!) the shell will do something ranging from crashing to not running the command and giving a useful error message.
- larrys 12y agoNot claiming to be an expert here but I typically do this when confronted with a large number of files. Instead of: command * for i in [someregex]* do command $i done I know I could also do command [someregex]* but like the comfort of having each item echo back to the terminal so I know the progress.
- andreasvc 12y agoThat still relies on the shell expanding a glob of millions of files. Another method is to use 'find' and 'xargs' to avoid specifying the files as arguments explicitly.
- jacquesm 12y agoDirectory scans suck. So if you break up the space into sets of prefixes you limit the number of files in each dir and traversal gets much faster. Ditto adding/removing items. Some filesystems are worse at this than others (xfs... let's not go there).
- adrianmsmith 12y agoWould the HN software need to scan the directory e.g. to read in all users, at any point? I don't know the source code of HN but I can't see why that would be necessary. (And if it did need to, presumably it's now need to recursively scan all sub-directories, which would also take a while?)
- jacquesm 12y agoNo, you need to scan the directory every time you read a file. So most filesystems do a lot of work to optimize this but it is still a significant factor.
- adrianmsmith 12y agoNot sure I agree with that. I ran the software for community with 6M users, and on 2003 hardware we had millions of files in one directory. That was with advfs on tru64 so things might be different with other file systems. But e.g. zfs can do this no problem as well. I just sort of assumed other FSs must have caught up in the intervening 10+ years but I haven't looked into their source code so an prepared to admit I might be wrong about them. The same way a database fetch doesn't load the whole table, filesystems can and do use trees and hashes to organize directories so that file lookup, creation and deletion by name can be fast and can be concurrent. I posted this in another comment, but this was my understanding of the situation in 2010. http://www.databasesandlife.com/flat-directories/ http://www.databasesandlife.com/flat-directories/ There must be a reason why they did this change, either I am wrong about performance (perhaps my results really were particular to those filesystems) or perhaps I am right and they made the change for another reason. I'd like to learn the answer.
- zimpenfish 12y agoIf you look up "directory hashing" (possibly also "directory sharding"), that'll explain things. Particularly relevant to things like email servers and shared web hosts.
- deleted 12y ago[deleted]
- js2 12y agoLarge directories can be very slow to scan (readdir). By fanning out the items into more directories of fewer items, performance is improved. Git does something similar with its objects directory. This is an old Unix trick. Note that Linux ext3/ext4 have a dir_index option which improves readdir performance. Edit: it's not readdir performance so much as just name lookups which are improved by this technique (and dir_index): http://ext2.sourceforge.net/2005-ols/paper-html/node3.html http://ext2.sourceforge.net/2005-ols/paper-html/node3.html
- adrianmsmith 12y agoMy experience was the opposite. In code I wrote - I never needed to scan the directory to find "all users" (after all, if you have millions of users, this is going to take a while whatever directory structure you use) - Modern filesystems either use a tree or hash structure to identify files, meaning that lookup by name, and creating/deleting files, is quick, even if you have millions of files. - Given no performance benefits are to be had by directory nesting, I always went with the option of simplicity, i.e. having everything in one directory. (I blogged about this here: http://www.databasesandlife.com/flat-directories/ http://www.databasesandlife.com/flat-directories/) But no doubt the HN developers had a reason for doing this change, I'd love to know what it is (e.g. if they need to do something I never needed to do, or if they need to do the same things but I was wrong.)
- caoimhin 12y agoThe fs caches the directories. So in a large, flat dir structure it has large, flat dirs it needs to cache. Now I'm not sure how big the win will be for accounts since one assumes active vs. inactive accounts will be randomly spread around alphabetically. So loads of these smaller dirs will be loaded. But for articles it should be a win since it's mainly the most recent ones that will be accessed so you'll have a hotspot and the vast majority of the directories won't be accessed.
- unreal37 12y agoThe site loads 5 times faster. So clearly there are performance benefits to directory nesting.
- deleted 12y ago[deleted]
- eCa 12y agoAn aside: When storing large quantities of things like this my personal preference is to split the id from the end. I was once i charge of a large number of images of book jackets named by the books' isbn. At least in that population (which of course is an extreme example considering how an isbn is created) the distribution is much more even (that is, the directory sizes are relatively equal) when using the end than the beginning, but I would not be surprised if that is a normal outcome. Maybe it's an application of Benford's law [1]. [1] http://en.wikipedia.org/wiki/Benford%27s_law http://en.wikipedia.org/wiki/Benford%27s_law
- diafygi 12y agoWhy worry about case-insensitive file systems if you are not using one currently?
- FroshKiller 12y agoSuppose they want to change platforms in the future or release the codebase for others to use. It was apparently an easy enough change to implement now, so why not?
- Siecje 12y agoPre mature optimization.
- squeaky-clean 12y agoThis is the exact opposite of pre-mature optimization. They have a mature product that works. We're using it right now. And now they're future proofing it a bit.
- kogir 12y agoBecause running out of the box on OS X makes testing way easier. Currently we use DMGs, and performance is terrible.
- wtbob 12y agoI know a lot of folks develop on OS X, but this just seems like another argument to develop on Linux or a BSD. But then, I haven't owned a non-Linux box in 16 years, so I may be an outlier...
- danik 12y agoIt isn't an argument. DMGs are fine for development and testing and they can be made case-insensitive. Or you could just, you know, create a separate partition. If the DMG speed is too slow for development and running tests(not testing with the full live dataset) you are doing something wrong.
- _wmd 12y agoI know it's crazy talk, but glancing at my own profile, I count maybe 100 bytes of data? Yet to represent that data in memory, it's going to blow up to 4096 bytes plus structs to represent the inode and directory entry/entries because you put each profile in its own file. By that count, you might get somewhere near a 40x cache utilization improvement if you just used a real database like the rest of us do - even just an embedded database. This of course before saying anything about transactional safety of writing directly to the filesystem
- blablabla123 12y agoI guess even most persistent embedded databases are on top of a good auld FS... SCNR...
- peterwwillis 12y agoUsing less virtual memory to store user data doesn't imply better cache use, only a smaller cache size. The tradeoff is memory over CPU. With a database you're using more CPU. It's a fair bet to say that your memory capacity will increase at a greater rate than your CPU, not to mention costing less to power and/or cool, and a simpler software architecture to support. Wasting memory is a simple hack to increase performance and decrease complexity. > This of course before saying anything about transactional safety of writing directly to the filesystem 1) transactions aren't made or broken by what or when they're written, they're made or broken by being verified after being written, and 2) this is a user forum for people to comment on news stories, not an e-commerce site. Worst case the filesystem's journal gets replayed and you lose some pithy comments.
- _wmd 12y ago> With a database you're using more CPU That's incorrect, you're potentialy trading several system calls (open, read, close) and their associated copies, which have high fixed costs for, with the right database, no system calls at all. I've spent most of the past year working with LMDB, and can decisively say that filesystems can in no way be competitive with an embedded database, by virtue of the UNIX filesystem interface. > this is a user forum for people to comment on news stories, not an e-commerce site That much is true, though based on what we've learned in the parent post, until today all passwords on the site were stored in one file. Many popular filesystems on Linux exhibit surprising results rewriting files, unless you're incredibly careful with fsync and suchlike. For example, http://lwn.net/Articles/322823/ http://lwn.net/Articles/322823/ is a famous case where the many-decades traditional approach of writing out "foo.tmp" before renaming to "foo" could result in complete data loss should an outage occur at just the right moment.
- ianstallings 12y agoCan we classify this as "archeology"?
- tim333 12y agoNewbie question here - I'm just curious. Is it quicker to store the data this way in loads of files or to use Postgres?
- kogir 12y agoFor new development I'd recommend PostgreSQL over flat files for most projects. Really depends on what you're trying to store though. For large data (images, audio) that can't fit in a table row, the filesystem is way better. In our case we started with flat files, and buying breathing room is the first step to move past them.
- sequoia 12y agoCuriosity: Why did you start with flat files? It looks like hackernews was started in 2007, relational databases had been around for quite some time at that point, and were the standard way to store such forum data (see: every popular forum framework at the time)... the decision to store this sort of data (news/link forum with comments, 100% text) as flat files is very confusing to me.
- tremols 12y agoMy guess is that Arc - the lisp language running HN created by Paul Graham - was new, and coding and maintaining a database driver was out of question. Today, perhaps the way to go would be to use some sort of json webservice interface to a database written in another language rather than writing a driver.
- adwf 12y agoThat would be my guess as well. It's one thing to decide you want a simple forum and have it coded within a couple of days. It's entirely another to spend months creating a stable database library and keep it upto date with all the latest changes.
- 12y ago
- gnurag 12y ago> and is why the site went down on June 18th. Do you mean the site will go down on June 18th?
- brudgers 12y agoYC's time machine startup will be in stealth mode.
- sirtel 12y agoAnd, HN becomes responsive. ✧＼ ٩( 'ω' )و /／✧
- bshimmin 12y agoResponsive as in "responsive design"? Hardly. The only thing that uses media queries is the vote arrow.
- unreal37 12y agoBefore responsive design came around, the word "responsive" actually meant a server would respond quickly to actions.
- sergiotapia 12y agoWords change with time. When you say 'responsive' in a web setting it's nearly always in regards to responsive web design - not 'this page is responsive now, returning results quickly!'. bshimmin shouldn't have been downvoted.
- logicallee 12y agoNo, responsive as in "responsive". (reacting quickly). ( However, the parent should NOT be downvoted, people. Despite total "ignorance" ... of a 2010 article and its aftermath. If you can call that ignorance. [1] [1] http://en.wikipedia.org/wiki/Responsive_web_design* http://en.wikipedia.org/wiki/Responsive_web_design* To the parent: the "Responsive Web Design" movement picked a really stupid name, but it's legitimate terminology and I guess the rest of us - and I say this with biterness - have to find some other word for talking about a server that is responsive, if we want to avoid confusion. For the moment it's legitimately confusing on the part of everyone who uses the word responsive the way the parent does - basically, they took one of the clearest and most positive adjectives you can say about a site, with no downsides for the user whatsoever, and misappropriated it to refer to something completely orthogonal and unrelated (in that it has nothing to do with render speed or anything else that the word meant prior to 2010.) )
- tdicola 12y agoWow that's interesting that you use files to store the data. Is there any sharding across machines or is it all just one machine? Do you use big SSDs or old spinning disks?
- icebraining 12y agoIt's a single machine.
- idoco 12y agoThanks, I got so much work done today!
- xenonite 12y agoJust curious: why are user names case sensitive?
- kogir 12y agoThere are 114 accounts that share the same lowercase representation.
- topac 12y agoThat's exactly how i would have changed things to make the website faster!!! -4 jan 1991-
- mariusz79 12y agoI just don't get one thing.. Don't you have dev and staging server, where you could develop, test, and pre-deploy everything without shutting down the website?
- kogir 12y agoOnline data migrations are complicated and error prone. We deemed it not worth it. All the code was tested before going live, but at some point you actually have to move and re-format all 8.5 million files.
- rafeed 12y agoIt's definitely snappier and now looks responsive too! Thanks for the hard work kogir et al!
- bryanh 12y agoI bet some before/after load charts would be pretty impressive!
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- apeace 12y agoPardon if I'm ignorant here, but is there a blocker to open-sourcing HN? I'm sure the community would love to help.
- IvyMike 12y agoPrevious discussion: https://news.ycombinator.com/item?id=5006037 https://news.ycombinator.com/item?id=5006037
- gdewilde 12y agoI love how hn doesn't load 150 circus elements. I can reload pages all day long. I was just thinking..... function byId(id) { return document.getElementById(id); } // hide arrows byId('up_' + item).style.visibility = 'hidden'; byId('down_' + item).style.visibility = 'hidden'; could be : function hide(id) { document.getElementById(id).style.visibility = 'hidden'; } // hide arrows hide('up_' + item); hide('down_' + item); Then it is 150 in stead of 185 chars, 19% smaller or 23% bigger. And the function name is better of course.