After looking at the LayeredBloomFilter and the LayerManager and the way it
is intended to be used I found a couple of changes that we might want to
consider.
1) WrappedBloomFilter should not implement copy(), that should be left to
the wrapping implementation.
2) We change LayerManager to be a templated type that contains a List<T
extends BloomFilter> and add two methods first() and last() to retrieve the
first and last internal filters respectively. These are common queries and
should be directly implemented.
3) We change LayeredBloomFilter to be a templated type <T extends
BloomFilter> where T is the type of BloomFilter to be used for each Layer.
For example the use of LayeredBloomFilter for KIP-936 requires a
BloomFilter with an associated timestamp. So when copy() is called for
duplication it must create the same BloomFilter. It uses
WrappedBloomFilter to add the timestamp property. The LayeredBloomFilter
in KIP-936 actually stores a custom TimestampedBloomFilter implementation
that extends WrappedBloomFilter.
This is a rather deep change to LayeredBloomFilter but I think Alex is
correct that we should use List, but that usage dictates that we use T
extends BloomFilter as the type.
Claude
On Sat, Apr 20, 2024 at 3:00 PM Alex Herbert <alex.d.herb...@gmail.com>
wrote:
> On Sat, 20 Apr 2024 at 11:36, Claude Warren <cla...@xenei.com> wrote:
>
> > The LayerdBloomFilter has a method find() that returns an array of ints
> > that are the indices into the layer array. This is easily reproducible
> > using an iterator.
> > There is also get() method that takes an integer argument (an index of
> the
> > bloom filter) and returns the Bloom filter from the layer. This is
> > reproducible but not as efficient using an iterator.
> >
>
> Note that using an iterator is how the LinkedList would do this. We are not
> using an ArrayList with Order(1) retrieval time.
> So performance of the current implementation here is already Order(n).
>
>
> > I think the array is the proper structure.
> >
>
> If an array is the correct structure then we should type to List. Typing to
> an interface allows changing the implementation with no effect on the API.
> For example changing to a concurrent data structure.
>
> The question is what is the most important functionality? Order(1) add and
> remove from the head and tail of the layers (Deque) or Order(1) retrieval
> of layers by depth index (List).
>
> Re: find
>
> It currently returns the layer index. What would you do with this other
> than call get(index) to get the BloomFilter. We could support this with a
> different find method:
>
> // find each bloom filter layer that contains the IndexProducer
> // API can be changed if this is required to return as soon as a filter is
> found that satisfies some requirement (Predicate vs Consumer).
> public void findEach(IndexProducer indexProducer, Consumer<BloomFilter>
> result)
>
> Why else do you require indices of layers? If there is no use case
> other than layer retrieval then this seems to be the wrong API.
>
> Alex
>
>
>
> > Claude
> >
> > On Fri, Apr 19, 2024 at 11:06 AM Alex Herbert <alex.d.herb...@gmail.com>
> > wrote:
> >
> > > On Fri, 19 Apr 2024 at 08:26, Claude Warren <cla...@xenei.com> wrote:
> > >
> > > > While the Deque makes clear the idea of enqueueing and dequeueing
> the
> > > > layers it does not have the method to natively traverse and extract
> > > entries
> > > > from the middle of the queue. Nor would I expect it to. So I think
> > the
> > > > Deque does not accurately reflect how the collection of Bloom filters
> > is
> > > > utilized.
> > > >
> > >
> > > You can traverse and remove entries with the Iterator of the Deque:
> > >
> > > Deque<Integer> d = new LinkedList<>();
> > > d.addAll(Arrays.asList(1, 2, 3, 4, 5));
> > > for (Iterator<Integer> it = d.iterator(); it.hasNext();) {
> > > int i = it.next();
> > > if (i == 3) {
> > > it.remove();
> > > }
> > > }
> > > System.out.println(d);
> > >
> > > prints:
> > >
> > > [1, 2, 4, 5]
> > >
> > > So it is easy to iterate the layers and remove them in Order(1) time
> (per
> > > removal).
> > >
> > > Alex
> > >
> > >
> > > >
> > > > On Wed, Apr 17, 2024 at 2:17 PM Alex Herbert <
> alex.d.herb...@gmail.com
> > >
> > > > wrote:
> > > >
> > > > > Looks good to me.
> > > > >
> > > > > Any opinions on changing the LayerManager to keep the layers in a
> > Deque
> > > > > rather than a LinkedList. I think it would only require a change to
> > the
> > > > > following method:
> > > > >
> > > > > public final BloomFilter get(int depth)
> > > > >
> > > > > Performance will be the same as the Deque can be a LinkedList. This
> > is
> > > > more
> > > > > about how any custom downstream code is currently using the
> > collection
> > > of
> > > > > layers.
> > > > >
> > > > > Alex
> > > >
> > > >
> > >
> >
> >
> > --
> > LinkedIn: http://www.linkedin.com/in/claudewarren
> >
>
--
LinkedIn: http://www.linkedin.com/in/claudewarren
