12 ms·

What we did about expired links on HN

• kevin 12y ago
  Written by dang in response to a question asked here: https://news.ycombinator.com/item?id=8423482 https://news.ycombinator.com/item?id=8423482
• dang 12y ago
  Url changed from http://pastebin.com/dETyYtpX http://pastebin.com/dETyYtpX because I added some things.
• IgorPartola 12y ago
  Would it be possible to extend this system to allow you to serialize and deserialize the closures? Then you could store them externally in a "real cache" and let that take care of the expiration, etc. You could then also open up a nice security hole :)
  • vilhelm_s 12y ago
    I thought the same thing. There certainly have been Scheme systems developed that can serialize closures and continuations (e.g. I found [1], and the systems they cite in the related work section). But it seems tricky to get the garbage collection to work right... somehow you need to tell the program which data should be serialized, and which should be stored in RAM and somehow marked as still being live. For the security aspect, maybe the server could have a secret key and store a MAC along with the serialized string? [1] http://www.iro.umontreal.ca/~feeley/papers/PierardFeeleySW07.pdf http://www.iro.umontreal.ca/~feeley/papers/PierardFeeleySW07...
  • pshc 12y ago
    Oh! Taking that a step further, what if you mmap'd an empty file first, say 1MB of zeroes. Then, just start writing closures to it, one after another. When you hit 1MB, use mremap to add another 1MB. And just keep going! The pagefile would become a fossil record of the webserver's access history. The earlier in the file, the older the request, and the less likely it would ever be mapped into physical RAM ever again. On a 64-bit machine with a modern hard drive, you could probably go forever :)
    • espeed 12y ago
      Chronicle Map would be great for that: http://openhft.net/products/chronicle-map/ http://openhft.net/products/chronicle-map/
  • derefr 12y ago
    Or you could just URLencode the serialized closure, and sign that URL. Now as long as the page exists, the closure exists!
    • rcfox 12y ago
      That sounds really dangerous. It probably wouldn't be too hard to inject arbitrary data into the server.
      • amock 12y ago
        Signing the URL should prevent that, but it still seems overly complicated.
        • nitrogen 12y ago
          Signed URLs is how AWS and CloudFront handle access permissions without actually storing the permissions on their servers.
          • amock 12y ago
            Yes, but that's a very different kind of system. AWS has to deal with a very large number of servers handling authentication for client that aren't trusted by the credential owner. HN has clients with credentials accessing a single server. It would be much easier to just store the serialized data in Memcached or Redis since the system is already centralized and use a token to look it up. Doing so requires less bandwidth and less messing with cryptography.
          • IgorPartola 12y ago
            Personally, I would be ok with a system I am responsible for giving the client a signed or encrypted token. I would not trust many (any?) crypto systems to have signed/encrypted arbitrary code passed to me from an untreated client.
            • derefr 12y ago
• iaw 12y ago
  Thank you for this. I thought I had noticed less expired links, and figured something was changed on the back-end, but this was very informative.
• redstripe 12y ago
  Does that mean HN runs in a single process and doesn't do any concurrent request processing? That's pretty impressive if that's the case.
  • TeMPOraL 12y ago
    As far as I can tell, it was always the case, yes.
  • dang 12y ago
    HN runs on a single core. Arc is implemented in Racket, which has green threads, so requests don't block on I/O. Whether that counts as concurrent is sort of definitional, but the CPU isn't processing two requests at once.
  • Ono-Sendai 12y ago
    That is pretty amazing that it keeps up with the traffic.
  • jacquesm 12y ago
    Actually, it shows you how incredibly inefficient most other ways of building a web application are. The amount of overhead is stupendous.
    • kijin 12y ago
      There are different kinds of overhead, different kinds of inefficiency. The HN codebase doesn't have the overhead of parsing hidden POST fields (for example), but it does incur a massive RAM overhead to store all that information as closures. A run-of-the-mill web app, on the other hand, would incur the overhead of passing state back and forth, and perhaps even store sessions on disk. But it might consume less RAM. What matters is what kind of inefficiency you're willing to tolerate in exchange for what kind of benefits. RAM overhead is a smart choice if you want your app to be very fast and you can afford to use a lot of RAM. A different organization, however, might choose to incur a bit more code-complexity and slower execution in exchange for other benefits. It all depends on what your priorities are.
• ams6110 12y ago
  The lesson is don't cling to a technically or intellectually elegant architecture if it's falling over in the real world.
  • judk 12y ago
    ...if you aren't angling for a buyout in a few months anyway.
  • kevin 12y ago
    Wouldn't exactly describe Hacker News as failing. It allowed one person to run a site for a growing community in his spare time and the sacrifice was the occasional expired link for some of its users. Not only do I think it was a fairly elegant solution, I feel like it was certainly a reasonable trade off. I'm sure pg would have been the first to change it had it actually effected things that truly mattered for a community site like Hacker News: story and comment quality.
  • deleted 12y ago
    [deleted]
  • spb 12y ago
    I wouldn't exactly describe an HTTP content retrieval method that revolves around state as a "technically or intellectually elegant architecture".
• aneeskA 12y ago
  Thank you for the changes. I appreciate very much not seeing "Expired link" these days :)
• duckingtest 12y ago
  Perhaps sending the same data to everyone and letting js filter it be much simpler and faster on a server end.
• rtpg 12y ago
  This seems like a pretty good example of perfect being the enemy of good. Would there be that much of a usability conflict if /?page=2 30 minutes ago was slightly different than /?page=2 now? Not to mention that if a scale of time that large has passed, there's a high chance that the closure-style links expire anyways
  • EpicEng 12y ago
    Agreed. I hated the "expired link" issue. It constantly sent me back to the front page. I would much rather see a newer version of page 2 than to be forced back to the beginning (after a backspace and a refresh).
    • couchand 12y ago
      It sounds like you don't mind the tradeoff made here but you'd like a better failure mode. That's a great point.
      • EpicEng 12y ago
        Yes, exactly. I'm fine with an imperfect solution to this problem, but I think that seeing a page N which was not the page N I would have seen had I clicked the link 30 minutes ago is far preferable to getting a silly error and being forced to navigate back to the front page.
  • kevin 12y ago
    It's not just about story stream, it was also about different users needing to see different things based on settings, permissions and function outside HN...until recently, the software that powered YC and powered HN were the same. Like Dan wrote, "Getting rid of those closures was a pain, and it made the code more complicated." The tradeoff pg made was for a bit of inconvenience in user experience for a much simpler architecture that allowed him to run HN as a side project while also running YC and writing the essays we've come to admire. You might have made a different decision, sure, but I can't say it wasn't the right call for his circumstances.
• chris_mahan 12y ago
  I just resigned myself to stay on the first page on HN.
• d23 12y ago
  Can someone explain to a non-functional guy how a closure makes this more simple, perhaps with a bit of pseudocode?
  • ordinary 12y ago
    function adder(x) { return function(y) { return x+y; }; } var plusthree = adder(3); var plusnine = adder(9); plusthree(2); // 5 plusnine(3) // 12 plusthree(4); // 7 adder is a function that returns a closure that closes over x. If the function that's returned were a normal function rather than a closure, the x that you pass to adder would not within the scope of the inner function, and you wouldn't be able to reference it. Calling plusthree or plusnine would simply fail. However, because the inner function is a closure, it remembers x. Every time you call adder, a new closure is created, with its own version of x, so you don't have to do anything extra like creating an object to store it in. The language runtime takes care of all that boring stuff for you.
  • TeMPOraL 12y ago
    Disclaimer: I haven't looked at the code, I'm making an educated guess here. I think it's implemented like this: function renderPage($stories) { renderHeaders(); renderStories($stories); renderMoreLink(storeLink(function() { renderPage(next30($stories)); })); } function handleLinkClicked($id) { $code = fetchLink($id); $code(); } Using storeLink() you save a function, than can be later executed when user clicked a particular link (remember, HN runs as a single process and does not restart itself every time like say, PHP does). This function remembers the context in which it was created - in this case, $stories variable - so all the data required to fulfil the request at later time gets stored with the function.
  • jbert 12y ago
    At a guess (after 1 min grep), this is the original code (from an old copy of the HN src). afaics, that's the code to render the entire table for all the stories (plus the 'more' link), including the html (note the inline 'tr' tags etc). https://github.com/wting/hackernews/blob/master/news.arc#L925-L956 https://github.com/wting/hackernews/blob/master/news.arc#L92... The point is that all the variable you want for rendering "page 2" are right there in scope. A closure can capture those, so you don't have to do any extra work serialising them, sending them to the browser, validating them on return, etc. Closures can seem odd the first time you come across them, but they're pretty mainstream these days (perl, python, ruby, C++, C#, golang all have them (some of them for a very long time :-), as well as the more traditionally-functional languages). There's more info here and it's the sort of topic you'll get lots of answers from in HN. http://en.wikipedia.org/wiki/Closure_%28computer_programming%29 http://en.wikipedia.org/wiki/Closure_%28computer_programming...
• lacker 12y ago
  I'm curious if you don't mind sharing, how many people are working full time on the HN codebase right now? I don't know if that number is even less than or greater than 1. I'm also curious if there's a straightforward way to serialize these closures. I'm guessing no or at least they would not be persistent across restarts. FWIW, if I were working on HN, I would be concerned that at some point, HN will require more hardware resources to scale, and it may require some fundamental architectural changes, like more separation between app logic and DB. I wonder to what degree you have scaling plans, like if we hit capacity X we would need to replace subsystem Y.
  • dang 12y ago
    > how many people are working full time on the HN codebase right now? Less than 1. If you include everything HN-related, that number goes up to 2 or a bit more, depending on how much time kogir has. > I'm also curious if there's a straightforward way to serialize these closures. Do you mean to disk, or to the client and back? My sense is that it's technically possible but the I/O overhead would make it not practical. However, that's not based on much knowledge. Perhaps we could do it now that we don't have so many. > I wonder to what degree you have scaling plans We have a lot of scaling plans, but I wouldn't call them definite.
  • kevin 12y ago
    There are two people dedicated to HN development. Daniel and Scott. Four other people from the YC software team also contribute, but not full time because they have to also work on other projects: Nick, Brett, Trevor and myself. Other people on the software team: Garry and Dalton. We actually just upgraded the hardware for HN very recently. A lot goes on behind the scenes and it's a testament to the team that it's all fairly transparent to the community to the point where most of you think nothing changes at all. The point is to keep the community focused on contributing, voting and commenting the very best content for hackers. It's one of the reasons I was delighted to see Dan write about some of the work they do like reducing expired links. It's a rare look at how much thought goes into what feels relatively simple.
    • jacquesm 12y ago
• SiVal 12y ago
  Of course, I may be overlooking something, but this sure seems like a case of overeducated engineers overengineering a solution that then underserves users relative to a naive solution. Individualized closures to keep track of what each user has already seen? Why not just have a single, current ranking of stories for everybody and let me pick how many of them I want on each page (up to a point). So, I have a preference that says I want 100 stories per page. Well then I get 3-1/3 pages worth of non-repeating stories without all the computer science. If I later click the "more" button, I get the second hundred, whatever they happen to be at the time I click "next". That's easy enough for me to deal with. If it has only been a few minutes since I loaded the front page, most of the second page will be new to me. I don't care if a few of them aren't. I'll just skip past them. I'll have plenty of titles to scan over. But if it has been, say, a day since I loaded the front page, instead of clicking "more", I'll probably just reload the front page. I can take care of that myself. No big deal. With the new API, of course, we can now just build it ourselves, but all this engineering sophistication that resulted in a fixed, 30-article front page and the maddening inability to ever get far past the first 30, reminded me of Ted Nelson's Xanadu Project, which was so cleverly designed to prevent dead links that it never went anywhere, while the naive Web (dead link?, oh well) changed the world.
  • willvarfar 12y ago
    Except that stories can move up and down the list over time, and users do care. Slow browsers like me were hitting dead links precisely because we were slow. Yes you can still store this much more centrally and cheaply than closures. You can have all stories with a timeline in and do a sort using next-thirty-at-this-timestamp and, despite you visiting every story and then sorting, I'd expect it to be snappy enough for a heavy hit site. Furthermore, you could speed it up with linked lists instead of timestamps too etc.
    • danielweber 12y ago
      If I take 20 minutes to browse the first 30 links, and then click "next", do I really want "next 30 as of 20 minutes ago"? If I'm on the second page and hit reload, what's the expected behavior? "Second 30 as of 20 minutes ago" or "second 30 right now"? I can kinda-sorta see how this implementation might be better in some corner-case, but it overalls leads me to having a confused state about just where I am in the stream.
• barrkel 12y ago
  I've occasionally mused about the possible value of introspectable and serializable closures. Rather than being memory-only, it would be nice if the weight of keeping them around could be palmed off to the browser using cookies or hidden fields. To be practical, it would require that the activation record chain kept alive by the closure is reasonably short, that the number of live variables in the chain is fairly small, and there be a reliable way of mapping code references in and out. But I think it can be done. One of these days, I'm going to implement a toy language with this feature combined with my other favourite, automatically recalculated data flow variables (think: "variables" that work like spreadsheet cells). These guys are highly applicable to data binding, and making them a first-order language concept makes them much more elegant to use.
  • brudgers 12y ago
    Storing closures on the browser creates a dependencies on JavaScript, user browser settings. and implementation details of various browsers. At the time HN was written, IE was common and Google Chrome did not exist. Doing arbitrary work on an arbitrary client increases application complexity significantly. Sometimes there's a big payoff. Sometimes there isn't.
    • barrkel 12y ago
      I meant closures (or rather, continuations) serialized, encrypted and stored as a string. They wouldn't be callable in the browser.
      • webXL 12y ago
        That's what ASP.net ViewState does more or less. There's a lot of overhead and little gain IMO. I think it's best to transfer as little state as possible across the wire for simplicity.
        • barrkel 12y ago
          It is not. ASP.net viewstate includes a serialization of a set of controls that, server-side, represent the state of the page. That's not what I'm talking about. This is why I think I need to write a toy language example - most people, given a brief outline of what I'm talking about, think I'm talking about something else they're more familiar with, and misunderstand.
• timdierks 12y ago
  This is clever, and the incremental approach is a good engineering direction. That said, readers should be aware that the closures approach is a dead end for a large & complex service: unless you can figure out how to serialize the full closure state to data that can be exchanged between machines, you're always going to be RAM-constrained and subject to machine failure. The loss of state isn't a big deal for a news site, but if you lost the user's state in the middle of a significant process (e.g. dropping the cart mid-checkout), it would be a big problem, even if it was infrequent. What would be great if a language provided a convenient way to repose closures into data blobs that could be exchanged between machines or sent via the browser (an untrusted channel that would have to be secured with cryptography). That said, it's not obvious how to capture the semantics of the full closure of the system state without significant work (look at how fragile object serialization / pickling is). Definitely a good area for language research; I'm sure there's some advances I'm not familiar with.
  • lysium 12y ago
    One difficulty with storing closures is storing and transferring functions, in particular between machines. There is progress in this direction, but it is not easy.
  • drostie 12y ago
    One thing that was exciting about Datomic to me (and still is, I just don't have any projects big enough to use it for) is that you get an immutable database state. You can emulate this in any normal database, but it gets harder to enforce the discipline among other members of your team. The basic idea is that you can serialize those same closures by just pointing to "the state of the database at revision #5968", and then, though the database moves on, you can always use that ID to compute the view of that database at that point. It does the same "heavy lifting" that storing these closures is doing, but you can easily share that ID across a distributed service with no "expired links" problems. It's worth mentioning that you can't send a closure in a non-functional context. That is, if Alice sends a closure to Bob, it cannot any longer be the case that Alice's other operations can mutate Bob's state. So you must be serializing an "orphaned" environment tree with a bunch of closures which point at different nodes of that tree. You could definitely do this even better by stealing some ideas from Smalltalk: encapsulate all of the states in some computational node (the original notion of "object" in OOP) which interacts with all of the other parts of the system communicate with by message-passing, and nothing else. To change the code on-the-fly, you just swap out the "code part" of some node for a new code part, and perhaps transform the state, queuing up the messages while you do so; then you can start replaying those messages to the new code. The benefit is that now at any time the nodes can move around servers arbitrarily, as long as you've got a good name-resolution service to tell you where the object is now. In other words: (1) interpret all the things so that code and data are the same; (2) shared-state is your enemy; serialize orphaned states only; (3) you have to explicitly handle the case where someone makes a request while you are sending their closure to another server.
• perlgeek 12y ago
  Shouldn't it be possible to create a very compact way of serisalizing the closures, and then using that serialization as an URL parameter? If you can uniquely identify the function, you can know the variables that are being closed over, so you would "just" have to serialize the function ID + list of values of the variables, and URL-encode it. Though I haven't done enough Lisp (or even Arc) to evaluate if that's doable without too much effort and fragile magics. (EDIT: clarified a bit)
• chrisBob 12y ago
  Is there a good reason to use pastebin for these type of posts instead of just putting all of the info in the HN post? The only thing I can think of is that it avoids being grouped into the ask section which I think has some disadvantages.
  • spb 12y ago
    And what about Gists?
    • dang 12y ago
      I forgot about those!
  • dang 12y ago
    I originally made it a pastebin link because I didn't want to post a huge off-topic thing into the API thread. Kevin simply linked to that. There's another reason, though: what I wrote was too long for an HN text post (I forget what the limit is, but this was definitely over it) and I didn't have time to make it shorter.
• pbreit 12y ago
  I am the last person to advocate a rewrite but such a thing seems appropriate at this point. Has anyone attempted that in rails, Python, node? Considering the source code is available, should be feasible?
  • zachbeane 12y ago
    The code hasn't been released in five years. There have been a bunch of security fixes since then, and likely many other changes as well.