| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.solr.cloud; |
| |
| import java.util.Collection; |
| import java.util.HashMap; |
| import java.util.HashSet; |
| import java.util.List; |
| import java.util.Map; |
| |
| import org.apache.lucene.util.TestUtil; |
| import org.apache.solr.SolrTestCaseJ4; |
| import org.apache.solr.common.cloud.CompositeIdRouter; |
| import org.apache.solr.common.cloud.DocCollection; |
| import org.apache.solr.common.cloud.DocRouter; |
| import org.apache.solr.common.cloud.DocRouter.Range; |
| import org.apache.solr.common.cloud.PlainIdRouter; |
| import org.apache.solr.common.cloud.Slice; |
| import org.apache.solr.common.util.Hash; |
| import org.apache.solr.common.util.StrUtils; |
| |
| public class TestHashPartitioner extends SolrTestCaseJ4 { |
| |
| public void testMapHashes() throws Exception { |
| DocRouter hp = DocRouter.DEFAULT; |
| List<Range> ranges; |
| |
| // make sure the partitioner uses the "natural" boundaries and doesn't suffer from an off-by-one |
| ranges = hp.partitionRange(2, hp.fullRange()); |
| assertEquals(Integer.MIN_VALUE, ranges.get(0).min); |
| assertEquals(0x80000000, ranges.get(0).min); |
| assertEquals(0xffffffff, ranges.get(0).max); |
| assertEquals(0x00000000, ranges.get(1).min); |
| assertEquals(0x7fffffff, ranges.get(1).max); |
| |
| ranges = hp.partitionRange(2, new DocRouter.Range(0, 0x7fffffff)); |
| assertEquals(0x00000000, ranges.get(0).min); |
| assertEquals(0x3fffffff, ranges.get(0).max); |
| assertEquals(0x40000000, ranges.get(1).min); |
| assertEquals(0x7fffffff, ranges.get(1).max); |
| |
| int defaultLowerBits = 0x0000ffff; |
| |
| for (int i = 1; i <= 30000; i++) { |
| // start skipping at higher numbers |
| if (i > 100) i+=13; |
| else if (i > 1000) i+=31; |
| else if (i > 5000) i+=101; |
| |
| long rangeSize = 0x0000000100000000L / i; |
| |
| ranges = hp.partitionRange(i, hp.fullRange()); |
| assertEquals(i, ranges.size()); |
| assertTrue("First range does not start before " + Integer.MIN_VALUE |
| + " it is:" + ranges.get(0).min, |
| ranges.get(0).min <= Integer.MIN_VALUE); |
| assertTrue("Last range does not end after " + Integer.MAX_VALUE |
| + " it is:" + ranges.get(ranges.size() - 1).max, |
| ranges.get(ranges.size() - 1).max >= Integer.MAX_VALUE); |
| |
| for (Range range : ranges) { |
| String s = range.toString(); |
| Range newRange = hp.fromString(s); |
| assertEquals(range, newRange); |
| } |
| |
| // ensure that ranges are contiguous and that size deviations are not too large. |
| int lastEnd = Integer.MIN_VALUE - 1; |
| for (Range range : ranges) { |
| int currStart = range.min; |
| int currEnd = range.max; |
| assertEquals(lastEnd+1, currStart); |
| |
| if (ranges.size() < 4000) { |
| // ranges should be rounded to avoid crossing hash domains |
| assertEquals(defaultLowerBits, currEnd & defaultLowerBits); |
| |
| // given our rounding condition that domains should be less than 1/16 of the step size, |
| // this means that any sizing deviations should also be less than 1/16th of the idealized range size. |
| // boolean round = rangeStep >= (1<<bits)*16; |
| |
| long currRangeSize = (long)currEnd - (long)currStart; |
| long error = Math.abs(rangeSize - currRangeSize); |
| assertTrue( error < rangeSize/16); |
| } |
| |
| |
| // String s = range.toString(); |
| // Range newRange = hp.fromString(s); |
| // assertEquals(range, newRange); |
| lastEnd = currEnd; |
| } |
| |
| } |
| } |
| |
| public int hash(String id) { |
| // our hashing is defined to be murmurhash3 on the UTF-8 bytes of the key. |
| return Hash.murmurhash3_x86_32(id, 0, id.length(), 0); |
| } |
| |
| public void testHashCodes() throws Exception { |
| DocRouter router = DocRouter.getDocRouter(PlainIdRouter.NAME); |
| assertTrue(router instanceof PlainIdRouter); |
| DocCollection coll = createCollection(4, router); |
| doNormalIdHashing(coll); |
| } |
| |
| public void doNormalIdHashing(DocCollection coll) throws Exception { |
| assertEquals(4, coll.getSlices().size()); |
| |
| doId(coll, "b", "shard1"); |
| doId(coll, "c", "shard2"); |
| doId(coll, "d", "shard3"); |
| doId(coll, "e", "shard4"); |
| } |
| |
| public void doId(DocCollection coll, String id, String expectedShard) { |
| doIndex(coll, id, expectedShard); |
| doQuery(coll, id, expectedShard); |
| } |
| |
| public void doIndex(DocCollection coll, String id, String expectedShard) { |
| DocRouter router = coll.getRouter(); |
| Slice target = router.getTargetSlice(id, null, null, null, coll); |
| assertEquals(expectedShard, target.getName()); |
| } |
| |
| public void doQuery(DocCollection coll, String id, String expectedShards) { |
| DocRouter router = coll.getRouter(); |
| Collection<Slice> slices = router.getSearchSlices(id, null, coll); |
| |
| List<String> expectedShardStr = StrUtils.splitSmart(expectedShards, ",", true); |
| |
| HashSet<String> expectedSet = new HashSet<>(expectedShardStr); |
| HashSet<String> obtainedSet = new HashSet<>(); |
| for (Slice slice : slices) { |
| obtainedSet.add(slice.getName()); |
| } |
| |
| assertEquals(slices.size(), obtainedSet.size()); // make sure no repeated slices |
| assertEquals(expectedSet, obtainedSet); |
| } |
| |
| public void testCompositeHashCodes() throws Exception { |
| DocRouter router = DocRouter.getDocRouter(CompositeIdRouter.NAME); |
| assertTrue(router instanceof CompositeIdRouter); |
| router = DocRouter.DEFAULT; |
| assertTrue(router instanceof CompositeIdRouter); |
| |
| DocCollection coll = createCollection(4, router); |
| doNormalIdHashing(coll); |
| |
| // ensure that the shard hashed to is only dependent on the first part of the compound key |
| doId(coll, "b!foo", "shard1"); |
| doId(coll, "c!bar", "shard2"); |
| doId(coll, "d!baz", "shard3"); |
| doId(coll, "e!qux", "shard4"); |
| |
| // syntax to specify bits. |
| // Anything over 2 bits should give the same results as above (since only top 2 bits |
| // affect our 4 slice collection). |
| doId(coll, "b/2!foo", "shard1"); |
| doId(coll, "c/2!bar", "shard2"); |
| doId(coll, "d/2!baz", "shard3"); |
| doId(coll, "e/2!qux", "shard4"); |
| |
| doId(coll, "b/32!foo", "shard1"); |
| doId(coll, "c/32!bar", "shard2"); |
| doId(coll, "d/32!baz", "shard3"); |
| doId(coll, "e/32!qux", "shard4"); |
| |
| // no bits allocated to the first part (kind of odd why anyone would do that though) |
| doIndex(coll, "foo/0!b", "shard1"); |
| doIndex(coll, "foo/0!c", "shard2"); |
| doIndex(coll, "foo/0!d", "shard3"); |
| doIndex(coll, "foo/0!e", "shard4"); |
| |
| // means cover whole range on the query side |
| doQuery(coll, "foo/0!", "shard1,shard2,shard3,shard4"); |
| |
| doQuery(coll, "b/1!", "shard1,shard2"); // top bit of hash(b)==1, so shard1 and shard2 |
| doQuery(coll, "d/1!", "shard3,shard4"); // top bit of hash(b)==0, so shard3 and shard4 |
| } |
| |
| /** Make sure CompositeIdRouter doesn't throw exceptions for non-conforming IDs */ |
| public void testNonConformingCompositeIds() throws Exception { |
| DocRouter router = DocRouter.getDocRouter(CompositeIdRouter.NAME); |
| DocCollection coll = createCollection(4, router); |
| String[] ids = { "A!B!C!D", "!!!!!!", "A!!!!B", "A!!B!!C", "A/59!B", "A/8/!B/19/", |
| "A!B/-5", "!/130!", "!!A/1000", "A//8!B///10!C////" }; |
| for (int i = 0 ; i < ids.length ; ++i) { |
| try { |
| Slice targetSlice = coll.getRouter().getTargetSlice(ids[i], null, null, null, coll); |
| assertNotNull(targetSlice); |
| } catch (Exception e) { |
| throw new Exception("Exception routing id '" + ids[i] + "'", e); |
| } |
| } |
| } |
| |
| /** Make sure CompositeIdRouter can route random IDs without throwing exceptions */ |
| public void testRandomCompositeIds() throws Exception { |
| DocRouter router = DocRouter.getDocRouter(CompositeIdRouter.NAME); |
| DocCollection coll = createCollection(TestUtil.nextInt(random(), 1, 10), router); |
| StringBuilder idBuilder = new StringBuilder(); |
| for (int i = 0 ; i < 10000 ; ++i) { |
| idBuilder.setLength(0); |
| int numParts = TestUtil.nextInt(random(), 1, 30); |
| for (int part = 0; part < numParts; ++part) { |
| switch (random().nextInt(5)) { |
| case 0: idBuilder.append('!'); break; |
| case 1: idBuilder.append('/'); break; |
| case 2: idBuilder.append(TestUtil.nextInt(random(),-100, 1000)); break; |
| default: { |
| int length = TestUtil.nextInt(random(), 1, 10); |
| char[] str = new char[length]; |
| TestUtil.randomFixedLengthUnicodeString(random(), str, 0, length); |
| idBuilder.append(str); |
| break; |
| } |
| } |
| } |
| String id = idBuilder.toString(); |
| try { |
| Slice targetSlice = router.getTargetSlice(id, null, null, null, coll); |
| assertNotNull(targetSlice); |
| } catch (Exception e) { |
| throw new Exception("Exception routing id '" + id + "'", e); |
| } |
| } |
| } |
| |
| /*** |
| public void testPrintHashCodes() throws Exception { |
| // from negative to positive, the upper bits of the hash ranges should be |
| // shard1: 11 |
| // shard2: 10 |
| // shard3: 00 |
| // shard4: 01 |
| |
| String[] highBitsToShard = {"shard3","shard4","shard1","shard2"}; |
| |
| |
| for (int i = 0; i<26; i++) { |
| String id = new String(Character.toChars('a'+i)); |
| int hash = hash(id); |
| System.out.println("hash of " + id + " is " + Integer.toHexString(hash) + " high bits=" + (hash>>>30) |
| + " shard="+highBitsToShard[hash>>>30]); |
| } |
| } |
| ***/ |
| |
| |
| |
| DocCollection createCollection(int nSlices, DocRouter router) { |
| List<Range> ranges = router.partitionRange(nSlices, router.fullRange()); |
| |
| Map<String,Slice> slices = new HashMap<>(); |
| for (int i=0; i<ranges.size(); i++) { |
| Range range = ranges.get(i); |
| Slice slice = new Slice("shard"+(i+1), null, map("range",range), "collections1"); |
| slices.put(slice.getName(), slice); |
| } |
| |
| DocCollection coll = new DocCollection("collection1", slices, null, router); |
| return coll; |
| } |
| |
| |
| |
| // from negative to positive, the upper bits of the hash ranges should be |
| // shard1: top bits:10 80000000:bfffffff |
| // shard2: top bits:11 c0000000:ffffffff |
| // shard3: top bits:00 00000000:3fffffff |
| // shard4: top bits:01 40000000:7fffffff |
| |
| /*** |
| hash of a is 3c2569b2 high bits=0 shard=shard3 |
| hash of b is 95de7e03 high bits=2 shard=shard1 |
| hash of c is e132d65f high bits=3 shard=shard2 |
| hash of d is 27191473 high bits=0 shard=shard3 |
| hash of e is 656c4367 high bits=1 shard=shard4 |
| hash of f is 2b64883b high bits=0 shard=shard3 |
| hash of g is f18ae416 high bits=3 shard=shard2 |
| hash of h is d482b2d3 high bits=3 shard=shard2 |
| hash of i is 811a702b high bits=2 shard=shard1 |
| hash of j is ca745a39 high bits=3 shard=shard2 |
| hash of k is cfbda5d1 high bits=3 shard=shard2 |
| hash of l is 1d5d6a2c high bits=0 shard=shard3 |
| hash of m is 5ae4385c high bits=1 shard=shard4 |
| hash of n is c651d8ac high bits=3 shard=shard2 |
| hash of o is 68348473 high bits=1 shard=shard4 |
| hash of p is 986fdf9a high bits=2 shard=shard1 |
| hash of q is ff8209e8 high bits=3 shard=shard2 |
| hash of r is 5c9373f1 high bits=1 shard=shard4 |
| hash of s is ff4acaf1 high bits=3 shard=shard2 |
| hash of t is ca87df4d high bits=3 shard=shard2 |
| hash of u is 62203ae0 high bits=1 shard=shard4 |
| hash of v is bdafcc55 high bits=2 shard=shard1 |
| hash of w is ff439d1f high bits=3 shard=shard2 |
| hash of x is 3e9a9b1b high bits=0 shard=shard3 |
| hash of y is 477d9216 high bits=1 shard=shard4 |
| hash of z is c1f69a17 high bits=3 shard=shard2 |
| ***/ |
| |
| } |