zookeeper-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hanm <...@git.apache.org>
Subject [GitHub] zookeeper pull request #590: [ZOOKEEPER-1177] Add the memory optimized watch...
Date Sat, 22 Sep 2018 04:38:36 GMT
Github user hanm commented on a diff in the pull request:

    https://github.com/apache/zookeeper/pull/590#discussion_r219660592
  
    --- Diff: src/java/main/org/apache/zookeeper/server/watch/BitHashSet.java ---
    @@ -0,0 +1,156 @@
    +/**
    + * 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.zookeeper.server.watch;
    +
    +import java.util.BitSet;
    +import java.util.Set;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.lang.Iterable;
    +
    +import org.apache.zookeeper.server.util.BitMap;
    +
    +/**
    + * Using BitSet to store all the elements, and use HashSet to cache limited
    + * number of elements to find a balance between memory and time complexity.
    + *
    + * Without HashSet, we need to to use O(N) time to get the elements, N is
    + * the bit numbers in elementBits. But we need to keep the size small to make
    + * sure it doesn't cost too much in memory, there is a tradeoff between
    + * memory and time complexity.
    + *
    + * Previously, was deciding to dynamically switch between SparseBitSet and
    + * HashSet based on the memory consumption, but it will take time to copy
    + * data over and may have some herd effect of keep copying data from one
    + * data structure to anther. The current solution can do a very good job
    + * given most of the paths have limited number of elements.
    + */
    +public class BitHashSet implements Iterable<Integer> {
    +
    +    static final long serialVersionUID = 6382565447128283568L;
    +
    +    /**
    +     * Change to SparseBitSet if we we want to optimize more, the number of
    +     * elements on a single server is usually limited, so BitSet should be
    +     * fine.
    +     */
    +    private final BitSet elementBits = new BitSet();
    +    private final Set<Integer> cache = new HashSet<Integer>();
    +
    +    private final int cacheSize;
    +
    +    // To record how many elements in this set.
    +    private int elementCount = 0;
    +
    +    public BitHashSet() {
    +        this(Integer.getInteger("zookeeper.bitHashCacheSize", 10));
    +    }
    +
    +    public BitHashSet(int cacheSize) {
    +        this.cacheSize = cacheSize;
    +    }
    +
    +    public synchronized boolean add(Integer elementBit) {
    +        if (elementBit == null || elementBits.get(elementBit)) {
    +            return false;
    +        }
    +        if (cache.size() < cacheSize) {
    +            cache.add(elementBit);
    +        }
    +        elementBits.set(elementBit);
    +        elementCount++;
    +        return true;
    +    }
    +
    +    /**
    +     * Remove the watches, and return the number of watches being removed.
    +     */
    +    public synchronized int remove(Set<Integer> bitSet, BitSet bits) {
    +        cache.removeAll(bitSet);
    +        elementBits.andNot(bits);
    +        int elementCountBefore = elementCount;
    +        elementCount = elementBits.cardinality();
    +        return elementCountBefore - elementCount;
    +    }
    +
    +    public synchronized boolean remove(Integer elementBit) {
    +        if (elementBit == null || !elementBits.get(elementBit)) {
    +            return false;
    +        }
    +
    +        cache.remove(elementBit);
    +        elementBits.clear(elementBit);
    +        elementCount--;
    +        return true;
    +    }
    +
    +    public synchronized boolean contains(Integer elementBit) {
    +        if (elementBit == null) {
    +            return false;
    +        }
    +        return elementBits.get(elementBit);
    --- End diff --
    
    should we look up `cache` first here? If not, what's the purpose of adding `cache`?


---

Mime
View raw message