发表于

持续原创输出，点击上方蓝字关注我


目录
–

  • 前言
  • Spring Boot 版本
  • 全局统一异常处理的前世今生
  • Spring Boot的异常如何分类？
  • 如何统一异常处理？
  • 异常匹配的顺序是什么？
  • 总结

前言

软件开发过程中难免遇到各种的BUG，各种的异常，一直就是在解决异常的路上永不停歇，如果你的代码中再出现try(){...}catch(){...}finally{...}代码块，你还有心情看下去吗？自己不觉得恶心吗？

冗余的代码往往回丧失写代码的动力，每天搬砖似的写代码，真的很难受。今天这篇文章教你如何去掉满屏的try(){...}catch(){...}finally{...}，解放你的双手。

Spring Boot 版本

本文基于的Spring Boot的版本是2.3.4.RELEASE。

全局统一异常处理的前世今生

早在Spring 3.x就已经提出了@ControllerAdvice，可以与@ExceptionHandler、@InitBinder、@ModelAttribute 等注解注解配套使用，这几个此处就不再详细解释了。

这几个注解小眼一瞟只有@ExceptionHandler与异常有关啊，翻译过来就是异常处理器。其实异常的处理可以分为两类，分别是局部异常处理和全局异常处理。

局部异常处理：@ExceptionHandler和@Controller注解搭配使用，只有指定的controller层出现了异常才会被@ExceptionHandler捕获到，实际生产中怕是有成百上千个controller了吧，显然这种方式不合适。

全局异常处理：既然局部异常处理不合适了，自然有人站出来解决问题了，于是就有了@ControllerAdvice这个注解的横空出世了，@ControllerAdvice搭配@ExceptionHandler彻底解决了全局统一异常处理。当然后面还出现了@RestControllerAdvice这个注解，其实就是@ControllerAdvice和@ResponseBody结晶。

Spring Boot的异常如何分类？

Java中的异常就很多，更别说Spring Boot中的异常了，这里不再根据传统意义上Java的异常进行分类了，而是按照controller进行分类，分为进入controller前的异常和业务层的异常，如下图：


进入controller之前异常一般是javax.servlet.ServletException类型的异常，因此在全局异常处理的时候需要统一处理。几个常见的异常如下：

  1. NoHandlerFoundException：客户端的请求没有找到对应的controller，将会抛出404异常。
  2. HttpRequestMethodNotSupportedException：若匹配到了（匹配结果是一个列表，不同的是http方法不同，如：Get、Post等），则尝试将请求的http方法与列表的控制器做匹配，若没有对应http方法的控制器，则抛该异常
  3. HttpMediaTypeNotSupportedException：然后再对请求头与控制器支持的做比较，比如content-type请求头，若控制器的参数签名包含注解@RequestBody，但是请求的content-type请求头的值没有包含application/json，那么会抛该异常（当然，不止这种情况会抛这个异常）
  4. MissingPathVariableException：未检测到路径参数。比如url为：/user/{userId}，参数签名包含@PathVariable("userId")，当请求的url为/user，在没有明确定义url为/user的情况下，会被判定为：缺少路径参数

如何统一异常处理？

在统一异常处理之前其实还有许多东西需要优化的，比如统一结果返回的形式。当然这里不再细说了，不属于本文范畴。

统一异常处理很简单，这里以前后端分离的项目为例，步骤如下：

  1. 新建一个统一异常处理的一个类
  2. 类上标注@RestControllerAdvice这一个注解，或者同时标注@ControllerAdvice和@ResponseBody这两个注解。
  3. 在方法上标注@ExceptionHandler注解，并且指定需要捕获的异常，可以同时捕获多个。

下面是作者随便配置一个demo，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
复制代码/**
 * 全局统一的异常处理，简单的配置下，根据自己的业务要求详细配置
 */
@RestControllerAdvice
@Slf4j
public class GlobalExceptionHandler {


    /**
     * 重复请求的异常
     * @param ex
     * @return
     */
    @ExceptionHandler(RepeatSubmitException.class)
    public ResultResponse onException(RepeatSubmitException ex){
        //打印日志
        log.error(ex.getMessage());
        //todo 日志入库等等操作

        //统一结果返回
        return new ResultResponse(ResultCodeEnum.CODE_NOT_REPEAT_SUBMIT);
    }


    /**
     * 自定义的业务上的异常
     */
    @ExceptionHandler(ServiceException.class)
    public ResultResponse onException(ServiceException ex){
        //打印日志
        log.error(ex.getMessage());
        //todo 日志入库等等操作

        //统一结果返回
        return new ResultResponse(ResultCodeEnum.CODE_SERVICE_FAIL);
    }


    /**
     * 捕获一些进入controller之前的异常，有些4xx的状态码统一设置为200
     * @param ex
     * @return
     */
    @ExceptionHandler({HttpRequestMethodNotSupportedException.class,
            HttpMediaTypeNotSupportedException.class, HttpMediaTypeNotAcceptableException.class,
            MissingPathVariableException.class, MissingServletRequestParameterException.class,
            ServletRequestBindingException.class, ConversionNotSupportedException.class,
            TypeMismatchException.class, HttpMessageNotReadableException.class,
            HttpMessageNotWritableException.class,
            MissingServletRequestPartException.class, BindException.class,
            NoHandlerFoundException.class, AsyncRequestTimeoutException.class})
    public ResultResponse onException(Exception ex){
        //打印日志
        log.error(ex.getMessage());
        //todo 日志入库等等操作

        //统一结果返回
        return new ResultResponse(ResultCodeEnum.CODE_FAIL);
    }
}

注意：上面的只是一个例子，实际开发中还有许多的异常需要捕获，比如TOKEN失效、过期等等异常，如果整合了其他的框架，还要注意这些框架抛出的异常，比如Shiro，Spring Security等等框架。

异常匹配的顺序是什么？

有些朋友可能疑惑了，如果我同时捕获了父类和子类，那么到底能够被那个异常处理器捕获呢？比如Exception和ServiceException。

此时可能就疑惑了，这里先揭晓一下答案，当然是ServiceException的异常处理器捕获了，精确匹配，如果没有ServiceException的异常处理器才会轮到它的父亲，父亲没有才会到祖父。总之一句话，精准匹配，找那个关系最近的。

为什么呢？这可不是凭空瞎说的，源码为证，出处org.springframework.web.method.annotation.ExceptionHandlerMethodResolver#getMappedMethod，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
复制代码@Nullable
 private Method getMappedMethod(Class<? extends Throwable> exceptionType) {
  List<Class<? extends Throwable>> matches = new ArrayList<>();
    //遍历异常处理器中定义的异常类型
  for (Class<? extends Throwable> mappedException : this.mappedMethods.keySet()) {
      //是否是抛出异常的父类，如果是添加到集合中
   if (mappedException.isAssignableFrom(exceptionType)) {    
        //添加到集合中
    matches.add(mappedException);  
   }
  }
    //如果集合不为空，则按照规则进行排序
  if (!matches.isEmpty()) {
   matches.sort(new ExceptionDepthComparator(exceptionType));
      //取第一个
   return this.mappedMethods.get(matches.get(0));
  }
  else {
   return null;
  }
 }

在初次异常处理的时候会执行上述的代码找到最匹配的那个异常处理器方法，后续都是直接从缓存中（一个Map结构，key是异常类型，value是异常处理器方法）。

别着急，上面代码最精华的地方就是对matches进行排序的代码了，我们来看看ExceptionDepthComparator这个比较器的关键代码，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码//递归调用，获取深度，depth值越小越精准匹配
private int getDepth(Class<?> declaredException, Class<?> exceptionToMatch, int depth) {
    //如果匹配了，返回
  if (exceptionToMatch.equals(declaredException)) {
   // Found it!
   return depth;
  }
  // 递归结束的条件，最大限度了
  if (exceptionToMatch == Throwable.class) {
   return Integer.MAX_VALUE;
  }
    //继续匹配父类
  return getDepth(declaredException, exceptionToMatch.getSuperclass(), depth + 1);
 }

精髓全在这里了，一个递归搞定，计算深度，depth初始值为0。值越小，匹配度越高越精准。

总结

全局异常的文章万万千，能够讲清楚的能有几篇呢？只出最精的文章，做最野的程序员，如果觉得不错的，关注分享走一波，谢谢支持！！！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

背景介绍

某日下午大约四点多，接到合作方消息，线上环境，我这边维护的某http服务突然大量超时（对方超时时间设置为300ms），我迅速到鹰眼平台开启采样，发现该服务平均QPS到了120左右，平均RT在2秒多到3秒，部分毛刺高达5到6秒（正常时候在60ms左右）。

qps情况：

image.png

rt情况

image.png

问题解决

该服务是一个对内的运营平台服务（只部署了两台docker）预期qps个位数，近期没做过任何的线上发布，核心操作是整合查询数据库，一次请求最多涉及40次左右的DB查询，最终查询结果为一个多层树形结构，一个响应体大约50K。之前口头跟调用方约定要做缓存，现在看到QPS在120左右，（QPS证明没有做缓存），遂要求对方做缓存，降低QPS。后QPS降到80以内，rt恢复正常（平均60ms），最终QPS一直降到40（后续需要推动调用方上缓存，保证QPS在个位数）。

问题定位

由于该服务核心操作是查询数据库，且一次请求有40次DB query，遂首先排查是否慢sql导致，查看db性能监控，发现db 平均rt在0.3ms以内，可以算出来DB整体耗时在12ms左右，排除慢sql导致RT变高。

image.png

开始怀疑，是否DB连接池在高并发下出现排队，tddl默认的连接池大小是10.一查监控，整个占用的连接数从来没有超过7个，排除连接池不足的问题。

image.png

至此，造成RT高的原因，在数据库层面被排除。

接着开始查采样到的服务调用链上的每一个执行点，看看到底是调用链上的那部分耗时最多。发现里面很多执行点都有一个特点，就是本地调用耗时特别长（几百毫秒），但是真正的服务调用（比如db查询动作）时间却很短，(0ms代表执行时间小于1ms，也间接印证之前db的平均RT在0.3ms以内)

本地调用耗时: 267ms

客户端发送请求: 0ms

服务端处理请求: 0ms

客户端收到响应: 1ms

总耗时: 1ms

这时候问题逐渐清晰，问题出现在本地方法执行的耗时过长，可是再次检查该服务所有代码，并没有需要长耗时的本地执行逻辑，那么继续看CPU的load情况。

image.png

load长时间在4左右徘徊，我们的docker部署在4c8G的宿主机上，但是我们不能独占这个4C的，持续这么高的load已经不正常了。

继续追查cpu load飙高的原因，接着去看GC日志，发现大量的Allocation Failure，然后ParNew次数在每分钟100次以上，明显异常，见下GC日志例子

1
yaml复制代码2020-03-25T16:16:18.390+0800: 1294233.934: [GC (Allocation Failure) 2020-03-25T16:16:18.391+0800: 1294233.935: [ParNew: 1770060K->25950K(1922432K), 0.0317141 secs] 2105763K->361653K(4019584K), 0.0323010 secs] [Times: user=0.12 sys=0.00, real=0.04 secs]

每次占用cpu的时间在0.04s左右，但是由于ParNew GC太过频繁，每分钟最高100次以上，整体占用cpu时间还是很可观。

image.png

看了下jvm内存参数

1
2
3
4
5
6
7
8
9
10
11
12
13
ini复制代码Heap Configuration:
   MinHeapFreeRatio         = 40
   MaxHeapFreeRatio         = 70
   MaxHeapSize              = 4294967296 (4096.0MB)
   NewSize                  = 2147483648 (2048.0MB)
   MaxNewSize               = 2147483648 (2048.0MB)
   OldSize                  = 2147483648 (2048.0MB)
   NewRatio                 = 2
   SurvivorRatio            = 10
   MetaspaceSize            = 268435456 (256.0MB)
   CompressedClassSpaceSize = 1073741824 (1024.0MB)
   MaxMetaspaceSize         = 536870912 (512.0MB)
   G1HeapRegionSize         = 0 (0.0MB)

年轻代分配了2G内存，其中eden区约1.7G

使用jmap查看年轻代对象占用空间情况,排名靠前的有多个org.apache.tomcat.util.buf包下的对象，比如ByteChunk、CharChunk、MessageBytes等，以及响应涉及的一些临时对象列表。其中ByteChunk等即tomcat响应输出相关类

image.png

至此问题明确，超大响应包（50K）在发送到网卡的过程中，需要经过从用户态user space拷贝到内核态 kernel space，然后在拷贝到网卡进行发送（像netty等的零拷贝针对的就是这种拷贝），加上响应体查询过程中，涉及的大量临时对象list，在高并发场景下，就导致年轻代内存占满，然后频繁gc（后续在合适的时间会压测该接口），这里还有一个点，很多人以为ParNewGC不会stop the world，其实是会的。频繁ParNewGC造成用户线程进入阻塞状态，让出CPU时间片，最终导致连接处理等待，接口的RT变高。整个排查过程，鹰眼，idb性能监控等可视化监控平台帮助真的很大，否则到处去查日志得查的晕头转向了。

经验总结

  1. 接口设计，需要避免超大响应体出现，分而治之，将一个大接口拆分为多个小接口。
  2. 缓存设计，像这个服务一样，一个请求带来将近40次DB查询的，需要考虑在服务端进行缓存（当时偷懒了，要求调用方去做缓存）。
  3. 性能设计，要对自己负责系统的性能了如指掌，可以通过压测等手段得到自己系统的天花板，否则，某一个接口hang住，会导致整个应用的可用性出现问题。
  4. 流量隔离，内部应用和外部流量之间，需要进行流量隔离，即使通过缓存，也有缓存击穿的问题。
  5. 口头说的东西都不靠谱，要落在文档上，还需要检查执行情况。

看完三件事❤️

如果你觉得这篇内容对你还蛮有帮助，我想邀请你帮我三个小忙：

  1. 点赞，转发，有你们的 『点赞和评论』，才是我创造的动力。
  2. 关注公众号 『 java烂猪皮 』，不定期分享原创知识。
  3. 同时可以期待后续文章ing🚀

作者：edenbaby

出处：club.perfma.com/article/184…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

一、核心概念

路由Route

路由是网关的核心抽象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
arduino复制代码public class Route implements Ordered {
	// 唯一id
	private final String id;
	// 跳转uri
	private final URI uri;
	// SpringBean优先级
	private final int order;
	// 断言
	private final AsyncPredicate<ServerWebExchange> predicate;
	// 当前路由特有的过滤器
	private final List<GatewayFilter> gatewayFilters;
	// 元数据
	private final Map<String, Object> metadata;
}

ServerWebExchange

ServerWebExchange是spring-web的一个接口，提供ServerHttpRequest、ServerHttpResponse，ApplicationContext等实例的get方法。

断言AsyncPredicate

断言用于判断路由是否匹配某个ServerWebExchange。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
csharp复制代码public interface AsyncPredicate<T> extends Function<T, Publisher<Boolean>> {
	// 构造与AsyncPredicate
	default AsyncPredicate<T> and(AsyncPredicate<? super T> other) {
		return new AndAsyncPredicate<>(this, other);
	}
	// 构造非AsyncPredicate
	default AsyncPredicate<T> negate() {
		return new NegateAsyncPredicate<>(this);
	}
	// 构造或AsyncPredicate
	default AsyncPredicate<T> or(AsyncPredicate<? super T> other) {
		return new OrAsyncPredicate<>(this, other);
	}
	// 构造默认AsyncPredicate
	static AsyncPredicate<ServerWebExchange> from(
			Predicate<? super ServerWebExchange> predicate) {
		return new DefaultAsyncPredicate<>(GatewayPredicate.wrapIfNeeded(predicate));
	}
	// 默认AsyncPredicate
	class DefaultAsyncPredicate<T> implements AsyncPredicate<T> {

		private final Predicate<T> delegate;

		public DefaultAsyncPredicate(Predicate<T> delegate) {
			this.delegate = delegate;
		}

		@Override
		public Publisher<Boolean> apply(T t) {
			return Mono.just(delegate.test(t));
		}

	}
	// 非AsyncPredicate
	class NegateAsyncPredicate<T> implements AsyncPredicate<T> {

		private final AsyncPredicate<? super T> predicate;

		public NegateAsyncPredicate(AsyncPredicate<? super T> predicate) {
			this.predicate = predicate;
		}

		@Override
		public Publisher<Boolean> apply(T t) {
			return Mono.from(predicate.apply(t)).map(b -> !b);
		}

	}
	// 与AsyncPredicate
	class AndAsyncPredicate<T> implements AsyncPredicate<T> {

		private final AsyncPredicate<? super T> left;

		private final AsyncPredicate<? super T> right;

		public AndAsyncPredicate(AsyncPredicate<? super T> left,
				AsyncPredicate<? super T> right) {
			this.left = left;
			this.right = right;
		}

		@Override
		public Publisher<Boolean> apply(T t) {
			return Mono.from(left.apply(t)).flatMap(
					result -> !result ? Mono.just(false) : Mono.from(right.apply(t)));
		}
	}
	// 或AsyncPredicate
	class OrAsyncPredicate<T> implements AsyncPredicate<T> {

		private final AsyncPredicate<? super T> left;

		private final AsyncPredicate<? super T> right;

		public OrAsyncPredicate(AsyncPredicate<? super T> left,
				AsyncPredicate<? super T> right) {
			this.left = left;
			this.right = right;
		}

		@Override
		public Publisher<Boolean> apply(T t) {
			return Mono.from(left.apply(t)).flatMap(
					result -> result ? Mono.just(true) : Mono.from(right.apply(t)));
		}

	}

}

路由过滤器GatewayFilter

针对于路由的过滤器，无法离开Route而存在。

1
2
3
java复制代码public interface GatewayFilter extends ShortcutConfigurable {
	Mono<Void> filter(ServerWebExchange exchange, GatewayFilterChain chain);
}

全局过滤器GlobalFilter

全局的过滤器，所有路由都必须执行的过滤器。后续Bean实例化的时候，会适配成GatewayFilter被使用。

1
2
3
kotlin复制代码public interface GlobalFilter {
	Mono<Void> filter(ServerWebExchange exchange, GatewayFilterChain chain);
}

过滤器链GatewayFilterChain

GatewayFilterChain过滤器链允许GatewayFilter过滤器按顺序，挨个执行。

1
2
3
kotlin复制代码public interface GatewayFilterChain {
	Mono<Void> filter(ServerWebExchange exchange);
}

路由定义RouteDefinition

类似于Spring的BeanDefinition，Route的一种构建方式就是通过RouteDefinition，比如从properties文件中解析得到的路由规则定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typescript复制代码public class RouteDefinition {
	// 唯一id
	private String id;
    	// 断言定义
	private List<PredicateDefinition> predicates = new ArrayList<>();
	// 过滤器定义
	private List<FilterDefinition> filters = new ArrayList<>();
	// 跳转uri
	private URI uri;
	// 元数据
	private Map<String, Object> metadata = new HashMap<>();
	// Spring优先级
	private int order = 0;
}

断言定义PredicateDefinition

从配置文件加载的断言定义，构造Route时，会用RoutePredicateFactory#applyAsync转换成AsyncPredicate。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
arduino复制代码public class PredicateDefinition {
	private String name;
	private Map<String, String> args = new LinkedHashMap<>();
	public PredicateDefinition() {
	}
    // predicates:
    //     - Path=/echo // 解析'Path=/echo'放入args
	public PredicateDefinition(String text) {
		int eqIdx = text.indexOf('=');
        // 设置name
		setName(text.substring(0, eqIdx));
	
		String[] args = tokenizeToStringArray(text.substring(eqIdx + 1), ",");
		// 设置args
		for (int i = 0; i < args.length; i++) {
			this.args.put(NameUtils.generateName(i), args[i]);
		}
	}
}

路由过滤器定义FilterDefinition

从配置文件加载的路由过滤器定义，构造Route时，会用GatewayFilterFactory#apply转换为GatewayFilter。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
arduino复制代码public class FilterDefinition {
	private String name;
	private Map<String, String> args = new LinkedHashMap<>();
	public FilterDefinition() {
	}
	// 解析配置文件 PrefixPath=/httpbin
	public FilterDefinition(String text) {
		int eqIdx = text.indexOf('=');
		if (eqIdx <= 0) {
			setName(text);
			return;
		}
		setName(text.substring(0, eqIdx));

		String[] args = tokenizeToStringArray(text.substring(eqIdx + 1), ",");

		for (int i = 0; i < args.length; i++) {
			this.args.put(NameUtils.generateName(i), args[i]);
		}
	}
}

获取路由定义RouteDefinitionLocator

RouteDefinitionLocator具有获取路由定义的能力。

1
2
3
csharp复制代码public interface RouteDefinitionLocator {
	Flux<RouteDefinition> getRouteDefinitions();
}

最后对外暴露的实际是CompositeRouteDefinitionLocator，他组合了所有RouteDefinitionLocator。

获取路由RouteLocator

RouteLocator具有获取路由Route的能力。网关处理请求时只会调用RouteLocator获取Route，通过Route的断言和过滤处理请求。

1
2
3
csharp复制代码public interface RouteLocator {
	Flux<Route> getRoutes();
}

Spring容器加载的时候，会把路由都放到CachingRouteLocator里，后续运行时只会和CachingRouteLocator打交道。

二、加载路由

讲解从Gateway的Bean装配，到加载Route到CachingRouteLocator。

自动配置

Spring-Cloud-Gateway的自动配置类是org.springframework.cloud.gateway.config.GatewayAutoConfiguration。重点看一些重要的Bean装配，全局Filter等下一章节讲请求流程的时候再分析。

Gateway配置文件

1
2
3
4
5
6
7
8
9
10
11
12
typescript复制代码@Bean
public GatewayProperties gatewayProperties() {
    return new GatewayProperties();
}
@ConfigurationProperties("spring.cloud.gateway")
@Validated
public class GatewayProperties {
	// 路由
	private List<RouteDefinition> routes = new ArrayList<>();
    // 默认过滤器
	private List<FilterDefinition> defaultFilters = new ArrayList<>();
}

RouteDefinitionLocator相关

  • PropertiesRouteDefinitionLocator：配置文件创建RouteDefinitionLocator
1
2
3
4
5
6
less复制代码@Bean
@ConditionalOnMissingBean
public PropertiesRouteDefinitionLocator propertiesRouteDefinitionLocator(
        GatewayProperties properties) {
    return new PropertiesRouteDefinitionLocator(properties);
}
  • InMemoryRouteDefinitionRepository：内存级别路由定义，无法持久化，支持动态新增和删除路由定义
1
2
3
4
5
less复制代码@Bean
@ConditionalOnMissingBean(RouteDefinitionRepository.class)
public InMemoryRouteDefinitionRepository inMemoryRouteDefinitionRepository() {
    return new InMemoryRouteDefinitionRepository();
}
  • CompositeRouteDefinitionLocator：组合其他所有的RouteDefinitionLocator，并且是Primary的
1
2
3
4
5
6
7
less复制代码@Bean
@Primary
public RouteDefinitionLocator routeDefinitionLocator(
        List<RouteDefinitionLocator> routeDefinitionLocators) {
    return new CompositeRouteDefinitionLocator(
            Flux.fromIterable(routeDefinitionLocators));
}

RouteLocator相关

  • RouteLocatorBuilder：辅助用编码方式注入自定义的RouteLocator。
1
2
3
4
5
typescript复制代码@Bean
public RouteLocatorBuilder routeLocatorBuilder(
        ConfigurableApplicationContext context) {
    return new RouteLocatorBuilder(context);
}
  • RouteDefinitionRouteLocator：用RouteDefinitionLocator和GatewayFilterFactory和RoutePredicateFactory构造Route，创建RouteLocator。
1
2
3
4
5
6
7
8
9
typescript复制代码@Bean
public RouteLocator routeDefinitionRouteLocator(GatewayProperties properties,
        List<GatewayFilterFactory> gatewayFilters,
        List<RoutePredicateFactory> predicates,
        RouteDefinitionLocator routeDefinitionLocator,
        ConfigurationService configurationService) {
    return new RouteDefinitionRouteLocator(routeDefinitionLocator, predicates,
            gatewayFilters, properties, configurationService);
}
  • CachingRouteLocator：委托CompositeRouteLocator聚合其他所有RouteLocator，实现RouteLocator。
1
2
3
4
5
6
7
less复制代码@Bean
@Primary
@ConditionalOnMissingBean(name = "cachedCompositeRouteLocator")
public RouteLocator cachedCompositeRouteLocator(List<RouteLocator> routeLocators) {
    return new CachingRouteLocator(
            new CompositeRouteLocator(Flux.fromIterable(routeLocators)));
}

加载路由入口类RouteRefreshListener

1
2
3
4
typescript复制代码@Bean
public RouteRefreshListener routeRefreshListener(ApplicationEventPublisher publisher) {
    return new RouteRefreshListener(publisher);
}

加载路由到CachingRouteLocator

RouteRefreshListener

加载路由到RouteLocator的入口，通过Spring事件触发。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
csharp复制代码public class RouteRefreshListener implements ApplicationListener<ApplicationEvent> {

	private final ApplicationEventPublisher publisher;

	public RouteRefreshListener(ApplicationEventPublisher publisher) {
		this.publisher = publisher;
	}

	@Override
	public void onApplicationEvent(ApplicationEvent event) {
		if (event instanceof ContextRefreshedEvent
				|| event instanceof RefreshScopeRefreshedEvent
				|| event instanceof InstanceRegisteredEvent) {
			reset();
		}
        // ... 省略其他事件判断，也可能触发reset
	}
	
    // 发布RefreshRoutesEvent事件
	private void reset() {
		this.publisher.publishEvent(new RefreshRoutesEvent(this));
	}

}

CachingRouteLocator

CachingRouteLocator收到RefreshRoutesEvent，委托CompositeRouteLocator获取Flux<Route>放入自己的缓存cache中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
typescript复制代码public class CachingRouteLocator implements Ordered, RouteLocator,
		ApplicationListener<RefreshRoutesEvent>, ApplicationEventPublisherAware {
	// 写死的缓存cache的key
	private static final String CACHE_KEY = "routes";
	// CompositeRouteLocator
	private final RouteLocator delegate;
	// Route列表
	private final Flux<Route> routes;
	// 缓存
	private final Map<String, List> cache = new ConcurrentHashMap<>();
	// 事件发布者
	private ApplicationEventPublisher applicationEventPublisher;

	public CachingRouteLocator(RouteLocator delegate) {
		this.delegate = delegate;
        // 这里并不会触发fetch，只有当需要routes的时候才会触发fetch，比如getRoutes()
		routes = CacheFlux.lookup(cache, CACHE_KEY, Route.class)
				.onCacheMissResume(this::fetch);
	}
	// 委托CompositeRouteLocator获取Route并排序
	private Flux<Route> fetch() {
		return this.delegate.getRoutes().sort(AnnotationAwareOrderComparator.INSTANCE);
	}
	// 获取Route，如果routes为空，会触发fetch
	@Override
	public Flux<Route> getRoutes() {
		return this.routes;
	}
    // 清空缓存
	public Flux<Route> refresh() {
		this.cache.clear();
		return this.routes;
	}
	// 接收RefreshRoutesEvent
	@Override
	public void onApplicationEvent(RefreshRoutesEvent event) {
		try {
        	// 委托CompositeRouteLocator获取Route并排序
			fetch()
            .collect(Collectors.toList())
            .subscribe(list -> Flux.fromIterable(list)
                  .materialize().collect(Collectors.toList()).subscribe(signals -> {
                      applicationEventPublisher.publishEvent(new RefreshRoutesResultEvent(this));
                      // 放入缓存
                      cache.put(CACHE_KEY, signals);
                  }, throwable -> handleRefreshError(throwable)));
		}
		catch (Throwable e) {
			handleRefreshError(e);
		}
	}
	// 发生异常发布RefreshRoutesResultEvent事件
	private void handleRefreshError(Throwable throwable) {
		applicationEventPublisher
				.publishEvent(new RefreshRoutesResultEvent(this, throwable));
	}
	void handleRefresh() {
		refresh();
	}
	@Override
	public int getOrder() {
		return 0;
	}
	@Override
	public void setApplicationEventPublisher(
			ApplicationEventPublisher applicationEventPublisher) {
		this.applicationEventPublisher = applicationEventPublisher;
	}
}

CompositeRouteLocator

通过其他RouteLocator获取所有Route。

1
2
3
4
5
6
7
8
9
10
11
kotlin复制代码public class CompositeRouteLocator implements RouteLocator {
	// 其他所有RouteLocator，除了CachingRouteLocator
	private final Flux<RouteLocator> delegates;
	public CompositeRouteLocator(Flux<RouteLocator> delegates) {
		this.delegates = delegates;
	}
	@Override
	public Flux<Route> getRoutes() {
		return this.delegates.flatMapSequential(RouteLocator::getRoutes);
	}
}

1 编码方式获取Route

1
2
3
4
5
6
7
8
9
10
11
less复制代码@Bean
public RouteLocator customRouteLocator(RouteLocatorBuilder builder) {
    return builder.routes()
            .route(r -> r.host("**.abc.org").and().path("/anything/png")
                .filters(f ->
                        f.prefixPath("/httpbin")
                                .addResponseHeader("X-TestHeader", "foobar"))
                .uri(uri)
            )
            .build();
}

RouteLocatorBuilder.Builder构造的RouteLocator，Bean注入的时候直接构造完成了。具体构造过程不细看了，也是利用了RoutePredicateFactory和GatewayFilterFactory。

1
2
3
4
5
6
csharp复制代码public static class Builder {
	private List<Route.AsyncBuilder> routes = new ArrayList<>();
    public RouteLocator build() {
        return () -> Flux.fromIterable(this.routes)
                .map(routeBuilder -> routeBuilder.build());
    }

2 RouteDefinitionRouteLocator

RouteDefinitionRouteLocator只负责通过RouteDefinition创建Route，委托CompositeRouteDefinitionLocator获取RouteDefinition，并通过ConfigurationService、RoutePredicateFactory、GatewayFilterFactory将RouteDefinition转换为Route返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
arduino复制代码public class RouteDefinitionRouteLocator
		implements RouteLocator, BeanFactoryAware, ApplicationEventPublisherAware {
	// 默认过滤器名字
	public static final String DEFAULT_FILTERS = "defaultFilters";
	// 委托CompositeRouteDefinitionLocator
	private final RouteDefinitionLocator routeDefinitionLocator;
	// ConfigurationService操作RoutePredicateFactory和GatewayFilterFactory
    // 转换断言和过滤器
	private final ConfigurationService configurationService;
	// name - RoutePredicateFactory
	private final Map<String, RoutePredicateFactory> predicates = new LinkedHashMap<>();
	// name - GatewayFilterFactory
	private final Map<String, GatewayFilterFactory> gatewayFilterFactories = new HashMap<>();
	// spring.cloud.gateway配置文件
	private final GatewayProperties gatewayProperties;
    
    @Override
	public Flux<Route> getRoutes() {
		Flux<Route> routes = this.routeDefinitionLocator
        		// 委托CompositeRouteDefinitionLocator获取RouteDefinition
        		.getRouteDefinitions()
                // 转换为Route
				.map(this::convertToRoute);
		// 如果spring.cloud.gateway.failOnRouteDefinitionError=true（默认）
        // 仅仅打印日志
		if (!gatewayProperties.isFailOnRouteDefinitionError()) {
			routes = routes.onErrorContinue((error, obj) -> {
					logger.warn(...);
			});
		}
		return routes;
	}
}
  • CompositeRouteDefinitionLocator

getRouteDefinitions循环所有RouteDefinitionLocator获取所有RouteDefinition。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
kotlin复制代码public class CompositeRouteDefinitionLocator implements RouteDefinitionLocator {
  private final Flux<RouteDefinitionLocator> delegates;
  private final IdGenerator idGenerator;
  public CompositeRouteDefinitionLocator(Flux<RouteDefinitionLocator> delegates) {
      this(delegates, new AlternativeJdkIdGenerator());
  }
  public CompositeRouteDefinitionLocator(Flux<RouteDefinitionLocator> delegates,
          IdGenerator idGenerator) {
      this.delegates = delegates;
      this.idGenerator = idGenerator;
  }

  @Override
  public Flux<RouteDefinition> getRouteDefinitions() {
      return this.delegates
              // 委托所有其他RouteDefinitionLocator获取RouteDefinition
              .flatMapSequential(RouteDefinitionLocator::getRouteDefinitions)
              .flatMap(routeDefinition -> {
                  // 如果RouteDefinition没有设置id，随便给一个
                  if (routeDefinition.getId() == null) {
                      return randomId().map(id -> {
                          routeDefinition.setId(id);
                          return routeDefinition;
                      });
                  }
                  return Mono.just(routeDefinition);
              });
  }
  // 获取随机id
  protected Mono<String> randomId() {
      return Mono.fromSupplier(idGenerator::toString)
              .publishOn(Schedulers.boundedElastic());
  }
}

RouteDefinitionLocator有很多种，以PropertiesRouteDefinitionLocator为例。

1
2
3
4
5
6
7
8
9
10
kotlin复制代码public class PropertiesRouteDefinitionLocator implements RouteDefinitionLocator {
  private final GatewayProperties properties;
  public PropertiesRouteDefinitionLocator(GatewayProperties properties) {
      this.properties = properties;
  }
  @Override
  public Flux<RouteDefinition> getRouteDefinitions() {
      return Flux.fromIterable(this.properties.getRoutes());
  }
}
  • RouteDefinitionRouteLocator.convertToRoute

通过ConfigurationService、RoutePredicateFactory、GatewayFilterFactory将RouteDefinition转换为Route。

1
2
3
4
5
6
7
8
9
10
11
scss复制代码private Route convertToRoute(RouteDefinition routeDefinition) {
  // 将routeDefinition里的PredicateDefinition
  // 通过RoutePredicateFactory转换为AsyncPredicate
  AsyncPredicate<ServerWebExchange> predicate = combinePredicates(routeDefinition);
  // 将routeDefinition里的FilterDefinition
  // 通过GatewayFilterFactory转换为GatewayFilter
  List<GatewayFilter> gatewayFilters = getFilters(routeDefinition);
  // 组装Route
  return Route.async(routeDefinition).asyncPredicate(predicate)
          .replaceFilters(gatewayFilters).build();
}

RouteDefinitionRouteLocator#combinePredicates转换PredicateDefinition为AsyncPredicate。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
scss复制代码private AsyncPredicate<ServerWebExchange> combinePredicates(
			RouteDefinition routeDefinition) {
    List<PredicateDefinition> predicates = routeDefinition.getPredicates();
    // 先获取第一个断言定义，转换为AsyncPredicate
    AsyncPredicate<ServerWebExchange> predicate = lookup(routeDefinition,
            predicates.get(0));
	// 后续定义用and连接
    for (PredicateDefinition andPredicate : predicates.subList(1,
            predicates.size())) {
        AsyncPredicate<ServerWebExchange> found = lookup(routeDefinition,
                andPredicate);
        predicate = predicate.and(found);
    }
    return predicate;
}
private AsyncPredicate<ServerWebExchange> lookup(RouteDefinition route,
			PredicateDefinition predicate) {
  // 通过PredicateDefinition的name找到对应的RoutePredicateFactory
  RoutePredicateFactory<Object> factory = this.predicates.get(predicate.getName());
  // ConfigurationService操作RouteDefinition和RoutePredicateFactory
  Object config = this.configurationService.with(factory)
          .name(predicate.getName())
          .properties(predicate.getArgs())
          .eventFunction((bound, properties) -> new PredicateArgsEvent(
                  RouteDefinitionRouteLocator.this, route.getId(), properties))
          .bind();
  return factory.applyAsync(config);
}

RouteDefinitionRouteLocator#getFilters将FilterDefinition转换为GatewayFilter。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
scss复制代码private List<GatewayFilter> getFilters(RouteDefinition routeDefinition) {
  List<GatewayFilter> filters = new ArrayList<>();
  // 如果默认过滤器不为空，加入默认过滤器
  if (!this.gatewayProperties.getDefaultFilters().isEmpty()) {
      filters.addAll(loadGatewayFilters(DEFAULT_FILTERS,
              new ArrayList<>(this.gatewayProperties.getDefaultFilters())));
  }
  // 如果routeDefinition里的过滤器不为空，加入过滤器
  if (!routeDefinition.getFilters().isEmpty()) {
      filters.addAll(loadGatewayFilters(routeDefinition.getId(),
              new ArrayList<>(routeDefinition.getFilters())));
  }
  // 排序
  AnnotationAwareOrderComparator.sort(filters);
  return filters;
}
List<GatewayFilter> loadGatewayFilters(String id,List<FilterDefinition> filterDefinitions) {
  ArrayList<GatewayFilter> ordered = new ArrayList<>(filterDefinitions.size());
  for (int i = 0; i < filterDefinitions.size(); i++) {
  	  // Filter定义 
      FilterDefinition definition = filterDefinitions.get(i);
      // 根据Filter定义的name获取GatewayFilterFactory
      GatewayFilterFactory factory = this.gatewayFilterFactories
              .get(definition.getName());
	  // 配置
      Object configuration = this.configurationService.with(factory)
              .name(definition.getName())
              .properties(definition.getArgs())
              .eventFunction((bound, properties) -> new FilterArgsEvent(
                      RouteDefinitionRouteLocator.this, id, (Map<String, Object>) properties))
              .bind();
	  // 转换为GatewayFilter
      GatewayFilter gatewayFilter = factory.apply(configuration);
      if (gatewayFilter instanceof Ordered) {
          ordered.add(gatewayFilter);
      }
      else {
          ordered.add(new OrderedGatewayFilter(gatewayFilter, i + 1));
      }
  }

  return ordered;
}

总结

  • 理清Route、RouteLocator、RouteDefinition、RouteDefinitionLocator的含义。最后对运行时实际暴露的对象只有CachingRouteLocator和Route。
  • RouteRefreshListener接收容器事件，发布RefreshRoutesEvent事件，触发路由加载至CachingRouteLocator。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

点赞再看，养成习惯，听说微信搜公众号《Java鱼仔》会让自己的技术更上一层楼

（一）概述

对于一个Web项目来说，最重要的不是功能酷不酷炫，而是这个项目安不安全。做过项目的人都知道，一个项目在上线前一定会经过安全漏扫，只有通过安全漏扫后这个项目才能正式上线。
Spring Security是一个功能强大且高度可定制的身份验证和访问控制框架，类似的安全框架还有Shiro。
Spring Security主要做两个事情，认证、授权。

（二）前期项目搭建

为了更好的展示SpringSecurity，我们先搭建一个简单的web项目出来。引入thymeleaf依赖

1
2
3
4
5
6
7
8
9
10
11
12
xml复制代码<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-thymeleaf</artifactId>
</dependency>
<dependency>
    <groupId>org.thymeleaf</groupId>
    <artifactId>thymeleaf-spring5</artifactId>
</dependency>
<dependency>
    <groupId>org.thymeleaf.extras</groupId>
    <artifactId>thymeleaf-extras-java8time</artifactId>
</dependency>

新建一个登陆页，一个首页，然后几个不同等级的展示页面：
login.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
html复制代码<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>登陆页</title>
</head>
<body>
<div>
    <form>
        <h2>登陆页</h2>
        <input type="text" id="username" placeholder="username">
        <input type="password" id="password" placeholder="password">
        <button type="button">登陆</button>
    </form>
</div>
</body>
</html>

首页index.html，主要就展示不同等级的按钮，为之后授权做准备

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
html复制代码<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>首页</title>
</head>
<body>
<div>
    <h2>首页</h2>
    <a href="/login">登陆</a>
    <div style="overflow: hidden">
        <div style="float: left;margin-left: 20px">
            <h3>level1</h3>
            <a href="/level1/1">level-1-1</a>
            <hr>
            <a href="/level1/2">level-1-2</a>
        </div>
        <div style="float: left;margin-left: 20px">
            <h3>level2</h3>
            <a href="/level2/1">level-2-1</a>
            <hr>
            <a href="/level2/2">level-2-2</a>
        </div>
        <div style="float: left;margin-left: 20px">
            <h3>level3</h3>
            <a href="/level3/1">level-3-1</a>
            <hr>
            <a href="/level3/2">level-3-2</a>
        </div>
    </div>
</div>
</body>
</html>

另外还有几个不同等级的页面

在这里插入图片描述

分别在body中写上自己对应的编号。

1
2
3
4
5
6
7
8
9
10
html复制代码<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
level-1-1
</body>
</html>

最后编写一个controller来接收请求：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码@Controller
public class RouteController {
    @RequestMapping({"/","/index"})
    public String index(){
        return "index";
    }
    @RequestMapping("/login")
    public String toLogin(){
        return "login";
    }
    @RequestMapping("/level1/{id}")
    public String level1(@PathVariable("id")String id){
        return "level1/"+id;
    }
    @RequestMapping("/level2/{id}")
    public String level2(@PathVariable("id")String id){
        return "level2/"+id;
    }
    @RequestMapping("/level3/{id}")
    public String level3(@PathVariable("id")String id){
        return "level3/"+id;
    }
}

最终的效果如下：
在这里插入图片描述
首页效果如下：
在这里插入图片描述

（三）认证与授权

在上面的这个页面中有两个问题，第一未做登陆认证的处理，第二三个level页面现在都能被所有人访问，未做授权。而上面的这两个问题都可以通过SpringSecurity来解决。

实现SpringSecurity只需要引入spring-boot-starter-security依赖，进行少量的配置，就可以实现强大的安全管理功能。

在正式接触前我们需要记住几个类：

1.WebSecurityConfigurerAdapter ：自定义Security策略

2.AuthenticationManagerBuilder：自定义认证策略

3.@EnableWebSecurity ：开启WebSecurity模式

我们新建一个config包，创建一个配置类SecurityConfig，继承WebSecurityConfigurerAdapter接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码@EnableWebSecurity
public class SecurityConfig extends WebSecurityConfigurerAdapter {
    //授权
    @Override
    protected void configure(HttpSecurity http) throws Exception {
        //首页所有人都能访问，level页面只有有权限的人才能访问
        http.authorizeRequests()
                .antMatchers("/").permitAll()
                .antMatchers("/level1/**").hasRole("vip1")
                .antMatchers("/level2/**").hasRole("vip2")
                .antMatchers("/level3/**").hasRole("vip3");
        //没有权限默认跳到登陆页，默认会重定向到/login
        http.formLogin();
    }
    //认证
    @Override
    protected void configure(AuthenticationManagerBuilder auth) throws Exception {
        auth.inMemoryAuthentication()
                .passwordEncoder(new BCryptPasswordEncoder())
                .withUser("root").password(new BCryptPasswordEncoder().encode("123456")).roles("vip1","vip2","vip3")
                .and()
                .withUser("admin").password(new BCryptPasswordEncoder().encode("123456")).roles("vip1");
    }
}

通过上面的这段代码，实现了授权和认证的功能，其中认证方法在内存中存入的用户信息。正常情况下用户的数据是从数据库中获取，授权功能给不同的页面设置不同的角色。

我们再次打开首页http://localhost:8080/，所有人都有权限看到，当我们点击里面的level1 2 3里的链接时，自动跳转到了http://localhost:8080/login

在这里插入图片描述

你会发现这个登陆页面明明不是自己写的，怎么就出现了？其实这就是SpringSecurity所提供的，http.formLogin();这段代码做了对登陆页的处理，没有权限默认跳到登陆页，默认会重定向到/login。

当我们用不同权限的账号登陆时，就能点击不同权限的链接，如果点击权限外的链接时，会报403错误

在这里插入图片描述

（四）注销的操作

既然有认证和授权，那么一定免不了注销的功能，SpringSecurity实现注销很简单，你只需要在SecurityConfig类的授权代码里增加一条代码。

1
2
java复制代码//登出
http.logout();

然后在前端index.html代码中增加一个注销的标签

1
html复制代码<a href="/logout">注销</a>

点击首页的注销按钮后就会跳转到SpringSecurity的注销提示界面
在这里插入图片描述
点击logout按钮后自动退出到登陆页面，如果你希望注销后还是回到首页的话，可以将注销代码修改成下面的方式：

1
java复制代码http.logout().logoutSuccessUrl("/");

（五）记住密码功能

一般情况下登陆页面肯定会有一个记住密码的功能，这个功能其实就是在本地生成一个cookie，用原生的java实现虽然不难，但是也需要一定的代码。而使用SpringSecurity只需要一行：

1
java复制代码http.rememberMe();

再次进入登陆页面后，就可以看到增加了一行记住密码的选项
在这里插入图片描述

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 1 篇文章，完整文章目录请移步到文章末尾~

前言

  • 链表的相关问题，在面试中出现频率较高，这些问题往往也是解决其他复杂问题的基础；
  • 在这篇文章里，我将梳理链表问题的问题 & 解法。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
删除链表节点 提示 & 题解
203. 移除链表元素 Remove Linked List Elements 【题解】
237. 删除链表中的节点 Delete Node in a Linked List 【题解】
19. 删除链表的倒数第N个节点 Remove Nth Node From End of List 【题解】
86. 分隔链表 Partition List 【题解】
328. 奇偶链表 Odd Even Linked List 【题解】
83. 删除排序链表中的重复元素 Remove Duplicates from Sorted List
82. 删除排序链表中的重复元素 II Remove Duplicates from Sorted List II
725. 分隔链表 Split Linked List in Parts
（扩展）0876. 链表的中间结点 Middle of the Linked List 【题解】
反转链表 提示 & 题解
206. 反转链表 Reverse Linked List 【题解】
92. 反转链表 II Reverse Linked List II 【题解】
234. 回文链表 Palindrome Linked List 【题解】
25. K 个一组翻转链表 Reverse Nodes in k-Group
合并有序链表 提示 & 题解
21. 合并两个有序链表 Merge Two Sorted Lists 【题解】
23. 合并K个升序链表 Merge k Sorted Lists 【题解】
排序链表 提示 & 题解
147. 对链表进行插入排序 Insertion Sort List 【题解】
148. 排序链表 Sort List 【题解】
环形链表 提示 & 题解
160. 相交链表 Intersection of Two Linked Lists 【题解】
141. 环形链表 Linked List Cycle 【题解】
142. 环形链表 II Linked List Cycle II 【题解】
61. 旋转链表 Rotate List 【题解】
其他 提示 & 题解
24. 两两交换链表中的节点 Swap Nodes in Pairs
143. 重排链表 Reorder List
138. 复制带随机指针的链表 Copy List with Random Pointer
380. 常数时间插入、删除和获取随机元素 Insert Delete GetRandom O(1)
381. O(1) 时间插入、删除和获取随机元素 - 允许重复 Insert Delete GetRandom O(1) - Duplicates allowed
707. 设计链表 Design Linked List
430. 扁平化多级双向链表 Flatten a Multilevel Doubly Linked List
817. 链表组件 Linked List Components 【题解】

目录

  1. 概述

1.1 链表的定义

链表是一种常见的基础数据结构，是一种线性表。与顺序表不同的是，链表中的每个节点不是顺序存储的，而是通过节点的指针域指向到下一个节点。

1.2 链表的优缺点

对比 优点 缺点
内存管理 充分利用计算机内存空间，更灵活地分配内存空间 指针域增加了内存消耗
操作效率 能在 O(1)O(1)O(1) 时间内删除或添加节点（前提是前驱节点已知） 失去了数组随机访问的特性，查询对应位置的节点需要 O(n)O(n)O(n) 时间
数据容量 需要预先分配内存空间，容量不足需要扩容 不需要预先分配内存空间，不需要扩容
访问性能 / CPU 缓存行无法提高效率

1.3 链表的类型

单链表、双链表、循环链表、静态链表

  1. 删除链表节点

删除链表节点时，考虑到可能删除的是链表的第一个节点（没有前驱节点），为了编码方便，可以考虑增加一个 哨兵节点。其中，在删除链表的倒数第 N 个节点问题里，使用快慢指针在一趟扫描里找出倒数第 N 个节点是比较重要的编程技巧。

237. Delete Node in a Linked List 删除链表中的节点 【题解】
203. Remove Linked List Elements 移除链表元素 【题解】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
kotlin复制代码不移除野指针
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head

        var pre = sentinel
        var cur: ListNode? = sentinel
        while (null != cur) {
            if (`val` == cur.`val`) {
                // 移除
                pre.next = cur.next
            } else {
                pre = cur
            }
            cur = cur.next
        }
        return sentinel.next
    }
}

移除野指针
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head

        var pre = sentinel
        var cur: ListNode? = sentinel
        while (null != cur) {
            val removeNode = if (`val` == cur.`val`) {
                // 移除
                pre.next = cur.next
                cur
            } else {
                pre = cur
                null
            }
            cur = cur.next
            if (null != removeNode) {
                removeNode.next = null
            }
        }
        return sentinel.next
    }
}
19. Remove Nth Node From End of List 删除链表的倒数第N个节点 【题解】

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
kotlin复制代码class Solution {
    fun removeNthFromEnd(head: ListNode, n: Int): ListNode? {
        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head

        var fast: ListNode? = sentinel
        var slow: ListNode? = sentinel

        for (index in 0 until n) {
            fast = fast!!.next
        }

        // 找到倒数第 k 个节点的前驱
        while (null != fast!!.next) {
            fast = fast.next
            slow = slow!!.next
        }
        slow!!.next = slow.next!!.next
        return sentinel.next
    }
}

复杂度分析：

  • 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)O(n)O(n)
  • 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)O(1)O(1)

类似地，876. Middle of the Linked List 链表的中间结点 【题解】 也是通过快慢指针来找到中间节点的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
kotlin复制代码class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        if (null == head || null == head.next) {
            return head
        }
        var fast = head
        var slow = head

        while (null != fast && null != fast.next) {
            fast = fast.next!!.next
            slow = slow!!.next
        }

        return slow
    }
}
86. Partition List 分隔链表 【题解】

删除链表中等于给定值 val 的所有节点。

思路：分隔链表无非是先将大于等于 val 的节点从原链表中移除到第二个链表中，最后再拼接两个链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
kotlin复制代码class Solution {
    fun partition(head: ListNode?, x: Int): ListNode? {
        if (null == head) {
            return null
        }

        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head
        var pre = sentinel
        // 第二链表
        var bigHead : ListNode? = null
        var bigRear = bigHead

        var cur = head
        while (null != cur) {
            if (cur.`val` >= x) {
                // 大于等于：移除
                pre.next = cur.next
                if(null == bigHead){
                    bigHead = cur
                    bigRear = cur
                }else{
                    bigRear!!.next = cur
                    bigRear = cur
                }
            } else {
                pre = cur
            }
            if (null == cur.next) {
                // 拼接
                pre.next = bigHead
                bigRear?.next = null
                break
            }
            cur = cur.next
        }
        return sentinel.next
    }
}

复杂度分析：

  • 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)O(n)O(n)
  • 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)O(1)O(1)
328. Odd Even Linked List 奇偶链表 【题解】

思路：奇偶链表无非是先将奇节点放在一个链表里，偶节点放在另一个链表里，最后把偶节点接在奇链表的尾部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
kotlin复制代码class Solution {
    fun oddEvenList(head: ListNode?): ListNode? {
        if (null == head) {
            return null
        }

        var odd: ListNode = head
        var even = head.next
        val evenHead = even

        while (null != even && null != even.next) {
            // 偶节点
            odd.next = even.next
            odd = odd.next!!
            // 奇节点
            even.next = odd.next
            even = even.next
        }
        odd.next = evenHead
        // 头节点不动
        return head
    }
}
83. Remove Duplicates from Sorted List 删除排序链表中的重复元素
82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II
  1. 反转链表

反转链表问题在面试中出现频率 非常非常高，相信有过几次面试经验的同学都会同意这个观点。在这里，我找出了 4 道反转链表的问题，从简单延伸到困难，快来试试吧。

206. 反转链表 Reverse Linked List 【题解】

反转一个单链表。

解法1：递归

1
2
3
4
5
6
7
8
9
10
11
kotlin复制代码class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        if(null == head || null == head.next){
            return head
        }
        val prefix = reverseList(head.next)
        head.next.next = head
        head.next = null
        return prefix
    }
}

复杂度分析：

  • 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)O(n)O(n)
  • 空间复杂度：使用了递归栈，空间复杂度为 O(n)O(n)O(n)

解法2：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
kotlin复制代码class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        var cur: ListNode? = head
        var headP: ListNode? = null

        while (null != cur) {
            val tmp = cur.next
            cur.next = headP
            headP = cur
            cur = tmp
        }
        return headP
    }
}

复杂度分析：

  • 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)O(n)O(n)
  • 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)O(1)O(1)
92. 反转链表 II Reverse Linked List II 【题解】

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
kotlin复制代码class Solution {
    fun reverseBetween(head: ListNode?, m: Int, n: Int): ListNode? {
        if (null == head || null == head.next) {
            return head
        }

        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head
        var rear = sentinel

        // 1. 找到反转开始位置前驱节点
        var cur = sentinel
        for (index in 0 until m - 1) {
            cur = cur.next!!
            rear = cur
        }

        // 2. 反转指定区域
        rear.next = reverseList(rear.next!!, n - m + 1)
        return sentinel.next
    }

    /**
     * 反转指定区域
     * @param size 长度
     */
    fun reverseList(head: ListNode, size: Int): ListNode? {
        var cur: ListNode? = head
        var headP: ListNode? = null
        // 反转的起始点需要连接到第 n 个节点
        val headTemp = head

        var count = 0
        while (null != cur && count < size) {
            val tmp = cur.next
            cur.next = headP
            headP = cur
            cur = tmp

            count++
        }

        // 连接到第 n 个节点
        headTemp.next = cur
        return headP
    }
}

复杂度分析：

  • 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)O(n)O(n)
  • 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)O(1)O(1)
234. Palindrome Linked List 回文链表 【题解】

请判断一个链表是否为回文链表。

思路：使用快慢指针找到中间节点，反转后半段链表（基于反转链表 II），比较前后两段链表是否相同，最后再反转回复到原链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
kotlin复制代码class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        if (null == head || null == head.next) {
            return true
        }

        // 1. 找到右边中节点（右中节点）
        var fast = head
        var slow = head

        while (null != fast && null != fast.next) {
            slow = slow!!.next
            fast = fast.next!!.next
        }

        // 2. 反转后半段
        val reverseP = reverseList(slow!!)

        // 3. 比较前后两段是否相同
        var p = head
        var q: ListNode? = reverseP
        var isPalindrome = true

        while (null != p && null != q) {
            if (p.`val` == q.`val`) {
                p = p.next
                q = q.next
            } else {
                isPalindrome = false
                break
            }
        }

        // 4. 恢复链表
        reverseList(reverseP)
        return isPalindrome
    }

    /**
     * 反转链表
     */
    private fun reverseList(head: ListNode): ListNode {
        // 略，见上一节...
    }
}

复杂度分析：

  • 时间复杂度：每个节点扫描两次，时间复杂度为 O(n)O(n)O(n)
  • 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)O(1)O(1)
25. K 个一组翻转链表 Reverse Nodes in k-Group

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

  1. 合并有序链表

合并有序链表问题在面试中出现频率 较高，其中，合并两个有序链表 是比较简单的，而它的进阶版 合并K个升序链表 要考虑的因素更全面，难度也有所增强，快来试试吧。

21. Merge Two Sorted Lists 合并两个有序链表 【题解】

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
kotlin复制代码class Solution {
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        if (null == l1) return l2
        if (null == l2) return l1

        // 哨兵节点
        val sentinel = ListNode(-1)
        var rear = sentinel

        var p = l1
        var q = l2

        while (null != p && null != q) {
            if (p.`val` < q.`val`) {
                rear.next = p
                rear = p
                p = p.next
            } else {
                rear.next = q
                rear = q
                q = q.next
            }
        }
        rear.next = if (null != p) p else q

        return sentinel.next
    }
}

复杂度分析：

  • 时间复杂度：每个节点扫描一次，时间复杂度为 O(m+n)O(m + n)O(m+n)
  • 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)O(1)O(1)
23. Merge k Sorted Lists 合并K个升序链表 【题解】

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

解法1：暴力法

思路1：与合并两个有序链表类似，每轮从 k 个链表中取出最小的节点，并插入结果链表中。其中，从 k 个数中取出最小节点的时间复杂度为 O(k)O(k)O(k)。

思路2：这个思路与上个思路类似，时间复杂度和空间复杂度页相同，即：依次将 k 个链表与结果链表合并。

1
复制代码略

复杂度分析：

  • 时间复杂度：O(nk∗k)O(nk * k)O(nk∗k)
  • 空间复杂度：O(1)O(1)O(1)

解法2：排序法

思路：用一个数组保存所有节点之后，进行快速排序，随后将数组输出单链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
kotlin复制代码class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isNullOrEmpty()) {
            return null
        }
        // 1. 用一个数组保存所有节点
        val array = ArrayList<ListNode>()
        for (list in lists) {
            var cur = list
            while (null != cur) {
                array.add(cur)
                cur = cur.next
            }
        }
        // 2. 快速排序
        array.sortWith(Comparator { node1, node2 -> node1.`val` - node2.`val` })
        // 3. 输出为链表
        val newHead = ListNode(-1)
        var rear = newHead
        for (node in array) {
            rear.next = node
            rear = node
        }
        return newHead.next
    }
}

复杂度分析：

  • 时间复杂度：合并节点时间 O(nk)O(nk)O(nk)，快速排序时间 O(nk∗lgnk)O(nk*lgnk)O(nk∗lgnk)，输出单链表时间 O(nk)O(nk)O(nk)，总体时间复杂度 O(nk∗lgnk)O(nk*lgnk)O(nk∗lgnk)
  • 空间复杂度：使用数组空间 O(nk)O(nk)O(nk)

解法3：归并法

思路：将 k 组链表分为两部分，然后递归地处理两组链表，最后再合并起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
kotlin复制代码class Solution {

    // 合并 k 个有序链表
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isNullOrEmpty()) {
            return null
        }
        return mergeKLists(lists, 0, lists.size - 1)
    }

    fun mergeKLists(lists: Array<ListNode?>, left: Int, right: Int): ListNode? {
        if (left == right) {
            return lists[left]
        }
        // 归并
        val mid = (left + right) ushr 1
        return mergeTwoLists(
            mergeKLists(lists, left, mid),
            mergeKLists(lists, mid + 1, right)
        )
    }

    // 合并两个有序链表
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        // 略，见上一节...
    }
}

复杂度分析：

  • 时间复杂度：时间主要在合并链表的操作上，从递归树可以看出，递归树每一层的节点个数都是 nknknk，而递归树的高度 h=lgkh = lgkh=lgk，因此总的时间复杂度为 O(nk∗lgk)O(nk*lgk)O(nk∗lgk)
  • 空间复杂度：使用了递归栈，空间复杂度为 O(lgk)O(lgk)O(lgk)

解法4：小顶堆法

思路：在解法1中，从 k 个数中取出最小节点的时间复杂度为 O(k)O(k)O(k)，可以使用最小堆（优先队列）来优化到 O(lgk)O(lgk)O(lgk)。其中，堆内节点始终是 k 个链表的未处理部分的表头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
kotlin复制代码class Solution {

    // 合并 k 个有序链表
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isNullOrEmpty()) {
            return null
        }

        // 最小堆
        val queue = PriorityQueue<ListNode>(lists.size) { node1, node2 -> node1.`val` - node2.`val` }

        // 1. 建堆
        for (list in lists) {
            if (null != list) {
                queue.offer(list)
            }
        }

        val sentinel = ListNode(-1)
        var rear = sentinel

        // 2. 出队
        while (queue.isNotEmpty()) {
            val node = queue.poll()!!
            // 输出到结果链表
            rear.next = node
            rear = node
            // 存在后继节点，加入堆中
            if (null != node.next) {
                queue.offer(node.next)
            }
        }
        return sentinel.next
    }
}

复杂度分析：

  • 时间复杂度：大小为 k 的二叉堆建堆时间为 O(k)O(k)O(k)，取堆顶的时间为 O(1)O(1)O(1)，插入一个新节点的时间为 O(lgk)O(lgk)O(lgk)，总体时间复杂度为 O(nk∗lgk)O(nk∗lgk)O(nk∗lgk)
  • 空间复杂度：二叉堆空间为 O(k)O(k)O(k)
  1. 排序链表
147. Insertion Sort List 对链表进行插入排序 |【题解】
148. Sort List 排序链表 【题解】
  1. 环形链表

链表相交 & 成环问题可以归为一类问题，在面试中出现频率较高；在之前的一篇文章里，我们单独讨论过：数据结构与算法 #2 链表相交 & 成环问题总结

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

大家好，我是小菜，一个渴望在互联网行业做到蔡不菜的小菜。可柔可刚，点赞则柔，白嫖则刚！
死鬼~看完记得给我来个三连哦！

本文主要介绍 微服务中的Nacos

如有需要，可以参考

如有帮助，不忘 点赞 ❥

微信公众号已开启，小菜良记，没关注的同学们记得关注哦！

在讲 Nacos 之前，我们需要了解什么是 Nacos：Nacos 是阿里的一个开源产品，它是针对微服务架构中的 服务发现、配置管理、服务治理 的综合性解决方案。

官网给出的回答：

Nacos 致力于帮助您发现、配置和管理微服务。Nacos 提供了一组简单易用的特性集，帮助您实现动态服务发现、服务配置管理、服务及流量管理。
Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。Nacos 是构建以“服务”为中心的现代应用架构(例如微服务范式、云原生范式)的服务基础设施。

综上所述，得出 Nacos 的四大特性：

  • 服务发现与服务健康检查
  • 动态配置管理
  • 动态DNS服务
  • 服务和元数据管理

附图：

源网侵删

看到Nacos支持这么多主流的开源生态，是心动的感觉！

一、入门基操

使用方式

Nacos的使用方式也极其简单，以下为 windows 下安装方式

步骤1

点击下载地址 下载最新稳定版本

步骤2

双击 bin 目录下的 startup.cmd 启动服务器

步骤3

通过浏览器访问 http://127.0.0.1:8848/nacos 打开 nacos 控制台登录页面，默认用户名密码皆为：nacos，登录成功后便可访问主页面。

扩展使用

发布配置

我们可以通过 地址 的方式发布配置：http://127.0.0.1:8848/nacos/v1/cs/configs，使用 postman 进行测试：

获取配置

我们可以通过 地址 的方式获取配置：http://127.0.0.1:8848/nacos/v1/cs/configs，使用 postman 进行测试：

发布服务

我们可以通过 地址 进行服务注册：http://127.0.0.1:8848/nacos/v1/ns/instance，使用 postman 进行测试：

服务发现

我们可以通过 地址 发现服务：http://127.0.0.1:8848/nacos/v1/ns/instance/list，

使用 postman 进行测试：

外部数据库支持

nacos默认是使用嵌入式数据库实现数据的存储，如果我们要使用外部 mysql 存储 nacos数据，进行以下步骤：

  • 步骤1

安装Mysql（5.6.5 ~ 8 之间的版本）

  • 步骤2

初始化 mysql 数据库，新建数据库 nacos，然后加载 conf/nacos-mysql.sql

  • 步骤3

修改 conf/application.properties文件，添加 mysql 数据源的配置，然后重启，便可生效

二、配置管理

在上述中我们已经知道Nacos其中的一个功能便是用于配置中心。配置中心是在微服务架构中，当系统从一个单体应用被拆分为分布式系统上一个个服务节点时，配置文件也必须随着迁移而分割，这样配置就分散了，而且各个配置中也存在互相冗余的部分。

配置中心所担任的角色：

配置中心将配置从各应用中剥离出来，对配置进行统一管理，应用自身不需要自己去管理配置

从图中我们总结流程如下：

  • 用户在配置中心更新配置信息
  • A 服务和 B 服务及时得到配置更新通知，从配置中心获取更新

发布配置

  • 步骤1中我们可以创建命名空间，命名空间（NameSpace）是用于隔离多个环境的（如开发、测试、生产），而每个应用在不同环境的同一配置（如数据库配置）的值是不一样的。
  • 步骤2中我们可以切换不同命名空间来发布不同配置，命名空间下类似 UUID 的一串便是每个命名空间的唯一ID。
  • 步骤3中我们可以点击发布配置，其中 DataId 和 group 是必填项

完成上面三个步骤后我们便可以看到生成了一条刚刚配置过的信息

获取配置

然后我们在项目中便可读取配置中的内容，步骤如下：

  • 步骤1

在 pom 文件中引入 nacos-client包：

1
2
3
4
5
xml复制代码<dependency>
    <groupId>com.alibaba.nacos</groupId>
    <artifactId>nacos-client</artifactId>
    <version>1.1.3</version>
</dependency>
  • 步骤2

通过 nacos-client 包下提供的 API，来获取配置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
java复制代码public static void main(String[] args) throws NacosException {
    //使用nacos client远程获取nacos服务上的配置信息
    //nacos server地址
    String serverAddr = "127.0.0.1:8848";
    //data id
    String dataId = "application-dev.properties";
    //group
    String group = "DEFAULT_GROUP";

    //namespace
    String namespace = "dfa1c276-69f7-47d6-9903-6850b9c248f7";
    Properties properties =new Properties();
    properties.put("serverAddr",serverAddr);
    properties.put("namespace",namespace);
    
    //获取配置
    ConfigService configService = NacosFactory.createConfigService(properties);
    
    // String dataId, String group, long timeoutMs
    String config = configService.getConfig(dataId, group, 5000);
    System.out.println(config);
}
/* OUTPUT:
spring.datasource.mysql.driverClassName = com.mysql.cj.jdbc.Driver
*/

配置的管理模型如下图所示：

  • 命名空间（NameSpace）

命名空间（NameSpace）用于不同环境（开发环境、测试环境和生产环境）的配置隔离。不同的命名空间下，可以存在相同名称的配置分组（Group）或配置集。

  • 配置分组（Group）

配置分组是对配置集进行分组，不同的配置分组下可以有相同的配置集（DateId）。默认的配置分组名称为 DEFAULT_GROUP。用于区分不同的项目或应用。

  • 配置集（DataId）

在系统中，一个配置文件通常就是一个 配置集，一个配置集可以包含了系统的各种配置信息，例如一个配置集可能包含了数据源、线程池、日志级别等配置项。每个配置集都可以定义一个有意义的名称。

分布式配置

在了解通过 Nacos 集中管理多个服务的配置之前，我们先大概了解下以下概念：

传统单体架构

所有功能模块打包到一起并放在一个 web 容器中运行，所有功能模块使用同一个数据库。

特点：

  • 开发效率高
  • 容易测试
  • 容易部署

缺点：

  • 复杂性会逐渐变高，维护性逐渐变差
  • 版本迭代逐渐变慢
  • 阻碍技术创新
  • 无法按需伸缩
微服务架构

微服务简单来说就是将一个项目拆分成多个服务。每一个微服务都是完整的应用，都有自己的业务逻辑和数据库。每一个业务模块都是用独立的服务完成，这种微服务架构模式也影响了应用和数据库之间的关系，不像传统多个业务模块共享一个数据库，微服务加购每个服务都有自己的数据库。

优点：

  • 分而治之，职责单一
  • 可伸缩
  • 局部容易修改、替换、部署，有利于持续集成和快速迭代
  • 不会受限于任何技术栈
Nacos

话不多说，我们直接用代码来演示配置中心的用法：

  • 步骤1 - 发布配置

我们在Nacos主页中创建两个配置文件：

service_a.properties：

service_b.properties：

  • 步骤2 - 创建父工程

pom.xml 如下：

  • 步骤3 - 创建子模块service-a

pom.xml 如下：

bootstrap.yml如下：

  • 步骤4 - 创建子模块service-b

pom.xml 如下：

bootstrap.yml如下：

工程目录结构如下：

ConfigController如下：

service-a运行结果为：

service-b运行结果为：

可以看到通过以上步骤成功获取到了我们在nacos中创建配置文件的内容。其中我们需要注意关键的步骤为：1. 引入 spring-cloud-alibaba-dependencies 和 spring-cloud-starter-alibaba-nacos-config 的 jar包。 2. 我们在 resources 下创建的配置文件必须是 bootstrap 而不能是 application 3. bootstrap.yml中的配置

bootstrap.yml另有玄机？

我们在上面看到配置核心点在于：

1
2
3
4
5
6
7
8
9
10
11
yaml复制代码spring:
  application:
    name: service_a
  cloud:
    nacos:
      config:
        server-addr: 127.0.0.1:8848                     # 配置中心地址
        # spring.application.name + file-extension = service_a.properties
        file-extension: properties                      # dataid名称的后缀
        namespace: dfa1c276-69f7-47d6-9903-6850b9c248f7 # 指定具体的namespace
        group: TEST_GROUP

这个是读取指定配置组下的指定配置，我们都知道开发讲究高内聚低耦合，如果有相同的配置项我们可以独立抽取成一个文件，这样我们就得引入多个配置文件，当然nacos也是支持的，配置如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
yaml复制代码spring:
  application:
    name: service_a
  cloud:
    nacos:
      config:
        server-addr: 127.0.0.1:8848                     # 配置中心地址
        # spring.application.name + file-extension = service_a.properties
        file-extension: properties                      # dataid名称的后缀
        namespace: dfa1c276-69f7-47d6-9903-6850b9c248f7 # 指定具体的namespace
        group: TEST_GROUP
        # 通过 ext-config 来配合使用
        ext-config[0]:
          data-id: service-common_1.properties
        ext-config[1]:
          data-id: service-common_2.properties
          group: GLOBALE_GROUP
        ext-config[2]:
          data-id: service-common_3.properties
          group: REFRESH_GROUP
          refresh: true  #动态刷新配置

注意ext-config 得从 0 开始，其中 refresh 标签用来实现动态刷新，就是配置文件修改后，项目不用重启也能实时读取最新的配置文件。

可能你会觉得通过 ext-config 有点麻烦，需要写那么多，为了简化我们还可以使用 shared-dataids 和 refreshable-dataids 实现同上一样的功能，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
yaml复制代码spring:
  application:
    name: service_a
  cloud:
    nacos:
      config:
        server-addr: 127.0.0.1:8848                     # 配置中心地址
        # spring.application.name + file-extension = service_a.properties
        file-extension: properties                      # dataid名称的后缀
        namespace: dfa1c276-69f7-47d6-9903-6850b9c248f7 # 指定具体的namespace
        group: TEST_GROUP
        
        shared-dataids: service-common_1.properties,service-common_2.properties,service-common_3.properties
        refreshable-dataids: service-common_3.properties

通过 shared-dataids 来支持多个共享 Data Id 的配置，多个之间用逗号隔开。
通过 refreshable-dataids 来支持哪些共享配置的 Data Id 在配置变化时，应用中是否可动态刷新，感知到最新的配置值，多个 Data Id 之间用逗号隔开。如果没有明确配置，默认情况下所有共享配置的 Data Id 都不支持动态刷新。

配置项的优先级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
yaml复制代码#方式1
file-extension: properties                      # dataid名称的后缀
namespace: dfa1c276-69f7-47d6-9903-6850b9c248f7 # 指定具体的namespace
group: TEST_GROUP

#方式2
ext-config[0]:
data-id: service-common_1.properties
ext-config[1]:
data-id: service-common_2.properties
group: GLOBALE_GROUP
ext-config[2]:
data-id: service-common_3.properties
group: REFRESH_GROUP
refresh: true  #动态刷新配置

#方式3
shared-dataids: service-common_1.properties,service-common_2.properties,service-common_3.properties
refreshable-dataids: service-common_3.properties

以上我们了解到了 nacos 有三种配置方式，其中优先级：

方式1 > 方式2（内部比较：n越大，优先级越高） > 方式3

以上我们已经了解完了Nacos作为配置中心的使用，接下来我们来看看Nacos作为服务的注册中心有什么奥秘！

三、服务发现

什么是服务发现

在微服务架构中，整个系统会按职责划分为多个服务，通过服务之间且做来实现业务目标。这样在我们的代码中免不了要进行服务间的远程调用，服务的消费方要调用服务的生产方，为了完成这一次请求，消费方需要知道服务生产方的网络位置（IP地址和端口号）

服务发现中心对比
对比项目 Nacos Eureka Consul ZooKeeper
一致性协议 支持 AP 和 CP 模型 AP 模型 CP模型 CP模型
健康检查 TCP/HTTP/MYSQL/Client Beat Client Beat TCP/HTTP/gRPC/Cmd Keep Alive
负载均衡器 权重/metadate/Selector Ribbon Fabio -
雪崩保护 有 有 无 无
自动注销实例 支持 支持 不支持 支持
访问协议 HTTP/DNS HTTP HTTP/DNS TCP
监听支持 支持 支持 支持 支持
多数据中心 支持 支持 支持 不支持
跨注册中心同步 支持 不支持 支持 不支持
SpringCloud集成 支持 支持 支持 不支持
Dubbo 集成 支持 不支持 不支持 支持
K8s 集成 支持 不支持 支持 不支持

服务发现入门

百说不如一练，咱们话不多说，直接上代码：

  • 步骤1 - 新建父工程

pom.xml如下：

  • 步骤2 - 新建服务生产者

pom.xml如下：

application.yml如下：

启动类如下：

ProviderController.java如下：

以上便是生成者的代码，其中关键点在于：1. 引入 spring-cloud-starter-alibaba-nacos-discovery jar包 2. 在启动类标注 @EnableDiscoveryClient 注解 3. 在 application.yml 中配置nacos服务中心的地址 4. 在 controller 中暴露服务

  • 步骤3 - 新建服务消费者

pom.xml如下：

application.yml如下：

启动类如下：

ConsumerController.java如下：

以上便是消费者的代码，其中关键点在于：1. 引入 spring-cloud-starter-alibaba-nacos-discovery jar包 2. 在启动类标注 @EnableDiscoveryClient 注解 3. 在 application.yml 中配置nacos服务中心的地址 4. 在 controller 中使用RestTemplate 调用服务。

以上我们可以看到在Nacos中注册了两个服务，分别是 service-provider 和 service-consumer，我们也可以在Nacos控制台看到：

同样，服务注册也支持命名空间的隔离，我们只需在application.yml中添加配置：

1
2
3
4
5
6
7
8
9
10
11
12
13
yaml复制代码server:
  port: 8083

spring:
  application:
    name: service-consumer
  cloud:
    nacos:
      discovery:
        server-addr: 127.0.0.1:8848
        # 命名空间
        namespace: dfa1c276-69f7-47d6-9903-6850b9c248f7
        cluster-name: DEFAULT
Feign 的使用

Feign是Netflix开发的声明式、模板化的HTTP客户端，Feign可以帮助我们更快捷、优雅地调用HTTP API。

Feign的使用方式也十分简单，几个步骤如下：

  • 步骤1

声明 Feign 客户端：

1
2
3
4
5
6
java复制代码@FeignClient(value = "service-provider") //生产者名称
public interface ConsumerService {

    @GetMapping("/getData")
    String getDate();
}
  • 步骤2

在 启动类 添加 @EnableFeignClients 注解

  • 步骤3

在 controller 层进行调用：

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码@RestController
public class ConsumerController {

    @Autowired
    private ConsumerService consumerService;

    @GetMapping("/getData")
    public String getData() {
        String date = consumerService.getDate();
        return "consumer consumer ---" + date;
    }
}

结果：

简单的使用，减少了与业务无关的 HTTP 请求相关代码的编写，使业务逻辑清晰。

END

以上便是 微服务中 Nacos 的大概介绍啦，希望看到这里的你也有所收获！路漫漫，小菜与你一同求索~

看完不赞，都是坏蛋

今天的你多努力一点，明天的你就能少说一句求人的话！

我是小菜，一个和你一起学习的男人。 💋

微信公众号已开启，小菜良记，没关注的同学们记得关注哦！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

中台的兴起

以阿里“小前台 大中台”为最明显的带动，国内多家企业，特别是互联网企业都拿起中台利器，以期实现在新市场环境下的突破与新生 。 中台用技术手段实现数据提取、价值沉淀，提炼共性需求、减少重复劳动，将带有自身格调的标准化服务做到比之前更有效率，让组织反应更快，这对于企业降低管理成本、实现协同，特别是用户满意度的提升，是很有建设性的探索 ，随着中台在更多公司的落地，有人欢喜有人忧， 花大功夫建立的 数据中台，业务中台，技术中台 可能不一定带来好的效果，这主要还是看人，业务线的Leader尤为重要，兵熊熊一个将熊熊一窝 !。

fs业务中台业务简介

业务有 2个商城业务线， 牙医管家SASS 软件 ，硬件研发业务，供应链业务

fs 业务中台主要是包括 商城 ，供应链 业务

踩坑大法好

技术

  • 采用的是 Java SpringCloud 技术栈，无论是 Netflix Zuul Eureka 还是 Alibaba Nacos Sentinel 任意一套 都需要自己 做二次开发，很多东西并不是说开箱就能用的，需要打磨沉淀出一套好的项目脚手架，不然很影响开发效率
  • 中间件 需要人统一维护管理 Redis 集群 MQ 集群 分布式任务调度集群等等
  • 服务的拆分：遵守康威定律根据 所在团队地区 及具体业务划分，不要想一出是一出
  • 权限划分: 近年来 删库事件太多了 参考 微盟集团 的事情，做好 安全，风险意识的培训，做好备份 等等
  • Dead Line ： 认真考虑最终交付期限的设定 ，培养好的 deadline 意识，从实际出发，避免项目延期交付

人

  • 首先是 招聘 如果不是在 北上广深 你想招聘 到既懂业务又懂技术是很难的，所以尽量靠内推和朋友介绍，招人难和找到合适的工作难 是老生常谈就不赘述了
  • 猪队友 林子大了什么鸟都有 千万不要以为 人人都能够保持一颗上进的心，能够努力学习 工作研发既不懂业务，技术水平也水的一匹，测试从不写测试用例，但是千万别让你的队友影响到你的心情，老板聪明的很，谁能干活谁不能心理一清二楚，千万不要 让这种队友担任重任，不然出了问题 它会第一时间甩锅到你的头上毫无责任心，不要为猪队友做的事生气，保持良好心态，做事留一线，私下沟通不了，再发邮件怼
  • 人的发展: 随着 2020 年行业的发展，行情并不好 ，996 大小周的公司越来越多 很正常，保持学习的热情，很重要在你 结婚生子之前尽量多学习专业知识，不然很多琐事会让你很难有心思去做你想做的事情
  • 责任心 中台有几个服务模块 是从 .net改成java的或者php 改成java的，老项目 实在是 做的一堆问题不得重构，在之后的工作还是发现无论是什么技术 做事没有责任的人担当做出来的事情 产品都让人老害怕了，对自己负责对产品负责从你我开始

业务

  • 研发不懂业务，那和战场上带枪不带子弹的士兵一样 吃败仗是肯定的，刚进一家新公司对业务不熟悉很正常，自己用心多看多学多问多思考，不说精通业务，最起码能对自己所做的业务有初步的认知
  • 在绝大多数公司都是 业务驱动技术，少部分公司是 技术驱动业务，业务重要性毋庸置疑，所以每个同学尽量在同一行业待久点，学到东西可能会更多，但是 你的行业必须是在高速发展的，不然你的青春就陪着夕阳产业一起欢度了

参考

中台的兴起，将进一步加速企业组织扁平化

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

反射定义

1，JAVA反射机制是在运行状态中

对于任意一个类，都能够知道这个类的所有属性和方法；

对于任意一个对象，都能够调用它的任意一个方法和属性；

这种动态获取的信息以及动态调用对象的方法的功能称为java语言的反射机制。

反射提供的功能：

  • 在运行时判断任意一个对象所属的类
  • 在运行时构造任意一个类的对象
  • 在运行时判断任意一个类所具有的成员变量和方法
  • 在运行时调用任意一个对象的方法
**（如果属性是private，正常情况下是不允许外界操作属性值，这里可以用Field类的setAccessible(true)方法，暂时打开操作的权限）**

反射的使用场景

  • Java编码时知道类和对象的具体信息，此时直接对类和对象进行操作即可，无需反射
  • 如果编码时不知道类或者对象的具体信息，此时应该使用反射来实现

反射源码解析

举例API ： 

1
scss复制代码Class.forName("com.my.reflectTest").newInstance()

1. 反射获取类实例 Class.forName(“xxx”);

　　首先调用了 java.lang.Class 的静态方法，获取类信息！

注意：forName()反射获取类信息，并没有将实现留给了java,而是交给了jvm去加载！

主要是先获取 ClassLoader, 然后调用 native 方法，获取信息，加载类则是回调 入参ClassLoader 进类加载！
1
2
3
4
5
6
7
8
swift复制代码 @CallerSensitive
    public static Class<?> forName(String className)
                throws ClassNotFoundException {
        // 先通过反射，获取调用进来的类信息，从而获取当前的 classLoader
        Class<?> caller = Reflection.getCallerClass();
        // 调用native方法进行获取class信息
        return forName0(className, true, ClassLoader.getClassLoader(caller), caller);
    }

2. java.lang.ClassLoader—–loadClass()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
scss复制代码// java.lang.ClassLoader
    protected Class<?> loadClass(String name, boolean resolve)
        throws ClassNotFoundException
    {
        // 先获取锁
        synchronized (getClassLoadingLock(name)) {
            // First, check if the class has already been loaded
            // 如果已经加载了的话，就不用再加载了
            Class<?> c = findLoadedClass(name);
            if (c == null) {
                long t0 = System.nanoTime();
                try {
                    // 双亲委托加载
                    if (parent != null) {
                        c = parent.loadClass(name, false);
                    } else {
                        c = findBootstrapClassOrNull(name);
                    }
                } catch (ClassNotFoundException e) {
                    // ClassNotFoundException thrown if class not found
                    // from the non-null parent class loader
                }
 
                // 父类没有加载到时，再自己加载
                if (c == null) {
                    // If still not found, then invoke findClass in order
                    // to find the class.
                    long t1 = System.nanoTime();
                    c = findClass(name);
 
                    // this is the defining class loader; record the stats
                    sun.misc.PerfCounter.getParentDelegationTime().addTime(t1 - t0);
                    sun.misc.PerfCounter.getFindClassTime().addElapsedTimeFrom(t1);
                    sun.misc.PerfCounter.getFindClasses().increment();
                }
            }
            if (resolve) {
                resolveClass(c);
            }
            return c;
        }
    }
    
    protected Object getClassLoadingLock(String className) {
        Object lock = this;
        if (parallelLockMap != null) {
            // 使用 ConcurrentHashMap来保存锁
            Object newLock = new Object();
            lock = parallelLockMap.putIfAbsent(className, newLock);
            if (lock == null) {
                lock = newLock;
            }
        }
        return lock;
    }
    
    protected final Class<?> findLoadedClass(String name) {
        if (!checkName(name))
            return null;
        return findLoadedClass0(name);
    }

3. newInstance()

1
scss复制代码newInstance() 其实相当于调用类的无参构造函数,主要做了三件事
  • 权限检测，如果不通过直接抛出异常；
  • 查找无参构造器，并将其缓存起来；
  • 调用具体方法的无参构造方法，生成实例并返回；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
kotlin复制代码// 首先肯定是 Class.newInstance
    @CallerSensitive
    public T newInstance()
        throws InstantiationException, IllegalAccessException
    {
        if (System.getSecurityManager() != null) {
            checkMemberAccess(Member.PUBLIC, Reflection.getCallerClass(), false);
        }
 
        // NOTE: the following code may not be strictly correct under
        // the current Java memory model.
 
        // Constructor lookup
        // newInstance() 其实相当于调用类的无参构造函数，所以，首先要找到其无参构造器
        if (cachedConstructor == null) {
            if (this == Class.class) {
                // 不允许调用 Class 的 newInstance() 方法
                throw new IllegalAccessException(
                    "Can not call newInstance() on the Class for java.lang.Class"
                );
            }
            try {
                // 获取无参构造器
                Class<?>[] empty = {};
                final Constructor<T> c = getConstructor0(empty, Member.DECLARED);
                // Disable accessibility checks on the constructor
                // since we have to do the security check here anyway
                // (the stack depth is wrong for the Constructor's
                // security check to work)
                java.security.AccessController.doPrivileged(
                    new java.security.PrivilegedAction<Void>() {
                        public Void run() {
                                c.setAccessible(true);
                                return null;
                            }
                        });
                cachedConstructor = c;
            } catch (NoSuchMethodException e) {
                throw (InstantiationException)
                    new InstantiationException(getName()).initCause(e);
            }
        }
        Constructor<T> tmpConstructor = cachedConstructor;
        // Security check (same as in java.lang.reflect.Constructor)
        int modifiers = tmpConstructor.getModifiers();
        if (!Reflection.quickCheckMemberAccess(this, modifiers)) {
            Class<?> caller = Reflection.getCallerClass();
            if (newInstanceCallerCache != caller) {
                Reflection.ensureMemberAccess(caller, this, null, modifiers);
                newInstanceCallerCache = caller;
            }
        }
        // Run constructor
        try {
            // 调用无参构造器
            return tmpConstructor.newInstance((Object[])null);
        } catch (InvocationTargetException e) {
            Unsafe.getUnsafe().throwException(e.getTargetException());
            // Not reached
            return null;
        }
    }

4. getConstructor0() 为获取匹配的构造方器；分三步：

　　1. 先获取所有的constructors, 然后通过进行参数类型比较；
　　2. 找到匹配后，通过 ReflectionFactory copy一份constructor返回；
　　3. 否则抛出 NoSuchMethodException;

1
2
3
4
5
6
7
8
9
10
11
12
13
scss复制代码private Constructor<T> getConstructor0(Class<?>[] parameterTypes,
                                        int which) throws NoSuchMethodException
    {
        // 获取所有构造器
        Constructor<T>[] constructors = privateGetDeclaredConstructors((which == Member.PUBLIC));
        for (Constructor<T> constructor : constructors) {
            if (arrayContentsEq(parameterTypes,
                                constructor.getParameterTypes())) {
                return getReflectionFactory().copyConstructor(constructor);
            }
        }
        throw new NoSuchMethodException(getName() + ".<init>" + argumentTypesToString(parameterTypes));
    }

5. privateGetDeclaredConstructors(), 获取所有的构造器主要步骤；

　　1. 先尝试从缓存中获取；
　　2. 如果缓存没有，则从jvm中重新获取，并存入缓存，缓存使用软引用进行保存，保证内存可用；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
kotlin复制代码// 获取当前类所有的构造方法，通过jvm或者缓存
    // Returns an array of "root" constructors. These Constructor
    // objects must NOT be propagated to the outside world, but must
    // instead be copied via ReflectionFactory.copyConstructor.
    private Constructor<T>[] privateGetDeclaredConstructors(boolean publicOnly) {
        checkInitted();
        Constructor<T>[] res;
        // 调用 reflectionData(), 获取保存的信息，使用软引用保存，从而使内存不够可以回收
        ReflectionData<T> rd = reflectionData();
        if (rd != null) {
            res = publicOnly ? rd.publicConstructors : rd.declaredConstructors;
            // 存在缓存，则直接返回
            if (res != null) return res;
        }
        // No cached value available; request value from VM
        if (isInterface()) {
            @SuppressWarnings("unchecked")
            Constructor<T>[] temporaryRes = (Constructor<T>[]) new Constructor<?>[0];
            res = temporaryRes;
        } else {
            // 使用native方法从jvm获取构造器
            res = getDeclaredConstructors0(publicOnly);
        }
        if (rd != null) {
            // 最后，将从jvm中读取的内容，存入缓存
            if (publicOnly) {
                rd.publicConstructors = res;
            } else {
                rd.declaredConstructors = res;
            }
        }
        return res;
    }
    
    // Lazily create and cache ReflectionData
    private ReflectionData<T> reflectionData() {
        SoftReference<ReflectionData<T>> reflectionData = this.reflectionData;
        int classRedefinedCount = this.classRedefinedCount;
        ReflectionData<T> rd;
        if (useCaches &&
            reflectionData != null &&
            (rd = reflectionData.get()) != null &&
            rd.redefinedCount == classRedefinedCount) {
            return rd;
        }
        // else no SoftReference or cleared SoftReference or stale ReflectionData
        // -> create and replace new instance
        return newReflectionData(reflectionData, classRedefinedCount);
    }
    
    // 新创建缓存，保存反射信息
    private ReflectionData<T> newReflectionData(SoftReference<ReflectionData<T>> oldReflectionData,
                                                int classRedefinedCount) {
        if (!useCaches) return null;
 
        // 使用cas保证更新的线程安全性，所以反射是保证线程安全的
        while (true) {
            ReflectionData<T> rd = new ReflectionData<>(classRedefinedCount);
            // try to CAS it...
            if (Atomic.casReflectionData(this, oldReflectionData, new SoftReference<>(rd))) {
                return rd;
            }
            // 先使用CAS更新，如果更新成功，则立即返回，否则测查当前已被其他线程更新的情况，如果和自己想要更新的状态一致，则也算是成功了
            oldReflectionData = this.reflectionData;
            classRedefinedCount = this.classRedefinedCount;
            if (oldReflectionData != null &&
                (rd = oldReflectionData.get()) != null &&
                rd.redefinedCount == classRedefinedCount) {
                return rd;
            }
        }
    }

另外，使用 relactionData() 进行缓存保存；ReflectionData 的数据结构如下！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ini复制代码// reflection data that might get invalidated when JVM TI RedefineClasses() is called
    private static class ReflectionData<T> {
        volatile Field[] declaredFields;
        volatile Field[] publicFields;
        volatile Method[] declaredMethods;
        volatile Method[] publicMethods;
        volatile Constructor<T>[] declaredConstructors;
        volatile Constructor<T>[] publicConstructors;
        // Intermediate results for getFields and getMethods
        volatile Field[] declaredPublicFields;
        volatile Method[] declaredPublicMethods;
        volatile Class<?>[] interfaces;
 
        // Value of classRedefinedCount when we created this ReflectionData instance
        final int redefinedCount;
 
        ReflectionData(int redefinedCount) {
            this.redefinedCount = redefinedCount;
        }
    }

6.通过上面，获取到 Constructor 了！接下来就只需调用其相应构造器的 newInstance()，即返回实例了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
scss复制代码// return tmpConstructor.newInstance((Object[])null); 
    // java.lang.reflect.Constructor
    @CallerSensitive
    public T newInstance(Object ... initargs)
        throws InstantiationException, IllegalAccessException,
               IllegalArgumentException, InvocationTargetException
    {
        if (!override) {
            if (!Reflection.quickCheckMemberAccess(clazz, modifiers)) {
                Class<?> caller = Reflection.getCallerClass();
                checkAccess(caller, clazz, null, modifiers);
            }
        }
        if ((clazz.getModifiers() & Modifier.ENUM) != 0)
            throw new IllegalArgumentException("Cannot reflectively create enum objects");
        ConstructorAccessor ca = constructorAccessor;   // read volatile
        if (ca == null) {
            ca = acquireConstructorAccessor();
        }
        @SuppressWarnings("unchecked")
        T inst = (T) ca.newInstance(initargs);
        return inst;
    }
    // sun.reflect.DelegatingConstructorAccessorImpl
    public Object newInstance(Object[] args)
      throws InstantiationException,
             IllegalArgumentException,
             InvocationTargetException
    {
        return delegate.newInstance(args);
    }
    // sun.reflect.NativeConstructorAccessorImpl
    public Object newInstance(Object[] args)
        throws InstantiationException,
               IllegalArgumentException,
               InvocationTargetException
    {
        // We can't inflate a constructor belonging to a vm-anonymous class
        // because that kind of class can't be referred to by name, hence can't
        // be found from the generated bytecode.
        if (++numInvocations > ReflectionFactory.inflationThreshold()
                && !ReflectUtil.isVMAnonymousClass(c.getDeclaringClass())) {
            ConstructorAccessorImpl acc = (ConstructorAccessorImpl)
                new MethodAccessorGenerator().
                    generateConstructor(c.getDeclaringClass(),
                                        c.getParameterTypes(),
                                        c.getExceptionTypes(),
                                        c.getModifiers());
            parent.setDelegate(acc);
        }
 
        // 调用native方法，进行调用 constructor
        return newInstance0(c, args);
    }

返回构造器的实例后，可以根据外部进行进行类型转换，从而使用接口或方法进行调用实例功能了。

总结

欢迎关注公众号：前程有光，领取一线大厂Java面试题总结+各知识点学习思维导+一份300页pdf文档的Java核心知识点总结！

这些资料的内容都是面试时面试官必问的知识点，篇章包括了很多知识点，其中包括了有基础知识、Java集合、JVM、多线程并发、spring原理、微服务、Netty 与RPC 、Kafka、日记、设计模式、Java算法、数据库、Zookeeper、分布式缓存、数据结构等等。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 2 篇文章，完整文章目录请移步到文章末尾~

前言

  • 链表相交 & 成环问题可以归为一类问题，在面试中出现频率较高；
  • 在这篇文章里，我将梳理链表相交 & 成环问题的解法。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
相关问题 提示 & 题解
160. 相交链表 Intersection of Two Linked Lists 【题解】
141. 环形链表 Linked List Cycle 【题解】
142. 环形链表 II Linked List Cycle II 【题解】
61. 旋转链表 Rotate List 【题解】
（扩展）457. 环形循环数组 Circular Array Loop 【题解】

目录

  1. 判断链表相交

160. Intersection of Two Linked Lists 相交链表 【题解】

编写一个程序，找到两个单链表相交的起始节点。

解法1：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
kotlin复制代码class Solution {
    fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
        if (null == headA || null == headB) {
            return null
        }
        
        val set = HashSet<ListNode>()
        var pA = headA
        var pB = headB
        while (null != pA) {
            set.add(pA)
            pA = pA.next
        }
        while (null != pB) {
            if (set.contains(pB)) {
                return pB
            }
            pB = pB.next
        }
        return null
    }
}

复杂度分析：

  • 时间复杂度：两个链表的节点最多访问一次，时间复杂度为O(m+n)O(m+n)O(m+n)
  • 空间复杂度：以其中一个链表构建哈希表，空间复杂度为O(m)O(m)O(m)

解法2：链表成环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
kotlin复制代码class Solution {
    fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
        if (null == headA || null == headB) {
            return null
        }
        
        var pA = headA
        var pB = headB
        while (pA != pB) {
            // 退出的关键是：pA和pB指向同一个指针（不是值相等），或者都指向null
            pA = if (null == pA) headB else pA.next
            pB = if (null == pB) headA else pB.next
        }
        return pA
    }
}

复杂度分析：

  • 时间复杂度：两个链表的节点最多访问一次，时间复杂度为O(m+n)O(m+n)O(m+n)
  • 空间复杂度：只是用了常量级别变量，空间复杂度为O(1)O(1)O(1)
  1. 判断链表成环

141. Linked List Cycle 环形链表 【题解】

给定一个链表，判断链表中是否有环。

解法1：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
kotlin复制代码class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        val set = HashSet<ListNode>()
        var p = head
        while (null != p) {
            if (set.contains(p)) {
                return true
            }
            set.add(p)
            p = p.next
        }
        return false
    }
}

复杂度分析：

  • 时间复杂度：链表的节点最多访问一次，时间复杂度为O(n)O(n)O(n)
  • 空间复杂度：哈希表空间复杂度为O(n)O(n)O(n)

解法2：Floyd 判圈算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
kotlin复制代码class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        var slow = head
        var fast = head
        while (null != fast && null != fast.next) {
            slow = slow!!.next
            fast = fast.next!!.next
            if (slow == fast) {
                return true
            }
        }
        return false
    }
}

复杂度分析：

  • 时间复杂度：O(n)O(n)O(n)
  • 空间复杂度：只是用了常量级别变量，空间复杂度为O(1)O(1)O(1)
  1. 判断链表成环起点

142. Linked List Cycle II 环形链表 II 【题解】

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。不允许修改给定的链表。

解法1：哈希表

与 第二节类似，略

解法2：Floyd 判圈算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
kotlin复制代码class Solution {
    fun detectCycle(head: ListNode?): ListNode? {
        // 1. 寻找双指针相交位置
        var slow = head
        var fast = head
        var intersect: ListNode? = null
        while (null != fast && null != fast.next) {
            slow = slow!!.next
            fast = fast.next!!.next
            if (slow == fast) {
                intersect = slow
                break
            }
        }
        // 2. 寻找成环位置
        if (null == intersect) {
            return null
        } else {
            var p = intersect
            var q = head
            while (p != q) {
                p = p!!.next
                q = q!!.next
            }
            return p
        }
    }
}

复杂度分析：

  • 时间复杂度：O(n)O(n)O(n)
  • 空间复杂度：只是用了常量级别变量，空间复杂度为O(1)O(1)O(1)
  1. 旋转链表

61. Rotate List 旋转链表 【题解】

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

解法1：链表成环

先将链表闭合成环，再找到新表头，断开前驱节点的连接。需要注意 k 大于链表长度的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
kotlin复制代码class Solution {
    fun rotateRight(head: ListNode?, k: Int): ListNode? {
        if (null == head || null == head.next || 0 == k) {
            return head
        }

        var cur = head

        // 1. 找到尾节点
        var count = 1
        while (null != cur!!.next) {
            cur = cur.next
            count++
        }
        if (0 == k % count) {
            // 旋转后未变化
            return head
        }
        // 2. 链表成环
        cur.next = head
        // 3. 找到倒数第 k 个节点的前驱节点
        cur = head
        for (index in 0 until count - (k % count) - 1) {
            cur = cur!!.next
        }
        // 4. 断开 preK
        val preK = cur
        val kP = preK!!.next
        preK.next = null
        return kP
    }
}

复杂度分析：

  • 时间复杂度：扫描两趟，时间复杂度为 O(n)O(n)O(n)
  • 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)O(1)O(1)
  1. (扩展) 判断环形循环数组

457. Circular Array Loop 环形循环数组 【题解】

给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。相反，如果是负数 (-k)，则向后移动 k 个索引。因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。

确定 nums 中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。

解法1：哈希表 + 记忆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
kotlin复制代码class Solution {
    fun circularArrayLoop(nums: IntArray): Boolean {

        val visits = BooleanArray(nums.size) { false }

        fun isCircle(from: Int): Boolean {
            if (visits[from]) {
                return false
            }
            val set = HashSet<Int>()
            var cur = from
            while (true) {
                // 路径标志
                visits[cur] = true
                val nextIndex = nums.jump(cur)
                if (nums[nextIndex] * nums[cur] < 0) {
                    // 逆向
                    return false
                }
                if (set.contains(cur)) {
                    return cur != nextIndex
                }
                set.add(cur)
                cur = nextIndex
            }
        }

        for (index in 0 until nums.size) {
            if (isCircle(index)) {
                return true
            }
        }
        return false
    }

    /**
     * @return index of next jump
     */
    fun IntArray.jump(curIndex: Int): Int {
        val nextIndex = curIndex + this[curIndex] % size
        if (nextIndex < 0) {
            return size + nextIndex
        }
        if (nextIndex >= size) {
            return nextIndex - size
        }
        return nextIndex
    }
}

复杂度分析：

  • 时间复杂度：每个位置最多访问一次，时间复杂度为O(n)O(n)O(n)
  • 空间复杂度：哈希表为O(n)，O(n)，O(n)，路径标志为O(n)O(n)O(n)，总体为O(n)O(n)O(n)

解法2：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
kotlin复制代码class Solution {
    fun circularArrayLoop(nums: IntArray): Boolean {
        val n = nums.size
        val U = 1000 * n // 保证取模后不变
        for (i in nums.indices) {
            if (nums[i] > U) continue
            // 快慢指针
            var fast = nums.next(i)
            var slow = i
            // println("i=$i, slow=$slow, fast=$fast")
            // -2,1,-1,-2,-2
            while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[nums.next(fast)] > 0) { // 往一个方向
                nums[slow] += U 
                nums[fast] += U
                slow = nums.next(slow)
                fast = nums.next(nums.next(fast))
                // println("slow=$slow, fast=$fast")
                if (slow == fast) {
                    // [-1,-2,-3,-4,-5,6]
                    if (slow != nums.next(slow)) return true // 要求循环长度大于 1
                    break
                }
            }
        }
        return false
    }

    private fun IntArray.next(index : Int) : Int {
        return ((index + this[index]) % size + size) % size
    }
}

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

背景：

项目中一部分数据如页面静态数据需要从redis中获取，以提高页面加载速度。页面数据的修改是通过管理画面修改mysql，通过定时任务或手动将mysql数据同步到redis，以供页面获取。这里数据同步不是增量同步，而是根据条件查询得到数据集后同步。网关中的一些参数同样是在mysql维护，然后定时或手动推送到redis，并通知网关刷新内存数据。有时增加一个数据的变动会出发多个同步操作，如增加一个api，既要将其在门户画面展示，又要推送到网关，如果想实时生效就需要两次手动操作。这样就很繁琐，因此设计一种实时或准实时将mysql同步至redis的方案。

方案1：

更新数据库的同时执行同步redis方法，如在增删改首页数据的方法添加注解，利用aop统一处理数据同步的逻辑。这种方案实际就是spring cache。但是这里不仅仅要将数据同步至redis，还要发布订阅事件，因此需要自己实现aop逻辑。

方案2：

利用canal，监听mysql数据变更进行数据同步和发布订阅事件。这样不必修改原代码，逻辑解耦。并且如果mysql修改失败不会触发同步操作。

综上采用方案2。

详细方案设计：

在canal定义一个destination监听数据库，当有感兴趣的数据变动时，通过feign调用对应服务的同步方法（这里的同步方法复用已有的手动调用方法，不用新写）。因为同步的是准全量数据，为避免mysql每次更新都查询，党一个数据变动后一分钟内没有新的数据变动，才触发同步操作。此外，通过apollo配置中心动态启停同步服务。

canal部署：

参照官网的方案，利用zookeeper进行服务协调，实现canal server，canal client的高可用。

由于测试环境分为SIT，QA和UAT，每个环境有单独的数据库，因此canal定义三个destination监听对应的数据库实例。

未来的优化方向：

  • Redis获取数据失败fallback到数据库
  • 增加一层内存缓存
  • 感知同步数据成功与否

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%