High memory usage

[JoshKeegan]

Unsure if memory leak, or just kestral behaviour as there are currently no memory limits on the container.
Repro: Do a lookup on "pi" digits for digit "1".

Would expect memory usage to go up as that will use the precomputed digits for the suffix array range but still need to search through ~10% of the suffix array to get the result, whereas a count would just hit the precomputed file. What I wasn't expecting is that it doesn't then release the memory.

[JoshKeegan]

Profiled memory usage and looks like it's not a memory leak, or kestral. The search algorithm loads the full range of sufix array data into system memory to sort it, which for a search like "1" will be ~500million x 64bits (~3.7GiB). Unless you force GC it just doesn't naturally return that memory to the system and it will just leave the heap larger (unless the system were low on memory I guess, in which case it'd be forced to do the heap compaction or get OOM killed).

Due to the sort happening in memory though we can't just put a memory limit on the container, as it would then run out of it when loading the digits...

Actions:

• Look at whether the sorting is necessary. Isn't suffix array ordered..? Even if not, we would only need to maintain n digits in memory to find the nth digit sorted, so maybe improving the sorting algorithm would be worthwhile (still going to have the same worst case scenario, but if someone is searching for the 5billionth occurrence of "1" then they're just trying to break the system :D)
• Mechanism for loading all digits required for the sort is slow. It loads each digit individually, accessing the stream 1 byte at a time. Since the digits aren't aligned with bytes this can be slow. Perhaps we can make some optimisations to that, maybe by adding methods to load ranges of digits rather than individually.

Note: this logic is ported from the original .aspx API, which got around this issue by just validating and enforcing a minimum string length to search for. Since we load some digits onto the client this is reasonable, but prevents them searching for later ocurrences of a digit. Ideally we'd optimise this problem away but if not we should at least add validation to prevent someone DOSing the site accidentally.

[JoshKeegan]

Sorting is required as the suffix array is ordered by the contents not the position, e.g. "32141" string as a suffix array would be:

suffix	i
1	5
141	3
2141	2
32141	1
41	4

So in the above array if you searched for "1" you would get a start index of 1 & end index of 2 (in the suffix array). Since they give indices in the original string of 5 & 3 you can see that a sort would still be required as the first occurrence (3) was not first.

[JoshKeegan]

We may also want to avoid using the suffix array and perform a naive linear search for very short lookup strings, which would prevent the additional memory usage entirely...
Since we return a count & suffix array ranges as part of the lookup response, we would still want to perform the suffix array search (or precomputed digits lookup). We therefore know how many digits we'd load into memory and can base the decision on that.

[JoshKeegan]

Looking back over this: the data is loaded into memory to be sorted so that the nth smallest element can be selected. This means that sorting the entire collection is inefficient. Instead of worrying about sorting, we can instead focus on the more specific problem of selection...

• If memory wasn't the issue but CPU we could perhaps switch to a selection algorithm rather than sorting, e.g. Quickselect.
• To reduce memory usage for the average case we could scan the data on disk, only storing the smallest n elements in memory.

I do wonder if my previous idea of switching to a naive linear search for very short lookup strings is still a better way to control the memory problem, but even if that was done then this sort could still be replaced with Quickselect.

[JoshKeegan]

Looks like this happened again today, just had to manually restart the container as health checks stopped responding:

Looking at what queries were submitted, this seems to have been caused by looking up very short strings (not just counting occurrences). Example:

This looks like a manually crafted request though, that or something went wrong on the front-end. resultId=0 should be resolved client-side, so this should have only needed a count request. A search would only be needed once ~100 results have already been viewed and local search is exhausted.

[JoshKeegan]

Happenned again earlier today, another hand-crafted request for the digit "3":

Have implemented QuickSelect this evening, like I suggested almost 4 years ago, as it's happened a few times recently. Has approx halved the response time, memory consumption is just about ok on the ancient laptop hosting the API.

Real-world worst case (single digit, cold start), now works consistently, taking ~80s.

[JoshKeegan]

Seems to be holding up, looking in the logs there are requests with referer https://pi.paulbennis.com/. Going there, it looks like it's using the API directly & will always call it, even for very short strings e.g. single digit, whick could be served client-side.

Might be worth switching these to a small linear search so if this site, or any other, sends these requests server-side it can still serve them without needing to sort the suffix array positions.

The logic on our own frontend https://pisearch.joshkeegan.co.uk/ is to always search the first 100k digits locally & only perform the suffix array search if that doesn't find the nth result you're after. Something similar server-side would make these very cheap, only falling back to a suffix array search once the Nth result wasn't within the first 100k digits, e.g. searching for the 1st occurrence of "1" would be quick, but the 100,000th would have to use the suffix array.

We could also do something more complex. We'll be doing the suffix array lookup regardless so we'll know how many results there are. Maybe there should be a cut-off where we switch to a linear search, e.g >10M results use linear search. Would need some benchmarking to pick the decision point, but this could make sense as we'd:

• always be able to serve requests (rather than changing behaviour to return an error for these extreme requests)
• significantly reduce worst-case memory usage. We currently still load the suffix array values into memory to run QuickSelect over
• might not impact worst case processing time..? This would be for a small search, e.g. "1" and the last occurrence number (500,034,127). We'd scan the full digits in this case.
  • Probably still faster than current algorithm.
  • Would need benchmarking
  • Very unlikely anyone is every going to want more than the first few results for such a short search.
  • We could also potentially decide whether to scan in reverse to halve the worst-case performance. We know from the suffix array lookup how many results there are, e.g. if there's 5M results and we want the last one, we know it's closer to the end of the digits, so could search from the end.