0%

第一个半马…真的没啥挑战性,哈哈哈哈哈。

事情起源于表姐在群里问要不要去参加马拉松,她那有名额,然后就兴冲冲的报名了,报了个半马,然后开始了为期几个月的夜跑锻炼任务,从最初的慢悠悠的每天三公里,到逐步拔高的每次五公里,然后开始选鞋完善装备,提高到了十公里。因为家里有事中途中断了一些日子,之后就三天打鱼两天晒网的锻炼着,直到马拉松开始的那天。

周六早起动身,从北京出发到白洋淀站下车。迎着末夏的烈日,面对明天的半马,还是很兴奋的。都说出问题的都是跑半马的,因为半马大多是新手,不懂得如何把握自己身体和跑步强度,所以还是有点担心,就抱着玩玩看的心态去跑的。

半马路线图,从容城雄安市民服务中心出发一直跑到安新,全马则是跑到雄县。

第一个半马还算是比较轻松的跑过来了吧,期间粗心大意的没有把盐丸当回事,结果起跑就不力,心跳一直过速,直接影响了发挥,边跑变琢磨是怎么回事,后来觉得出汗多了,便找周围的人要了两粒盐丸,然后感觉心跳就慢慢的降到正常水平了。目标不高,完赛就好~,顺便拿起奖牌嘚瑟了一把。因为比赛在周日,担心第二天无法上班,其实多虑了,跑后做好充分的拉伸,第二天依然照常去上班了,腿也没有预期的酸痛,只是身体进行了一周左右的慢慢康复,身体的磨损在逐渐自我修复。

后面的时间可能不会再继续练跑步了,小区周围没有公园,只能在大街上跑,有比较多的尾气,感觉对身体不太好,然后买了辆山地准备以后骑行山间了。买后的一个周末独自骑行去了香山,前后 30 公里左右,感觉还不错,以后准备依赖这个了~

背景介绍

近一年都在做语言栈的转型,也注意到周围很多公司都在做相似的事情,大概的路径是 Python -> Go -> Java,转型的起因也是有诸多的因素,像 Python 这种开发速度快,执行相对慢的语言更适合中小型项目,加上国内语言生态不够成熟,项目做大了会发现大家一刀切的转到其它语言上,当然这些说的是在做 web 后端方向上,Python 在数据分析和人工智能方向上还是势头很猛的。Go 可能还是因为它能承载的并发更高,性能更好而逐渐流行起来。在并发模型上 Java 原生 API 使用上确实做得不好驾驭,Go 则要相对好用很多。还有在某些垂直领域上,Java 的生态已经很成熟,其它语言栈上则需要自己造轮子,相应对于开发人员的水平要求就会低很多了。

在当前互联网领域,后端研发做 web 主要谈的还是通过抽象和建模来提高项目的可迭代性与可维护性,另一方面谈的是工程实现上的优化和性能上的优化。在这些后面依赖的则是中台来保证的基础服务综合稳定性。

在语言栈转型中也踩过一些坑,遇到过一些小问题,当然这些也得益于一个相对靠谱的方案来保证迁移的安全,基于这些经验总结一下,在以后的迁移中使问题可预见和避免采坑。

转型流程

首先要明确转型的三个开发流程 MRO (Migration, Reconstruction, Optimization)

  • 迁移 就是把原语言代码照着抄一遍到新语言项目上,按照新语言的工程实现风格来做就可以。
  • 重构 的目的是来提高项目代码的可维护性和可迭代性,让代码更加优雅和好读懂,可以放到迁移完成来做。
  • 优化 则可以是在模块依赖、调用关系、接口字段等方面调整来降低项目的复杂性和提高合理性。

然后看我们人力和时间是否充足,我想大部分情况下是不充足的,按照最短时间交付的原则,我们应该只做迁移流程,也就是说先对原有代码进行语言上的迁移,这样我们可以快速实现交付。在人力充沛的情况下可以配备两个小组,一个维护现有系统,一个主力开发新系统,或者说锁定需求全力开发新系统。在对快速交付更看中的行业里前一个方案更合适一些。

交付流程

在交付过程中的验证流程 单测验证 -> 测试环境功能验证 -> QA生产回测 -> 灰度验证 -> 完全上线
只有功能和单测代码都迁移完才能算代码部分完成,需要优先保证单测行数覆盖率再去保证分支覆盖率,测试环境的功能验证需要覆盖所有 case 来保证大部分问题都被发现,然后进入小范围的灰度验证,之后逐步提高灰度比率直至完全上线。如果是纯读接口则可以直接进行异步校验,就是请求两遍,然后对比差异来不断的发现和修复 bug,直至问题收敛完全解决。
如果明确只做迁移,那么期间如果有发现旧逻辑的 bug 也不要管,这样才好去对比验证,验证通过上线后再去修复。只有通过明确目的和流程并且遵循这个流程做,才能更快的去交付。

验证方案

针对新代码的验证方案分为别为读写接口做不同的验证方案:

  • 读接口:异步请求到新接口做接口响应值校验,打印出差异数据,然后不断修正逻辑。这样可以避免在线上灰度造成数据的不一致。
  • 写接口:测试用例覆盖,然后测试环境验证,灰度回测,灰度验证,修复问题,继续灰度验证。

平稳交付

在整个交付的过程中,转型前后对 SLA 要提供一致的保证,可以看看下面的几个衡量标准:

服务可用性级别 服务正常运行时间 年宕机时间 日宕机时间
1 90% 36.5day 2.4hour
2 99% 3.65day 14min
3 99.9% 8.76hour 86sec
4 99.99% 52.6min 8.6sec
5 99.999% 5.26min 0.86sec
6 99.9999% 31.5sec 8.6msec

在线 MD 表格生成

一般 3 个 9 的可用性全年宕机时间约为 8.76 小时,针对不同系统不同用户规模对于系统可用性的要求不一样,边缘业务的要求可能会低一些,但是对于核心支付链路场景 TPS 可能不高,但是必须要求保证高可用级别。如何保证或者提升服务的 SLA 是我们接下来要探讨的目标,一般有下面两个影响因素:

  • MTBF (Mean Time Between Failures) 系统服务平均故障时间间隔
  • MTTR (Mean Time To Recover) 系统服务平均故障恢复时长

也就是说我们系统要尽可能的降低故障频率以及出现故障时能尽快的恢复。基于这两点我们在做系统平稳过渡时,要充分测试所有 case ,并且进行内部灰度方案和异步重试对比,发现异常立即回滚查找结局问题后再重新灰度。这里需要做到一键开关,数据可监控和追溯。

持续监控,感知系统稳定性的第一步就是监控,通过监控和系统日志来排查问题和及时响应处理。监控有两个层面,一个是基础设施提供的机器监控以及接口级别的响应稳定性监控,另一个是业务数据层面的多维度监控。系统日志按照等级大致分为 INFO 日志以及 ERROR 日志。

快速交付

关于快速交付,可以了解 下敏捷开发,及早和持续不断的交付有价值的软件。关于 Scrum 开发的介绍可以看: 什么是敏捷

现状及未来

基于公司现状考虑 nginx 不支持长时间和自定义灰度,所以 http 接口层没做改动,只是在内部逻辑上通过 rpc 服务转到新的系统中。基于以上要点可以做到功能的快速交付。截止此文撰写时间,语言栈转型已经将系统核心接口逻辑 100% 迁移到新的系统上,对于日常系统需求已经可以做到在新系统开发和接入了。后面要做的有以下几点:

  1. 将系统外围逻辑迁移到新系统;
  2. 不断监控降噪,细化监控粒度,继续提高服务的稳定性;
  3. 当前对于Python的花式“魔法” 硬翻译还需要不断重构和优化。
  4. 完善监控大盘,通过数据驱动来运营优化我们的流程;
  5. 项目复盘总结以及业务普及宣讲,提升人员对于业务细节的认知。

转型痛点

迁移后再做重构和优化过程。在迁移过程中有一个痛点是新需求过来了,要么锁定需求只做迁移,要么写两遍。基于人力情况可以选择一个小组同时写新旧系统或者一个小组维护新的一个小组维护旧的。
在转型过程中新需求过来有时要写两边,或者要把旧系统流量打到新系统接口上,常常在排查问题时遇到流量忘记转移的情况,所以在迁移过程要尽可能的快速交付上线。

反思

  1. 对于每一位工程师来说语言栈的转型既是挑战也是机遇,只有保持开放学习心态,及时调整和提升才能更好应对,同时增强自身软素质。
  2. 当前互联网环境下分布式是必经之地,而系统绝非 100% 可靠,每一个环节可能的异常在上线后必定遇到,所以针对不同场景我们要在 AP 与 CP 之间做出选择。
  3. 对于支付交易核心链路,一条柱子肯定是不稳的,双链路也未必可靠,但至少更稳一些。曾经遇到过相隔几公里的两条光纤被施工队挖断的情况,双机房访问直接 gg 了,但总归是少见的。
  4. 提系统可用性要避免出问题,除了问题要快快快速响应恢复,有问题先回滚。

多图预警!!!
多图预警!!!
多图预警!!!
多图预警!!!

云南是一个离家好几千公里的地方。最初要去的想法是在一次同学聚会上大家商量的,结果到了十月一只有们两个人过来玩了,倒也好,制定行程和订票比较省事。于是,参加完同学婚礼就开始了我们的云南之旅,从国际庄直飞昆明。


去之前做攻略的时候并没有觉得昆明有什么好玩的地方,所以只是做了一天半的行程,要说昆明吃的地方也就是鲜花饼和米线了。对比过几家不同的,一个是花多纷的鲜花饼,另一个是建新园的米线不错。


玩的地方是真没觉得什么,然后就是去了云南省博物馆看了看,一般我到一个城市会先去了解下这个城市的历史和人文,博物馆建的是很恢弘有气势。看了看滇人、昆明人和汉人之间的历史渊源。



明明天还很早,博物馆就早早往外赶人了,算是逛了一半吧,然后看旁边有个官渡古镇,便抱着试试看的心态去逛了逛,果然跟预料的一样,纯粹的商业化街道让人不会再来第二次,就像北方的太行水镇、古北水镇,北京的王府井小吃街和天津的古文化街。。。

也许第一天太兴奋了吧,晚上不想回去,这边比北京在地理时区上差一个多小时。然后便跑去了云大看妹子,可惜到了都晚上了(😶),有大学地方就有小吃街,果然不出所料。

在昆明的第二天,睡了个懒觉,下午去的海埂公园看的滇池。不得不说,景色是真的不错,空气也很好,来到这里就是一场洗肺之旅。

海埂公园是从南到北的,可以遥望西山,走着走着不知不觉就想着去西山看看,站在山顶来俯瞰滇池和昆明应该很不错。就这样被什么驱使着,拿着地图导航,顺着一个不知名的小路就上⛰了。还真是曲径通幽处,好多次都给走错路了,因为真的挺偏。


山中刚下过雨路有点滑,望着遮住天空的树也不知道累,总归心情是很好的,空气也很好,想到这里总对比起北京令人头疼的雾霾天,天高皇帝远,有点不想回去了,在这种地方真的挺宜居的。

想看到的总归是要看到的,但不是在山顶,而是在爬山的某条路途中。

最后,爬到山顶是不能了,来的有点晚,得趁着天黑前下山回去,结果顺着某德导航走了一条崎岖山路,纯人工走出来的土路,崎岖泥泞,向前看不见头,向后难以攀爬。。。有点绝望了,真不知道这种路怎么会被收录并作为导航路线。。。大概是下图这样子的,真的是手脚并用出来的,最口看到村口灯光的时候特别的激动,是看到希望的激动😂。



已经很晚了,到了有人的地方赶紧打车回去市里找了个吃饭的地方。傣族风味,看评价还是挺地道的,发现和其它吃过的才来说,做法上好像没有太特别的地方,只是这里的都加了好多特别香味的香草。

要去的地方总归要去的,一个号称风花雪月的地方——大理,但是我要说与我和我的小伙伴无关。虽然我没有被过多的安利大理的美,但也还是抱着去放松的心态走一趟的。

后面几天的行程比较集中,便商量租了辆车,两个新手,开启了试车模式,尤其我这个拿本六年没摸过车的纯新手,还是比较紧张和激动的。。。我们开上了苍山,到过洱海,去过古镇((⊙o⊙)…好像哪里不对),先练了半天车。



开过了洱海边的乡间小路、白族人的原始村镇,看到了一片金黄的稻田,如此没见过世面的我自己都很惊讶。。。






站在洱海边遥望苍山,哪些传说的爱情故事也只是传说,我所切实感受到的是景色真的很棒,随手一拍都是能做壁纸的那种。我想和对象一起来的话,住着海景房也是会很浪漫的吧???






待在这样的环境里我想一辈子也不会厌倦吧。晚上开去大理古城吃饭,石井私房菜,一个小巷子里,菜品也不错。邻桌的也是从北京过来旅游的。

也许大理的爱情偶遇会在古城中一个故事里发生,在不经意之间吧。

开车就要到平时不能到的地方去看看,经过重重山路不经意间来到了赵灵儿的故乡。查了查发现这里是南诏文化,巍山自治县,这里也有一个古城,慢悠悠的古城里有着原始的居民,又没有太过浓厚的商业化,保护的还相对比较好。



来大理的第三天,想着去丽江看看,最后因为时间距离问题没去,二刷再说吧。那么之前在洱海西线走了一遍,今天就在东线的环海公路走一遍吧。来到了一个叫双廊古镇的浓浓商业化的地方,有着网红打卡地天空之境,随处可见的海景房,这些都不重要,重要的是回去路上沿海公路,听着小歌吹着海风,心情超级好。当然还要感谢一下驾驶员智哥~



出来玩还是不要太久的,容易疲惫,好时光总是很快的,回家啦~



走啦~


参考攻略

云南游玩交通参考

大理景点分布

行程规划

预算

人生只有贪心,没有动态规划。

数据结构

  • 数组
  • 栈,先进后出
  • 队列,先进先出
    • 双端队列,双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两边进行。
    • 环形队列,环形队列是一种特殊的队列结构,保证了元素也是先进先出的,但与一般队列的区别是,他们是环形的,即队列头部的上个元素是队列尾部,通常是容纳元素数固定的一个闭环。
  • 堆,一种特别的树状数据结构。堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
  • 链表
    • 单向链表。
    • 双向链表。
    • 跳表,一种带多级索引的链表。
  • 散列表,是根据键而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。
    • 二叉树,二叉树是一个连通的无环图,并且每一个顶点的度不大于3。
    • 红黑树,是一种自平衡二叉查找树。
    • 字典树(Trie)
  • 图,图(Graph)是由顶点的有穷非空集合和顶点之间的边的集合组成。
  • 布隆过滤器,一个概率型数据结构,可以用来判断一个元素是否在一个集合中。判断某个元素在,可能会被误判;判断某个元素不在,那么一定不在。

算法思想

分治法

分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

例子:快排、归并排序、MapReduce

贪心算法

贪心算法就是在每一步的选择中都按照当前最优的选择,从而希望最终结果得到最优解。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

例子:最小生成树、哈夫曼编码

动态规划(Dynamic Programming)

动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。
若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

递归+记忆=递推

适用情况:

  1. 具有最优子结构性质。
  2. 无后效性,子问题确定后不会再改变。
  3. 子问题重叠的性质。

例子:背包问题
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
https://www.zhihu.com/question/23995189/answer/613096905

回溯法(backtracking)

回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  1. 找到一个可能存在的正确的答案
  2. 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。

例子:八皇后问题

https://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://www.cnblogs.com/zuzZ/p/8178950.html

分支界限法

与贪婪算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。

概率算法

例子:
数值随机化算法
蒙特卡罗(Monte Carlo)算法
拉斯维加斯(Las Vegas)算法
舍伍德(Sherwood)算法

https://zhuanlan.zhihu.com/p/42619498

练习题

15. 三数之和

题目

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路

初读这道题时忽略了一个点,就是在检查时,如果有两个重复的数字可以都用上组成一个三元组集合,但是在返回结果的时候不能第一个数字参与组成三元组后第二个相同数字继续组成三元组。

有三种思路,先进性排序处理,然后再进行处理。第一种就是做三层枚举;第二种就是两层枚举,在进行 set O(1) 查找;第三种是一层枚举,然后从剩余列表中的左右两边进行查找,满足三元组的添加记录。

下面是主要介绍第三种思路的细节

  1. 排序处理
  2. 从第 0 位置开始遍历
    1. 分别取剩余数组的首尾值进行求和
    2. 如果大于零则向前移动尾部游标
    3. 如果小于零则向后移动头部游标
    4. 如果等于零则添加记录
      1. 添加记录后对首尾游标向中间移动一格
    5. 如果首尾游标没有相交则继续 2.1 步骤处理
  3. 进行下一位置的遍历,直到数组尾部
  4. 返回结果

整个流程思路基本是这样子的,然后我们对于边界情况的处理单独进行描述

  1. 如果当前遍历位置值大于 0 则直接返回结果
  2. 对于我在 ① 中描述的情况,需要在 2.1 之前进行与判断,当前位置与上一位置值相同则跳过,进行排重处理
  3. 同样的情况处理在 4.1 之后也要进行首尾游标移动方向相邻值的排重处理

解题思维

  1. 首先需要做到的是充分理解题意,至少要做到能肉眼推导正确结果。
  2. 解决方案一般都会有多种,合理选择最优方案进行骨架设计 ②,充分考虑时间和空间复杂度。
  3. 然后解决边界条件 ③,优化代码可读性。
  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
import java.util.*;

public class ThreeSum {

public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resp = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
int l = i + 1;
int r = nums.length - 1;
if (i > 0 && nums[i-1] == nums[i]) continue;
while (l < r){
int sum = nums[i] + nums[l] + nums[r];
if ( sum> 0) r--;
else if (sum < 0) l++;
else if (sum == 0){
resp.add(Arrays.asList(nums[i], nums[l] , nums[r]));
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++;
r--;
}
}
}
return resp;
}
}

22. 括号生成

题目

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

1
2
3
4
5
6
7
8
9
10
11
12
[---
title: 51. N皇后
date: 2019-08-20
tags: [算法, leetcode]
id: 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
import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
public static void main(String[] args) {
GenerateParenthesis obj = new GenerateParenthesis();
List<String> stringList = obj.generateParenthesis(3);
System.out.println(stringList);
}

public List<String> generateParenthesis(int n) {
List<String> collect = new ArrayList<>();
gen(collect, "", n, n);
return collect;
}

public void gen(List<String> collect, String cur, int left, int right) {
if (left == 0 && right == 0) {
collect.add(cur);
return;
}
if (left > 0) {
gen(collect, cur + "(", left - 1, right);
}
if (right > 0 && right > left) {
gen(collect, cur + ")", left, right - 1);
}
}
}

49、242. 字母异位词

第一题:

242. 有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:

输入: s = “rat”, t = “car”
输出: false

说明:
你可以假设字符串只包含小写字母。

解答第一个思路是使用 HashMap 进行字频统计再对比,第二个思路是字符串排序后进行比较。

第二题:

49. 字母异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明:

所有输入均为小写字母。
不考虑答案输出的顺序。

练习输出:

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
import java.util.*;

public class Anagram {
public static void main(String[] args) {
System.out.println(isAnagram("anagram", "nagaram"));
System.out.println(isAnagram2("anagram", "nagaram"));
groupAnagrams(new String[]{"eat", "ate", "aaa"});
}

public static boolean isAnagram(String s, String t) {
if (null == s && null == t) {
return true;
} else if (null == s || null == t) {
return false;
} else if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> left = new HashMap<>();
Map<Character, Integer> right = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
left.put(s.charAt(i), left.getOrDefault(s.charAt(i), 0) + 1);
}
for (int j = 0; j < t.length(); j++) {
right.put(t.charAt(j), right.getOrDefault(t.charAt(j), 0) + 1);
}
for (Map.Entry<Character, Integer> c : left.entrySet()) {
if (!c.getValue().equals(right.getOrDefault(c.getKey(), 0))) {
return false;
}
}

return true;
}

public static boolean isAnagram2(String s, String t) {
if (null == s && null == t) {
return true;
} else if (null == s || null == t) {
return false;
} else if (s.length() != t.length()) {
return false;
}
char[] left = s.toCharArray();
char[] right = t.toCharArray();
Arrays.sort(left);
Arrays.sort(right);
for (int i = 0; i < left.length; i++) {
if (left[i] != right[i]) {
return false;
}
}
return true;
}

public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> res = new HashMap<>();
for (String sr : strs) {
char[] chars = sr.toCharArray();
Arrays.sort(chars);
String sortedSr = new String(chars);
if (!res.containsKey(sortedSr)) {
res.put(sortedSr, new ArrayList<>());
}
List<String> mapVal = res.get(sortedSr);
mapVal.add(sr);
}
List<List<String>> rep = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : res.entrySet()) {
rep.add(entry.getValue());
}
return rep;
}
}

51. N皇后

题目

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 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
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
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SolveNQueens {
public static void main(String[] args) {
SolveNQueens queens = new SolveNQueens();
System.out.println(queens.solveNQueens(5));
}

public List<List<String>> solveNQueens(int n) {
List<List<String>> resp = new ArrayList<>();
Set<Integer> cols = new HashSet<>();
Set<Integer> pie = new HashSet<>();
Set<Integer> na = new HashSet<>();
dfs(n, 0, new ArrayList<>(), resp, cols, pie, na);
return resp;
}

public void dfs(int max, int row, List<String> curState, List<List<String>> resp,
Set<Integer> cols, Set<Integer> pie, Set<Integer> na) {
// 终结条件
if (row >= max) {
if (curState.size() == max) {
resp.add(curState);
}
return;
}
// 循环列
for (int col = 0; col < max; col++) {
if (cols.contains(col) || pie.contains(row + col) || na.contains(row - col)) {
continue;
}
cols.add(col);
pie.add(row + col);
na.add(row - col);
curState.add(trans(col, max));
int size = curState.size();
List<String> newState = (max - row == 1) ? new ArrayList<String>() {{
addAll(curState);
}} : curState;
// 递归层
dfs(max, row + 1, newState, resp, cols, pie, na);
cols.remove(col);
pie.remove(row + col);
na.remove(row - col);
curState.remove(size - 1);
}
}

public String trans(int point, int max) {
char[] chars = new char[max];
for (int i = 0; i < max; i++) {
chars[i] = i == point ? 'Q' : '.';
}
return String.valueOf(chars);
}
}

69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
  由于返回类型是整数,小数部分将被舍去。

思路

二分查找比较

需要注意的地方有两个

  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
27
28
29
30
31
32
33
34
35
public class MySqrt {
public static void main(String[] args) {
MySqrt mySqrt = new MySqrt();
System.out.println(mySqrt.mySqrt(2147395599));

}

// 边界问题
// 1. 0\1边界
// 类型长度越界
public int mySqrt(int x) {
if (x == 0) return 0;
if (x == 1) return 1;
return mySqrt(x, 0, x);
}

public int mySqrt(long x, long left, long right) {
long cur = (right - left) / 2 + left;
long cur2 = cur * cur;
if (cur2 == x) {
return (int) cur;
} else if (right - left == 1) {
return (int) left;
}

if (cur2 < x) {
left = cur;
} else if (cur2 > x) {
right = cur;
} else {
return (int) cur;
}
return mySqrt(x, left, right);
}
}

扩展

牛顿迭代法


98. 验证二叉搜索树

题目

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:

1
2
3
  2
/ \
1 3

输出: true
示例 2:

输入:

1
2
3
4
5
  5
/ \
1 4
  / \
  3 6

输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。

思路

首先拿到这个题看起来思路比较简单,实现起来还有有点困难,而且在思考过程中踩过一个坑,又爬上来的。哎,看题还是要全面点。

  1. 首先想到就是中序遍历了,放到一个列表中,然后比较大小即可。
  2. 或者是做一个递归操作,判断当前节点是否在一个范围即可。

思路是这么两个思路,代码实现起来为了执行效率做了短路处理,就是边遍历边检查,遇到错误就一路返回不再进行后面处理,当然这是思路理顺后的优化。

中序遍历没坑,直接写就行了,有坑的是第二种操作,刚开始觉得只要比较当前节点的父节点和两个子节点就好了,就像下面画的,已 C 点为当前节点进行处理,实际是一个错误的思路,并且情况也分析的不对。

意识到问题后就重新分析,把当前节点作为最底端的节点,我们去比较的都是当前节点和父辈及以上的节点的大小,也就是拆出来四种情况。

其中 表示当前节点,和其它点的相对位置表示左右子节点关系,min -> max 指向当前节点值必须在此区间中才可以,+∞-∞ 为单点情况的边界表示。最后拆分出这四种子情况,只要任一节点符合这四种情况之一即当前节点满足,当所有节点均满足则二叉搜索🌲有效,事实根据这个思路写出的代码验证是可行的。比较开心的是重新思考后的思路写出来的代码一次通过✌️。

代码

解法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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root){
return forEachNode(root, new ArrayList<>());
}

public boolean forEachNode(TreeNode node, List<Integer> val){
if (null == node) {
return true;
}
if (!forEachNode(node.left, val)){
return false;
}
if (!validOrAdd(val, node)){
return false;
}
if (!forEachNode(node.right, val)){
return false;
}
return true;
}
public boolean validOrAdd(List<Integer> val, TreeNode node){
if(val.size() > 0 && val.get(val.size() - 1) >= node.val){
return false;
}else{
return val.add(node.val);
}
}
}

解法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
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root){
return subValidBSTLeft(root, null, null);
}

public boolean subValidBSTLeft(TreeNode node, Integer min, Integer max) {
if (null == node){
return true;
}
if (null == min && null == max){
}else if (null == min && null !=max && node.val < max){
}else if (null != min && null == max && min < node.val){
}else if (null != min && null != max && min < node.val && node.val < max){
}else {
return false;
}
// left
if (!subValidBSTLeft(node.left, min, node.val)){
return false;
}
// right
if (!subValidBSTLeft(node.right, node.val, max)){
return false;
}
return true;
}
}

102. 二叉树的层次遍历

问题

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resp = new ArrayList<>();
levelOrder(root, 0, resp);
return resp;
}
public void levelOrder(TreeNode cur, int cur_level, List<List<Integer>> resp) {
if(null == cur){
return;
}
if(cur_level == resp.size()){
resp.add(new ArrayList<>());
}
resp.get(cur_level).add(cur.val);
levelOrder(cur.left, cur_level+1, resp);
levelOrder(cur.right, cur_level+1, resp);
}
}

一次过


104. 二叉树的最大深度

问题

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

解答

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxDepth(TreeNode root) {
return maxDepth(root, 0);
}
public int maxDepth(TreeNode cur, int level) {
if(null == cur) return level;
int left_level = maxDepth(cur.left, level + 1);
int right_level = maxDepth(cur.right, level + 1);
return left_level > right_level ? left_level: right_level;
}
}

一次过


111. 二叉树的最小深度

题目

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最小深度 2.

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int minDepth(TreeNode root) {
return minDepth(root, 0);
}

public int minDepth(TreeNode cur, int level) {
if (null == cur) return level;
if (null == cur.left && null == cur.right) {
return level + 1;
} else if (null != cur.left && null == cur.right) {
return minDepth(cur.left, level + 1);
} else if (null == cur.left && null != cur.right) {
return minDepth(cur.right, level + 1);
} else {
int left_level = minDepth(cur.left, level + 1);
int right_level = minDepth(cur.right, level + 1);
return left_level > right_level ? right_level : left_level;
}
}
}

141. 环形链表

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

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

正常的解题思路,通过记录走过的节点来判断是否有环。

时间复杂度:O(n),对于含有 n 个元素的链表,我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1) 的时间。

空间复杂度:O(n),空间取决于添加到哈希表中的元素数目,最多可以添加 n 个元素。

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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<Integer> points = new HashSet<Integer>();
ListNode cur = head;
while (null != cur){
int curHashCode = cur.hashCode();
if(points.contains(curHashCode)){
return true;
}
points.add(curHashCode);
cur = cur.next;
}
return false;
}
}

第二种解题思路是双指针大小步,一个指针每次走一步,另一个指针每次走两步,如果有环的话则两个指针最终会相遇。

在最糟糕的情形下,时间复杂度为 O(N+K),也就是 O(n)。

空间复杂度:O(1),我们只使用了慢指针和快指针两个结点,所以空间复杂度为 O(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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (null == head){
return false;
}else if (null == head.next){
return false;
}else if (head == head.next.next){
return true;
}
ListNode minCur = head.next;
ListNode maxCur = head.next.next;
while (minCur != maxCur){
if (null == minCur.next){
return false;
}else if (null == maxCur.next){
return false;
}else if (null == maxCur.next.next){
return false;
}
minCur = minCur.next;
maxCur = maxCur.next.next;
if (minCur == maxCur){
return true;
}
}
return false;
}
}

146. LRU缓存

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

链接:https://leetcode-cn.com/problems/lru-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
from collections import OrderedDict

class LRUCache(object):

def __init__(self, capacity):
"""
:type capacity: int
"""
self._cache = OrderedDict()
self._size = capacity

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self._cache:
return -1
val = self._cache.pop(key)
self._cache[key] = val
return val

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self._cache:
self._cache.pop(key)
self._cache[key] = value
else:
if len(self._cache) == self._size:
self._cache.popitem(last=False)
self._cache[key] = value


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

有序字典的解法
时间复杂度 O(1)
空间复杂度 O(capacity)

Java 解法需要 LinkedHashMap TODO

LRU(Least Recently Used)最少最近使用,一种页面置换算法。

LFU(Least Frequently Used)最近最不常用。

其它

LRU


206. 反转链表

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class ReverseLinkedList {
public static void main(String[] args) {
ListNode listNode = ListNode.of(
1,
ListNode.of(
2,
ListNode.of(
3,
ListNode.of(
4,
ListNode.of(
5, null
)
)
)
)
);
ListNode next = listNode;
while (null != next) {
System.out.println(next.val);
next = next.next;
}

System.out.println("===");
ListNode reverse = reverse3(listNode);

ListNode next2 = reverse;
while (null != next2) {
System.out.println(next2.val);
next2 = next2.next;
}
}

/**
* 官方推荐的
* @param head
* @return
*/
public static ListNode reverse2(ListNode head) {
// prev -> curr -> nextTemp
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}

/**
* 自己写的
* @param head
* @return
*/
public static ListNode reverse(ListNode head) {
// cur -> prev -> tmp
ListNode cur = head;
ListNode next = head.next;
head.next = null;
while (null != cur) {
ListNode tmp = null;
if (null != next) {
tmp = next.next;
next.next = cur;
}
if (null == next) {
break;
}
cur = next;
next = tmp;
}
return cur;
}

/**
* 复写的
* 1. 记录前一个节点,当前节点
* 2. 迭代
* 3. 取出当前节点到临时变量
* 4. -- 现在有 prev -> curr -> next 三个节点
* 5. 将 curr.next -> prev,改变指向方向
* 6. 依次挪动节点位置 prev = curr , curr = nextTemp
* 7. 最后返回 prev
*
* 时间复杂度 O(n)
* 空间复杂度 O(1)
* @param head
* @return
*/
public static ListNode reverse3(ListNode head) {
// prev -> curr -> next
ListNode prev = null;
ListNode curr = head;
while (null != curr) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}

208. 实现 Trie (前缀树)

题目

实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

分析

前缀树
Trie
字典树

解答

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
public class Trie {
private final int SIZE = 26;
private Node root;

private class Node {
private boolean isStr;
private int num;
private Node[] child;

public Node() {
child = new Node[SIZE];
isStr = false;
num = 1;
}
}

public Trie() {
root = new Node();
}

public void insert(String word) {
if (null == word || word.isEmpty()) {
return;
}
Node pNode = this.root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (pNode.child[index] == null) {
Node tmp = new Node();
pNode.child[index] = tmp;
} else {
pNode.child[index].num++;
}
pNode = pNode.child[index];
}
pNode.isStr = true;
}

public boolean search(String word) {
if (null == word || word.isEmpty()) {
return false;
}
Node pNode = this.root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (pNode.child[index] == null || (word.length() - i == 1 && pNode.child[index].isStr == false)) {
return false;
}
pNode = pNode.child[index];
}
return true;
}

public boolean startsWith(String prefix) {
if (null == prefix || prefix.isEmpty()) {
return false;
}
Node pNode = this.root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (pNode.child[index] == null) {
return false;
}
pNode = pNode.child[index];
}
return true;
}
}

703. 数据流中的第K大元素

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第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
import java.util.PriorityQueue;

public class KthLargest {
private PriorityQueue<Integer> minHeap;
private int kSize;

public KthLargest(int k, int[] nums) {
kSize = k;
minHeap=new PriorityQueue<Integer>(kSize);
for (int i = 0; i< nums.length; i++){
add(nums[i]);
}
}

public int add(int val) {
if (minHeap.size() < kSize){
minHeap.offer(val);
}else if (minHeap.peek() < val){
minHeap.poll();
minHeap.offer(val);
}
return minHeap.peek();
}
}

Java中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。

关于堆操作:https://shmilyaw-hotmail-com.iteye.com/blog/1775868

操作说明:

方法名功能描述
add(Ee)在队列头部增加一个元素,如果容量已满,则抛出异常,成功则返回true。
clear()清空
contains(Objecto)检查是否包含当前参数元素
offer(Ee)在队列头部增加一个元素,如果容量已满,则返回false,成功加入,返回true。
peek()返回队列头部节点,但不移除队列头节点。
poll()将队列头部元素移出队列并返回。
remove(Objecto)将队列头部元素移出队列并返回,如果队列为空,则抛出异常。
size()返回长度

发现自己没玩过的事情好多,上周末便实施了一次露营⛺️之路,叫上小伙伴一起报了个户外团,第一次去选择的比较休闲级别的,然后自带了几十斤装备在山上扎营看天。

去之前连帐篷都没有打开过,不过好在很好弄,去到了迅速选择好营地很快就扎好了。然后在山顶四处转了转。第一次出来玩还是挺兴奋的,但没多久就冻得回帐篷换上了衣服,对比去的时候早上北京的天气超级闷热。

周围也有好多同行的人在扎营,还有两只🐶子互相溜着玩,和它们的主人一样的兴奋。

到了傍晚,就开始下起了大雾,一直持续到了第二天早上,后来想想从山脚下看来这应该是☁️吧,那就是身在云中了。在这么个野外环境下,找厕所也是很方了,哈哈哈。

下了这么一晚上的雾,有点遗憾的是没能看到星空🌃,而且没能选到一个防露水的帐篷晚上被滴醒好几次😶。。。

早上还是挺可以的,看到了日出🌅和云海,还有四处觅食的🐂。其实云海肉眼看上去不太明显,但是做成一个加速的短视频就很好看了。

露营前简单做的攻略

说明:

  1. 加粗为必备
  2. 标 A 的说明已准备好

装备:

帐篷A防潮垫A睡袋A、气垫(防咯)、头灯A、手电A、登山包A充电宝A、手机

雨衣A、雨鞋套A、登山鞋或运动鞋长袖防风衣物、羽绒服、头巾、棉帽

暖贴A、水杯、水5L A湿巾A纸巾A、洗漱用品、垃圾袋A、耳塞(风声吵)、眼罩

自发热小火锅A、八宝粥、面包、筷子、红牛、便携气炉

药物(快客、思密达+ 、藿香正气、创可贴、防虫喷雾、布洛芬)、风油精 AAAAA

银行卡一张A、工具刀A、备用手机A

这里说一些注意点

  1. 帐篷一定要四季防雨防露水的,赶上下雨就惨了
  2. 防潮垫一定要有,并且根据情况准备厚点的防咯
  3. 暖贴可以准备一些晚上睡觉冷贴身上
  4. 垃圾袋还是多带点将垃圾带走
  5. 工具刀准备一下防止意外保护安全
  6. 如果带气炉的话要注意地铁不让进
  7. 吃的尽量带一些高热量食物,自发热小火锅我觉得必备

最后附上一张小朋友拍的很棒的照片。

在这几年的微服务开发过程中遇到过两次因为网络问题导致的系统故障,并且没有做好降级策略,导致系统的不可用时间增加,所以今天专门整理一篇关于网络故障的问题分析处理以及开发中需要注意的地方。

基础部分

TCP 连接,先抛大图:

a

主要分为三部分:

  1. 建立连接
  2. 传输数据
  3. 关闭连接

原理不做过多介绍,主要说说常见的异常和模拟方式。

常见的异常类型

b
上面的异常是一些常见的功能性异常,其它性能方面的异常不在本文讨论范围。

实施手段

需要的工具

  • python 脚本
  • iptables,对网络流量进行规则过滤
  • tcpkill,用来断开网络构造异常
  • curl,发起 http 访问请求

Python脚本

主要作用是启动一个TCP监听,然后将接收到的数据在转发回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#! /usr/bin/python
# -*- coding:utf-8 -*-
import socket
import sys
def start_tcp_server(ip, port):
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server_address = (ip, port)
print('Starting listen on ip %s, port %s' % server_address)
sock.bind(server_address)
try:
sock.listen(1)
except socket.error as exc:
print('Fail to listen on port %s' % exc)
return
while True:
print("Waiting for connection")
client, addr = sock.accept()
data = client.recv(1000)
client.send(data)
client.close()
print(data)
if __name__ == '__main__':
start_tcp_server('0.0.0.0', 12345)

iptables 基本使用

1
2
3
4
5
// 查看当前生效规则
iptables -L -n
// 清空所有规则
iptables --flush
iptables -F

tcpkill 基本使用

https://yq.aliyun.com/articles/59308

1
2
3
4
// 安装
sudo apt-get install dsniff
// 使用
...

curl 超时设置

使用 curl 有两个超时时间,一个是连接超时时间,另一个是数据传输的最大允许时间。
连接超时时间用 --connect-timeout 参数来指定,数据传输的最大允许时间用 -m 参数来指定。

1
curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"

实施过程

  1. A机器启动Python脚本,监听12345端口。
  2. B级器通过curl命令进行访问。
  3. 在访问过程中通过配置iptables来实现网络的各种异常情况。
  4. 通过 tcpkill 来实现连接中断的异常情况。

正常访问

1
2
3
4
5
xyz@xyz-pc:~$ curl "http://192.168.1.110:12345"
GET / HTTP/1.1
Host: 192.168.1.110:12345
User-Agent: curl/7.58.0
Accept: */*

查看和清除规则

1
2
3
4
5
6
7
8
9
10
11
12
13
xyz@xyz-pc:~$ sudo iptables -L -n
[sudo] xyz 的密码:
Chain INPUT (policy ACCEPT)
target prot opt source destination

Chain FORWARD (policy ACCEPT)
target prot opt source destination

Chain OUTPUT (policy ACCEPT)
target prot opt source destination
DROP tcp -- 0.0.0.0/0 0.0.0.0/0 tcp dpt:12345 flags:0x17/0x02

xyz@xyz-pc:~$ sudo iptables -F

连接超时

1
2
3
xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp --syn --dport 12345 -j DROP
xyz@xyz-pc:~$ curl --connect-timeout 10 "http://192.168.1.110:12345"
curl: (28) Connection timed out after 10001 milliseconds

读取数据超时

1
2
3
xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp -m state --state ESTABLISHED --dport 12345 -j DROP
xyz@xyz-pc:~$ curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"
curl: (28) Operation timed out after 20001 milliseconds with 0 bytes received

拒绝连接

1
2
3
xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp --dport 12345 -j REJECT
xyz@xyz-pc:~$ curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"
curl: (7) Failed to connect to 192.168.1.110 port 12345: 拒绝连接

连接被重置

这里需要将Python脚本的 client.close() 注释掉。

1
2
3
4
5
6
7
xyz@xyz-pc:~$ sudo tcpkill -iwlp8s0 port 12345
xyz@xyz-pc:~$ curl --connect-timeout 10 "http://192.168.1.110:12345"
GET / HTTP/1.1
Host: 192.168.1.110:12345
User-Agent: curl/7.58.0
Accept: */*
curl: (56) Recv failure: 连接被对方重设

总结

在越来越多的企业微服务化进程中,肯定会遇到网络请求的各种问题,当我们在做一个基础组件或者进行网络通信请求时需要考虑到这些异常情况,最好还是将各种常见的情况模拟实施一下,来保证服务的稳定性。首先要说的是请求的超时设置,不论是在进行 HTTP 访问还是封装后的 RPC 请求,超时设置是最基本的。
基于不同语言的不同组件实现质量来说。曾经遇到过一个问题是,一个服务处于假死状态,Java 的客户端中默认超时和多线程可以使主线程服务不会受到过多影响,golang 中的客户端默认设置了一个很长的超时时间,服务在一定程度上受到了影响,而Python的客户端超时时间也是很长,还有就是Python只有一个主线程再跑,所以此时服务会被 hang 住了。
所以这里还有一个问题就是服务降级,当前服务如果出现问题,重试几次后仍然失败,那么是否降级来保证当前服务的可用性,其实考虑的是异常服务对于当下的重要性,是否在整个核心服务链路当中,否则的话进行降级处理。
还有一个关键点是慎用重试,偶然的网络波动导致的异常在重试下会很有效,但是当遇到服务性能导致的超时问题时,就遇到大量的客户端重试导致请求翻倍,很可能会直接把服务打挂,所以不要轻易使用重试,可以通过一些额外的补偿机制来提高服务稳定性。

未防止爬虫盗爬我的文章,在末尾打个广告。这篇文章首发在我的个人博客 知一的指纹 http://noogel.xyz ,有需要技术交流的朋友可以加我个人微信:zhi2012666

参考

https://blog.csdn.net/llianlianpay/article/details/79768890
https://www.cnblogs.com/gl1573/p/10129382.html
https://blog.csdn.net/wangyiyungw/article/details/85004905