Algorithm(leetcode 算法题)

Longest Increasing Path in a Matrix

这次不做 Graph 的题了,换了一道,粗看题目第一反应还是用 dp ……果然我被 dp 荼毒的很厉害么 23333,不过跟一贯只向右向下延展的走步策略题不一样,一个点四个方向上的值只要大于点本身就是可行的路径,所以我的初始编码版本是在向右下延展的基础上,加上往回蔓延的策略,当前一个点可通向的方向最大步数一旦更新,该方向的邻点入队列作为新的当前点重新进行检查

好处是思路简洁编码实现迅速,当然缺点就是喜闻乐见的超时了……

之后一直很忙碌,都是在睡觉和坐车上班的间隙思考优化,但不知道是因为可用时间确实太短太碎片还是思路真的局限的太厉害,居然一直拖着拖到最后都没想清楚优化思路……

等到放假抽了一个小时集中精力,无意间多瞥了一眼题目的 Related Topic,茅塞顿开,一个深度搜索+缓存访问就能解决的问题为什么我会强行用 dp 呢……果然是被荼毒的很厉害啊看到矩阵看到最优迭代上来就想用 dp 也是没救了……

最后 Beats 率也就 40% 左右,不是很理想。完整 AC 代码:

class Solution(object):
	def dfsSearch(self, point, visited, matrix, dp, m, n):
		x, y = point[0], point[1]
		if visited[x][y]:
			return dp[x][y]
		else:
			maxCount = 1
			dirList = [(x, y-1), (x, y+1), (x-1, y), (x+1, y)]
			for p in dirList:
				if p[0] >= 0 and p[0] < m and p[1] >= 0 and p[1] < n and matrix[p[0]][p[1]] > matrix[x][y]:
					self.dfsSearch(p, visited, matrix, dp, m, n)
					dp[x][y] = max(dp[x][y], dp[p[0]][p[1]] + 1)
			visited[x][y] = True
	def longestIncreasingPath(self, matrix):
		if len(matrix) == 0: return 0
		m, n, maxCount = len(matrix), len(matrix[0]), 0
		visited = [[False for j in range(n)] for i in range(m)]
		dp = [[1 for j in range(n)] for i in range(m)]
		for x in range(m):
			for y in range(n):
				self.dfsSearch((x, y), visited, matrix, dp, m, n)
				maxCount = max(maxCount, dp[x][y])
		return maxCount

Review(阅读并点评至少一篇技术文章)

Cluster Schedulers

在上期的 changelog 中被推荐的文章之一,从一个比较高的角度来看集群调度器的起源、发展、现状、未来以及原理本质等等

这篇文章非常好的一点是在开头就非常清晰的给出了文章内容的重点,这里也简单列一下:

  • Google 最初开发集群调度器的目的以及展望
  • 这些设计与展望它们是如何解决我们剩下的问题的,又为何没有解决
  • 向现存基础设施上加装调度器的挑战
  • 使用调度器配合进行混合部署
  • 在 imagix 上我们为什么选择了 Nomad 而不是 Kubernetes
  • 等待解决的问题
  • 这些新工具带来的新问题
  • 等着我们的未来将会是什么

选这篇文章的原因之一是它似乎提到了个人很感兴趣的一点:Kubernetes 的不足,为什么选用其他组件(例如本文提到的 Nomad)而不是 Kubernetes

作者有几句话我很喜欢:

you only truly understand the power of a piece of technology when you actually use it.
(你永远无法真正理解你没用过的技术)
One particular mistake I see a lot of us tend to make (including yours truly) about certain tools and technology is centering our conversation/evaluation around the stock problems they aim to solve and the features they provide, as opposed to the problem we actually have at hand.
(我们时常无法看清当前自己面临的真正问题,反而是在对名声鹊起的某些特定技术工具的讨论中迷失了自己)

我们都知道能达到 Google 那样规模计算量和数据量的组织屈指可数,但大家却总是不经意想去做 Google 在做的事——而不首先思考一切工具技术究竟是为了什么

在作者看来当前未解决的问题主要有三个:

  • 打包📦问题
  • 部署问题
  • 生命周期问题

三点仍能向下细分,例如部署就涉及重启和回滚两个重要的部分,生命周期又涉及 CI/CD 的问题等等

中间作者详细的分析了当前软件开发存在问题的本质,还介绍了他们团队当前的技术栈,并以此为基准说明为什么不选择 Kubernetes 而选择了 Nomad,叙述清晰有条理,作者对很多工程操作(如基础架构的增量重构)法则思路的理解都非常值得学习

他们不用 Kubernetes 的三大原因:

  • Docker:k8s 是基于容器的编排系统,意味着我们现有和将来的所有应用都要变成容器化的打包方式,成本巨大,而且作者所在的团队本身就希望限制容器化应用的数量而不是使其激增

  • 网络:k8s 的网络架构非常复杂,层层抽象,几乎是完全接管了系统的网络架构。他们目前的服务量级不高,大部分应用是简单的绑定端口并暴露给 consul,复杂的 SDN 对他们来说并不需要

  • 基础架构的增量式重构:在架构的增量修改上,一次性只对已有架构作一些轻量可见的改变,一旦出问题可以回滚,而引入 k8s 对已有架构的影响非常大,甚至需要替换掉技术栈中非常重要的、起核心连接作用的 consul 组件,这个成本太高,不符合增量式修改的原则,风险过大

用 Nomad 立竿见影的优势:

  • 对当前技术栈变动最小
  • 与 consul 的良好集成
  • 简洁优雅的重启方式
  • 灵活性
  • 操作的自主性
  • 简单易用,上手成本低

目前 Nomad 对他们来说尚且存在的缺陷:

  • 没有访问控制支持,大部分使用是将 Nomad 运行在另一个用于制定访问控制策略的代理背后,例如作者团队的 HAProxy
  • 缺乏认购超额(oversubscription)机制,Nomad 没有资源限额、优先级以及超额获取的管理支持,因此资源的回收利用也不可能,这对延迟敏感型服务来说非常关键,因此目前作者所在团队还无法将核心关键服务切换到 Nomad 上

还有很多具体的技术细节作者都有非常深入的思考和恰当的考量,非常值得一读


Technique(技术技巧)

原子计数器的替代方案

最近工作遇到一个问题:多个进程要从一个队列中取出 Job 来消费,视消费的结果决定是否往某个全局计数器 +1,每个 Job 有唯一标识 id,但 Job 可能消费失败,失败后会回到队列,此时不能重复计数

遇到这个问题脑海里第一时间冒出来的词差不多就是:原子锁、全局唯一自增 id / 计数器、读写锁等等,顺着这些思路甚至开始考虑该怎么自己实现锁了(蠢蠢欲动想造轮子)……当然结果是发现自己应该不具备编码实现一套完整锁机制的能力😂

因为进程的数量最多也就 5,退而求其次想到一个替代方案是按进程分多个 Key 统计,但因为进程内也是有多个线程级别的抽象在并发消费 Job,所以并没有根本上解决问题

此时同事提出了一个简单优雅的方案:利用 Redis 的原子保证,不是采取计数器的方式,而是用 Redis 一个 Key 作为 Set,计数器直接 +1 的操作换为向 Set 中丢 Job 的标识 id

这样最后结束 Set 中元素数量就是计数器结果,而且还去了重,不需要手动实现任何额外锁,完美

嗯……为什么我自己想不到呢……


Share(分享有观点和思考的技术文章)

Docker, Moby, Containers

照惯例本期依旧是 changelog 的 GoTime 模块……但是!但是!这回的访谈邀请的是 Docker 的创始人之一、Docker 公司 CTO 的 Solomon!对没错就是那个头像可爱到爆炸并且之前决定从 Docker 离职发了篇博文配的图也可爱爆炸的!Solomon Hykes!

发现这篇访谈的一个主持人之一跟我一样非常兴奋啊我果然不是一个人诶嘿嘿

Solomon

正篇从 Docker 的起源谈起:它源于 DotCloud —— 一个 PaaS,底层由容器(container)技术支持。容器其实并不是一个全新的东西,它很早就存在 Linux 系统里,而追溯历史我们会发现最初 container 这个词其实是一个非常局限的术语,如今主流所熟知的 container 定义其实是 shipping container,后者涵盖的内容范围要大得多:linux container 是 docker 拓宽边界所使用的性质之一,shipping container 才是我们代码所落实到的那一个概念

DotCloud 平台还在时就有大量的顾客对底层提供支持的技术非常感兴趣,最终 Solomon 的团队决定将这部分技术开源出来,名为 Docker 的项目就此诞生了。为了集中精力做好这个项目关闭了 DotCloud 这,而针对 Docker 是从一个付费 PaaS 的核心支持技术诞生的开源项目这一点,一位主持人从商业角度提了一个非常有趣的问题:在客户提出对底层技术感兴趣并想用于他们自己的生意而不愿意付钱时,为什么最终决定将整个技术开源而不是采取常见的 "修改付费策略使客户觉得物有所值"、"修改价格模型" 等保守稳定的做法呢?对此 Solomon 认为 Docker 和 PaaS 的对比就好像乐高和常规玩具,乐高具有强大的定制化功能,你可以用乐高按你自己的想法制作和修改,而普通的玩具你想要做个修改,你恐怕得联系厂商,耗费巨大的金钱和时间等待他们出新的功能,在这个层面上 Docker 这一项目具备巨大的潜力,他能从本质上真正满足客户们的需求,这比没什么市场竞争力的 PaaS 要有价值的多

回到 GoTime 这一频道的主题上来后 Solomon 表示 Docker 是从 python 转向 go 语言的,但早期项目本身确实完全不涉及 Go 语言。Solomob 本身不对编程语言有什么信仰,他更倾向于 Go 的原因是他希望 Docker 这个项目可以有更多的贡献者、参与者,而且他希望用一种可以编译成通用二进制的语言,能在一定程度上使开发者们可以不在乎底层的语言,不过这里面也有 Solomon 自己本人的一点喜好在里面,原话是这么说的:

Sometimes there's just a tool or a language, you wanna use it, and then after the fact you're gonna make up rational reasons to justify it...

而提到使用 Go 的更深层的原因,Solomon 表示他本人是一个 c 系统工程师出身的 hacker,但无法否认很多东西用 c 来实现确实是浪费时间,所以有了更轻便的 python,但 Go 具备了更多的优势:

  • 以 c 的范式来编程
  • 有轻量级的线程
  • 可以享受到回调的好处又没有回调地狱

Docker 字母在开发过程中也或多或少遇上过技术上的问题,例如在对系统 LXC 的调用上:Docker 本质是对现有的 LXC 命令行工具的封装,而 LXC 并不总是可靠,他可能失败或返回,甚至永远挂起,这部分的处理相对较复杂

Docker 在不久之前宣布更名为 Moby,Solomon 表示他们团队主要是为了在 Docker 这一开源项目的网络、存储、运行时优化等各方面作出贡献社区的参与者考虑。Docker 作为一个开源产品同时一个开源的项目,两者面向的群体不同,不同的群体也对 Docker 抱有不一样的期待,Docker 已经成长到必须正视这些区别的体量了,就像 Red Hat 将他们的 Linux 版本拆分出了 Red Hat Enterprise 和 Fedora 一样

除了上述部分,Solomon 还花了很大篇幅更深入去讲述这个 Docker 项目更名的意义、他们团队为此已经和准备努力去做的事情,对改名这一操作感到困惑的开发者们可以细读一下


Comment(来自别人的评价与相关讨论)