Sentinel is a lightweight flow control framework for distributed service framework. It mainly takes flow as the entry point to maintain system stability from multiple dimensions such as flow control, fusing degradation and system load protection.

Sentinel was born in alibaba in 2012 and its main goal is traffic control. From 2013 to 2017, Sentinel grew rapidly and became a fundamental part of all Alibaba microservices, covering almost all core e-commerce scenarios. In 2018, Sentinel evolved into an open source project.

Sentinel ecosystem

Sentinel features

  • Rich application scenarios: Sentinel has undertaken the core scenarios of Alibaba’s double Eleven traffic drive in the past 10 years, such as SEC killing (i.e. burst traffic control within the range of system capacity), message peaking and valley filling, cluster flow control, real-time fusing of unavailable downstream applications, etc.
  • Complete real-time monitoring: Sentinel also provides real-time monitoring capabilities. From the console, you can see a summary of the performance of a single machine-by-second data, or even a cluster of less than 500 machines, for accessing the application.
  • Extensive Open source ecosystem: Sentinel provides out-of-the-box integration modules with other open source frameworks/libraries, such as Spring Cloud, Apache Dubbo, gRPC, Quarkus. You can quickly access Sentinel by introducing the appropriate dependencies and simple configuration. Sentinel also provides native implementations of Java, Go, C++ and other languages.
  • Comprehensive SPI extension mechanism: Sentinel provides an easy-to-use, comprehensive SPI extension interface. You can quickly customize the logic by implementing an extension interface. For example, customize rule management and adapt dynamic data sources.

Sentinel features

Introduction to sliding Windows

  • Window parameters:

    • IntervalLength: intervalLength, that is, the length of statistical time, determines the number of statistical Windows during data calculation
    • WindowLength: indicates the time window width
    • Count: indicates the statistics in a time window
    • StartTime: indicates the startTime of each time window. Each time point belongs to a time window, that is, the time axis is divided according to the width of the time window, windowLength. Each time window has a startTime startTime.

  • Gets a statistic at a time

    • Get the current time currTime
    • According to currTime – (used time window). StartTime < intervalLength, find the participating time window
    • The statistic of the current time can be obtained by summing the statistic of count participating in the time window

  • Updates statistics at a certain time

    • Get the current time currTime
    • Find the time window to which the current time belongs and update the count in the time window

There’s an infinite number of time Windows that are divided over the entire time axis. However, it is implementationally impossible to represent an infinite number of time Windows, so implementations use a fixed size array of time Windows. Multiplexing/cyclic storage of time Windows is adopted. Basis: Only a few time Windows need to be counted at a certain point in time, so only a few time Windows need to be saved. SampleCount is the size of the array. Relationship: sampleCount=intervalLength/windowLength

Update statistics at a point in time:

  • Get the current time currTime
  • Index = (currTime/windowLength) % sampleCount
  • Window = array[index]
  • Run the currTime – time window command to check whether the time window has expired. Reset the time window, that is, the inside of the statistic count to zero, and then add count; Add count directly before expiration.

Get statistics at a point in time:

  • Get the current time currTime
  • StartTime < intervalLength: currTime – Time window startTime < intervalLength

Flow control architecture

In Sentinel, all resources are assigned a resourceName (resourceName). Each resource call creates an Entry object. Entry can be created automatically by adapting to the mainstream framework or explicitly by annotating or calling the SphU API. When an Entry is created, a series of slot chains are also created. These slots have different responsibilities, for example:

  • NodeSelectorSlotCollect the paths of resources and store the call paths of these resources in a tree structure for limiting traffic degradation according to the call paths;
  • ClusterBuilderSlotThe statistics of the storage resource and caller information, such as RT, QPS, thread count of the resource, will be used as the basis for multi-dimensional flow limiting and degradation;
  • StatisticSlotIt is used to record and statistics the monitoring information of runtime indicators in different latitudes.
  • FlowSlotIs used for traffic control according to preset traffic limiting rules and slot statistics.
  • AuthoritySlotAccording to the configuration of the blacklist and whitelist and call source information, to do the blacklist and whitelist control;
  • DegradeSlotBy statistics and preset rules, to do the circuit breaker downgrade;
  • SystemSlotThe total inlet flow is controlled by the state of the system, such as load1.

StatisticSlot is one of Sentinel’s core functional slots for real-time call statistics.

  • clusterNode: Runtime statistics of ClusterNodes with unique resource identifiers
  • origin: based on statistics from different callers
  • defaultnode: Runtime statistics based on context entry name and resource ID
  • Sentinel uses a high performance sliding window data structureLeapArrayTo collect real-time second-level indicator data, which can well support high concurrency scenarios with more writes than reads.

Statistical core class

  • ArrayMetric uses a class that hides the implementation of a time window and has a member variable, LeapArray

  • LeapArray time window implementation, which has an array of time Windows, the elements of the array for WindowWrap, i.e. time Windows

  • WindowWrap time window, T for MetricBucket

  • MetricBucket statistics, which contain variables for specific statistics whose “type” is determined by MetrciEvent

  • MetricEvent statistic type, which corresponds to the statistic variables stored in MetricBucktet

Relationships between classes

Resource real-time statistics class, there are three statistical dimensions, second level (rollingCounterInSecond), minute level (rollingCounterInMinute), connection number level. Through ArrayMetric, LeapArray to achieve sliding window statistics.

When the first request comes in, Sentinel creates a new fixed-time-width window bucket that records runtime data metrics such as RT, QPS, BQ, and so on, depending on sample Count. Sentinel uses valid bucket statistics to determine whether the request can be delivered. For example, if a rule definition has only 100 requests that can pass, it will sum the QPS in all valid buckets and compare them to the threshold defined in the rule. The request continues because the previous buckets may fail and the window data needs to be reset.

Core implementation: LeapArray

  • Get the current window, divided into four scenarios:

    • 1. If the old bucket does not exist, we create a new bucket in windowStart and try to update the circular array via CAS. Only one thread can successfully update, while the other thread produces its timeslice.
    • 2. If the current windowStart is equal to the start timestamp of the old bucket, the time is in the bucket, so return the bucket directly.
    • 3. If the start timestamp of an old bucket is behind the time provided, it means that the bucket is deprecated. We must reset the bucket to the current windowStart. Note that reset and clean up operations are hardly atomic, so we need an update lock to ensure bucket updates are correct. Updating the lock is conditional (on a small scale) and will only take effect if the bucket is deprecated, so in most cases it does not result in a performance penalty.
    • 4, should not pass here, because the time provided is already behind, usually caused by clock back.
/**
 * Get bucket item at provided timestamp.
 *
 * @param timeMillis a valid timestamp in milliseconds
 * @return current bucket item at provided timestamp if the time is valid; null if time is invalid
 */
public WindowWrap<T> currentWindow(long timeMillis) {
    if (timeMillis < 0) {
        return null;
    }

    int idx = calculateTimeIdx(timeMillis);
    // Calculate current bucket start time.
    long windowStart = calculateWindowStart(timeMillis);

    /* * Get bucket item at given time from the array. * * (1) Bucket is absent, then just create a new bucket and CAS update to circular array. * (2) Bucket is up-to-date, then just return the bucket. * (3) Bucket is deprecated, then reset current bucket and clean all deprecated buckets. */
    while (true) {
        WindowWrap<T> old = array.get(idx);
        if (old == null) {
            /* * B0 B1 B2 NULL B4 * ||_______|_______|_______|_______|_______||___ * 200 400 600 800 1000 1200 timestamp * ^ * time=888 * bucket is empty, so create new and update * * If the old bucket is absent, then we create a new bucket at {@code windowStart}, * then try to update circular array via a CAS operation. Only one thread can * succeed to update, while other threads yield its time slice. */
            WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
            if (array.compareAndSet(idx, null, window)) {
                // Successfully updated, return the created bucket.
                return window;
            } else {
                // Contention failed, the thread will yield its time slice to wait for bucket available.Thread.yield(); }}else if (windowStart == old.windowStart()) {
            /* * B0 B1 B2 B3 B4 * ||_______|_______|_______|_______|_______||___ * 200 400 600 800 1000 1200 timestamp * ^ * time=888 * startTime of Bucket 3: 800, so it's up-to-date * * If current {@code windowStart} is equal to the start timestamp of old bucket, * that means the time is within the bucket, so directly return the bucket. */
            return old;
        } else if (windowStart > old.windowStart()) {
            /* * (old) * B0 B1 B2 NULL B4 * |_______||_______|_______|_______|_______|_______||___ * ... 1200 1400 1600 1800 2000 2200 timestamp * ^ * time=1676 * startTime of Bucket 2: 400, deprecated, should be reset * * If the start timestamp of old bucket is behind provided time, that means * the bucket is deprecated. We have to reset the bucket to current {@code windowStart}. * Note that the reset  and clean-up operations are hard to be atomic, * so we need a update lock to guarantee the correctness of bucket update. * * The update lock is conditional (tiny scope) and will take effect only when * bucket is deprecated, so in most cases it won't lead to performance loss. */
            if (updateLock.tryLock()) {
                try {
                    // Successfully get the update lock, now we reset the bucket.
                    return resetWindowTo(old, windowStart);
                } finally{ updateLock.unlock(); }}else {
                // Contention failed, the thread will yield its time slice to wait for bucket available.Thread.yield(); }}else if (windowStart < old.windowStart()) {
            // Should not go through here, as the provided time is already behind.
            return newWindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); }}}Copy the code
  • Gets the array index position, and the window start time
For example, sampleCount=60, intervalInMs=60*1000, curTime= 1640931929894
// timeId = 1640931929894/1000 = 1640931929;
// idx = 1640931929%60 = 29;
Array.length ()=sampleCount; // Calculate the index position of the ring array. The current time is the number of milliseconds rounded by the window time width (windowLengthInMs = intervalInMs/sampleCount)
private int calculateTimeIdx(/*@Valid*/ long timeMillis) {
    long timeId = timeMillis / windowLengthInMs;
    // Calculate current index so we can map the timestamp to the leap array.
    return (int)(timeId % array.length()); } for example, curTime=1640931929894
  		windowStart = 1640931929894-1640931929894%1000 = 1640931929000
// Calculate the window start time
protected long calculateWindowStart(/*@Valid*/ long timeMillis) {
  return timeMillis - timeMillis % windowLengthInMs;
}
Copy the code
  • Gets all current window statistics
public List<T> values(long timeMillis) {
    if (timeMillis < 0) {
        return new ArrayList<T>();
    }
    int size = array.length();
    List<T> result = new ArrayList<T>(size);

    for (int i = 0; i < size; i++) {
        WindowWrap<T> windowWrap = array.get(i);
        if (windowWrap == null || isWindowDeprecated(timeMillis, windowWrap)) {
            continue;
        }
        result.add(windowWrap.value());
    }
    return result;
}

IsWindowDeprecated: The current window is deprecated if the current time minus the old window start time is greater than the total window interval time
For example, sampleCount=60, intervalInMs=60*1000, curTime= 1640931929894
// 1640931929894-1640931919000 > 60*1000 = 60894 > 60000 = true
public boolean isWindowDeprecated(long time, WindowWrap<T> windowWrap) {
  return time - windowWrap.windowStart() > intervalInMs;
}
Copy the code

Use scenarios of sliding Windows

FlowRuleManager

Flow control rules management, statistics per minute indicators, also maintained by LeapArray ring array, divided into 60 slots, each window interval of 1 second.

@SuppressWarnings("PMD.ThreadPoolCreationRule")
private static final ScheduledExecutorService SCHEDULER = Executors.newScheduledThreadPool(1.new NamedThreadFactory("sentinel-metrics-record-task".true));
Copy the code

TimeUtil

The system time is used when the system is idle, the system is busy or the time cannot be obtained for sentinel maintenance. It is also maintained by LeapArray ring array with 3 slots and a time sliding window of 1 second.

public TimeUtil(a) {
    this.statistics = new LeapArray<TimeUtil.Statistic>(3.3000) {

        @Override
        public Statistic newEmptyBucket(long timeMillis) {
            return new Statistic();
        }

        @Override
        protected WindowWrap<Statistic> resetWindowTo(WindowWrap<Statistic> windowWrap, long startTime) {
            Statistic val = windowWrap.value();
            val.getReads().reset();
            val.getWrites().reset();
            windowWrap.resetTo(startTime);
            returnwindowWrap; }};this.currentTimeMillis = System.currentTimeMillis();
    this.lastCheck = this.currentTimeMillis;
    Thread daemon = new Thread(this);
    daemon.setDaemon(true);
    daemon.setName("sentinel-time-tick-thread");
    daemon.start();
}
Copy the code

Traffic limiting is implemented

Traffic limiting implementation, second level indicators statistics, traffic limiting and other control, using LeapArray ring array maintenance, 2 slots, time sliding window of 500 ms.

P (PASS) Number of PASS requests B (BLOCK) Number of blocked requests, w (OCCUPIED_PASS) Number of PASS requests in the future quota

SampleCount =2, intervalInMs=1*1000, timeMillis= 162021-12-30 20:13:10 –> (2021-12-30 20:13:10)

Current array index:

idx = (1640866390362/500)%2 = 0; Current windowStart time: windowStart = 1640866390362-1640866390362%500 = 1640866390000

old = array[idx] = array[0]; Old.windowstart () = 1640866348000 –> (2021-12-30 20:12:28) windowStart > old.windowStart() ===> Reset current window value ===> resetWindowTo(old, windowStart);

Realization of reference

  • The MetricBucket class uses LongAdder for counting statistics, which provides better performance (reducing the number of optimistic lock retries) than things like AtomicLong.
  • Sliding Windows reuse WindowWrap using LeapArray to avoid creating lots of duplicate objects and reduce YGC stress.

Contrast: Hystrix current limiting implementation

Hystrix’s sliding window implementation class HystrixRollingNumber. In Hystrix, a sliding window contains several buckets (default is 10), and each bucket stores statistics for a certain period of time (default is 1s).

Each rectangle represents a bucket, and each bucket records four indicators within one second: the amount of success, the amount of failure, the amount of timeout, and the amount of rejection. Together, these 10 buckets make a complete sliding window.

For business purposes, it is worth noting that the bucket object has an immutable property -windowStart, which indicates that the bucket object is used to hold statistics during the time period [windowStart, windowStart + bucketSizeInMillseconds].

Technically, it is worth noting that since each bucket is concurrently updated with metric data by multiple threads, bucket objects need to provide some thread-safe data structure and update methods. To this end, Hystrix makes heavy use of CAS rather than locks.

Hystrix maintains these buckets using an array of rings, and its implementation of the array of rings resembles a queue for a FIFO. The array implementation has a method called addLast(Bucket O), which is used to append new Bucket objects to the end of the annular array. When the number of elements in the array does not exceed the maximum size, it simply maintains the tail pointer. Otherwise, when maintaining the tail pointer, the element at the first position should be removed by maintaining the head pointer. As you can see, this array of rings behaves like a FIFO queue.

conclusion

This chapter mainly introduces the origin and development of Sentinel, analyzes the implementation of Sentinel current limiting sliding window LeapArray data structure design, and compares the implementation of Hystrix current limiting.

Reference:

Github.com/alibaba/Sen…

Cloud.tencent.com/developer/a…

Recommended reading

Exploration of low-cost screen adaptation solution for Zhengcai Cloud Flutter

Redis Bitmaps

MySQL InnoDB lock system source code analysis

, recruiting

Zhengcaiyun Technology team (Zero) is a passionate, creative and executive team based in picturesque Hangzhou. The team has more than 300 r&d partners, including “old” soldiers from Alibaba, Huawei and NetEase, as well as newcomers from Zhejiang University, University of Science and Technology of China, Hangzhou Electric And other universities. Team in the day-to-day business development, but also in cloud native, chain blocks, artificial intelligence, low code platform system, middleware, data, material, engineering platform, the performance experience, visualization technology areas such as exploration and practice, to promote and fell to the ground a series of internal technical products, continue to explore new frontiers of technology. In addition, the team is involved in community building, Currently, There are Google Flutter, SciKit-Learn, Apache Dubbo, Apache Rocketmq, Apache Pulsar, CNCF Dapr, Apache DolphinScheduler, and Alibaba Seata and many other contributors to the excellent open source community. If you want to change something that’s been bothering you, want to start bothering you. If you want to change, you’ve been told you need more ideas, but you don’t have a solution. If you want change, you have the power to make it happen, but you don’t need it. If you want to change what you want to accomplish, you need a team to support you, but you don’t have the position to lead people. If you want to change the original savvy is good, but there is always a layer of fuzzy window…… If you believe in the power of believing, believing that ordinary people can achieve extraordinary things, believing that you can meet a better version of yourself. If you want to be a part of the process of growing a technology team with deep business understanding, sound technology systems, technology value creation, and impact spillover as your business takes off, I think we should talk. Any time, waiting for you to write something and send it to [email protected]

Wechat official account

The article is published synchronously, the public number of political cloud technology team, welcome to pay attention to