Need order of magnitude cuts in frequency of nountype network queries

[Jono]

Hi everybody,
I think we have a serious scaling problem. Facts:

1. At about 11am this morning, we exceeded the 10,000 Yelp queries per
day allowed by our Yelp API key. (All copies of Ubiquity are using a
single API key... that's not good.)
2. Currently *every nountype* is getting queried on *every keystroke*.
(Technically, not quite every keystroke if you're typing fast; but
every time that the suggestion list is updated, which I think is every
250ms or once per keystroke, whichever is slower.)
3. Since the "restaurant" nountype queries Yelp, this means that those
calls to yelp are happening even if the user *has no intention of
using the Yelp command*.
4. Because of 1-3, it's easy to see how we could exceed the 10,000
yelp queries per day very, very quickly: that's a limit of
essentially 10,000 ubiquity input keystrokes across *all Ubiquity
users*.
5. Edwin today pointed out, in this thread:
http://groups.google.com/group/ubiquity-firefox/browse_thread/thread/8006d17f3edb3859#
that he uses custom async noun-types and they are getting hammered by
the constant queries... to the point where he asked for the option to
make his nountypes opt-out of general noun-type recognition.

The reason for querying all noun types on all input is so that we can
recognize the nountypes of the input and suggest appropriate verbs
based on those nountypes. There are three cases where this is
important:
* Languages where the nouns normally come first
* Cases where the user has a selection and the input is empty (Either
because they hit the delete key or because this is a context-menu
interaction.) Either way, the selection alone is what we are using to
base suggestions on.
* Cases where the user just happens to type a noun for input rather than a verb.

The following are the strategies that I can think of for reducing the
number of noun network queries.

1. Space them out with timing. Even if we update the suggestion list
on every keystroke/every 250ms, there is no sense in doing network
queries that often - if it takes 1 second for the network query to
return (under ideal circumstances), then there's no point calling it
more often than 1/second. So we could put in a 1/second maximum on
network-noun calls separate from the 250ms maximum on suggestion list
updates. That saves us a factor of 4.

2. There's little point in querying *all* nountypes when the input
doesn't fit one of the cases above. For instance, if the user's input
includes a verb, there's no reason to query all nountypes--only the
nountypes for that verb's specific arguments. In Parser1, we never
called the code that queries all nountypes except when the input was
empty or when the input matched no verbs at all. Parser2 seems to be
querying all nountypes in all circumstances -- which ends up producing
a lot of suggestions that get ranked off the bottom of the list
anyway, because if the input is "tran" then we can and should be
giving "translate" as the top suggestion, not anything nountype-based.

3. We can be cacheing async noun call results much more aggressively.
In most cases, whether an input matches a nountype or not does not
change -- "pizza" is not going to suddenly stop being a type of
restaurant. The *suggestions* may change, but the *fact that there
are suggestions*, which is all we need in order to recognize a
nountype, does not change. So we could cache that, perhaps outside
the nountype itself.

4. Finally, in the longer term we can use Aza's idea of building our
own server that proxies the nountype calls. That way if one user
queries us to ask whether "pizza" is a kind of restaurant, then the
next 10,000 users who query "pizza" will hit our cache. This could
cut our calls down dramatically, but it requires a lot of work to put
up such a server so it's not a short term solution.

What do people think? Are there more ways to reduce the number of
nountype network calls? Which ones of these should we pursue? How
urgent is this relative to the other things that we need to be doing?

--Jono

[satyr]

2. I had no problem with the Parser 1 strategy.

Mixing noun-first suggs with normal suggs is a bad idea. When you know
your task, seeing irrelevant suggs is nothing but annoying.

[mitcho (Michael 芳貴 Erlewine)]

Jono, thanks for bringing this to our attention. Here are some thoughts I have on the different approaches we could take:

1. Space them out with timing.  Even if we update the suggestion list
on every keystroke/every 250ms, there is no sense in doing network
queries that often - if it takes 1 second for the network query to
return (under ideal circumstances), then there's no point calling it
more often than 1/second.  So we could put in a 1/second maximum on
network-noun calls separate from the 250ms maximum on suggestion list
updates.  That saves us a factor of 4.

Something else we could try is to add a delay to async nountype calls... wait 200 ms, say, and then hit the API. Yes, this will make async suggestions slower, but it will have the effect of reducing the overall number of API calls as less of the parses during keystrokes will reach that threshold and initialize those requests.

I believe this would require some retooling of the ajaxRequests counting and management code, though Brandon can say for sure.
 

2. There's little point in querying *all* nountypes when the input
doesn't fit one of the cases above.  For instance, if the user's input
includes a verb, there's no reason to query all nountypes--only the
nountypes for that verb's specific arguments.  In Parser1, we never
called the code that queries all nountypes except when the input was
empty or when the input matched no verbs at all.  Parser2 seems to be
querying all nountypes in all circumstances -- which ends up producing
a lot of suggestions that get ranked off the bottom of the list
anyway, because if the input is "tran" then we can and should be
giving "translate" as the top suggestion, not anything nountype-based.

Yes, this is exactly what happens, because there is always one seed parse in Parser 2 that does not have a verb. This is the parse that lets you enter "twitter is awesome!" and get the suggestion "twitter twitter is awesome!" We could make it so that, if a verb prefix was found, we *don't* run this parse where we try every other verb... I would be strongly opposed to this idea, as I believe it will make it much less easy to use and confusing for users (for example, in Japanese, for example, where we don't require spaces between words, even one letter matching with a verb name could trigger a stop to all other verb parses, making it essentially unusable) but if this is what we need to do to keep our async requests in check for the time being, it's something to consider.
 

3. We can be cacheing async noun call results much more aggressively.
In most cases, whether an input matches a nountype or not does not
change -- "pizza" is not going to suddenly stop being a type of
restaurant.  The *suggestions* may change, but the *fact that there
are suggestions*, which is all we need in order to recognize a
nountype, does not change.  So we could cache that, perhaps outside
the nountype itself. 

 
Is what you're saying that we can split some of these two async nountypes into two things: 1. a filter (ideally regexp) to only try certain kinds of queries) and 2. the actual suggestions? That would indeed be a good idea, but I think some of the async suggestion code actually does do some filtering of some queries themselves. I may be wrong, though. :/

How
urgent is this relative to the other things that we need to be doing?

I think, unfortunately, the stories you gave us about yelp + Edwin (feedly) tell us that this is a major issue we must attack hard before the 0.5 release.

m

--
mitcho (Michael 芳貴 Erlewine)
mit...@mitcho.com
Linguist, coder, and teacher

[Blair McBride]

> I think we have a serious scaling problem.

Agreed!

> 1. Space them out with timing.

Doing #3 (caching) will mean this wouldn't be necessary.

> 2. There's little point in querying *all* nountypes when the input
> doesn't fit one of the cases above.

Agreed - that's kinda silly if its doing that.

> 3. We can be cacheing async noun call results much more aggressively.

Not just can - SHOULD (or even NEED). Even if we had #4 (our own
server), client-side caching will eventually be required.

> 4. Finally, in the longer term we can use Aza's idea of building our
> own server that proxies the nountype calls.

I like. This could also mean a simplification of client-side code, and
help with the service provider model that's been discussed recently (by
having the server translate results from different services into a
standard format).

> Which ones of these should we pursue?

#3 (caching) seems the best bet to me - not amazingly hard to implement,
and will help both short-term and long-term. #2 sounds like a regression
bug to me. #4 is a good longer-term plan, and sounds like it would need
a lot of IT investment.

Another option is brokering deals with relevant service providers to
give our API keys less restricted access, in exchange for bringing them
extra business. Of course, that only works with providers that have the
resources available, not smaller providers (or command-author supplied
services).

- Blair

[satyr]

> So we could cache that, perhaps outside
> the nountype itself.

I'd leave it to nouns themselves as some of them wouldn't like
external caching (async suggs aren't limited to ajax).
They should already be caching if they do high-cost async calls anyway.

[Blair McBride]

It seems silly to me to have to re-implement the same caching behavour
for every noun type that wants it. But I do agree there should be a way
to *not* use cached data - but that's going to be relatively rare.

I think the best way would be to have Ubiquity core handle all caching
unless the noun explicitly requests otherwise (ie, opt out).

As an added bonus, that also means all existing nouns get caching for free.

- Blair

[satyr]

Using the same caching behavior won't be optimal. Nouns know
themselves and can cache better.

Consider that the noun N knows the input P and U will be the same
result and has P's result already:
* If noun-caching, N returns the cached result for U.
* If parser-caching, the parser has to force N to retrieve U's result
since it doesn't know the relation.

Also note that nouns are singletons, but there can be multiple parser instances.
I guess for simplest cases, NounUtils can provide something that
prevents re-implementations.

[Brandon Pung]

I like the things that have been suggested here. I agree with blair that 1) local caching, and 2) only querying all noun types if no verbs match the query are two great places to start. Both of those can likely be implemented relatively quickly and without much infrastructure changes. My only concern with the second one is the stuff that mitcho brought up about how this change would effect other languages such as Japanese. I don't know Japanese, so I'm not entirely aware of how much of an impact this change would make.

As a side note, I gave a presentation about Ubiquity 0.5 at Labs Night last night. The presentation went great and a lot of people were really excited about what we've done. Interestingly, the biggest question that people had was how we were going to control the number of API calls made. They brought up the same concerns that Jono brought up in this thread. So it's certainly a problem we need to tackle for 0.5 or 0.5.1 at the latest. I think we can get the two changes I mentioned above included in 0.5, if that's what we'd like to do.

-Brandon

--
Brandon James Pung
Massachusetts Institute of Technology Class of 2010
Department of Electrical Engineering and Computer Science
828.777.8640 | bp...@mit.edu

[Jono DiCarlo]

Something else to add: I think it's OK if we treat synchronous and
asynchronous noun types differently. For the majority of nountypes
that work entirely on the client side and produce their suggestions
immediately, we can keep doing what we're doing (including querying
them even when there exist verb-first matches). We could decide that
the new rules we're discussing in this thread will be applied only to
that subset of nountypes that do network calls. (There are also local
asynchronous queries, like an awesomebar completion query -- not sure
where that would fall.) Mitcho, would doing it this way help with the
problem you pointed out? We would still have suggestions from the
immediate nountypes even when there is a verb match, so we would still
have 'twitter twitter is awesome' (because arb_text is immediate) and
most of the Japanese equivalents?

Asynchronous nountypes already have to register a certain public
attribute so that its outstanding queries can be canceled if the user
input to the command manager changes. (Brandon knows the details
better than I do.) So we already know which nountypes are doing async
queries; it's a small step from there to dividing up all nountypes
into two separate lists of "immediate nountypes" and "remote
nountypes" and then using them differently.

[Jono DiCarlo]

> Also note that nouns are singletons, but there can be multiple parser instances.
> I guess for simplest cases, NounUtils can provide something that
> prevents re-implementations.

I agree with what Satyr says: NounUtils can provide a basic default
implementation of caching, but some nountypes are going to need to
override it with a specialized cache algorithm of their own. We could
make it so that any nountype that doesn't implement a cache of its own
will get to use the default cache.

A side benefit is that at some point we're going to want to start
using SuggestionMemory in the nountypes. I think the default cache
algorithm can also include some logic to rank the output based on
frequency of use. Or perhaps the default cache mechanism can even be
built on top of SuggestionMemory.

We'll need to figure out whether the nountype API will need to be
altered at all to make room for caching. I don't think it should -
caches should generally be transparent. We may need to make all
nountypes have a common prototype, something like....


nounPrototype = {
suggest: function(text, etc etc etc) {
// most nountypes should leave this alone
var suggestions = this._cacheLookup(text);
if (!suggestions) {
suggestions = this._generateNewSuggestions(text);
}
return suggestions; // or pass them to callback obviously
},
_cacheLookup: function(text, etc etc etc) {
//default cache logic; override this if you want different
behavior
return cachedSuggestions;
},
_addToCache: function(text, suggestions) {
//default cache logic; override this if you want different
behavior
},
_generateNewSuggestions: function(text, etc etc etc) {
//Suggestion logic goes here; most nountypes will override this
function
this._addToCache(text, newResults);
return newResults;
},
default: function() {
//Most nountypes override this function too; it needn't touch the
cache at all.
}
}

What do you think?

[Blair McBride]

As long as the default caching behaviour is opt-out rather than opt-in,
I'm happy.

- Blair

["mitcho (Michael 芳貴 Erlewine)"]

> Something else to add: I think it's OK if we treat synchronous and
> asynchronous noun types differently. For the majority of nountypes
> that work entirely on the client side and produce their suggestions
> immediately, we can keep doing what we're doing (including querying
> them even when there exist verb-first matches). We could decide that
> the new rules we're discussing in this thread will be applied only to
> that subset of nountypes that do network calls. (There are also local
> asynchronous queries, like an awesomebar completion query -- not sure
> where that would fall.) Mitcho, would doing it this way help with the
> problem you pointed out? We would still have suggestions from the
> immediate nountypes even when there is a verb match, so we would still
> have 'twitter twitter is awesome' (because arb_text is immediate) and
> most of the Japanese equivalents?

Yes, this sounds great. It does mean that some of the great things we
can do with asynchronous nountypes, like detecting locations, etc.,
and offering the map command, say, would not work (in English or in
Japanese) but I think it's a good compromise. I can work on trying to
implement this sort of dichotomy today, hopefully touching base with
Brandon to get his thoughts on how to implement it as well.

m

--
mitcho (Michael 芳貴 Erlewine)
mit...@mitcho.com

http://mitcho.com/
linguist, coder, teacher

["mitcho (Michael 芳貴 Erlewine)"]

FYI: I spent a good chunk of time today implementing this approach
Jono and I discussed below.

Parser 2 has two types of parses:

1. parses with verbs (from prefixes it found at the beginning or end
of the input)
2. parses w/o verbs, aka argument-first parses/suggestions

For (1) parses it will now only check the argument strings against the
nountypes needed by that specific verb. For (2) parses, it will only
check nountypes with a special noExternalCalls = true property. satyr,
Brandon, and I agreed that this opt-in strategy for nountypes is a
safer option in this situation, as we'd like to err on the side of
less API calls.

There are a few other things we should consider in the near future.
For example, what if a nountype is async but also returns an immediate
suggestion which should be used in the argument-first suggestions?
satyr and I discussed possibly checking for an immediateSuggest
method, but it'd be good to get some more thoughts and feedback before
we think about this and other use cases.

In the mean time, however, this parser change should greatly reduce
the number of API calls made. If we get some noun-internal caching in
0.5 as well, we hopefully will be able to stem the tide.

mitcho

ps: Happy Firefox 3.5 day! :D

> mitcho (Michael 芳貴 Erlewine)

[Jono DiCarlo]

I talked to Brandon about when we should query async noun types, and I
think there are actually three cases, not just the two you said:
1. Parses with verbs (in which case, query only the nountype that the
verb has for arguments)
2. Parsers without verbs, *when there are also parses with verbs that
exist for the same input*. In which case, we should query all *local*
nountypes.
3. Parsers without verbs, *when no parses with verbs exist for the
same input*. In which case, we should query all local and all async
nountypes.

(case 4 would be "Input is empty", but it should be treated exactly
the same as case 3.)

If we don't allow for case 3, we will be missing a huge number of
useful suggestions.

So let's try implementing cases 1, 2, and 3, and see what that does to
our number of network calls.
IF we find that is still way too high, THEN we can temporarily go to
treating case 3 like case 2.

Requiring the opt-in for a nountype to be treated as local will break
any custom local nountypes that people have written.
Don't async nountypes have to have an ajax query property or something
like that (so that the query knows how to cancel them) -- can't we use
that to tell whether a nountype is a local nountype or an async
nountype?

--Jono


On Jun 30, 9:46 am, "mitcho (Michael 芳貴 Erlewine)" <mit...@mitcho.com>
wrote:

[Jono DiCarlo]

See the following bugs that I just added to Trac:


https://ubiquity.mozilla.com/trac/ticket/799 (reduce number of API
calls)
https://ubiquity.mozilla.com/trac/ticket/797 (cache nountype
results)
https://ubiquity.mozilla.com/trac/ticket/800 (don't query all
nountypes when there are verb matches)

[Jono DiCarlo]

The answer to my question:

> Don't async nountypes have to have an ajax query property or something
> like that (so that the query knows how to cancel them) -- can't we use
> that to tell whether a nountype is a local nountype or an async
> nountype?

is that "async vs. immediate return" is a different question from
"local vs. network". And it's local vs. network that we care about in
this case. So we really do need the new metadata property.

By the way, we had a meeting with me/Aza/Brandon/Anant yesterday and
did some thinking about how a proxy server would work. Our conclusion
was that it's not going to be an easy job, but it will have a lot of
compelling advantages, and it can be used by other projects like
Taskfox in addition to Ubiquity. We're definitely going to be
experimenting with the proxy server during quarter 3, and we're going
to try to have it working along with the release of Ubiquity 0.6.

--Jono