ShardBucketCollection #184

jklamer · 2018-08-01T19:01:48Z

Description:

This is a new abstract collection implementation that allows for easy sorting of located items, like AtlasEntities or CheckFlags, into different buckets as defined by shards. This collection acts as wrapper for the underlying bucket collections. The bucket collection type is determined by the implementer. There are a number of control functions that need to be implemented to allow for simple and flexible use.

Rectangle and Counter changes were made to enable the testing and creation of this class.

Details:
The collection lazily constructs collections per bucket. It uses synchronized blocks to ensure only one collection is initialized per shard and no information is lost. This is to allow for multithreaded insertion/sorting, but it does not guarantee the wrapped collection is thread safe.
The bucket collections are stored in an array and the initializing shards are stored in an immutable R-tree with the index of its corresponding collection in the array. In the figure below I show the SlippyTile shards I used to initialize a number of test collections, each with the corresponding collection array index.

All collection functions interface with the collection index and/or collection array.

The collection does not support safe iterating while inserting.

Potential Impact:

This will change no current implementations but it will enable a number of different located sorting tasks by enabling quick and simple implementation.

Unit Test Approach:

I created the most basic test collection possible and tested all the main collection functionalities on that as well as some of the unique functionalities. I then created more test collections that take advantage of the flexibility of the control functions and tested that they worked as intended.

There are multiple tests checking for the same thing in different ways to gain code coverage.

Test Results:

As expected.

In doubt: Contributing Guidelines

lucaspcram · 2018-08-02T16:46:12Z

src/main/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollection.java

+        if (Objects.nonNull(collection))
+        {
+            final long addCount = collection.stream().filter(this::add).count();
+            return addCount > 0;


Very slick.

lucaspcram · 2018-08-02T16:47:56Z

...est/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollectionTestClasses.java

+{
+    /**
+     * Collection that will handle splitting multipolygons into buckets by overrideing the add
+     * function


nit: overriding

MikeGost

Good stuff! Minor nits in the test classes.

MikeGost · 2018-08-02T16:56:40Z

src/test/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollectionTest.java

+            caught = true;
+        }
+
+        Assert.assertTrue("Resolve shard default method is an unsupported operation", caught);


Check out @Test(expected = UnsupportedOperationException.class) annotation to allow for easily verifying expected exceptions. Might simplify this code a little.

+1 for this. I use this patten in ProtoIntegerStringDictionaryAdapterTest. Check that for an example in action.

MikeGost · 2018-08-02T17:00:10Z

src/test/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollectionTest.java

+        final PolyLine[] allArray = polylineBuckets2.toArray(array1);
+        Assert.assertArrayEquals(array2, allArray);
+
+        // get code coverage


What does get code coverage mean?

I want to use all the methods to get good coverage score for sonar.

lucaspcram · 2018-08-02T17:11:31Z

src/main/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollection.java

+
+    /**
+     * Construct the collection by allocation space for a collection for each of the shards and
+     * assigning the index back.


nit: allocating

lucaspcram · 2018-08-02T17:13:43Z

src/main/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollection.java

+     * @param shard
+     *            shard associated with the collection
+     * @return true if the collection has been added to successful and changed as a result, false
+     *         otherwise


nit: successfully

lucaspcram · 2018-08-02T17:31:49Z

src/main/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollection.java

+    public boolean contains(final Object object)
+    {
+        final Optional<LocatedType> typedItem = this.castToLocatedType(object);
+        if (typedItem.isPresent())


I like this pattern a lot actually. I will be stealing it ;)

credit due to @matthieun

lucaspcram · 2018-08-02T17:34:56Z

Looks good @jklamer . Left a few minor documentation nits.

So help me to understand this a bit better. Is this sort of like a way to partition a collection of Locateds based on some sharding?

Based on the logic in the add method, it seems to me like you give it a Located and it figures out (using an RTree) which collection (which is tied to a shard, hence the RTree and the ShardToCollectionIndex class) that Located belongs in.

And then from there, it looks like you can ask for all collections that overlap some arbitrary bounds (based on the shard boundary with which that collection is associated), which it can compute efficiently due to having a spatial index.

Am I getting it?

What types of problems does this facilitate solving? (I am sure there are many, since you clearly put some serious effort into creating this.)

jklamer · 2018-08-02T22:05:54Z

@lucaspcram Yes exactly you are getting it.
Problems this will help facilitate solving: sorting and helping limiting the scope of other locality related tasks.

matthieun

One question about the Sharding v.s. RTree. If you think this is unnecessary, I will approve!

matthieun · 2018-08-03T16:54:09Z

src/main/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollection.java

+ *            Type of the Collection of LocatedType associated with shards
+ * @author jklamer
+ */
+public abstract class ShardBucketCollection<LocatedType extends Located & Serializable, CollectionType extends Collection<LocatedType> & Serializable>


This is the most complex declaration I have seen ;)

It looks much scarier than it is

matthieun · 2018-08-03T17:05:55Z

src/main/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollection.java

+        this(maximumBounds, SlippyTile.allTiles(zoomLevel, maximumBounds));
+    }
+
+    public ShardBucketCollection(final Rectangle maximumBounds, final Sharding sharding)


Sharding implementations are already behaving like a spatial index. I believe here you could gain some performance and simplification by using the sharding itself to query the intersecting bounds instead of a RTree, as the scope here is much smaller that what RTrees can handle...

Well, if I query the sharing directly I would also need a map of of shard -> index, so that would require two look-ups instead of just the one now, even if the second look up is constant time it is more steps. I would also need to store both sharding and the map of shard ->index, instead of just the RTree.

In terms of what RTree's can handle, this allows for initializations for slippy tiles up to the SlippyTile max zoom, which is 30. At zoom 19 there are 274.9 billion tiles. So even if the max bounds isn't the whole world the Rtree needs the ability to hold a lot even if my tests didn't work it that hard.

I see, if it works for you now, we can merge it!

matthieun · 2018-08-06T16:04:41Z

src/main/java/org/openstreetmap/atlas/utilities/collections/ShardBucketCollection.java

+        this(maximumBounds, SlippyTile.allTiles(zoomLevel, maximumBounds));
+    }
+
+    public ShardBucketCollection(final Rectangle maximumBounds, final Sharding sharding)


I see, if it works for you now, we can merge it!

ShardBucketCollection

0ad17d5

MikeGost added the New Feature label Aug 2, 2018

lucaspcram reviewed Aug 2, 2018

View reviewed changes

MikeGost reviewed Aug 2, 2018

View reviewed changes

lucaspcram reviewed Aug 2, 2018

View reviewed changes

PR comments addressed

2d6932d

matthieun requested changes Aug 3, 2018

View reviewed changes

matthieun approved these changes Aug 6, 2018

View reviewed changes

matthieun merged commit 7f1e7a6 into osmlab:dev Aug 6, 2018

matthieun added this to the 5.1.6 milestone Aug 6, 2018

jklamer deleted the shardBucketCollection branch May 29, 2019 04:20

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ShardBucketCollection #184

ShardBucketCollection #184

jklamer commented Aug 1, 2018

lucaspcram Aug 2, 2018

jklamer Aug 2, 2018

lucaspcram Aug 2, 2018

MikeGost left a comment

MikeGost Aug 2, 2018

lucaspcram Aug 2, 2018

MikeGost Aug 2, 2018

jklamer Aug 2, 2018

lucaspcram Aug 2, 2018

lucaspcram Aug 2, 2018

lucaspcram Aug 2, 2018

jklamer Aug 2, 2018

lucaspcram commented Aug 2, 2018 •

edited

Loading

jklamer commented Aug 2, 2018

matthieun left a comment

matthieun Aug 3, 2018

jklamer Aug 3, 2018

matthieun Aug 3, 2018

jklamer Aug 3, 2018

matthieun Aug 6, 2018

jklamer Aug 6, 2018

matthieun Aug 6, 2018

ShardBucketCollection #184

ShardBucketCollection #184

Conversation

jklamer commented Aug 1, 2018

Description:

Potential Impact:

Unit Test Approach:

Test Results:

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

MikeGost left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

lucaspcram commented Aug 2, 2018 • edited Loading

jklamer commented Aug 2, 2018

matthieun left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

lucaspcram commented Aug 2, 2018 •

edited

Loading