Reducing search indexing latency to one second | Hacker News Reader

Reducing search indexing latency to one second

blog.twitter.com

149 pointsi0exception40 comments

Indexing latency aside, when I search for something on Twitter it shows me results as I type

When I tap on the result, there is invariably something else at the tap location

What's the terminology for this? Flash of ephemeral search result?

Are there any good ways of avoiding this problem?

This is something that seemingly none of the big platforms or companies get right. Not Twitter, not Microsoft, not Firefox, not Apple, not a single one of them.

Seemingly they missed the lesson web developers learned ten years ago that you can't change content that the user is currently looking at without any interaction done, unless that's to be expected from the user.

But auto-loading items in a list is somehow still difficult for these companies to get right. Once you're done typing your query in the window's start menu, apple's "quick launcher thing" or twitter's search widget, it takes X seconds for the query to actually finish, so while you're hovering the menu, it changes content from underneath and the thing you wanted to click on, has been switched to something else.

I'm starting to wonder if this is on purpose, as seemingly no one is getting this right, but I don't understand what metric they are optimizing for (incorrectly) to believing that this behavior is correct.

I am so angry at this behavior on Firefox.

I type the first letter. Firefox displays 10 options. I think they are bookmarks and recent google searches containing the letter. The ordering kinda corresponds to how recently or how often I used them, but it is not exactly that, for example the link I choose almost always somehow remains at the 2nd place. Whatever.

I type the second letter. Again, Firefox displays 10 options, bookmarks and recent google searches that contain the substring. At that moment, the link I want to click is quite often displayed somewhere. So I move my mouse...

...but a fraction of second later, Firefox loads "things it thinks I might want to search" (probably popular search results by other people that start with those two letters I typed) and inserts them into positions 2 - 5, moving the other search results below them...

...and just as I am pressing my mouse button, the link below my mouse cursor is replaced by google search for something completely irrelevant.

Aaaaargh!

(I wonder whether it is an accident, or on purpose, that the most frequently used link goes to the 2nd place, not the 1st one, so it gets replaced by an irrelevant google search. I suspect it probably increases some metric somewhere, and is probably interpreted as a good thing.)

Why not disable search suggestions? Having every keypress sent to google doesn't seem great.

Er... yeah, that makes sense. Thanks, I turned it off. I didn't realize this was optional.

I get this on iPhone search. I see what I want and go tap it, but it changes at the last second and I end up opening the wrong thing. And now I’ve trained the AI on the wrong thing just to make things worse.

Not sure what I'm doing differently but the search suggestions go below the history suggestions for me.

> Seemingly they missed the lesson web developers learned ten years ago that you can't change content that the user is currently looking at without any interaction done, unless that's to be expected from the user.

Did web developers learn this lesson? Because I still see this literally every day on the web.

My guess: the web developers who learned that lesson 10 years ago are now outnumbered and outvoted by the developers and designers who don't have enough experience to do interaction design well. Neophytes will pretty much always outnumber experts, and the neophytes can only be counted on to adhere to a handful of the most popular design guidelines.

> you can't change content that the user is currently looking at without any interaction done, unless that's to be expected from the user

I think it’a more realistic to say that there has to be some latency bound in any user interaction. Clearly the result of any action is not instantaneous. Search boxes are tricky because the user isn’t sure what side effect typing an additional character will have - it could not refine the search or get a whole new set of results. If it’s not indicated to the user when the operation completes, then they can assume the former and then click at a bad time.

> I'm starting to wonder if this is on purpose

People click on it, thus metrics tell that users like it, when they changed user interaction went down, so they kept it ... almost sounds plausible.

This is certainly one of the most frustrating things in modern UIs, although I’m not sure what it’s called I feel like it’s common enough for someone to have coined a name by this point. There are a few ways I can think of to deal with it:

1. Have very close to 0 latency. Clearly not always doable.

2. When in the process of searching, indicate to the user that the results aren’t fresh and new ones are coming - grey out the current options for instance.

3. Analyze how long the new results have been shown for and treat very short durations differently. If the new results have been up for 2ms, it’s not possible for that to be your desired intention.

Another possibility would be to freeze the results if the user is moving their mouse/arrow keys over the options.

That would not be sufficient even with a mouse: sometimes, I start moving my mouse and then click on the result that has already moved before I even started moving the mouse, but the whole interaction takes less than one second so I don't have the time to react to the update.

Graying out the results while the new one are coming can also be annoying: if the result that I am looking for is here and the new results are slow to come, I would be frustrated to be unable to click on it.

The whole situation is annoying but I don't know of a good solution and therefore I can't blame people who don't get this right.

doesn't work for mobile unfortunately

A possible solution: Human reaction time is on the order of something like 215ms, if the change happened less than 100ms ago or so, the user probably wanted the previous result as opposed to the current one. Add a additional dialog to confirm?

This was one of the approaches I thought of but I wanted to know if this is a "solved" problem or whether there are some prevailing best practices by people who have spent time researching the various approaches

Apparently it seems like one of those "can't believe it's 2020 and we can't solve X" types of problems

nifty! i was thinking that new results (even if more relevant) get appended to the bottom

I believe the most common terminology for this is "layout shift": https://web.dev/cls/

It is more specifically about parts of the UI moving rather than disappearing and being replaced with something else. But the idea is the same.

Just to tack on, I cannot understand autocomplete results that do this:

Search: abc Results: abcdef, abcxyz

Then I type d

Results: abcxyz

How did typing more of the top result make it less likely I wanted the top result?

Even worse: not considering exact matches when autocompleting. I’m looking at you, JIRA.

My name is Stephen. My username in my company JIRA is `stephen`. It is simply not possible for coworkers to reference my own name in many fields due to autocomplete behavior. Every other employee named Stephen (or user with `stephen` prefixing their username) is presented, but mine is unavailable.

Oh absolutely. I'd also add in that if I type "jor" then your autocomplete shouldn't say "nobody by that name, there's a jörgen but they clearly can't be talking about them so I won't return that at all".

I would just call that a UI race condition. Desktop GUIs occasionally had them but anything mobile oriented is just so much worse.

IMO it should be solved at browser level. Basically browser should remember which pixel corresponds to which HTML element at any given timestamp. So when you click, it should check whether that div was located at this pixel 1 second ago. If it was not there, just ignore that click.

Until then it should be solved at application level.

This would break things like games

I guess you could do something like a css property to turn it off or on

Sure, this is just rough description. Probably it's better to just send a different event, so conventional websites won't react to it, but you can handle it if you want.

I've thought about this a bit and I think one way I might do it is freeze the list once a user has typed something, even as better results are coming in. Once they type a new letter you can redo the search with the better results, and users will do that anyways if they don't see their results in that list.

Huh!

I thought it was always me and I was being too cynical but on mobile web, half of the times, I am scrolling and stop to click on media/link in the tweet and freaking add shows up and I end up clicking on that. May be it's just my device but annoying as hell UX.

Disable Javascript. For example,

https://mobile.twitter.com/search?q=

works without Javascript

This is excellent.

I was recently reviewing Lucene concepts and found this video really good: https://www.youtube.com/watch?v=T5RmMNDR5XI

Also this site has a series of Lucene articles that are pretty nice. The one on Term Vectors in particular: http://makble.com/what-is-term-vector-in-lucene

Based on some quick research it seems like Lucene is already using a sorted skip data structure for the posting list, so I wonder why they had to do a custom implementation? Perhaps it has to do with their custom Document ID scheme and how they want to preserve order in the Posting List being different from the default behavior. It also sounds like searchers are searching on indexes as they're being written, and there is some custom coordination around visibility, which might require diverging from Lucene default behavior.

Either way, pretty impressive!

Interestingly, Elasticsearch exposes something similar to this, based on a Lucene level feature that enables index level sorting.

You can specify such an index level default sort (similar to what they use custom IDs to achieve) and it will use skip lists to make searching with that sort faster. It will impose an indexing overhead but I would guess for usecases like this it could make sense.

https://www.elastic.co/blog/index-sorting-elasticsearch-6-0

Google: "Yah, we did that 20 years ago on mechanical hard drives."

Seriously though: Google built realtime indexing a very long time ago.

I co-implemented a small-scale (like 100k pages) full text search engine about 20 years ago with a lot of inspiration from the 1998 paper "The Anatomy of a Large-Scale Hypertextual Web Search Engine".

I had always assumed Google used 2-3 layers sort of like in Hierarchical storage management (HSM); fresh data stored in RAM and older data stored on HDDs, then combining them during the query step. I was itching to have a go at implementing that, but it wasn't really required for our use case.

I believe that these days many big enough latency optimized systems use a hierarchy of storage solutions (magnetic, flash, RAM).

Here's a useful rule of thumb: the costs per byte of RAM:flash:magnetic are approximately 100:10:1.

This is a really good piece of technical writing. I particularly enjoyed the explanation of skip lists.

One of my favorite data structures. I was learning about the internals of LevelDB/RocksDB and noticed they use skiplists as a default for the in-memory datastore. It's an alternative to balanced trees (AVL/Red-black) but it's way easier to implement and understand. Invented in the '80s and still widely used in modern tools.

Is there an engineering blog where they describe how they manage to show the exact timeline from where I left off each time I open the app?

If I remember correctly, every time a tweet is made, a fan-out operation is made, adding the tweet to each of the follower's timeline. I would think the app just needs to remember the position on their own timeline?

That's part of it, but not the entire solution.

http://highscalability.com/blog/2013/7/8/the-architecture-tw...

> Outliers, those with huge follower lists, are becoming a common case. Sending a tweet from a user with a lot of followers, that is with a large fanout, can be slow. Twitter tries to do it under 5 seconds, but it doesn’t always work, especially when celebrities tweet and tweet each other, which is happening more and more. One of the consequences is replies can arrive before the original tweet is received. Twitter is changing from doing all the work on writes to doing more work on reads for high value users.

Doing a quick google search, there are claims of "6,000 tweets per second in 2020", or about 6 tweets per millisecond. The blog posts mentions there is an edge case for getting more than 16 tweets per millisecond.

Rather close margins assuming an exponentiation usage growth of Twitter. I wonder how long that variant is going to last.

We left out some detail here to keep the post readable. In reality, we can handle 16 Tweets per millisecond per partition. We have tens of partitions, so that makes the edge case less likely. If we do see a gigantic growth in Tweet rate, we would need to increase the number of partitions anyways, so we decided this edge case was acceptable.

Reply on news.ycombinator.com