Showing posts with label Design. Show all posts
Showing posts with label Design. Show all posts

Implement Circuit Breaker Pattern with Netflix Hystrix


When we design services, it's important to make them resilient and prevent cascading failures.

Circuit Breaker Pattern
From -Martin Fowler
The basic idea behind the circuit breaker is very simple. You wrap a protected function call in a circuit breaker object, which monitors for failures. Once the failures reach a certain threshold, the circuit breaker trips, and all further calls to the circuit breaker return with an error, without the protected call being made at all. Usually you'll also want some kind of monitor alert if the circuit breaker trips.

There are several ways to apply circuit breaker pattern in java.

Using Netflix Hystrix
public class GetProductsCommand extends HystrixCommand<Set<Product>> {
  private final GetProductsConfiguration config;
  public GetEntitlementsCommand(final GetProductsConfiguration config, final String token) {
      super(HystrixCommandGroupKey.Factory.asKey("products"),config.getTimeoutInMilliseconds());
      this.config = config;
      this.token = token;
  }

  @Override
  protected Set<Product> run() throws Exception {
   // if it's client error, throws HystrixBadRequestException
   // it will not trigger fallback, not count against failure metrics and thus not trigger the circuit breaker.
  }
  @Override
  protected Set<Product> getFallback() throws Exception {}

  @Component
  public static class GetProductsConfiguration {
      @Autowired
      // auto wire services that's going to be used by GetProductsCommand
      @Value("${cobra.oauth.timeout.milliseconds:1000}")
      private int timeoutInMilliseconds;    
  }
}

Call HystrixCommand asynchronously, Get result later
@Autowired
private GetProductsConfiguration getProductsConfiguration;

// call it asycnchoursly
final Future<Set<Products>> productsFuture = new GetProductsCommand(getProductsConfiguration, token).queue();

// later
final Set<Products> products = productsFuture.get();

Propagating ThreadLocal to HystrixCommand
Sometimes, the service we are calling expects it's called in same http thread - it expects thread local from current http thread
requestAttributes = (ServletRequestAttributes) RequestContextHolder.currentRequestAttributes();

We can get current requestAttributes and pass to HystrixCommand:
public class MyHystrixCommand extends HystrixCommand<Result> {
  private final ServletRequestAttributes requestAttributes;
  public GetEntitlementsCommand() {
      super(HystrixCommandGroupKey.Factory.asKey("default"));
      this.requestAttributes = requestAttributes;
      this.requestAttributes = RequestContextHolder.getRequestAttributes();
      this.thread = Thread.currentThread();      
  }
  @Override
  protected Result run() throws Exception {
    try {
      RequestContextHolder.setRequestAttributes(requestAttributes);
      //do something
    } finally {
      clearThreadLocal();
    }
  }
  private void clearThreadLocal()
  {
    if (Thread.currentThread() != thread) {
      RequestContextHolder.resetRequestAttributes();
    }
    thread = null;
  }
}

Using Spring Cloud Hystrix
Spring cloud wraps Netflix Hystrix to make it easier to use.

First add @EnableCircuitBreaker in spring configuration class.
Then add @HystrixCommand annotation to service methods.
@HystrixCommand(fallbackMethod = "fallBack",
commandProperties = {
        @HystrixProperty(name = "fallback.isolation.semaphore.maxConcurrentRequests", value = "1000"),
        @HystrixProperty(name = "execution.isolation.semaphore.maxConcurrentRequests", value = "1000"),
        @HystrixProperty(name = "execution.isolation.thread.timeoutInMilliseconds", value = "2000")},
ignoreExceptions = {InvalidTokenException.class})
public Set<Product> getProducts() {}

public Set<Product> fallBack() {}

@HystrixProperty(name = "execution.isolation.strategy", value = "SEMAPHORE")
  • THREAD — it executes on a separate thread and concurrent requests are limited by the number of threads in the thread-pool
  • SEMAPHORE — it executes on the calling thread and concurrent requests are limited by the semaphore count
Resources:
Netflix Hystrix How to Use

Designing Data Structure


During programming, it's important to design and use right data structures.

Here is a list of problems that we can use to improve our data structure design skills.

Design an in-memory search engine
How to index and store in memory
How to support free text queries, phrase queries
Map<String, List<Document>>
List<Document> is sorted
Document: docId, List<Long> positionIds
List<Long> is sorted
How to save to files
How to merge small files into big files
-- When save to file, make it sorted by word
-- Use merge sort to merge multiple fields
How to make it scalable - how solr cloud works

Google – Manager Peer Problem
1. setManager(A, B) sets A as a direct manager of B
2. setPeer(A, B) sets A as a colleague of B. After that, A and B will have the same direct Manager.

3. query(A, B) returns if A is in the management chain of B.
Tree + HashMap
Map<Integer, TNode> nodeMap

TNode: value, parent, neighbors

Design an Excel sheet’s Data structure
http://codeinterviews.com/Uber-Design-Excel/
You need to perform operations like addition. The excel sheet is very sparse and is used to store numbers in the range 1-65K. Index for a cell is known.
Sparse table: Map<Integer, Map<Integer, String>> data
Follow-up question: In excel, one cell can refer to other cells, if I update one cell, how do you update all the dependent cells?
--Topological sort

- Use multiple data structures
Design a data structure that supports insert, delete, search and getRandom in constant time
private List<String> list = new ArrayList<String>();
Map<String,Integer> indexes = new HashMap<String,Integer>();
-- When remove key, swap the old element in list with the last element, and change the last element index to its new location

Follow up
- What if the value may be duplicated?
- How to test getRandom()?
-- Implement addItem - O(1), getTop10Items
-- Implement HashTable with get,set,delete,getRandom functions in O(1).

Implement Get and Insert for TimeTravelingHashTable
- insert(key, value, timestamp)
- get(key, timestamp)
- get(key) // returns value associated with key at latest time.
Map<K, TreeMap<Float, V>> keyToBSTMap = new HashMap<>();
public V get(K k, Float time){
        if(keyToBSTMap.containsKey(k) == false) return null;
        if(keyToBSTMap.get(k).containsKey(time))
                return  keyToBSTMap.get(k).get(time);
        else
                return  keyToBSTMap.get(k).lowerEntry(time).getValue();
}

Stack supports getMin or getMax
Stack<Integer> main = new Stack<>();
Stack<Integer> minStack = new Stack<>();

Design a stack with operations(findMiddle|deleteMiddle) on middle element
-- Use Double Linked List

LeetCode 311 - Sparse Matrix Multiplication
https://discuss.leetcode.com/topic/30631/my-java-solution
Map<Integer, HashMap<Integer, Integer>> tableA, tableB

Design SparseVector:
-- supports dot(SparseVector that)
Design SparseMatrix
-- supports plus(SparseMatrix that)

Google - remove alarm
https://reeestart.wordpress.com/2016/06/30/google-remove-alarm/
hash map - map priority to set of alarm id

max priority heap - PriorityQueue<Integer>

Recover a Quack Data Structure
Copy its all elements in to an array
--it's pop()/peek() randomly remove or return first or last element

Two Sum III - Data structure design
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
1. O(1) add, O(n) find
2. O(n) add, O(1) find

Add and Search Word
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Shortest Word Distance II
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.


Your method will be called repeatedly many times with different parameters.
Map<String, List<Integer>> map:  word -< sorted index

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.

How to Build Better Application Libaray


When we build library that will be used by many other projects(either internally or externally), we should think about how client will use it, build sample application, talk with client team: what they want us to improve, make the library easier for client team to use.

Examples
Build Common Authentication Library
For example, if we are building a common authentication library, we should package all configuration file(or Java Configuration classes), properties files in the library, also allow the client to overwrite the existing properties files.

The sensitive information(such as db password, aws key etc - at least for production) should be encrypted, and only the manager or operation team should know the encryption key.
Check How to Encrypt Properties in Spring Apllication

It should provide readme file about how to import it(when import it, whether need exclude some dependencies etc), what kind of properties client can overwrite etc.

The client only need import it, change some properties if needed, the application should just work.

Evolve the Library
The library should evolve, it may be developed with old versions such as Spring 3, Jersey 1, codehause Jackson, but over time, it should evolve to newer version Spring 4, Jersey 2, fasterxml Jackson. 

It may build different branch: old branch with old libraries, new branch with new libraries, client can choose when to upgrade to newer version.

How to Build Better Common Library - Lesson Learned


Make it easy to use
Convention over configuration
Package common shared configuration in library
When we are using spring to build (common enterprise) library that will be used by other teams, it's better that we include common shared configuration- using @Configuration class or XML and all other needed stuff in the library.
The client just need import the configuration class and add needed properties file. 

It would be great if we also include basic property files such as thelib_common.properties, and client can provide custom property file such as thelib_overwrite.properties to overwrite it.

So all client need to do is just import the configuration class and add properties file if needed.
@Import({TheLibAppConfig.class})

Build client library - so client can only import necessary libs
When build a service that is going to be called by other teams, provide a client library that only includes classes, libs that are going to be used by client.

Usually client only need some model classes to build request and parse response, 

Some times, we found that we have to use xxService-common library, which includes too many classes, 3-rd libs that client is not used at all.

Check what libs imported
Remove unneeded dependencies

Build Sample Client Application to demo how to use it
Build sample application to demonstrate how client should call the service, check the built application whether it includes unneeded dependencies.

Split functions into multiple small libraries instead of Big Library

Don't declare same dependencies multiple times
For example: if the commons module import XX lib, the service module imports common, then don't import XX-lib again in service module.

Evolve the Library
-- To use newer framework: from codehaus.jackson to fastxml.jackson, jersey 1 to jersey 2, old spring to newer spring.

Don't constrain client teams choices because they use your library.

Labels

ANT (6) Algorithm (69) Algorithm Series (35) Android (7) 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) JSON (7) Java (186) JavaScript (27) 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) 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) adsense (5) bat (8) regex (5) xml (5)