开发者博客 – IT技术 尽在开发者博客

开发者博客 – 科技是第一生产力


  • 首页

  • 归档

  • 搜索

图像检索在高德地图POI数据生产中的应用 一 背景 二 技术

发表于 2021-11-10

简介: 高德通过自有海量的图像源,来保证现实世界的每一个新增的POI及时制作成数据。在较短时间间隔内(小于月度),同一个地方的POI 的变化量是很低的。

作者 | 灵笼、怀迩

来源 | 阿里技术公众号

一 背景

POI 是 Point of Interest 的缩写。在电子地图上,POI 代表餐厅、超市、政府机关、旅游景点、交通设施等等 。POI是电子地图的核心数据。对普通用户而言,POI 数据包含的名称和位置信息,能够满足其使用电子地图“查找目的地”,进而唤起导航服务的基本需求;对电子地图而言,通过提供“搜索附近”、“点评”等操作,可提高用户的活跃时长。另外,POI数据是线上线下连接互动的一个纽带,是基于位置服务(Location Based Service)产业的一个重要组件。

高德通过自有海量的图像源,来保证现实世界的每一个新增的POI及时制作成数据。在较短时间间隔内(小于月度),同一个地方的POI 的变化量是很低的,如下图所示,只有“汤火功夫”POI是一个新增的挂牌。

图1. 同一地方上不同时间的POI牌匾对比

如果对全部POI进行处理的话,则会带来高昂的作业成本,因此需要对其中没有变化的POI进行自动化过滤,其中关键技术能力就是图像匹配,该场景是一个较为典型的图像检索任务。

1 技术定义

图像检索问题定义:给定查询图像(Query),通过分析视觉内容,在大型图像库中(Gallery)中搜索出相似的图像。该方向一直是计算机视觉领域的一个长期研究课题,在行人重识别、人脸识别、视觉定位等任务中均有广泛的研究。图像检索的核心技术是度量学习,其目标是在固定维度的特征空间中,约束模型将同类别样本拉近,不同类别样本推远。在深度学习时代,主要有几种经典的结构,包括:对比损失(contractive loss)、三元组损失(triplet loss)、中心损失(center loss)等,均是通过正负样本定义以及损失函数设计上进行优化。此外,图像检索还有一个必不可少的要素就是特征提取,通常包括:全局特征、局部特征、辅助特征等,主要是针对不同任务特点进行相应的优化,例如:行人重识别以及人脸识别具有很强的刚性约束,并且具备明显的关键特征(行人/人脸关键点),因此会将人体分割或关键点检测信息融合到模型特征提取中。

2 问题特点

POI牌匾的图像检索和学术上主流检索任务(如行人重识别)有着较大的区别,主要包括以下几点:异源数据、遮挡严重以及文本依赖性。

异源数据

行人重识别任务也存在异源数据问题,但是该任务的异源更多是不同相机拍摄以及不同场景的区别。而在POI牌匾检索场景中,存在更严重的异源数据问题,如下图所示:

图2. 不同拍摄条件下的异源图像

左图来自低质量相机,并且是前向拍摄;右图来自高质量相机,并且是侧向拍摄;因为相机拍摄质量以及拍摄视角不同,这就导致POI牌匾的亮度、形状、清晰度等都存在非常大的差异。而如何在差异较大的异源数据中实现POI牌匾检索,是一个非常具有挑战性的问题。

遮挡严重

在道路场景中,经常存在树木以及车辆等干扰信息,并且由于拍摄视角原因,拍摄到的POI牌匾经常会面临严重的遮挡问题,如下图所示:

图3. 遮挡严重的POI牌匾示例

而且该遮挡场景还是不规则的,导致很难对两个牌匾进行较好地特征对齐,这给POI牌匾检索带来巨大的挑战。

文本依赖性

POI牌匾还有一个独有特性就是对文本强依赖,主要是对POI名称文本的依赖。在下图场景中,两个牌匾的整体布局以及颜色都非常相似,但是其中POI名称发生了变化。而在该场景下,我们希望两个牌匾不要匹配,这就需要引入文本特征来增强特征区分性。不过,由于遮挡原因也会导致文本特征不同,因此需要结合图像特征进行权衡。而且,文本特征和图像特征来自多个模态,如何将多模信息进行融合也是该业务特有的技术难点。

图4. 仅文本变化的POI牌匾示例

二 技术方案

牌匾检索的技术方案主要包括数据迭代和模型优化两块。在数据生成部分,我们分为了冷启动自动生成数据以及模型迭代生成数据两个步骤。在模型优化部分,我们设计了一个多模态检索模型,包括视觉分支和文本分支两部分,主要是考虑到牌匾的文本信息比较丰富,因此将视觉信息与文本信息进行融合。针对视觉信息特征的提取,我们进一步设计了全局特征分支与局部特征分支,并分别进行了优化。整体技术框架如下图所示:

图5. 整体技术方案

首先利用传统匹配算法Sift自动生成模型所需的训练数据,完成模型的冷启动;并且在模型上线后,对线上人工作业结果进行自动挖掘,并组织成训练数据,以迭代模型优化。多模态检索模型是基于三元组损失(Triplet Los)的度量学习框架下进行设计的,输入包括了:1)POI牌匾的图像信息;2)POI牌匾的文本信息。图像信息使用双分支进行特征提取,文本信息使用BERT进行特征提取,最后再将文本特征与视觉特征进行融合。

1 数据

为训练检索模型,通常需要进行实例级标注,即按照POI牌匾粒度进行标注。而在不同资料中筛选同一POI牌匾是一件非常复杂的工作,如果进行人工标注的话,则会带来高昂的标注成本,并且无法大规模标注。因此,我们设计了一套简单高效的训练数据自动生成方式,可用于模型冷启动,整个环节无需任何人工标注。

我们借鉴了传统特征点匹配算法思想,利用Sift特征点匹配算法对两趟资料中的所有牌匾进行两两匹配,并通过内点数量对匹配结果进行筛选,即内点数量大于阈值的匹配牌匾视作同一牌匾。通常来说,传统特征点匹配算法会存在泛化性不足问题,由此生成的训练数据很可能导致模型无法很好学习,具体体现在:1)训练样本较为简单;2)类别冲突,即同一牌匾分为多个类别;3)类别错误,即不同牌匾分为同一类别。因此,我们针对该问题进行了相应优化:1)采用多趟资料匹配结果,提升同一类别下牌匾的多样性;2)采用Batch采样策略以及MDR loss[2]来降低模型对错误标签数据的敏感性。

具体来说,对于样本多样性问题,我们使用了多趟资料的匹配结果来生成训练数据,因为在不同资料中同一牌匾存在多张来自不同视角的拍摄结果,这就保证了同一类别下牌匾的多样性,避免了自动生成的样本都为简单样本问题。Batch采样策略即按类别进行采样,而数据中类别总数远远大于batch size,因此可以缓解类别冲突的问题。MDR loss是在Triplet loss基础上设计了根据不同距离区间进行正则化约束的新的度量学习框架,从而减少模型对对噪声样本的过拟合。

图6. MDR loss示意图,和Triplet loss相比增加了距离正则约束

图6 是Triplet loss和MDR loss的对比示意图。MDR loss希望正样本和anchor之间的距离不被拉到无限近,同时负样本也不希望被推到无限远。以类别错误噪声样本来说,不同牌匾被误分为同一类别,按照Triplet loss的优化目标则会强制模型将两者距离学习到无限近,这样的话,模型会过拟合到噪声样本上,从而导致最终效果较差。

2 模型

为了优化牌匾检索效果,我们融合了牌匾中的视觉信息与文本信息,设计了多模态检索模型。针对视觉信息,我们优化了模型全局特征和局部特征的提取能力。针对文本信息,我们使用BERT对牌匾的OCR结果进行编码,将其作为辅助特征,并与视觉特征融合后进行度量学习。

全局特征

通常对于检索任务来说,使用深度学习模型提取到的全局特征更为鲁棒,可以适应牌匾视角、颜色、光照变化等不同场景。为了进一步提升全局特征的鲁棒性,我们主要从以下两方面进行了优化:1)采用Attention机制,加强对重要特征的关注;2)网络backbone的改进,以关注到更多细粒度特征。

在我们的业务场景中,存在一些外观相似而细节有一定差异的牌匾,如图8 (c) 所示,在这种情况下,我们希望模型可以关注到牌匾中的细粒度信息,比如牌匾中文字的字体、文字排版或者是文字内容本身。而注意力机制则可以帮助模型在大量信息中准确地关注到能够区分不同牌匾更为关键的部分。因此,我们在网络中引入了注意力模块,让模型学习关键信息,以提升全局特征的辨别能力。我们采用了空间注意力机制SGE(Spatial Group-wise Enhance)[4],SGE通过对特征图上的每个空间位置生成一个注意力因子来调整每个空间位置处特征的重要性。SGE模块如图7所示。它首先对特征图进行了分组,然后对每组特征图计算语义特征向量,使用语义特征向量和特征图进行position-wise点乘,得到注意力图,然后将注意力图与特征图进行position-wise点乘,以此来增强特征,从而获得在空间上分布更好的语义特征。

图7. SGE示意图,引入了空间注意力机制

为了减少局部特征的损失,我们对网络backbone进行了改进,取消了ResNet网络最后一个block中的下采样,使得最终的特征图中包含更多的局部信息。除此之外,我们使用GeM[3]池化层替代了最后一个global average pooling,GeM是一种可学习的特征聚合方法,global max pooling和global average pooling都是它的特殊情况,使用GeM池化可以进一步提升全局特征鲁棒性。

局部特征

在针对全局特征进行优化以后,现有模型仍然在以下三个方面表现不够好:1)牌匾截断的情况,特征学习质量差,如图8(a);2)遮挡的牌匾,特征中引入一些无关的上下文信息,如图8(b);3)相似但不同的牌匾难以区分,如图8(c)。因此,我们进一步设计了局部特征分支[1],让模型更加关注牌匾的几何、纹理等局部信息,与全局特征共同做牌匾检索。

(a)

(b)

(c)

图8. 需局部特征优化的不同示例,(a)截断 (b)遮挡(c)文本变化

针对局部特征的提取,我们主要的思路是将牌匾垂直切分成几个部分,分别关注每个部分的局部特征[7],并对局部特征进行对齐后优化。对齐操作如下图9所示,首先将特征图进行垂直池化,得到分块的局部特征图,再计算两张图局部特征之间的相似度矩阵,然后根据公式1找到最短距离将两张图像进行对齐,其中,i,j分别表示两张图中的第i块特征和第j块特征,dij表示两张图中第i块和第j块特征的欧式距离。

公式1. 局部对齐计算公式

图9. POI牌匾局部对齐示意图

通过这种方式进行局部特征对齐,可以很好地提升牌匾在截断、遮挡、检测框不准等情况下的检索效果。

文本特征

POI牌匾对文本强依赖,可能存在仅牌匾名称文本发生变化的场景。我们设计的全局特征分支以及局部特征分支,虽然可一定程度上学习到文本特征,但是文本信息在整体信息中占比较小,并且监督信号仅为两张图是否相似,导致文本特征并没有被很好的学习到。因此,我们利用已有的文本OCR识别结果,并引入BERT对OCR结果进行编码得到文本特征,该特征作为辅助特征分支和视觉特征进行融合,融合后的特征用于最终的牌匾检索度量学习。值得注意的是,在对牌匾提取OCR结果时,为了减少单帧内识别结果不准的影响,我们利用了一趟资料内同一牌匾的多帧OCR结果,并且将所得到的OCR结果进行拼接,使用BERT对OCR结果特征编码时,对来自不同帧的OCR结果之间插入符号做区分。

3 模型效果

在新的技术方案下,POI牌匾图像检索取得了非常好的效果,准确率和召回率都大于95%,大幅提升了线上指标,并且模型速度也有了巨大的提升。我们随机选择了一些匹配结果,如图10所示。

图10. 评测集中随机抽取的POI牌匾检索结果

我们在优化过程中,有一些非常难的Case也在逐渐被解决,如下图11所示:

图11. 评测集中难例展示,(a)(b)(c)是优化前的错误检索结果,(d)(e)(f)是优化后的检索结果

图(a)、(b)、(c)展示的是优化前的Bad case(左图为query图像,右图为Rank1检索结果),从Bad case中我们不难发现,牌匾检索对细粒度特征提取要求非常高,因为这些case普遍特点是具备整体相似性,但是局部特征有区别。这些Bad case就是我们设计的多模态检索模型的初衷,并且也在优化过程逐渐得以解决,如图(d)、(e)、(f)所示。我们提出的多模态检索模型通过对全局特征优化以及引入局部特征对齐,使得模型更多关注到牌匾上更有区分性的局部特征,如文字信息,文字字体、板式,牌匾纹理等,因此我们的模型对于外观相似的不同牌匾具有更好的区分能力,如图(a)和图(d)效果对比。此外,由于不同视角牌匾存在遮挡、拍摄时的光照强度不同以及不同相机色彩差异大等因素,部分牌匾只利用视觉特征检索非常困难。因此,我们通过辅助特征分支加入了OCR信息,进一步增强了特征的鲁棒性,使得牌匾检索可以综合考虑牌匾的视觉信息和牌匾中的文本信息进行检索,如图(b)和图(e)效果对比。

三 未来发展和挑战

图像检索是在高德地图数据自动化生产中的一次尝试,取得了不错的效果,并且已在实际业务中使用。但是模型并不是完美的,仍会存在Corner case,为了解决这些case,我们未来将会从半监督学习/主动学习自动补充数据,以及引入Transformer[9,10]优化特征提取和融合两方面进行探讨。

1 数据:基于半监督学习/主动学习的数据挖掘

数据是非常重要的,因为模型很难做到完美,总是会存在Corner case,而解决Corner case的一个非常高效的手段就是针对性补充数据。补充数据的关键是如何挖掘Corner case以及如何自动标注,该方向也是目前学术的研究热点,即半监督学习以及主动学习。半监督学习利用有标签数据训练出的模型来对海量无标签数据产生伪标签,进一步标签数据和伪标签数据混合后再优化模型。主动学习是利用有标签数据训练出的模型对海量无标签数据进行数据挖掘,并人工标注挖掘出的有价值数据。两者区别在于是否需要部分人工标注,半监督学习是完全由模型自身产生标签,但是可能导致模型效果存在上限,而主动学习则可以一定程度可提高该上限,因此未来需要深入研究两者的结合,从而更好的补充训练数据,解决Corner case。

2 模型:基于Transformer的特征提取与融合

Transformer是目前学术的研究热点,大量的工作已证明其在分类、检测、分割、跟踪以及行人重识别等任务上的有效性。和CNN相比,Transformer具有全局感受野以及高阶相关性建模的特点,使其在特征提取上有着更好的表征能力。此外,Transformer的输入较为灵活,可以方便地将其他模态信息进行编码,并和图像特征一起输入到模型中,因此其在多模特征融合上也有较大的优势。综上来看,Transformer可以通过对图像Patch的相关性建模来解决POI牌匾在遮挡/截断场景下的匹配效果,并且可以通过对文本特征编码来实现多模特征的融合。

本文参考文献

[1] Zhang X, Luo H, Fan X, et al. Alignedreid: Surpassing human-level performance in person re-identification[J]. arXiv preprint arXiv:1711.08184, 2017.

[2]Kim, Yonghyun, and Wonpyo Park. “Multi-level Distance Regularization for Deep Metric Learning.” arXiv preprint arXiv:2102.04223,2021.

[3]Radenović F, Tolias G, Chum O. Fine-tuning CNN image retrieval with no human annotation[J]. IEEE transactions on pattern analysis and machine intelligence, 2018, 41(7): 1655-1668.

[4]Li X, Hu X, Yang J. Spatial group-wise enhance: Improving semantic feature learning in convolutional networks[J]. arXiv preprint arXiv:1905.09646, 2019.

原文链接

本文为阿里云原创内容,未经允许不得转载。

本文转载自: 掘金

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

『超级架构师』服务限流的思路与手段

发表于 2021-11-10

「这是我参与11月更文挑战的第9天,活动详情查看:2021最后一次更文挑战」。PS:已经更文多少天,N就写几。一定要写对文案,否则文章不计入在内。

前言

本文已收录到 Github-java3c ,里面有我的系列文章,欢迎大家Star。

Hello 大家好,我是l拉不拉米,在我的『超级架构师』专栏前两篇文章《『超级架构师』图码实战限流算法(一)》、《『超级架构师』图码实战限流算法(二)》中,以伪代码实例讲解限流的几种主流算法,这一篇主要通过理论 + 图解 + 代码的形式讲解系统限流的几种手段思路。

容器限流

Tomcat 限流

tomcat限流的方式就是通过tomcat的配置文件,设置最大线程数,当请求的并发大于最大线程数时,请求就会排队执行,相当于实现了限流的目的。

在tomcat目录文件conf/server.xml下配置:

1
2
3
4
xml复制代码<Connector port="8080" protocol="HTTP/1.1"
connectionTimeout="20000"
maxThreads="150"
redirectPort="8443" />

这里的maxThreads即是最大并发线程数。

Nginx 限流

nginx的限流与tomcat的限流类似,也是通过配置文件实现。

主要是两种方式:

  • 控制速率
  • 控制并发连接数

控制速率

在 nginx.conf 配置文件的 http 模块中添加限流配置:

格式:limit_req_zone key zone rate

  • key :定义限流对象,binary_remote_addr 是一种key,表示基于 remote_addr(客户端IP) 来做限流,binary_ 的目的是压缩内存占用量。
  • zone:定义共享内存区来存储访问信息, myRateLimit:10m 表示一个大小为10M,名字为myRateLimit的内存区域。1M能存储16000 IP地址的访问信息,10M 可以存储16W IP地址访问信息。
  • rate: 用于设置最大访问速率,rate=10r/s 表示每秒最多处理10个请求。Nginx 实际上以毫秒为粒度来跟踪请求信息,因此 10r/s 实际上是限制:每100毫秒处理一 个请求。这意味着,自上一个请求处理完后,若后续100毫秒内又有请求到达,将拒绝处理该请求。
1
2
3
xml复制代码http {
limit_req_zone $binary_remote_addr zone=myRateLimit:10m rate=10r/s;
}

配置 server,使用 limit_req 指令应用限流。

1
2
3
4
5
6
xml复制代码server {
location / {
limit_req zone=myRateLimit;
proxy_pass http://my_upstream;
}
}

控制并发连接数

利用 limit_conn_zone 和 limit_conn 两个指令即可。

Nginx 官方例子:

1
2
3
4
5
6
7
8
xml复制代码limit_conn_zone $binary_remote_addr zone=perip:10m;
limit_conn_zone $server_name zone=perserver:10m;

server {
...
limit_conn perip 10;
limit_conn perserver 100;
}

limit_conn perip 10 作用的 key 是 $binary_remote_addr,表示限制单个IP同时最多能持有10个连接。

limit_conn perserver 100 作用的 key 是 $server_name,表示虚拟主机(server) 同时能处理并发连接的总数。

服务端限流

限流算法

服务端限流常用的限流算法有4种:

  • 固定窗口算法
  • 滑动窗口算法
  • 漏桶算法
  • 令牌桶算法

在前两篇文章《『超级架构师』图码实战限流算法(一)》、《『超级架构师』图码实战限流算法(二)》中有图码详解。

具体的实现

Google Guava 类库的 RateLimiter

基于令牌桶算法实现,适用于单体架构。

1
2
3
4
5
6
7
8
java复制代码// 每秒2个的速率提交任务
final RateLimiter rateLimiter = RateLimiter.create(2.0);
void submitTasks(List tasks, Executor executor) {
for (Runnable task : tasks) {
rateLimiter.acquire(); // may wait
executor.execute(task);
}
}
redis + Lua

redis提供分布式K-V存储,lua脚本保证原子性。

Lua脚本大致逻辑如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
lua复制代码-- 获取调用脚本时传入的第一个key值(用作限流的 key)
local key = KEYS[1]
-- 获取调用脚本时传入的第一个参数值(限流大小)
local limit = tonumber(ARGV[1])

-- 获取当前流量大小
local curentLimit = tonumber(redis.call('get', key) or "0")

-- 是否超出限流
if curentLimit + 1 > limit then
-- 返回(拒绝)
return 0
else
-- 没有超出 value + 1
redis.call("INCRBY", key, 1)
-- 设置过期时间
redis.call("EXPIRE", key, 2)
-- 返回(放行)
return 1
end
网关层限流:

比如Zuul、Spring Cloud Gateway等,而像spring cloud - gateway网关限流底层实现原理,就是基于Redis + Lua,通过内置Lua限流脚本的方式。

image

阿里巴巴sentinel

启动sentinel务端,在sentinel的控制台针对你的接口资源配置相应的规则即可,非常简单。

image

服务熔断

系统在设计之初就把熔断措施考虑进去。当系统出现问题时,如果短时间内无法修复,系统要自动做出判断,开启熔断开关,拒绝流量访问,避免大流量对后端的过载请求。

系统也应该能够动态监测后端程序的修复情况,当程序已恢复稳定时,可以关闭熔断开关,恢复正常服务。常见的熔断组件有Hystrix以及阿里的Sentinel,两种互有优缺点,可以根据业务的实际情况进行选择。

sentinel

服务降级

将系统的所有功能服务进行一个分级,当系统出现问题需要紧急限流时,可将不是那么重要的功能进行降级处理,停止服务,这样可以释放出更多的资源供给核心功能的去用。

例如在电商平台中,如果突发流量激增,可临时将商品评论、积分等非核心功能进行降级,停止这些服务,释放出机器和CPU等资源来保障用户正常下单,而这些降级的功能服务可以等整个系统恢复正常后,再来启动,进行补单/补偿处理。除了功能降级以外,还可以采用不直接操作数据库,而全部读缓存、写缓存的方式作为临时降级方案。

延迟处理

这个模式需要在系统的前端设置一个流量缓冲池,将所有的请求全部缓冲进这个池子,不立即处理。然后后端真正的业务处理程序从这个池子中取出请求依次处理,常见的可以用队列模式来实现。这就相当于用异步的方式去减少了后端的处理压力,但是当流量较大时,后端的处理能力有限,缓冲池里的请求可能处理不及时,会有一定程度延迟。漏桶算法以及令牌桶算法就是这个思路。

特权处理

这个模式需要将用户进行分类,通过预设的分类,让系统优先处理需要高保障的用户群体,其它用户群的请求就会延迟处理或者直接不处理。

缓存、降级、限流的区别

缓存

缓存,是用来增加系统吞吐量,提升访问速度提供高并发。

降级

降级,是在系统某些服务组件不可用的时候、流量暴增、资源耗尽等情况下,暂时屏蔽掉出问题的服务,继续提供降级服务,给用户尽可能的友好提示,返回兜底数据,不会影响整体业务流程,待问题解决再重新上线服务。

限流

限流,是指在使用缓存和降级无效的场景。比如当达到阈值后限制接口调用频率,访问次数,库存个数等,在出现服务不可用之前,提前把服务降级。只服务好一部分用户。

最后

创作不易,感谢您的点赞!!🙏🙏

本文转载自: 掘金

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

《三战Leetcode》寻找有序数组的中位数

发表于 2021-11-10

「这是我参与11月更文挑战的第10天,活动详情查看:2021最后一次更文挑战」。


  • 🤟 博主介绍: 本文由【IT学习日记】原创、需要转载请联系博主
  • 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦

一、前言

  大家好,又到了三分钟算法修行时间,之前挑选的算法都是中低难度的,这次找个难度较高的,看看会遇到啥问题。至于难到啥程度,来看看Leetcode下解题的网友评论。

  本篇文章大纲:

二、 题目

  名称:寻找两个正序数组的中位数

  题意:给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数 。

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
java复制代码
示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

示例 4:

输入:nums1 = [], nums2 = [1]
输出:1.00000

示例 5:

输入:nums1 = [2], nums2 = []
输出:2.00000

提示:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

  进阶要求:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗(注意这个要求,这个要求才是解决这道题目的关键)

三、题目解析

  这道题目很简单,就是从两个有序的数组中查询到它们的中文数,难点在于如何设计一个事件复杂度为O(log(m+n))的算法。 下面抽取题目关键信息来解读题目:

  中位数:指顺序排序一组数据中居于中间位置的数值。 它分为两种情况,一是当数组长度为奇数时,正中间的数为中位数,二是当数组长度为偶数时,通常是将最中间的两个数相加取平均值作 为中位数,具体看下图:


解法一:暴力破解


  相信很多小伙伴一看到题目,脑海中就已经有了这种解题的思路:将两个数组合并起来 ,然后重新排序,再根据奇偶情况获取合并后的新数组的中位数。

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
java复制代码
/**
*
* 方式一:时间复杂度和空间复杂度都为O(m+n)
*
* @param nums1
* @param nums2
* @return
*/
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int numLength = nums1.length + nums2.length;
// 定义合并后的集合
List<Integer> list = new ArrayList();
// 使用for循环将元素添加到新的数组(方式一)
//for (int i : nums1) {
// list.add(i);
//}
//for (int i : nums2) {
// list.add(i);
//}
// 使用lambda表达式将数组合并到集合中(方式二)
list.addAll(Arrays.stream(nums1).boxed().collect(Collectors.toList()));
list.addAll(Arrays.stream(nums2).boxed().collect(Collectors.toList()));
// 使用结合工具类的排序方式对存放了两个数组的集合进行排序(sort底层的排序方式是:)
Collections.sort(list);
int middle = list.size() / 2;
// 两数组元素之和为偶数
if (numLength % 2 == 0) {
int leftMiddle = middle - 1;
double middleValue = (Double.valueOf(list.get(leftMiddle)) + Double.valueOf(list.get(middle))) / 2;
return middleValue;
} else {
return Double.valueOf(list.get(middle));
}
}

2、时间复杂度推导:

  通过上面的代码,我们会发现随着输入规模的增大(即数组元素增多),程序需要花费执行时间处理的语句主要是在将[两个数组元素放入新的集合]以及对这个[新的集合进行排序]的过程。

  将两个数组元素合并到一个数组执行函数可以使用函数:f(x)=m + n(m,n分别为两个数组的长度)表示,根据大O记法的推导可以得到时间复杂度为:O(m + n)

  对新数组排序的Collections.sort()方法的最坏情况下时间复杂度为:O(n * log(n))。

 因此,使用暴力破解的方式总的时间复杂度为:O(m+n) + O(n * log(n)),这个复杂度如果当数组长度变长后,效率是会比较低的,不推荐使用。

3、空间复杂度推导:

  因为每次合并都需要申请一个新的集合来存放两个数组的元素,所以需要申请空间的函数可以表示为:f(x) = m + n,根据大O记法标准推导,可以得到空间复杂度为:O(m+ n)。

4、执行结果:

解法二、双指针法

  暴力破解法,当输入规模大的时候,效率极低,且没有满足题目的进阶要求,能否对时间复杂度和空间复杂度进一步优化呢?

  答案是可以的。我们的目的是查询两个有序数组的中位数,在暴力破解中我们是通过申请新的数组集合来存放两个数组的值然后进行排序,最终得出结果,这一步是否真的需要呢?

  答案是不需要,我们目的是查询中位数,中位数无非根据数组长度有奇偶两种情况,我们可以使用两个指针来指向对应的元素即可,这样我们就可以省略[申请新的数组空间]和对[新数组重新排序]的两个步骤,从而优化了时间复杂度和空间复杂度,下面来看看具体的代码。

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
ini复制代码    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
int num1Length = nums1.length;
int num2Length = nums2.length;
int sumLength = num1Length + num2Length;
// 第一个中位数指针
int preItem = 0;
// 第二个中位数指针(如果两个数组总长度为奇数,则直接返回该值即可)
int curItem = 0;
// 遍历的数组1的元素下标
int num1Index = 0;
// 遍历的数组2的元素下标
int num2Index = 0;
// 需要遍历的次数(查询中位数,并不需要将两个数组元素都遍历完)
int foreachTime = sumLength / 2;
for (int i = 0; i <= foreachTime; i++) {
// 保证preItem总是在curItem前面
preItem = curItem;
// num2Index >= num2Length需要放在nums1[num1Index] < nums2[num2Index]前面,否则会出现下标越界
// nums1[num1Index] < nums2[num2Index]的目的就是为了按照模拟从小到大的顺序循环两个数组的元素
if (num1Index < num1Length && (num2Index >= num2Length || nums1[num1Index] < nums2[num2Index])) {
curItem = nums1[num1Index++];
} else {
curItem = nums2[num2Index++];
}
}
// 如果是偶数,则取中间两个元素的平均值
if (sumLength % 2 == 0) {
return Double.valueOf(preItem + curItem) / 2;
}
return curItem;
}

1、时间复杂度推导

  根据上面代码可知,随着输入规模的增大(即数组元素增多),程序需要执行花费时间处理的语句主要是在for循环中(for循环又只跟两个数组的长度相关),可以用函数表示为:f(n) = m + n,根据大O记法规则推断,该方式的时间复杂度为:O(m + n)。

2、空间复杂度推导

  根据上面解题代码可知,使用双指针法只需要申请两个指针和一些存储长度、下标的变量对应的空间,并且这些空间并不会随着问题规模的增大(即数组元素的增多)而变化,因此该算法的空间复杂度为:O(1)

3、执行结果

4、小结

  通过定义双指针模拟指向中位数,我们去除了不必要的空间申请和重新排序,进一步优化了算法的时间复杂度和空间复杂度,在平常的业务中,如果遇到相似的业务要求,可以优先考虑维护指针的方式来避免不必要的空间申请。

解法三、二分查找法

  通过双指针,我们将算法的时间复杂度降低到了O(m +n),但是依然没有达到题目中O(log(m + n))的要求。如何满足这个要求呢,现在好像没有一个比较清晰的思路,这时候不妨再反过来思考下题目的要求。

  题目中要求时间复杂度需要达到O(log(m + n)),回想下我们之前接触到的算法中,有没有与log(对数)相关的东西,没错,比较常见的就是二分法,每次循环都排除n/2的元素,最终得出结果,下面来看看这个题目如何提取成二分法的形式。

  题目最终结果是要求中位数,中位数又分为奇偶情况,那我们就可以将抽象求中位数成求有序数组中的第k小数,其中k就是对应的中位数(即 (m + n) /2,或者(m+n)/2 +1),这样我们就可以对k进行二分查找法找到符合条件的数值。

1、求解第k小数的思路

  假设存在数组A和数组B,它们的中位数为k,此时要求k的值,则可以通过二分法,即每轮都对A[k/2]和B[k/2]进行比较(注意:这里的k是表示第几个,如果转换成数组对应的元素的话需要减去1),如果A[k/2]>=B[k/2],则B[k/2]和B[k/2]之前的元素就可排除掉,原因如下:

  当A[k/2]>=B[k/2]时,在A数组中比A[k/2]元素小的值有k/2-1个,在数组B中比B[k/2]小的有k-1个,即使A数组中A[k/2]之前的所有元素都比B[k/2]元素小,那总的个数也是等于:k/2-1 + k/2-1 = k-2个,所以B[k/2]最多只能是k-1小的数,而不是第k小数,所以B[k/2]之前的数组更不可能是第k小数,故B[k/2]及之前的元素可以排除掉。反之亦然。

 因为排除掉的元素一定位于数组的前面(数组是有序的),所以每轮之后k的值也需要减去排除掉的元素的个数,然后再进行下一轮的第k小数查询,步骤依次类推。

  通过上面的思路整理,我们可以看出此处使用了递归的思想,递归的出口则是当某个数组长度为了0时(此时中位数就是可以取不为0的数组中的值即可)或者是k=1(即求第1个小数,此时中位数则取两个数组中起始下标对应值最小的元素)时,需要注意的是:因为k/2的值可能大于数组的长度,所以每次比较 min(k/2,len(数组) 对应的数字,把小的那个对应的数组的数字排除,将两个新数组进入递归。

2、图解步骤讲解

  假设存在数组A元素有[1,2,3]和数组B元素有[1,2,3,4,5,6],因为k=(A数组长度 + B数组长度 + 1)/2 = 5,则根据第k小数的方式查询中位数的步骤如下:

  第一轮循环:

  第二轮循环:

  第三轮循环:

  第四轮循环:

3、代码讲解

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
java复制代码 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
//奇数时k值,除法是向下取整,因此需要+1
int left = (n + m + 1) / 2;
// 偶数时取两个中间值的平均值做中位数
int right = (n + m + 2) / 2;
//将偶数和奇数的情况区分
if((n + m) % 2 == 0){
return (getMedian(nums1, 0, n - 1, nums2, 0, m - 1, left) + getMedian(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
} else {
return getMedian(nums1, 0, n - 1, nums2, 0, m - 1, left);
}
}

public static double getMedian(int[] num1, int num1StartIndex, int num1EndIndex, int[] num2, int num2StartIndex, int num2EndIndex, int k) {
// 获取需要遍历数组的长度(不能直接用num1.length获取,这样会导致数组的长度一致不会变动)
int num1Length = num1EndIndex - num1StartIndex + 1;
int num2Length = num2EndIndex - num2StartIndex + 1;
// 总长度
int totalLength = num1Length + num2Length;
// 如果num1长度大于num2,则进行交换位置,保证num1数组为包含元素最少的数组
if (num1Length > num2Length) {
return getMedian(num2, num2StartIndex, num2EndIndex, num1, num1StartIndex, num1EndIndex, k);
}
// 如果最短的数组长度为0,则中位数获取剩下还有元素的数组
if (num1Length == 0) {
return num2[num2StartIndex + k - 1];
}
// 如果k为1(表示查询第一小的数值),表示数组第一个元素为中位数,则取两个数组中位数中最小的值
if (k == 1) {
return Math.min(num1[num1StartIndex], num2[num2StartIndex]);
}
// 计算两个数组起始下标的位置
// 疑问:为什么比较的两个值需要添加num1StartIndex和num2StartIndex,原因是比较的是k/2的元素,但是每轮递归后
// k需要减去上一轮排除的元素的个数
// 减去1是因为前面计算的都是长度,但是offset对应的是数组下标
// Math.min是为了防止数组长度比k/2长度小而导致数组越界的问题,使用它表示如果数组长度小于k/2时,则直接将数组坐标指到最后一个
int num1CompareItem = num1StartIndex + Math.min(num1Length, k / 2) - 1;
int num2CompareItem = num2StartIndex + Math.min(num2Length, k / 2) - 1;
// 判断两个数组中位数的值
if (num1[num1CompareItem] > num2[num2CompareItem]) {
return getMedian(num1, num1StartIndex, num1EndIndex, num2, num2CompareItem + 1, num2EndIndex, k - (num2CompareItem - num2StartIndex+ 1));
} else {
return getMedian(num1, num1CompareItem + 1, num1EndIndex, num2, num2StartIndex, num2EndIndex, k - (num1CompareItem -num1StartIndex + 1));
}
}

4、执行结果

5、时间复杂度推导

  根据上面的图解和代码,可以看到每循环一次,就可以排除对应数组的 k/2个元素。即如有n个元素,循环次数的就是呈现下面的规律:n,n/2,n/4,….n/2^k^,1(接下来操作元素的剩余个数),用函数表示则为:f(k) => n /2^k^ = 1 ,即f(k) = log2^n^,根据大O记法,可以推断出时间复杂度为:O(log(n)),其中n表示的是元素个数即等于两个元素数组之和,故写成:O(log(m + n))。

6、空间复杂度推导

  上面的解法中我们使用到了尾递归的方式,不需要重复推栈,所以需要申请的空间的只是一些临时的变量,输入规模的大小并不会影响它们,因此空间复杂度为O(1)。

 尾递归和递归之间的联系和区别会在下一篇文章详细讲解,敬请期待!

7、小结

  使用二分查询解决这个算法难点在于思想的归纳和边界值的确定,这个能力并不是一蹴而就的,是需要积累,因此,如果第一遍看完文章不能完全理解是比较正常的,不要急于否定自己,多看几次,梳理出自己疑惑的点,再去进行实践,这样慢慢的就可以将它们转换成自己的东西。

算法思想在实际的应用

  ·1、暴力破解:这个思想最简单,也是在平常的业务中是被应用到最多的,但是并不是一个好的选择,如果使用暴力破解,一定要考虑问题的输入规模拓张的问题,否则效率将极低。

  ·2、二分查找法:主要运用在快速定位数组元素,提高效率。

写在最后

  纸上得来终觉浅,绝知此事要躬行。看完文章理解了不代表你真的掌握 了,只要亲自动手编写出来,才算你转换成自己的东西了,赶紧打开开发工具,行动起来吧,实践中如遇到不懂的问题可以联系我!

  如果文章如您有帮助,欢迎给我点赞、关注、收藏(一键三连)。

本文转载自: 掘金

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

基于 Istio 的全链路灰度方案探索和实践 背景 场景说明

发表于 2021-11-10

简介: 本文介绍的基于“流量打标”和“按标路由” 能力是一个通用方案,基于此可以较好地解决测试环境治理、线上全链路灰度发布等相关问题,基于服务网格技术做到与开发语言无关。同时,该方案适应于不同的7层协议,当前已支持 HTTP/gRpc 和 Dubbo 协议。

作者|曾宇星(宇曾)

背景

微服务软件架构下,业务新功能上线前搭建完整的一套测试系统进行验证是相当费人费时的事,随着所拆分出微服务数量的不断增大其难度也愈大。这一整套测试系统所需付出的机器成本往往也不低,为了保证应用新版本上线前的功能正确性验证效率,这套系统还必须一直单独维护好。当业务变得庞大且复杂时,往往还得准备多套,这是整个行业共同面临且难解的成本和效率挑战。如果能在同一套生产系统中完成新版本上线前的功能验证的话,所节约的人力和财力是相当可观的。

除了开发阶段的功能验证,生产环境中引入灰度发布才能更好地控制新版本软件上线的风险和爆炸半径。灰度发布是将具有一定特征或者比例的生产流量分配到需要被验证的服务版本中,以观察新版本上线后的运行状态是否符合预期。

阿里云 ASM Pro基于 Service Mesh 所构建的全链路灰度方案,能很好帮助解决以上两个场景的问题。

ASM Pro 产品功能架构图:

核心能力使用的就是上图扩展的流量打标和按标路由以及流量 Fallback 的能力,下面详细介绍说明。

场景说明

全链路灰度发布的常见场景如下:

以 Bookinfo 为例,入口流量会带上期望的 tag 分组,sidecar 通过获取请求上下文(Header 或 Context) 中的期望 tag,将流量路由分发到对应 tag 分组,若对应 tag 分组不存在,默认会 fallback 路由到 base 分组,具体 fallback 策略可配置。接下来详细描述具体的实现细节。

入口流量的 tag 标签,一般是在网关层面基于类似 tag 插件的方式,将请求流量进行打标。 比如将 userid 处于一定范围的打上代表灰度的 tag,考虑到实际环境网关的选择和实现的多样性,网关这块实现不在本文讨论的范围内。

下面我们着重讨论基于 ASM Pro 如何做到全链路流量打标和实现全链路灰度。

实现原理

Inbound 是指请求发到 App 的入口流量,Outbond 是指 App 向外发起请求的出口流量。

上图是一个业务应用在开启 mesh 后典型流量路径:业务 App 接收到一个外部请求 p1,接着调用背后所依赖的另一个服务的接口。此时,请求的流量路径是 p1->p2->p3->p4,其中 p2 是 Sidecar 对 p1 的转发,p4 是 Sidecar 对 p3 的转发。为了实现全链路灰度,p3 和 p4 都需要获取到 p1 进来的流量标签,才能将请求路由到标签所对应的后端服务实例,且 p3 和 p4 也要带上同样的标签。关键在于,如何让标签的传递对于应用完全无感,从而实现全链路的标签透传,这是全链路灰度的关键技术。ASM Pro 的实现是基于分布式链路追踪技术(比如,OpenTracing、OpenTelemetry 等)中的 traceId 来实现这一功能。

在分布式链路追踪技术中,traceId 被用于唯一地标识一个完整的调用链,链路上的每一个应用所发出的扇出(fanout)调用,都会通过分布式链路追踪的 SDK 将源头的 traceId 给带上。ASM Pro 全链路灰度解决方案的实现正是建立在这一分布式应用架构所广泛采纳的实践之上的。

上图中,Sidecar 本来所看到的 inbound 和 outbound 流量是完全独立的,无法感知两者的对应关系,也不清楚一个 inbound 请求是否导致了多个 outbound 请求的发生。换句话说,图中 p1 和 p3 两个请求之间是否有对应关系 Sidecar 并不知情。

在 ASM Pro 全链路灰度解决方案中,通过 traceId 将 p1 和 p3 两个请求做关联,具体说来依赖了 Sidecar 中的 x-request-id 这个 trace header。Sidecar 内部维护了一张映射表,其中记录了 traceId 和标签的对应关系。当 Sidecar 收到 p1 请求时,将请求中的 traceId 和标签存储到这张表中。当收到 p3 请求时,从映射表中查询获得 traceId 所对应的标签并将这一标签加入到 p4 请求中,从而实现全链路的打标和按标路由。下图大致示例了这一实现原理。

换句话说,ASM Pro 的全链路灰度功能需要应用使用分布式链路追踪技术。如果想运用这一技术的应用没有使用分布式链路追踪技术的话不可避免地涉及到一定的改造工作。对于 Java 应用来说,仍可以考虑采用 Java Agent 以 AOP 的方式让业务无需改造地实现 traceId 在 inbound 和 outbound 之间透传。

实现流量打标

ASM Pro 中引入了全新的 TrafficLabel CRD 用于定义 Sidecar 所需透传的流量标签从哪里获取。下面所例举的 YAML 文件中,定义了流量标签来源和需要将标签存储 OpenTracing 中(具体是 x-trace 头)。其中流量标的名为 trafficLabel,取值依次从 getContext(x−request−id)到最后从本地环境的getContext(x-request-id) 到最后从本地环境的getContext(x−request−id)到最后从本地环境的(localLabel)中获取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
yaml复制代码apiVersion: istio.alibabacloud.com/v1beta1
kind: TrafficLabel
metadata:
name: default
spec:
rules:
- labels:
- name: trafficLabel
valueFrom:
- $getContext(x-request-id) //若使用aliyun arms,对应为x-b3-traceid
- $(localLabel)
attachTo:
- opentracing
# 表示生效的协议,空为都不生效,*为都生效
protocols: "*"

CR 定义包含两块,即标签的获取和存储。

  • 获取逻辑:先根据协议上下文或者头(Header 部分)中的定义的字段获取流量标签,如果没有,会根据 traceId 通过 Sidecar 本地记录的 map 获取, 该 map 表中保存了 traceId 对应流量标识的映射。若 map 表中找到对应映射,会将该流量打上对应的流量标,若获取不到,会将流量标取值为本地部署对应环境的 localLabel。localLabel 对应本地部署的关联 label,label 名为 ASM_TRAFFIC_TAG。

本地部署对应环境的标签名为”ASM_TRAFFIC_TAG”,实际部署可以结合 CI/CD 系统来关联。

  • 存储逻辑:attachTo 指定存储在协议上下文的对应字段,比如 HTTP 对应 Header 字段,Dubbo 对应 rpc context 部分,具体存储到哪一个字段中可配置。

有了TrafficLabel 的定义,我们知道如何将流量打标和传递标签,但光有这个还不足以做到全链路灰度,我们还需要一个可以基于 trafficLabel 流量标识来做路由的功能,也就是“按标路由”,以及路由 fallback 等逻辑,以便当路由的目的地不存在时,可以实现降级的功能。

按流量标签路由

这一功能的实现扩展了 Istio 的 VirtualService 和 DestinationRule。

在 DestinationRule 中定义 Subset

自定义分组 subset 对应的是 trafficLabel 的 value

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
yaml复制代码apiVersion: networking.istio.io/v1alpha3
kind: DestinationRule
metadata:
name: myapp
spec:
host: myapp/*
subsets:
- name: myproject # 项目环境
labels:
env: abc
- name: isolation # 隔离环境
labels:
env: xxx # 机器分组
- name: testing-trunk # 主干环境
labels:
env: yyy
- name: testing # 日常环境
labels:
env: zzz
---
apiVersion: networking.istio.io/v1alpha3
kind: ServiceEntry
metadata:
name: myapp
spec:
hosts:
- myapp/*
ports:
- number: 12200
name: http
protocol: HTTP
endpoints:
- address: 0.0.0.0
labels:
env: abc
- address: 1.1.1.1
labels:
env: xxx
- address: 2.2.2.2
labels:
env: zzz
- address: 3.3.3.3
labels:
env: yyy

Subset 支持两种指定形式:

  • labels 用于匹配应用中带特定标记的节点(endpoint);
  • 通过 ServiceEntry 用于指定属于特定 subset 的 IP 地址,注意这种方式与labels指定逻辑不同,它们可以不是从注册中心(K8s 或者其他)拿到的地址,直接通过配置的方式指定。适用于 Mock 环境,这个环境下的节点并没有向服务注册中心注册。

在 VirtualService 中基于 subset

1)全局默认配置

  • route 部分可以按顺序指定多个 destination,多个 destination 之间按照 weight 值的比例来分配流量。
  • 每个 destination 下可以指定 fallback 策略,case 标识在什么情况下执行 fallback,取值:noinstances(无服务资源)、noavailabled(有服务资源但是服务不可用),target 指定 fallback 的目标环境。如果不指定 fallback,则强制在该 destination 的环境下执行。
  • 按标路由逻辑,我们通过改造 VirtualService,让 subset 支持占位符 trafficLabel,该占位符trafficLabel, 该占位符 trafficLabel,该占位符trafficLabel 表示从请求流量标中获取目标环境, 对应 TrafficLabel CR 中的定义。

全局默认模式对应泳道,也就是单个环境内封闭,同时指定了环境级别的 fallback 策略。自定义分组 subset 对应的是 trafficLabel 的 value

配置样例如下:

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
yaml复制代码apiVersion: networking.istio.io/v1alpha3
kind: VirtualService
metadata:
name: default-route
spec:
hosts: # 对所有应用生效
- */*
http:
- name: default-route
route:
- destination:
subset: $trafficLabel
weight: 100
fallback:
case: noinstances
target: testing-trunk
- destination:
host: */*
subset: testing-trunk # 主干环境
weight: 0
fallback:
case: noavailabled
target: testing
- destination:
subset: testing # 日常环境
weight: 0
fallback:
case: noavailabled
target: mock
- destination:
host: */*
subset: mock # Mock中心
weight: 0

2)个人开发环境定制

  • 先打到日常环境,当日常环境没有服务资源时,再打到主干环境。

apiVersion: networking.istio.io/v1alpha3
kind: VirtualService
metadata:
name: projectx-route
spec:
hosts: # 只对myapp生效

+ myapp/\*
http:
+ name: dev-x-route
match:
trafficLabel:
    - exact: dev-x # dev环境: x
    route:
    - destination:
    host: myapp/\*
    subset: testing # 日常环境
    weight: 100
    fallback:
    case: noinstances
    target: testing-trunk
    - destination:
    host: myapp/\*
    subset: testing-trunk # 主干环境
    weight: 0

3) 支持权重配置

将打了主干环境标并且本机环境是 dev-x 的流量,80% 打到主干环境,20% 打到日常环境。当主干环境没有可用的服务资源时,流量打到日常。

sourceLabels 为本地 workload 对应的 label

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
yaml复制代码apiVersion: networking.istio.io/v1alpha3
kind: VirtualService
metadata:
name: dev-x-route
spec:
hosts: # 对哪些应用生效(不支持多应用配置)
- myapp/*
http:
- name: dev-x-route
match:
trafficLabel:
- exact: testing-trunk # 主干环境标
sourceLabels:
- exact: dev-x # 流量来自某个项目环境
route:
- destination:
host: myapp/*
subset: testing-trunk # 80%流量打向主干环境
weight: 80
fallback:
case: noavailabled
target: testing
- destination:
host: myapp/*
subset: testing # 20%流量打向日常环境
weight: 20

按(环境)标路由

该方案依赖业务部署应用时带上相关标识(例子中对应 label 为 ASM_TRAFFIC_TAG: xxx),常见为环境标识,标识可以理解是服务部署的相关元信息,这个依赖上游部署系统 CI/CD 系统的串联,大概示意图如下:

  • K8s 场景,通过业务部署时自动带上对应环境/分组 label 标识即可,也就是采用K8s 本身作为元数据管理中心。
  • 非 K8s 场景,可以通过微服务已集成的服务注册中心或者元数据配置管理服务(metadata server)来集成实现。

注:ASM Pro 自研开发了ServiceDiretory 组件(可以参看 ASM Pro 产品功能架构图),实现了多注册中心对接以及部署元信息的动态获取;

应用场景延伸

下面是典型的一个基于流量打标和按标路由实现的多套开发环境治理功能;每个开发者对应的 Dev X 环境只需部署有版本更新的服务即可;如果需要和其他开发者联调,可以通过配置 fallback 将服务请求 fallback 流转到对应开发环境即可。如下图的 Dev Y 环境的B -> Dev X 环境的 C。

同理,将 Dev X 环境等同于线上灰度版本环境也是可以的,对应可以解决线上环境的全链路灰度发布问题。

总结

本文介绍的基于“流量打标”和“按标路由” 能力是一个通用方案,基于此可以较好地解决测试环境治理、线上全链路灰度发布等相关问题,基于服务网格技术做到与开发语言无关。同时,该方案适应于不同的7层协议,当前已支持 HTTP/gRpc 和 Dubbo 协议。

对应全链路灰度,其他厂商也有一些方案,对比其他方案 ASM Pro 的解决方案的优点是:

  • 支持多语言、多协议。
  • 统一配置模板 TrafficLabel, 配置简单且灵活,支持多级别的配置(全局、namespace 、pod 级别)。
  • 支持路由 fallback 实现降级。

基于“流量打标” 和 “按标路由”能力还可以用于其他相关场景:

  • 大促前的性能压测。在线上压测的场景中,为了让压测数据和正式的线上数据实现隔离,常用的方法是对于消息队列,缓存,数据库使用影子的方式。这就需要流量打标的技术,通过 tag 区分请求是测试流量还是生产流量。当然,这需要 Sidecar 对中间件比如 Redis、RocketMQ 等进行支持。
  • 单元化路由。常见的单元化路由场景,可能是需要根据请求流量中的某些元信息比如 uid,然后通过配置得出对应所属的单元。在这个场景中,我们可以通过扩展 TrafficLabel 定义获取“单元标”的函数来给流量打上“单元标”,然后基于“单元标”将流量路由到对应的服务单元。

原文链接

本文为阿里云原创内容,未经允许不得转载。

本文转载自: 掘金

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

自定义注解实现方式全解析

发表于 2021-11-10

这是我参与11月更文挑战的第10天,活动详情查看:2021最后一次更文挑战

自定义注意在日常开发中经常使用,同时有很多实现自定义注解的方式,本文将带你一一了解。

1.源注解解析

@Retention

1
2
3
4
5
6
js复制代码    //注解只会存在源代码中,将会被编译器丢弃
SOURCE,
//注解将会保留到class文件阶段,但是在加载如vm的时候会被抛弃
CLASS,
//注解不单会被保留到class文件阶段,而且也会被vm加载进虚拟机的时候保留
RUNTIME

@Target

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
bash复制代码用于描述类、接口(包括注解类型) 或enum声明 Class, interface (including annotation type), or enum declaration 
TYPE,

用于描述域 Field declaration (includes enum constants)
FIELD,

用于描述方法 Method declaration
METHOD,

用于描述参数 Formal parameter declaration
PARAMETER,

用于描述构造器 Constructor declaration
CONSTRUCTOR,

用于描述局部变量 Local variable declaration
LOCAL_VARIABLE,

Annotation type declaration
ANNOTATION_TYPE,

用于描述包 Package declaration
PACKAGE,

用来标注类型参数 Type parameter declaration
TYPE_PARAMETER,

*能标注任何类型名称 Use of a type
TYPE_USE

2.依赖于@Conditional

原理是是否满足@Conditional中绑定类的条件,如果满足,就将使用注解的类注入进factory,不满足就不注入,只能在类中使用或者配合@bean使用。

1.添加注解类

首先定义一个注解类,定义的变量为参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
js复制代码@Conditional(CustomOnPropertyCondition.class)意思为CustomOnPropertyCondition类中返回为true才会使用注解

package com.airboot.bootdemo.config;
import org.springframework.context.annotation.Conditional;
import java.lang.annotation.*;

@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.TYPE, ElementType.METHOD})
@Documented
@Conditional(CustomPropertyCondition.class)
public @interface CustomProperty {

//参数
String name() default "";
/**
* havingValue数组,支持or匹配
*/

//参数
String[] havingValue() default {};

}

2.CustomOnPropertyCondition类

实现condition接口,以下是实现接口后的代码,然后在其中填补。

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
js复制代码public class CustomPropertyCondition implements Condition {
@Override
public boolean matches(ConditionContext conditionContext, AnnotatedTypeMetadata annotatedTypeMetadata) {
return false;
}
}

import org.springframework.context.annotation.Condition;
import org.springframework.context.annotation.ConditionContext;
import org.springframework.core.type.AnnotatedTypeMetadata;
import org.springframework.web.bind.annotation.RequestMapping;

import java.util.Map;


public class CustomPropertyCondition implements Condition {
@Override
public boolean matches(ConditionContext conditionContext, AnnotatedTypeMetadata annotatedTypeMetadata) {
//获取注解上的参数和配置值
Map<String, Object> annotationAttributes = annotatedTypeMetadata.getAnnotationAttributes(RequestMapping.class.getName());
//获取具体的参数值
String propertyName = (String) annotationAttributes.get("name");
String[] values = (String[]) annotationAttributes.get("havingValue");
if (0 == values.length) {
return false;
}
//从application.properties中获取配置
String propertyValue = conditionContext.getEnvironment().getProperty(propertyName);
// 有一个匹配上就ok
for (String havingValue : values) {
if (propertyValue.equalsIgnoreCase(havingValue)) {
return true;
}
}
return false;
}
}
1
2
3
js复制代码Map<String, Object> annotationAttributes = annotatedTypeMetadata.getAnnotationAttributes(RequestMapping.class.getName()); 获取类中注解上的参数

String propertyValue = conditionContext.getEnvironment().getProperty(propertyName);获取application.properties上的配置。

3.使用注解

1
2
3
4
5
6
7
8
js复制代码@RequestMapping(value ="/Demo")
@Controller
@ResponseBody
@Api("demo测试类")
@CustomProperty(name = "condition",havingValue = {"2"})
public class DemoController {

}

注解会在在spring boot启动时加载。

3.使用HandlerMethodArgumentResolver

注意该方法只能接受get请求。

1.添加注解类

1
2
3
4
5
6
7
8
9
10
11
12
13
js复制代码package com.airboot.bootdemo.config;

import java.lang.annotation.*;


@Target({ElementType.PARAMETER, ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface UserCheck {

//当前用户在request中的名字
String value() default "userid";
}

2.定义类HandlerMethodArgumentResolver

其中resolveArgument中返回的是controllor的参数,也就是这个方法里面可以组装入参 。UserCheckMethodArgumentResolver 为拦截注解后的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
js复制代码import org.springframework.core.MethodParameter;
import org.springframework.web.bind.support.WebDataBinderFactory;
import org.springframework.web.context.request.NativeWebRequest;
import org.springframework.web.method.support.HandlerMethodArgumentResolver;
import org.springframework.web.method.support.ModelAndViewContainer;

public class UserCheckMethodArgumentResolver implements HandlerMethodArgumentResolver {
@Override
public boolean supportsParameter(MethodParameter methodParameter) {
return false;
}

@Override
public Object resolveArgument(MethodParameter methodParameter, ModelAndViewContainer modelAndViewContainer, NativeWebRequest nativeWebRequest, WebDataBinderFactory webDataBinderFactory) throws Exception {
return null;
}
}
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
js复制代码import com.airboot.bootdemo.entity.DemoVO;
import org.springframework.core.MethodParameter;
import org.springframework.web.bind.support.WebDataBinderFactory;
import org.springframework.web.context.request.NativeWebRequest;
import org.springframework.web.method.support.HandlerMethodArgumentResolver;
import org.springframework.web.method.support.ModelAndViewContainer;

public class UserCheckMethodArgumentResolver implements HandlerMethodArgumentResolver {
@Override
public boolean supportsParameter(MethodParameter parameter) {
if (parameter.getParameterType().isAssignableFrom(DemoVO.class) && parameter.hasParameterAnnotation(UserCheck.class)) {
return true;
}
return false;
}

@Override
public Object resolveArgument(MethodParameter parameter, ModelAndViewContainer mavContainer, NativeWebRequest webRequest, WebDataBinderFactory binderFactory) throws Exception {
UserCheck currentUserAnnotation = parameter.getParameterAnnotation(UserCheck.class);
//获取head中的
String userId = webRequest.getHeader("userId");
//组装入参 return后的参数 类型需要和controllor中的相同
DemoVO demoVO = new DemoVO();
demoVO.setId(Long.valueOf(1));
return demoVO;
}
}

3.使用注解

1
2
3
4
js复制代码    @GetMapping(value = "/selectDemoByVo")
public List<DemoVO> selectDemoByVo(@RequestBody @UserCheck DemoVO demoVO) {
return demoService.selectDemoVO(demoVO);
}

4.基于aop

该方式在日常最常用。主要使用了AOP的功能。

1.AOP的名词介绍

1
2
3
4
5
6
7
8
9
10
bash复制代码1.JoinPoint  
* java.lang.Object[] getArgs():获取连接点方法运行时的入参列表;
* Signature getSignature() :获取连接点的方法签名对象;
* java.lang.Object getTarget() :获取连接点所在的目标对象;
* java.lang.Object getThis() :获取代理对象本身;

2.ProceedingJoinPoint
* ProceedingJoinPoint继承JoinPoint子接口,它新增了两个用于执行连接点方法的方法:
* java.lang.Object proceed() throws java.lang.Throwable:通过反射执行目标对象的连接点处的方法;
* java.lang.Object proceed(java.lang.Object[] args) throws java.lang.Throwable:通过反射执行目标对象连接点处的方法,不过使用新的入参替换原来的入参。

2.添加注解类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
js复制代码import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Target({ ElementType.METHOD })
@Retention(RetentionPolicy.RUNTIME)
public @interface TestAnnotation {

int p0() default 0;
String p1() default "";
Class<?> clazz();

}

3.切面配置

其中切点要切到注解类的路径。

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
js复制代码import org.aspectj.lang.ProceedingJoinPoint;
import org.aspectj.lang.annotation.*;
import org.springframework.stereotype.Component;
import lombok.extern.slf4j.Slf4j;

@Slf4j
@Aspect
@Component
public class TestAspect {

// 切入点签名
@Pointcut("@annotation(com.airboot.bootdemo.config.TestAnnotation)")
private void cut() {
}

// 前置通知
@Before("cut()")
public void BeforeCall() {
log.info("====前置通知start");

log.info("====前置通知end");
}

// 环绕通知
@Around(value = "cut()")
public Object AroundCall(ProceedingJoinPoint joinPoint) throws Throwable {
log.info("====环绕通知start");

// 注解所切的方法所在类的全类名
String typeName = joinPoint.getTarget().getClass().getName();
log.info("目标对象:[{}]", typeName);

// 注解所切的方法名
String methodName = joinPoint.getSignature().getName();
log.info("所切方法名:[{}]", methodName);

StringBuilder sb = new StringBuilder();
// 获取参数
Object[] arguments = joinPoint.getArgs();
for (Object argument : arguments) {
sb.append(argument.toString());
}
log.info("所切方法入参:[{}]", sb.toString());

// 统计方法执行时间
long start = System.currentTimeMillis();

//执行目标方法,并获得对应方法的返回值
Object result = joinPoint.proceed();
log.info("返回结果:[{}]", result);

long end = System.currentTimeMillis();
log.info("====执行方法共用时:[{}]", (end - start));

log.info("====环绕通知之结束");
return result;
}

// 后置通知
@After("cut()")
public void AfterCall() {
log.info("====后置通知start");

log.info("====后置通知end");
}

// 最终通知
@AfterReturning("cut()")
public void AfterReturningCall() {
log.info("====最终通知start");

log.info("====最终通知end");
}

// 异常通知
@AfterThrowing(value = "cut()", throwing = "ex")
public void afterThrowing(Throwable ex) {
throw new RuntimeException(ex);
}

}

4.使用注解

1
2
3
4
5
js复制代码    @RequestMapping(value = "/selectDemoByVo")
@TestAnnotation(p0 = 123, p1 = "qaws",clazz = DemoVO.class)
public List<DemoVO> selectDemoByVo(@RequestBody DemoVO demoVO) {
return demoService.selectDemoVO(demoVO);
}

5.拦截器

1.添加注解类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bash复制代码import java.lang.annotation.*;

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface InterceptorAnnotation {


String[] value() default {};

String[] authorities() default {};

String[] roles() default {};
}

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
js复制代码import org.springframework.web.method.HandlerMethod;
import org.springframework.web.servlet.handler.HandlerInterceptorAdapter;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.lang.reflect.Method;

public class TestAnnotationInterceptor extends HandlerInterceptorAdapter {
// 在调用方法之前执行拦截
@Override
public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception {
// 将handler强转为HandlerMethod, 前面已经证实这个handler就是HandlerMethod
HandlerMethod handlerMethod = (HandlerMethod) handler;
// 从方法处理器中获取出要调用的方法
Method method = handlerMethod.getMethod();
// 获取出方法上的自定义注解
InterceptorAnnotation access = method.getAnnotation(InterceptorAnnotation.class);
if (access == null) {
// 如果注解为null,没有注解 不拦截
return true;
}
//获取注解值
if (access.authorities().length > 0) {
// 如果权限配置不为空, 则取出配置值
String[] authorities = access.authorities();
}
// 拦截之后应该返回公共结果, 这里没做处理
return true;
}
}

3.注册拦截器

1
2
3
4
5
6
7
8
9
10
11
js复制代码import org.springframework.context.annotation.Configuration;
import org.springframework.web.servlet.config.annotation.InterceptorRegistry;
import org.springframework.web.servlet.config.annotation.WebMvcConfigurerAdapter;

@Configuration
public class InterceptorConfig extends WebMvcConfigurerAdapter {
@Override
public void addInterceptors(InterceptorRegistry registry) {
registry.addInterceptor(new TestAnnotationInterceptor()).addPathPatterns("/**");
}
}

4.使用注解

1
2
3
4
5
js复制代码    @RequestMapping(value = "/selectDemoByVo")
@InterceptorAnnotation(authorities = {"admin"})
public List<DemoVO> selectDemoByVo(@RequestBody DemoVO demoVO) {
return demoService.selectDemoVO(demoVO);
}

6.ConstraintValidator注解实现验证

此方法大多是验证入参格式使用。

1.添加注解类

其中message是返回值,groups()和payload() 是必须有的。@Constraint(validatedBy = TestConstraintValidator.class) 是处理注解逻辑的类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
js复制代码import javax.validation.Constraint;
import javax.validation.Payload;
import java.lang.annotation.*;

@Target({ElementType.METHOD, ElementType.FIELD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Constraint(validatedBy = TestConstraintValidator.class)
public @interface TestConstraintAnnotation {

String message() default "入参大小不合适";

long min();

long max();

boolean required() default true;

Class<?>[] groups() default {};

Class<? extends Payload>[] payload() default {};

}

2.逻辑类

需要实现ConstraintValidator<TestConstraintAnnotation, Object>,第一个参数是注解类,第二个参数是入参类型。只有第一次调用时才会调用initialize ,如果满足isValid逻辑,那么就正常执行,不满足会有message提示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
js复制代码public class TestConstraintValidator implements ConstraintValidator<TestConstraintAnnotation, Object> {
private long max = 1;
private long min = 1;

@Override
public void initialize(TestConstraintAnnotation constraintAnnotation) {
max = constraintAnnotation.max();
min = constraintAnnotation.min();
}

@Override
public boolean isValid(Object o, ConstraintValidatorContext constraintValidatorContext) {
if(o == null){
return true;
}
if(Long.valueOf(o.toString())>=min && Long.valueOf(o.toString())<=max){
return true;
}
return false;
}
}

3.使用注解

vo中在需要验证的参数上加上自定义的注解,在方法接收参数前加入@Valid 说明本方法需要验证。

1
2
3
4
bash复制代码    @RequestMapping(value = "/selectDemoByVo")
public List<DemoVO> selectDemoByVo(@Valid @RequestBody DemoVO demoVO) {
return demoService.selectDemoVO(demoVO);
}
1
2
bash复制代码    @TestConstraintAnnotation(min = 1, max = 10)
private Long id;

本文转载自: 掘金

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

在使用sharding jdbc 生成分布式ID的策略失效

发表于 2021-11-10

在使用sharding jdbc 生成分布式ID的策略失效
官方文档

1
2
properties复制代码spring.shardingsphere.sharding.tables.t_order_item.key-generator.column=order_item_id
spring.shardingsphere.sharding.tables.t_order_item.key-generator.type=SNOWFLAKE

本地的yaml配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
yaml复制代码spring:
application:
name: note
shardingsphere:
enabled: true
sharding:
tables:
t_order:
keyGenerator:
column: id
#生成算法 UUID SNOWFLAKE
type: SNOWFLAKE
#可选配置
props:
worker-id: 132

按照官方的配置应该没错 配置一个生成列 以及生成算法
但是插入到表中 还是报错的 因为这个key是主键 且不能为空
使用这个分布式ID生成算法 生成失败 ID还是为空

配置没有问题 就来看看mapper 插入层 因为使用的mybatsi
看看mapper

1
2
3
4
5
6
7
8
java复制代码/**
* 添加对象所有字段
*
* @param order 插入字段对象(必须含ID)
* @return int
*/
@Insert("insert into t_order(id,user_id,order_sn,gmt_create,gmt_update) values(null,#{userId},#{orderSn},#{gmtCreate},#{gmtUpdate})")
int insert(Order order);

因为之前使用mysql的自增ID 故这样是没有问题的
现在修改为分布式ID 在这样写就有问题了
修改如下

1
2
3
4
5
6
7
8
java复制代码/**
* 添加对象所有字段
*
* @param order 插入字段对象(必须含ID)
* @return int
*/
@Insert("insert into t_order(user_id,order_sn,gmt_create,gmt_update) values(#{userId},#{orderSn},#{gmtCreate},#{gmtUpdate})")
int insert(Order order);

直接SQL层不操作ID 让sharding jdbc 帮我们生成分布式ID
修改后即成功生成分布式ID
效果图
sharding jdbc 生成分布式ID失败原因总结

  • mapper层错误 如上
  • 生成键还是自增的 分布式ID不能为自增
  • ID的类型不对 导致ID存储不上例如 雪花算法 生成long类型的ID 为18位 你用 int 类型存 肯定存不上的
  • 自定义生成算法 出错 或者spi机制查找不到

end 希望可以帮到各位

本文转载自: 掘金

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

Kubernetes + Spring Cloud 集成链路

发表于 2021-11-10

「这是我参与11月更文挑战的第10天,活动详情查看:2021最后一次更文挑战」


一、概述

1、什么是 SkyWalking ?

分布式系统的应用程序性能监视工具,专为微服务、云原生架构和基于容器(Docker、K8s、Mesos)架构而设计。
提供分布式追踪、服务网格遥测分析、度量聚合和可视化一体化解决方案。

官网地址:skywalking.apache.org/

2、SkyWalking 特性

  • 多种监控手段,语言探针和 Service Mesh
  • 多语言自动探针,Java,.NET Core和Node.JS
  • 轻量高效,不需要大数据
  • 模块化,UI、存储、集群管理多种机制可选
  • 支持告警
  • 优秀的可视化方案

3、整体结构

在这里插入图片描述
整个架构,分成上、下、左、右四部分:

考虑到让描述更简单,我们舍弃掉 Metric 指标相关,而着重在 Tracing 链路相关功能。

  • 上部分 Agent :负责从应用中,收集链路信息,发送给 SkyWalking OAP 服务器。目前支持
    SkyWalking、Zikpin、Jaeger 等提供的 Tracing 数据信息。而我们目前采用的是,SkyWalking Agent 收集 SkyWalking Tracing数据,传递给服务器。
  • 下部分 SkyWalking OAP :负责接收 Agent 发送的 Tracing 数据信息,然后进行分析(Analysis Core) ,存储到外部存储器( Storage ),最终提供查询( Query)功能。
  • 右部分 Storage :Tracing 数据存储。目前支持 ES、MySQL、Sharding Sphere、TiDB、H2
    多种存储器。而我们目前采用的是 ES ,主要考虑是 SkyWalking 开发团队自己的生产环境采用 ES 为主。
  • 左部分 SkyWalking UI :负责提供控台,查看链路等等

简单概况原理为下图:
在这里插入图片描述

二、搭建 skywalking

1、环境准备

  • Mkubernetes 版本:1.18.5
  • Nginx Ingress 版本:2.2.8
  • Helm 版本:3.2.4
  • 持久化存储驱动:NFS

2、使用 chart 部署

本文主要讲述的是如何使用 Helm Charts 将 SkyWalking 部署到 Kubernetes 集群中,相关文档可以参考skywalking-kubernetes

目前推荐的四种方式:

  • 使用 helm 3 提供的 helm serve 启动本地 helm repo
  • 使用本地 chart 文件部署
  • 使用 harbor 提供的 repo 功能
  • 直接从官方 repo 进行部署(暂不满足)

注意:目前 skywalking 的 chart 还没有提交到官方仓库,请先参照前三种方式进行部署

2.1、 下载 chart 文件

可以直接使用本地文件部署 skywalking,按照上面的步骤将skywalking chart下载完成之后,直接使用以下命令进行部署:

1
2
3
4
5
6
bash复制代码git clone https://github.com/apache/skywalking-kubernetes
cd skywalking-kubernetes/chart
helm repo add elastic https://helm.elastic.co
helm dep up skywalking
export SKYWALKING_RELEASE_NAME=skywalking # 定义自己的名称
export SKYWALKING_RELEASE_NAMESPACE=default # 定义自己的命名空间

2.2、定义已存在es参数文件

修改values-my-es.yaml:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
yaml复制代码oap:
image:
tag: 8.1.0-es7 # Set the right tag according to the existing Elasticsearch version
storageType: elasticsearch7

ui:
image:
tag: 8.1.0

elasticsearch:
enabled: false
config: # For users of an existing elasticsearch cluster,takes effect when `elasticsearch.enabled` is false
host: elasticsearch-client
port:
http: 9200
user: "elastic" # [optional]
password: "admin@123" # [optional]

2.3、helm 安装

1
2
bash复制代码helm install "${SKYWALKING_RELEASE_NAME}" skywalking -n "${SKYWALKING_RELEASE_NAMESPACE}" \
-f ./skywalking/values-my-es.yaml

安装完成后,我们核实下安装情况:

1
2
3
4
bash复制代码$ kubectl get deployment -n skywalking
NAME READY UP-TO-DATE AVAILABLE AGE
my-skywalking-oap 2/2 2 2 9m
my-skywalking-ui 1/1 1 1 9m

三、使用 Skywalking Agent

Java 中使用 agent ,提供了以下三种方式供你选择

  • 使用官方提供的基础镜像
  • 将 agent 包构建到已经存在的基础镜像中
  • sidecar 模式挂载 agent(推荐)

1、使用官方提供的基础镜像

查看官方 docker hub 提供的基础镜像,只需要在你构建服务镜像是 From 这个镜像即可,直接集成到 Jenkins 中可以更加方便

2、将 agent 包构建到已经存在的基础镜像中

提供这种方式的原因是:官方的镜像属于精简镜像,并且是 openjdk ,可能很多命令没有,需要自己二次安装,这里略过。

3、sidecar 模式挂载 agent

由于服务是部署在 Kubernetes 中,使用这种方式来使用 Skywalking Agent ,这种方式的好处在与不需要修改原来的基础镜像,也不用重新构建新的服务镜像,而是以sidecar 模式,通过共享 volume 的方式将 agent 所需的相关文件挂载到已经存在的服务镜像中。

3.1、构建 skywalking agent image

自己构建,参考:hub.docker.com/r/prophet/s…

通过以下 dockerfile 进行构建:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bash复制代码FROM alpine:3.8

LABEL maintainer="zuozewei@hotmail.com"

ENV SKYWALKING_VERSION=8.1.0

ADD http://mirrors.tuna.tsinghua.edu.cn/apache/skywalking/${SKYWALKING_VERSION}/apache-skywalking-apm-${SKYWALKING_VERSION}.tar.gz /

RUN tar -zxvf /apache-skywalking-apm-${SKYWALKING_VERSION}.tar.gz && \
mv apache-skywalking-apm-bin skywalking && \
mv /skywalking/agent/optional-plugins/apm-trace-ignore-plugin* /skywalking/agent/plugins/ && \
echo -e "\n# Ignore Path" >> /skywalking/agent/config/agent.config && \
echo "# see https://github.com/apache/skywalking/blob/v8.1.0/docs/en/setup/service-agent/java-agent/agent-optional-plugins/trace-ignore-plugin.md" >> /skywalking/agent/config/agent.config && \
echo 'trace.ignore_path=${SW_IGNORE_PATH:/health}' >> /skywalking/agent/config/agent.config
1
bash复制代码docker build -t 172.16.106.237/monitor/skywalking-agent:8.1.0 .

待 docker build 完毕后,push 到仓库即可。

3.2、使用 sidecar 挂载

示例配置文件如下:

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
yaml复制代码apiVersion: apps/v1
kind: Deployment
metadata:
name: demo-skywalking
spec:
replicas: 1
selector:
matchLabels:
app: demo-skywalking
strategy:
rollingUpdate:
maxSurge: 1
maxUnavailable: 0
type: RollingUpdate
template:
metadata:
labels:
app: demo-skywalking
spec:
initContainers:
- name: init-skywalking-agent
image: 172.16.106.237/monitor/skywalking-agent:8.1.0
command:
- 'sh'
- '-c'
- 'set -ex;mkdir -p /vmskywalking/agent;cp -r /skywalking/agent/* /vmskywalking/agent;'
volumeMounts:
- mountPath: /vmskywalking/agent
name: skywalking-agent
containers:
- image: nginx:1.7.9
imagePullPolicy: Always
name: nginx
ports:
- containerPort: 80
protocol: TCP
volumeMounts:
- mountPath: /opt/skywalking/agent
name: skywalking-agent
volumes:
- name: skywalking-agent
emptyDir: {}

以上是挂载 sidecar 的 deployment.yaml 文件,以 nginx 作为服务为例,主要是通过共享 volume 的方式挂载 agent,首先 initContainers 通过 skywalking-agent 卷挂载了 sw-agent-sidecar 中的 /vmskywalking/agent ,并且将上面构建好的镜像中的 agent 目录 cp 到了 /vmskywalking/agent 目录,完成之后 nginx 启动时也挂载了 skywalking-agent 卷,并将其挂载到了容器的 /opt/skywalking/agent 目录,这样就完成了共享过程。

四、改造 Spring Cloud 应用

1、docker打包并推送到仓库

修改下 dockerfile 配置,集成 skywalking agent:

1
2
3
4
5
6
xml复制代码FROM insideo/centos7-java8-build
VOLUME /tmp
ADD mall-admin.jar app.jar
RUN bash -c 'touch /app.jar'
RUN ln -snf /usr/share/zoneinfo/Asia/Shanghai /etc/localtime && echo Asia/Shanghai > /etc/timezone
ENTRYPOINT ["java","-Dapp.id=svc-mall-admin","-javaagent:/opt/skywalking/agent/skywalking-agent.jar","-Dskywalking.agent.service_name=svc-mall-admin","-Dskywalking.collector.backend_service=my-skywalking-oap.skywalking.svc.cluster.local:11800","-jar","-Dspring.profiles.active=prod","-Djava.security.egd=file:/dev/./urandom","/app.jar"]

改好了,直接运行 maven package 就能将这个项目打包成镜像。

注意:

k8s 创建 Service 时,它会创建相应的 DNS 条目。此条目的格式为 <service-name>.<namespace-name>.svc.cluster.local,这意味着如果容器只使用 <service-name>,它将解析为本地服务到命名空间。 如果要跨命名空间访问,则需要使用完全限定的域名。

2、编写 k8s的yaml版本的部署脚本

这里我以其中某服务举例:

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
yaml复制代码---
apiVersion: apps/v1
kind: Deployment
metadata:
name: svc-mall-admin
spec:
replicas: 1
selector:
matchLabels:
app: svc-mall-admin
strategy:
rollingUpdate:
maxSurge: 1
maxUnavailable: 0
type: RollingUpdate
template:
metadata:
labels:
app: svc-mall-admin
spec:
initContainers:
- name: init-skywalking-agent
image: 172.16.106.237/monitor/skywalking-agent:8.1.0
command:
- 'sh'
- '-c'
- 'set -ex;mkdir -p /vmskywalking/agent;cp -r /skywalking/agent/* /vmskywalking/agent;'
volumeMounts:
- mountPath: /vmskywalking/agent
name: skywalking-agent
containers:
- image: 172.16.106.237/mall_repo/mall-admin:1.0
imagePullPolicy: Always
name: mall-admin
ports:
- containerPort: 8180
protocol: TCP
volumeMounts:
- mountPath: /opt/skywalking/agent
name: skywalking-agent
volumes:
- name: skywalking-agent
emptyDir: {}
---
apiVersion: v1
kind: Service
metadata:
name: svc-mall-admin
spec:
ports:
- name: http
port: 8180
protocol: TCP
targetPort: 8180
selector:
app: svc-mall-admin

然后就可以直接运行了,它就可以将的项目全部跑起来了。

五、测试验证

完事,可以去 SkyWalking UI 查看是否链路收集成功。

1、 测试应用 API

首先,请求下 Spring Cloud 应用提供的 API。因为,我们要追踪下该链路。
在这里插入图片描述

2、 查看 SkyWalking UI 界面

在这里插入图片描述

这里,我们会看到 SkyWalking 中非常重要的三个概念:

  • 服务(Service) :表示对请求提供相同行为的一系列或一组工作负载。在使用 Agent 或 SDK 的时候,你可以定义服务的名字。如果不定义的话,SkyWalking 将会使用你在平台(例如说 Istio)上定义的名字。这里,我们可以看到 Spring Cloud 应用的服务为 svc-mall-admin,就是我们在 agent 环境变量 service_name 中所定义的。
  • 服务实例(Service Instance) :上述的一组工作负载中的每一个工作负载称为一个实例。就像 Kubernetes 中的 pods 一样, 服务实例未必就是操作系统上的一个进程。但当你在使用 Agent 的时候, 一个服务实例实际就是操作系统上的一个真实进程。这里,我们可以看到 Spring Cloud 应用的服务为 UUID@hostname,由 Agent 自动生成。
  • 端点(Endpoint) :对于特定服务所接收的请求路径, 如 HTTP 的 URI 路径和 gRPC 服务的类名 + 方法签名。

这里,我们可以看到 Spring Cloud 应用的一个端点,为 API 接口 /mall-admin/admin/login。

更多 agent 参数介绍参考:github.com/apache/skyw…

点击「拓扑图」菜单,进入查看拓扑图的界面:
在这里插入图片描述
点击「追踪」菜单,进入查看链路数据的界面:
在这里插入图片描述

六、小结

本文详细介绍了如何使用 Kubernetes + Spring Cloud 集成 SkyWalking,顺便说下调用链监控在目前的微服务系统里面是必不可少的组件,分布式追踪、服务网格遥测分析、度量聚合和可视化还是挺好用的,这里我们选择了 Skywalking,具体原因和细节的玩法就不在此详述了。

本文源码:

  • github.com/zuozewei/bl…

本文转载自: 掘金

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

C语言04-函数递归(上)

发表于 2021-11-10

「这是我参与11月更文挑战的第10天,活动详情查看:2021最后一次更文挑战」

最近,想复习一下C语言,所以笔者将会在掘金每天更新一篇关于C语言的文章! 各位初学C语言的大一新生,以及想要复习C语言/C++知识的不要错过哦! 夯实基础,慢下来就是快!

什么是递归?

程序调用自身的编程技巧称为递归( recursion)。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。


递归的好处是什么?

递归的两个必要条件

1.存在限制条件,当满足这个限制条件的时候,递归便不再继续。

2.每次递归调用之后越来越接近这个限制条件


递归的重要性

1
2
3
复制代码递归是一个很强的描述工具,不是算法。唯一的作用就是辅助你的思维,比如有时候从递归的角度很
容易构造递推式。至于现有语言的语法上能否高效率的支持递归不是核心问题。
数据结构中的二叉树的很多接口都是用到递归思维

什么时候使用递归?

1.当解决一个问题时,递归和非递归都可以使用,且没有明显问题,就使用递归

2.当解决一个问题递归写起来很简答,非递归写起来比较复杂,且递归没有明显问题,那就用递归。

3.如果说用递归解决问题,写起来简单,但是有明显问题,那就不能用递归,要用非递归方式解决

1
markdown复制代码    注意:递归不能无限递归下去,否则会造成死循环和栈溢出

习题练习:

多说无益,实践是检验真理的唯一标准!下面我们就使用递归和非递归的方式来看看每个题怎么写吧!


1.用递归的方式顺序打印一个数的每一位

image.png

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
scss复制代码//1.用递归的方式顺序打印一个数的每一位
当n为两位数时还要进行拆分,所以if判断条件为n>9
Print(1234)
Print(123)
Print(12)
Print(1)
//


void Print(int n)
{
if (n > 9)
{
Print(n / 10);
}
printf("%d ", n % 10);
}

int main()
{
int n = 0;
//输入要打印的数
scanf("%d", &n);
Print(n);
return 0;
}

运行结果:


2.用递归的方式逆序打印一个数

image.png


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
arduino复制代码void Print(int n)
{
if (n > 0)
{
printf("%d ", n % 10);
n /= 10;
//n%10:得到最后一位数字
//n/10 :除掉最后一位数字
Print(n);
}
else
return;
}
int main()
{
int n = 0;
//输入要打印的数
scanf("%d", &n);
Print(n);
return 0;
}

运行结果:


3.用非递归的方式求阶乘

阶乘: n! = 12*3…n 如 :3!=321=6*\


阶乘是什么:

1
2
3
yaml复制代码阶乘是基斯顿·卡曼(Christian Kramp,1760~1826)于 1808 年发明的运算符号,是数学术语。

一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。自然数n的阶乘写作n!。1808年,基斯顿·卡曼引进这个表示法。
1
2
3
4
5
arduino复制代码//用递归+非递归的方式求阶乘
// //注意:负数没有阶乘。
//阶乘是指从1到n的连续自然数相乘的积。符号为:n!
// 所以我人为规定,输入为负数时,输出1
//非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ini复制代码
int Fac1(int n)
{
int i = 0;
int sum = 1;//注意sum不可以初始化为0,因为0乘任何数都为0
//i也不可以从0开始 0*任何数字都为0
for (i = 1; i <= n; i++)
{
sum *= i;
}
return sum;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fac1(n);
printf("%d\n", ret);
return 0;
}

4.用递归的方式求阶乘

image.png


根据上述图解就可以写出代码了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
arduino复制代码//递归方式
int Fac2(int n)
{
return n < 1 ? 1 : Fac2(n - 1) * n;
}

int main()
{
int n = 0;
scanf("%d", &n);
int rett = Fac2(n);
printf("%d\n", rett);
return 0;
}
今天就先到这吧~感谢你能看到这里!希望对你有所帮助!欢迎老铁们点个关注订阅这个专题! 同时欢迎大佬们批评指正!

本文转载自: 掘金

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

Java 线程池使用总结

发表于 2021-11-10

「这是我参与11月更文挑战的第4天,活动详情查看:2021最后一次更文挑战」

前言

image.png

如图:阿里巴巴 Java 开发手册中对于线程池的创建有着明确的规范。 Executors 返回的线程池有着无法避免的劣势。使用线程池强制使用 ThreadPoolExecutor 创建,建议小伙伴在对线程池的机制有充分的了解的前提下使用 。

当然使用 ThreadPoolExecutor 创建线程池的原因还有:

  1. 根据机器的性能、业务场景来手动配置线程池的参数比如核心线程数、使用的任务队列、拒绝策略等等。
  2. 显示地给我们的线程池命名,这样有助于定位问题。
  3. 方便开发人员对线程池运行状况进行监测,方便及时调整策略避免生产问题。

这里分享一个线上事故的案例 线程池运用不当的一次线上事故 。案例很精彩,场景很现实。是一次很不错的关于线程池问题处理过程。

PS:如果不想看笔者大致总结:父任务依赖子任务执行,且放在同一个线程池 newFixedThreadPool 中执行,导致核心线程死锁无界队列任务不断增加。

正文

既然线程池是日常工作非常常见的知识且使用过程中需要对此有着充分的认知,所以今天就总结一下线程池的常见知识点。

简单的例子

如下使用 ThreadPoolExecutor 实现了自定义线程池完成 Callable 的任务:

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
java复制代码class ImpCallable implements Callable<String> {
// 核心线程数
private static final int CORE_POOL_SIZE=2;
// 最大线程数
private static final int MAX_POOL_SIZE=4;
// 线程数大于 corePoolSize 线程持续时间
private static final int KEEP_ALIVE_TIME=1;
// 阻塞队列的大小
private static final int QUEUE_CAPACITY=5;
private static final TimeUnit UNIT = TimeUnit.SECONDS;
// 自定义线程名
private static final String THREAD_NAME = "my-self-thread-pool-%d";

public static void main(String[] args) throws ExecutionException, InterruptedException {

ThreadPoolExecutor executor = new ThreadPoolExecutor(
CORE_POOL_SIZE,
MAX_POOL_SIZE,
KEEP_ALIVE_TIME,
UNIT,
new ArrayBlockingQueue<>(QUEUE_CAPACITY),
new BasicThreadFactory.Builder().namingPattern(THREAD_NAME).build(),
new ThreadPoolExecutor.CallerRunsPolicy());
ImpCallable task = new ImpCallable();
List<Future<String>> futureList = new ArrayList<>();
for (int i = 0; i < 10; i++) {
// 提交任务到线程池
Future<String> future = executor.submit(task);
// 任务结果 future 加入结果队列
futureList.add(future);
}

for (Future<String> fut : futureList) {
try {
// 取出结果
System.out.println(new Date() + "--" + fut.get());
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}

executor.shutdown();

try {
executor.awaitTermination(5, TimeUnit.SECONDS);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("All threads Finished");
}

@Override
public String call() throws Exception {
Thread.sleep(2000L);
return Thread.currentThread().getName();
}
}

阻塞队列

用来保存等待被执行的任务的阻塞队列,Java 中提供了如下阻塞队列:

  1. ArrayBlockingQueue:基于数组结构的有界阻塞队列,其构造必须指定大小。对象按 FIFO 排序。
  2. LinkedBlockingQuene:基于链表结构的阻塞队列,大小不固定,若不指定大小,其大小有Integer.MAX_VALUE 来决定。对象按 FIFO 排序。吞吐量通常要高于 ArrayBlockingQuene。
  3. SynchronousQuene:特殊的 BlockingQueue,对其的操作必须是放和取交替完成。
  4. priorityBlockingQuene:类似于 LinkedBlockingQueue,对象的排序由对象的自然顺序或者构造函数的 Comparator 决定。

自定义线程名

创建线程的工厂,通过自定义的线程工厂可以给每个新建的线程设置一个具有识别度的线程名。

关于这一点非常有必要,方便快速定位问题以及监控线程池。

拒绝策略

线程池的饱和策略,当阻塞队列满了,且没有空闲的工作线程,如果继续提交任务,必须采取一种策略处理该任务,线程池提供了4种策略:

  1. AbortPolicy 直接抛出异常,默认策略,可以及时发现线程池的瓶颈。
  2. CallerRunsPolicy 使用调用者所在的线程来执行任务,新任务不会丢失,采用谁提交谁负责的策略,有效控制线程池压力。
  3. 、DiscardOldestPolicy 丢弃阻塞队列中靠最前的任务,并执行当前任务,该策略存在丢失任务的风险,不建议使用。
  4. DiscardPolicy 直接丢弃任务,该策略简单粗暴以保证系统可以为主要目标,不建议使用。

当然也可以根据应用场景实现 RejectedExecutionHandler 接口,自定义饱和策略。如记录日志或持久化存储不能处理的任务。

线程池大小

关于线程池线程大小可以根据实际业务场景具体设置。

推荐个适用面比较广的公式( N 为 CPU 核心数):

  • CPU 密集型任务 N+1 。
  • IO 密集型任务 2N 。

线程池状态

image.png

如上图线程池的状态分为五种,分别对应 Java 中五个 int 字段:

1
2
3
4
5
arduino复制代码private static final int RUNNING = -536870912;
private static final int SHUTDOWN = 0;
private static final int STOP = 536870912;
private static final int TIDYING = 1073741824;
private static final int TERMINATED = 1610612736;
  1. RUNNING 线程创建成功初始化状态,能够接收新任务,以及对已添加的任务进行处理。
  2. SHUTDOWN 不接收新任务,但能处理已添加的任务。
  3. STOP 不接收新任务,不处理已添加的任务,并且会中断正在处理的任务。
  4. TIDYING 当所有的任务已终止队列任务也为空线程池会变为 TIDYING 状态。
  5. TERMINATED 线程池彻底终止,由 TIDYING 状态变成 TERMINATED 状态。

监控线程池

我们可以通过第三方组件监控线程池的运行状态比如 SpringBoot 中的 Actuator 。

除此之外,我们还可以利用 ThreadPoolExecutor 的相关 API 监测线程池状态。如下图我们可以轻松获得线程池的各项参数,结合邮件实时监测线程池健康状况。

image.png

这里推荐美团 Java线程池实现原理及其在美团业务中的实践。

美团线程池的文章中实现了线程池核心参数动态配置、线程池健康监测与告警、线程池的集中管理等功能。感兴趣的小伙伴可以自行研究。

参考资料

  • Java线程池拒绝策略
  • 更好的使用JAVA线程池
  • Java 线程池的几种状态
  • Java线程池实现原理及其在美团业务中的实践
  • Java线程池中创建 ThreadFactory 设置线程名称的三种方式

本文转载自: 掘金

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

【Java入门100例】06计算1+1/2!+ +1

发表于 2021-11-10

这是我参与11月更文挑战的第10天,活动详情查看:2021最后一次更文挑战

🌲本文收录于专栏《Java入门练习100例》——试用于学完「Java基础语法」后的巩固提高及「LeetCode刷题」前的小试牛刀。

作者其它优质专栏推荐:

点赞再看,养成习惯。微信搜索【一条coding】关注这个在互联网摸爬滚打的程序员。

本文收录于技术专家修炼,里面有我的学习路线、系列文章、面试题库、自学资料、电子书等。欢迎star⭐️

题目描述

难度:简单

计算 1 + 1/2! + 1/3! + 1/4! + … + 1/20! 的值。

知识点

  • 循环结构
  • 阶乘的计算
  • 初窥动态规划

解题思路

1.循环结构

观察算式的规律,从1-20,每次加1,循环20次。

2.阶乘的计算

n!是为阶乘,等于1*2*3*4...(n-1)*n

3.初窥动态规划

动态规划,一直是算法中的难点,本次不做深度讲解,通俗的说一下。

就是把复杂问题简单化,比如4 的阶乘可以看到3 的阶乘再乘4,而3的阶乘可以看做2的阶乘再乘3,2的阶乘等于1乘2。

其实就是这样一个思想,可以看下leetcode《爬楼梯》这道题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码/**
* 计算 1 + 1/2! + 1/3! + 1/4! + + 1/20! 的值
*/
public class question_06 {
public static void main(String args[]) {
double sum=0,a=1;
int i=1;
while(i<=20) {
sum=sum+a;
i=i+1;
//关键点,动态规划思想
a=a*(1.0/i);
}
System.out.println("sum="+sum);
}
}

输出结果

总结

上一节的问题:什么时候用for?什么时候用while?

答:其实两者区别不大,大多数情况都可以解决问题。只需记住一点:循环次数未知时用while。

最后

独脚难行,孤掌难鸣,一个人的力量终究是有限的,一个人的旅途也注定是孤独的。当你定好计划,怀着满腔热血准备出发的时候,一定要找个伙伴,和唐僧西天取经一样,师徒四人团结一心才能通过九九八十一难。
所以,

如果你想学好Java

想进大厂

想拿高薪

想有一群志同道合的伙伴

请加入技术交流

本文转载自: 掘金

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

1…380381382…956

开发者博客

9558 日志
1953 标签
RSS
© 2025 开发者博客
本站总访问量次
由 Hexo 强力驱动
|
主题 — NexT.Muse v5.1.4
0%