Building Troubleshooting Friendly Application - Using Feature Toggle


In last post, I talked about how to change log level and add diagnosis information per request at runtime. It helps us to debug and trouble shooting problems in production environment.

But at that time, we use X-DEBUG-KEY header,  check whether it matches the key at server side, if so enable this feature. 

This is unsafe(as we may return internal implementation information to client). - even we encrypt the X-DEBUG-KEY in the source code and change it before push to production.

Recently, we developed a common feature toggle service. So now we can use the feature toggle service to control who can use the debug request feature and turn it on/off dynamically at server side.
FeatureService
Admin can create/update/delete feature. The feature can be stored in database(sql or nosql).
Client will call isFeatureOn with feature name and a map. isFeatureOn will get the feature from db and check whether it's on. It will return Decision.NEUTRAL if not exist.
public interface FeatureService {
    Decision isFeatureOn(String name, Map<String, Object> variables);
    public Optional<Feature> getFeature(final String name);
    public void addFeature(Feature feature);
    public void updateFeature(Feature feature);
    void deleteFeature(Iterator<String> iterator);
    Collection<Feature> getAllFeatures();
}
Feature and Expression
Feature contains a list of expression, and will call the expression's apply method to check whether the feature should be on or off. 


Currently we only support AnyMatchExpression, PercentageExpression and ScriptExpression, but it can be easily extended.

Notice we can use the optional ttlSeconds to control how long the feature will be on, after that it will be expired. This adds another safety layer to the feature toggle service.

-- We annotate updateTime with View.Viewable.class, so outside API can only view it but can't update it: check Using Jackson JSON View to Protect Mass Assignment Vulnerabilities

public class Feature {
    private String name;
    private String appId;
    /**
     * This is used as extension, in case later we support rejectFirst.
     */
    private boolean acceptFirst = true;
    public Feature() {}
    @JsonView(View.Editable.class)
    private List<Expression> expressionList = new ArrayList<>();
    @JsonView(View.Editable.class)
    protected int ttlSeconds = -1;

    @JsonView(View.Viewable.class) // all other properties are marked as Editable, except updateTime
    private Date updateTime;

    @JsonIgnore
    public boolean isEffective() {
        if (ttlSeconds != -1) {
            if (updateTime == null) {
                logger.error("Invalid feature {}, updateTime is null while timeToLive is {}", name, ttlSeconds);
                throw new XXException(ErrorCode.INTERNAL_ERROR,
                        String.format("Invalid feature %s: ", getName()));
            }
            final MutableDateTime expiredTime = new MutableDateTime(updateTime);
            expiredTime.addSeconds(ttlSeconds);

            return expiredTime.isAfterNow();
        }
        return true;
    }
    public Decision isFeatureOn(final Map<String, String> variables) {
        if (hasExpired()) {
            return Decision.NEUTRAL;
        }
        final List<Expression> expressionList = getExpressionList();
        for (final Expression expression : expressionList) {
            if (expression.apply(variables).equals(Decision.ACCEPT)) {
                return Decision.ACCEPT;
            }
        }
        return Decision.NEUTRAL;
    }
    // ignore equals, hashcode, toString, getter, setter..    
}    

@JsonIgnoreProperties(ignoreUnknown = true)
@org.codehaus.jackson.annotate.JsonIgnoreProperties(ignoreUnknown = true)
@JsonTypeInfo(use = JsonTypeInfo.Id.NAME, include = JsonTypeInfo.As.PROPERTY, property = AbstractExpression.FIELD_TYPE,
        visible = false)
@JsonSubTypes({@Type(value = PercentageExpression.class, name = PercentageExpression.TYPE),
        @Type(value = AnyMatchExpression.class, name = AnyMatchExpression.TYPE),
        @Type(value = ScriptExpression.class, name = ScriptExpression.TYPE)})
public interface Expression {
    public Decision apply(Map<String, Object> variables);
}

public class AnyMatchExpression extends AbstractExpression {
    public static final String TYPE = "anyMatch";
    /**
     * which variable name to look up
     */
    private String variableName;

    private boolean caseInsensitive;
    @JsonProperty("set")
    private Set<String> set = new HashSet<>();

    public AnyMatchExpression() {
        type = TYPE;
    }
    @Override
    public Decision apply(final Map<String, Object> variables) {
        final Object object = variables.get(variableName);
        if (object != null) {
            final Iterable<String> idIt = SomeUtil.COMMA_SPLITTER.split(object.toString());
            for (String id : idIt) {
                if (caseInsensitive) {
                    id = id.toLowerCase();
                }
                if (set.contains(id)) {
                    return Decision.ACCEPT;
                }
            }
        }
        return Decision.NEUTRAL;
    }
    /**
     * Precondition: There is no null value in the set. Otherwise it will throw NPE.
     */
    public void setSet(final HashSet<String> set) {
        if (caseInsensitive) {
            final HashSet<String> lowercaseSet = new HashSet<>();
            for (final String word : set) {
                lowercaseSet.add(word.toLowerCase());
            }

            this.set = lowercaseSet;
        } else {
            this.set = set;
        }
    }
    // ignore toString, getter, setter..
}
public class PercentageExpression extends AbstractExpression {
    public static final String TYPE = "percentage";
    /**
     * a value between 0 and 100
     */
    private int percentage;
    public PercentageExpression() {
        type = TYPE;
    }
    @Override
    public Decision apply(final Map<String, Object> variables) {
        if (percentage == 100) {
            return Decision.ACCEPT;
        }
        final Random random = new Random();
        final int rValue = random.nextInt(100);
        if (rValue < percentage) {
            return Decision.ACCEPT;
        }
        return Decision.REJECT;
    }
}
Check Whether Debug Request Feature is On
Now we can check whether the debug request feature is turned on for this user. - we only do this when X_DEBUG_REQUEST header exists. - Of course we cache the Feature object, so we don't do db call every time.
protected void checkDebugRequestFeature(final ContainerRequest request) {
    if (debugRequestEnabled) {
        final String debugRequest = request.getHeaderValue(X_DEBUG_REQUEST);
        if (StringUtils.isNotBlank(debugRequest)) {
            final User user = getUserObjectHere();

            if (SomeUtil.isFeatureOn(SomeUtil.FEATURE_DEBUG_REQUEST, user, featureService)) {
                MDC.put(X_DEBUG_REQUEST, debugRequest);
                RequestContextUtil.getRequestContext().setEnableDebug(Boolean.valueOf(debugRequest));
            } else {
                RequestContextUtil.getRequestContext().setEnableDebug(false);
            }
        }
    }
}
Other User Cases Using Feature Toggle
Feature Toggle is a quite simple but powerful service. With it, we can do A/B testing, we can test and trouble shooting on productions: such as we can allow some specific users to debug request, to mock user etc.

Improve Apache Commons ArrayUtils removeElements to O(n)


Recently, I read apache commons ArrayUtils removeElements source code and found that its implementation is not efficient when try to get all indexes that needed to be removed.

It's O(m*n): n is the length of origin array, m is the unique count of toBeRemoved.
    final BitSet toRemove = new BitSet();
    for (final Map.Entry<Byte, MutableInt> e : occurrences.entrySet()) {
        final Byte v = e.getKey();
        int found = 0;
        for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
            found = indexOf(array, v.byteValue(), found);
            if (found < 0) {
                break;
            }
            toRemove.set(found++);
        }
    }

We can just scan the origin array once to get all indexes that needed to be removed.
    final BitSet toRemove = new BitSet();

    // the only change here, time complexity changed to O(n)
    for (int i = 0; i < array.length; i++) {
        final int key = array[i];

        final MutableInt count = occurrences.get(key);
        if (count != null) {
            count.decrement();
            if (count.intValue() == 0) {
                occurrences.remove(key);
            }
            toRemove.set(i);
        }
    }

I created one JIRA: Improve ArrayUtils removeElements time complexity to O(n)
The complete code
The implementation is quite elegant and robust.
 
    public static int[] removeElements(final int[] array, final int... values) {
        if (isEmpty(array) || isEmpty(values)) {
            return clone(array); // can't just return origin array
        }
        final HashMap<Integer, MutableInt> occurrences = new HashMap<Integer, MutableInt>(values.length);
        for (final int v : values) {
            final Integer boxed = Integer.valueOf(v);
            final MutableInt count = occurrences.get(boxed);
            if (count == null) {
                occurrences.put(boxed, new MutableInt(1));
            } else {
                count.increment();
            }
        }
        final BitSet toRemove = new BitSet();

        // My change here, time complexity changed to O(n)
        for (int i = 0; i < array.length; i++) {
            final int key = array[i];

            final MutableInt count = occurrences.get(key);
            if (count != null) {
                count.decrement();
                if (count.intValue() == 0) {
                    occurrences.remove(key);
                }
                toRemove.set(i);
            }
        }

        return (int[]) removeAll(array, toRemove);
    }

    static Object removeAll(final Object array, final BitSet indices) {
        final int srcLength = ArrayUtils.getLength(array);
        // No need to check maxIndex here, because method only currently called from removeElements()
        // which guarantee to generate on;y valid bit entries.
//        final int maxIndex = indices.length();
//        if (maxIndex > srcLength) { 
//            throw new IndexOutOfBoundsException("Index: " + (maxIndex-1) + ", Length: " + srcLength);
//        }
        final int removals = indices.cardinality(); // true bits are items to remove
        final Object result = Array.newInstance(array.getClass().getComponentType(), srcLength - removals);
        int srcIndex=0;
        int destIndex=0;
        int count;
        int set;
        while((set = indices.nextSetBit(srcIndex)) != -1){
            count = set - srcIndex;
            if (count > 0) {
                System.arraycopy(array, srcIndex, result, destIndex, count);
                destIndex += count;
            }
            srcIndex = indices.nextClearBit(set);
        }
        count = srcLength - srcIndex;
        if (count > 0) {
            System.arraycopy(array, srcIndex, result, destIndex, count);            
        }
        return result;
    } 

Find the element that Appears Once - Using BitSet


We can use different approaches:
1. Use two hashsets(as we don't need the real count): uniqueSet, duplicateSet
The first time we see the element, we put it into both sets, if we see it again, we remove it from uniqueSet.
2. We can use BitSet to reduce space - uniqueBitSet and duplicateBitSet
The first time we see the element, we put set its bit in uniqueBitSet and duplicateBitSet, if we see it again, we clear its bit in duplicateBitSet.
    // Using Bitset
    public static int findUnqiueNumber1(final int[] array) {
        final BitSet unique = new BitSet(), duplicate = new BitSet();
        for (final int number : array) {
            // first time see this number
            if (!duplicate.get(number)) {
                unique.set(number);
                duplicate.set(number);
            } else {
                // if see it again
                unique.clear(number);
            }
        }

        final int unqinueValue = unique.nextSetBit(0);

        if (unqinueValue == -1) {
            throw new NoUniqueException("No unique number");
        }
        final int nextUnqiueValue = unique.nextSetBit(unqinueValue + 1);
        if (nextUnqiueValue != -1) {
            throw new MoreThanOneUniqueException(String.format(
                    "More than 1 unique number found. We found at least %s, %s", unqinueValue, nextUnqiueValue));
        }

        return unqinueValue;
    }

    // Using HashSet
    public static int findUnqiueNumber2(final int[] array) {
        final Set<Integer> uniqueSet = new HashSet<>(), duplicateSet = new HashSet<>();
        for (final int number : array) {
            // first time see this number
            if (!duplicateSet.contains(number)) {
                uniqueSet.add(number);
                duplicateSet.add(number);
            } else {
                // if see it again
                uniqueSet.remove(number);
            }
        }

        if (uniqueSet.isEmpty()) {
            throw new NoUniqueException("No unique number");
        }
        if (uniqueSet.size() > 1) {
            throw new MoreThanOneUniqueException(
                    String.format("More than 1 unique number found. We found %s count", uniqueSet.size()));
        }
        final int unqinueValue = uniqueSet.iterator().next();
        return unqinueValue;
    }


    private static class MoreThanOneUniqueException extends RuntimeException {
        private static final long serialVersionUID = 1L;

        public MoreThanOneUniqueException(final String messge) {
            super(messge);
        }
    }
    private static class NoUniqueException extends RuntimeException {
        private static final long serialVersionUID = 1L;

        public NoUniqueException(final String messge) {
            super(messge);
        }
    }

    @Rule
    public ExpectedException thrown = ExpectedException.none();

    @Test
    public void test() {
        Assert.assertEquals(findUnqiueNumber2(new int[] {1}), 1);
        Assert.assertEquals(findUnqiueNumber2(new int[] {1, 2, 2}), 1);
        Assert.assertEquals(findUnqiueNumber2(new int[] {1, 2, 2}), 1);
    }

    @Test
    public void testNoUnqiue() {
        thrown.expect(NoUniqueException.class);
        findUnqiueNumber2(new int[] {});
    }

    @Test
    public void testNoUnqiue2() {
        thrown.expect(NoUniqueException.class);
        findUnqiueNumber2(new int[] {1, 1, 2, 2});
    }

    @Test
    public void testMoreThanONeUnqiue() {
        thrown.expect(MoreThanOneUniqueException.class);
        findUnqiueNumber2(new int[] {1, 2});
    } 
Related:
[CareerCup] 10.4 Find All Duplicates Elements
You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4 kilobytes of memory available, how would you print all duplicate elements in the array?

It can also be solved by using BitSet. add i into bitset, if i happens again, print it out.
Bonus:
org.apache.commons.lang3.ArrayUtils.removeElements(int[], int...)
    public static int[] removeElements(final int[] array, final int... values) {
        if (isEmpty(array) || isEmpty(values)) {
            return clone(array);
        }
        final HashMap<Integer, MutableInt> occurrences = new HashMap<Integer, MutableInt>(values.length); // use MutableInt to avoid Integer creation again and again.
        for (final int v : values) {
            final Integer boxed = Integer.valueOf(v);
            final MutableInt count = occurrences.get(boxed);
            if (count == null) {
                occurrences.put(boxed, new MutableInt(1));
            } else {
                count.increment();
            }
        }
        final BitSet toRemove = new BitSet();
        for (final Map.Entry<Integer, MutableInt> e : occurrences.entrySet()) {
            final Integer v = e.getKey();
            int found = 0;
            for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
                found = indexOf(array, v.intValue(), found);
                if (found < 0) {
                    break;
                }
                toRemove.set(found++);
            }
        }
        return (int[]) removeAll(array, toRemove);
    }
    static Object removeAll(final Object array, final BitSet indices) {
        final int srcLength = ArrayUtils.getLength(array);
        // No need to check maxIndex here, because method only currently called from removeElements()
        // which guarantee to generate on;y valid bit entries.
//        final int maxIndex = indices.length();
//        if (maxIndex > srcLength) { 
//            throw new IndexOutOfBoundsException("Index: " + (maxIndex-1) + ", Length: " + srcLength);
//        }
        final int removals = indices.cardinality(); // true bits are items to remove
        final Object result = Array.newInstance(array.getClass().getComponentType(), srcLength - removals);
        int srcIndex=0;
        int destIndex=0;
        int count;
        int set;
        while((set = indices.nextSetBit(srcIndex)) != -1){
            count = set - srcIndex;
            if (count > 0) {
               System.arraycopy(array, srcIndex, result, destIndex, count); // System.arraycopy is native and faster.
               destIndex += count;
            }
            srcIndex = indices.nextClearBit(set);
        }
        count = srcLength - srcIndex;
        if (count > 0) {
            System.arraycopy(array, srcIndex, result, destIndex, count);            
        }
        return result;
    }

java.util.BitSet.cardinality()
public int cardinality() {
    int sum = 0;
    for (int i = 0; i < wordsInUse; i++)
        sum += Long.bitCount(words[i]);
    return sum;
}    

ConcurrentModificationException: Remove during Loop - Java Common Bug Pattern


It's a common bug that we try to use collection.remove during looping the collection.

For example: in ehcache 2.7.0 getAll method
    public Map getAll(Collection keys) throws IllegalStateException, CacheException {
        getAllObserver.begin();
        checkStatus();

        if (disabled) {
            return null;
        }

        if (keys.isEmpty()) {
            return Collections.EMPTY_MAP; // optimize here: no need to create new map
        }

        Map elements = compoundStore.getAll(keys);

        long misses = 0;
        for (Entry entry : elements.entrySet()) {
            Object key = entry.getKey();
            Element element = entry.getValue();
            if (element == null) {
                misses++;
            } else {
                if (isExpired(element)) {
                    tryRemoveImmediately(key, true);
                    elements.remove(key); // bug here.
                    misses++;
                } else {
                    element.updateAccessStatistics();
                }
            }
        }
        int requests = elements.size();
        if (misses == 0) {
            getAllObserver.end(GetAllOutcome.ALL_HIT, requests, 0);
        } else if (misses == requests) {
            getAllObserver.end(GetAllOutcome.ALL_MISS, 0, misses);
        } else {
            getAllObserver.end(GetAllOutcome.PARTIAL, requests - misses, misses);
        }
        return elements;
    }

This was fixed in latest version: ehcache 2.10.0 getAll method
Usually we use Iterator> it=map.entrySet().iterator(); then use it.remove() to delete the element.
Here the iterator of the map returned by compoundStore.getAll() may not support remove method. 
That's why ehcache first adds all expired key to a HashSet, then call:
          try {
              elements.keySet().removeAll(expired);
          } catch (UnsupportedOperationException e) {
              elements = new HashMap(elements);
              elements.keySet().removeAll(expired);
          }

Here is the HashSet removeAll method:
     * Note that this implementation will throw an
     * UnsupportedOperationExceptionif the iterator returned by the

     * iteratormethod does not implement the removemethod.
    public boolean removeAll(Collection c) {
        Objects.requireNonNull(c);
        boolean modified = false;

        if (size() > c.size()) { // optimization: different branch based on size diff
            for (Iterator i = c.iterator(); i.hasNext(); )
                modified |= remove(i.next());
        } else {
            for (Iterator i = iterator(); i.hasNext(); ) {
                if (c.contains(i.next())) {
                    i.remove();
                    modified = true;
                }
            }
        }
        return modified;

    }
ehcache 2.10.0 getAll method
public Map getAll(Collection keys) throws IllegalStateException, CacheException {
        getAllObserver.begin();
        checkStatus();

        if (disabled) {
            return null;
        }

        if (keys.isEmpty()) {
            getAllObserver.end(GetAllOutcome.ALL_HIT, 0, 0);
            return Collections.EMPTY_MAP;
        }

        Map elements = compoundStore.getAll(keys);
        Set expired = new HashSet();
        for (Entry entry : elements.entrySet()) {
            Object key = entry.getKey();
            Element element = entry.getValue();
            if (element != null) {
                if (isExpired(element)) {
                    tryRemoveImmediately(key, true);
                    expired.add(key);
                } else {
                    element.updateAccessStatistics();
                }
            }
        }
        if (!expired.isEmpty()) {
          try {
              elements.keySet().removeAll(expired);
          } catch (UnsupportedOperationException e) {
              elements = new HashMap(elements);
              elements.keySet().removeAll(expired);
          }
        }

        int requests = keys.size();
        int hits = elements.size();
        if (hits == 0) {
            getAllObserver.end(GetAllOutcome.ALL_MISS, 0, requests);
        } else if (requests == hits) {
            getAllObserver.end(GetAllOutcome.ALL_HIT, requests, 0);
        } else {
            getAllObserver.end(GetAllOutcome.PARTIAL, hits, requests - hits);
        }
        return elements;
    }

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)