Limit the number of vanityPath MapEntry

[Antonio Sanso <as...@adobe.com>]

hi *,

I have been working on [0], namely Limit the number of vanityPath MapEntry.
In a nutshell at the moment we keep a cache of vanityPaths.
So far so good. The problem is that this cache is unbounded. Namely if the Sling instance has 1000000 vanityPaths all the vanityPaths are kept in memory.
Of course the memory is limited and is not hard to imagine an OutOfMemory…
For this reason I am willing to propose a limit the number of vanity path Osgi configuration.
That’s said we need now to adapt the map/resolve algorithm to this new situation.
So far I so two possible solutions ( but IMHO one is really not a way to go).
Let’s take in consideration the resolve case (the map case can be then solved in a similar way).

The two possible solution are when the cache is bound:

- do a search for a vanityPath if the /requestPath is not in the cache (as anticipated above I think this is not a great solution since it can be expensive, indeed I assume the majorities of requests are not even “vanityPath requests” so both the cache and the search will return empty result)
- the second solution is a bit more convoluted but way more efficient. Let me try to explain:

* the cache is now bounded to the number of vanityPath entries as per config
* the algorithm stays as is for now for resolve(). So it before looks for vanityPath in the cache and then continues to look in the repository for a path that matches a resource
* if a requestedPath ends to be evaluated as NonExistingResource a last resort vanityPath search is executed and tries to find for a vanityPath entry 

There is only on problem here. This indeed can lead to a non compatible change and can work only if we also introduce a new configuration where a vanityPath cannot be set to a value that is equal to an existing resource.
E.g. if I have some content /foo and in /bar I try to set a vanityPath /foo this is not taken in consideration as valid vanityPath

Sorry for the rather complicated mail but WDYT?

regards

antonio

[0] https://issues.apache.org/jira/browse/SLING-4216

Re: Limit the number of vanityPath MapEntry

[Antonio Sanso <as...@adobe.com>]

On Dec 8, 2014, at 1:40 PM, Vikas Saurabh <vi...@gmail.com> wrote:

>> Since the cache initialization was a separate thread I had to take care on properly handle this situation and updating properly the bloomfilter.
> 
> Sorry for being a little slow to catch up. But, as far as I understood
> the issue -- it is about that we need to load all vanity mappings
> during startup to declare that the instance is indeed up. I thought it
> implied that until the thread that loads/caches/marks all vanity paths
> finishes its task, startup isn't marked as complete (please excuse the
> different terms -- I'm not sure of the exact usages in sling)

This is the current behavior. In SLING-3290 in order to speed up the startup time the idea was to have he initialization of the cache in a new thread 
and using the BloomFilter as a fallback for startup. 
The problem there is that while the cache was initialized and the system was up with the Bloomfilter somebody was allowed to add new vanityPaths.
As you might imagine this could be pretty brittle to handle...

> 
>> With this new approach of limiting the vanity Path entries size I think the Bloom Filter can come back in the solution :)
> 
> I think even with bloom filter (assuming we don't serialize its state
> back on clean shutdowns), we'd have to read 'all' vanity mappings once
> during startup. Bloom filter would just use less memory to mark if we
> really have mapping in repo (even when there is a miss on cached
> vanity entry)
> 
> I think SLING-3290 is about reducing number of MapEntries required to
> load up all vanity paths…

this was about minimize the start time (back then there wasn’t the though to limit the cache unluckily :()

> but, I think SLING-4216 is more to do with
> how many of vanity entries would we like to keep in memory -- which I
> think can be solved with some cache implementation (probably LRU???) +
> bloom filter(to tell if going back to repo would be useful or not)

exactly

regards

antonio

> 
> Thanks,
> Vikas

Re: Limit the number of vanityPath MapEntry

[Vikas Saurabh <vi...@gmail.com>]

> Since the cache initialization was a separate thread I had to take care on properly handle this situation and updating properly the bloomfilter.

Sorry for being a little slow to catch up. But, as far as I understood
the issue -- it is about that we need to load all vanity mappings
during startup to declare that the instance is indeed up. I thought it
implied that until the thread that loads/caches/marks all vanity paths
finishes its task, startup isn't marked as complete (please excuse the
different terms -- I'm not sure of the exact usages in sling)

> With this new approach of limiting the vanity Path entries size I think the Bloom Filter can come back in the solution :)

I think even with bloom filter (assuming we don't serialize its state
back on clean shutdowns), we'd have to read 'all' vanity mappings once
during startup. Bloom filter would just use less memory to mark if we
really have mapping in repo (even when there is a miss on cached
vanity entry)

I think SLING-3290 is about reducing number of MapEntries required to
load up all vanity paths... but, I think SLING-4216 is more to do with
how many of vanity entries would we like to keep in memory -- which I
think can be solved with some cache implementation (probably LRU???) +
bloom filter(to tell if going back to repo would be useful or not)

Thanks,
Vikas

Re: Limit the number of vanityPath MapEntry

[Antonio Sanso <as...@adobe.com>]

fair enough Vikas,

as said I was also proposing BloomFilter.
At that stage I "gave up” mainly due “synchronization issue” at startup.
Since the cache initialization was a separate thread I had to take care on properly handle this situation and updating properly the bloomfilter.
With this new approach of limiting the vanity Path entries size I think the Bloom Filter can come back in the solution :)

Thanks for the “remainder”

regards

antonio

On Dec 5, 2014, at 6:02 PM, Vikas Saurabh <vi...@gmail.com> wrote:

>> we already took in consideration Bloom Filter for a related issue [2].
>> We decided that is still not too optimal since it leads toward content duplication and I would like to avoid that for now
>> 
>> [2] https://issues.apache.org/jira/browse/SLING-3290
>> 
> 
> Well, imho, bloom filters won't duplicate content -- they'd just have
> bit-masks to tentatively mark existence of a value. Moreover, if we
> use guava's implementation (which I think sling doesn't want to do...
> if I am reading SLING-3290 correctly), then we can serialize them on
> clean shutdown to have practically no work done during startup. For
> crashes, we can probably live with re-creating the filter again.
> 
> About, BloomFilterUtils attached in SLING-3290, I think it's just
> using 1 hash function to create mask. In general, bloom filter
> implementation would have more number of hashes to configure less
> false-positives.
> 
> About caching actual data in RAM (and assuming sling would sit on top
> of Oak??) -- should caching of most used nodes be a responsibility of
> repository implementation?.. but, that's probably a different
> discussion.
> 
> Thanks,
> Vikas

Re: Limit the number of vanityPath MapEntry

[Vikas Saurabh <vi...@gmail.com>]

> we already took in consideration Bloom Filter for a related issue [2].
> We decided that is still not too optimal since it leads toward content duplication and I would like to avoid that for now
>
> [2] https://issues.apache.org/jira/browse/SLING-3290
>

Well, imho, bloom filters won't duplicate content -- they'd just have
bit-masks to tentatively mark existence of a value. Moreover, if we
use guava's implementation (which I think sling doesn't want to do...
if I am reading SLING-3290 correctly), then we can serialize them on
clean shutdown to have practically no work done during startup. For
crashes, we can probably live with re-creating the filter again.

About, BloomFilterUtils attached in SLING-3290, I think it's just
using 1 hash function to create mask. In general, bloom filter
implementation would have more number of hashes to configure less
false-positives.

About caching actual data in RAM (and assuming sling would sit on top
of Oak??) -- should caching of most used nodes be a responsibility of
repository implementation?.. but, that's probably a different
discussion.

Thanks,
Vikas

Re: Limit the number of vanityPath MapEntry

[Antonio Sanso <as...@adobe.com>]

Thanks Vikas,

we already took in consideration Bloom Filter for a related issue [2].
We decided that is still not too optimal since it leads toward content duplication and I would like to avoid that for now

regards

antonio

[2] https://issues.apache.org/jira/browse/SLING-3290

On Dec 5, 2014, at 4:26 PM, Vikas Saurabh <vi...@gmail.com> wrote:

>> - do a search for a vanityPath if the /requestPath is not in the cache (as anticipated above I think this is not a great solution since it can be expensive, indeed I assume the majorities of requests are not even “vanityPath requests” so both the cache and the search will return empty result)
> 
> I think the major concern here is that (a lot of) non-vanity path
> resources would still have to go to repo for lookup. Would a bloom
> filter[1] implementation be possible to help taking that decision?
> 
> Thanks,
> Vikas
> [1]: http://en.wikipedia.org/wiki/Bloom_filter

Re: Limit the number of vanityPath MapEntry

[Vikas Saurabh <vi...@gmail.com>]

> - do a search for a vanityPath if the /requestPath is not in the cache (as anticipated above I think this is not a great solution since it can be expensive, indeed I assume the majorities of requests are not even “vanityPath requests” so both the cache and the search will return empty result)

I think the major concern here is that (a lot of) non-vanity path
resources would still have to go to repo for lookup. Would a bloom
filter[1] implementation be possible to help taking that decision?

Thanks,
Vikas
[1]: http://en.wikipedia.org/wiki/Bloom_filter