ARTS-WEEK1

#ARTS #Leetcode

起因

最近参加了左耳朵耗子叔发起的学习小组，小组约定：

每周至少做一个leetcode的算法题；
阅读并点评至少一篇英文技术文章；
学习至少一个技术技巧
分享一篇由观点和思考的技术文章

希望能借此机会，提升自己的技术水平。现在是第一周，完成了一个ARTS：

Algorithm 来源 LeetCode15, LeetCode16
Review 分享一篇go的微服务如何接入eureka
Tip 分享最近看kubernetes源码学习到的
Share 分享go的微服务如何接入eureka

Algorithm

leetcode的15，16题：

https://leetcode.com/problems/3sum/

https://leetcode.com/problems/3sum-closest/

其实这两题和leetcode的第一题Two Sum是解决的同一个问题。Two Sum这题给定了一个数组和一个目标整数，希望在数组中找到两个数，其和等于目标整数。15题3sum，给定一个数组，找出三个整数，其和等于0；16题，给定一个数组，一个目标整数，找出三个整数之和，其和与目标整数最接近。

首先来看看15题。找出数组中三个数，其和等于0；首先，我们可以想到的是，对于数组中的一个数，数组中其他两个元素之和有没等于这个数的相反数的。所有可以写一层循环，计算第i的元素，其后i+1到len（nums）组成的数组中，有没两个数之和等于-nums[i]的。对于两数之和的问题，有O(n)的解法，这里不再赘述。所以整个算法的时间复杂度为O(n*n)。

【参考代码Go版】

func threeSum(nums []int) [][]int {
	results := [][]int{}
	n := len(nums)
	if n == 0 || n < 3 {
		return results
	}
	sort.Ints(nums)
	for i := 0; i < n-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		target := -nums[i]
		left := i + 1
		right := n - 1
		for left < right {
			sum := nums[left] + nums[right]
			if sum == target {
				results = append(results, []int{nums[left], nums[right], nums[i]})
				left++
				right--
				for left < right && nums[left] == nums[left-1] {
					left++
				}
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			} else if sum > target {
				right--
			} else if sum < target {
				left++
			}
		}
	}
	return results    
}

16题，我们可以在15题的基础上加一个参数，用来存储三个整数之和，对于每一次的循环，我们将其计算出来，和之前的结果比较，看谁最接近目标整数，代码如下：

func threeSumClosest(nums []int, target int) int {
	var result int
	length := len(nums)
	if length == 0 || length < 4 {
		for _, v := range  nums {
			result +=v
		}
		return result
	}
	sort.Ints(nums)
	result = nums[0]+nums[1]+nums[2]
	for i := 0; i< length - 2; i++ {
		want := target - nums[i]
		for left, right := i+1, length-1 ; left < right; {
			sum := nums[left] + nums[right]
			if  sum == want {
				return target
			}
			if sum < want {
				left++
			} else if sum > want {
				right--
			}
			current := sum + nums[i]
			if math.Abs(float64(current-target)) < math.Abs(float64(result-target)){
				result = current
			}
		}
	}
	return result    
}

Review

How do software engineers design and adapt huge systems, like the Google search engine, Facebook, or Windows?

文中作者以Borg为例，讲述了他任务的大型系统是怎么创建的，从文中看作者负责Borglet这块。

开始时有一个大的，相对复杂，但不是那么巨大的内核。
新的需求增长迅速，导致系统显著的变的更巨大，更复杂。
了解整个Borg系统的工程师，多次组织重构。

对于第一点，Borg启动的时候，就面临大量的需求。包括管理上千台的服务器集群；自动调度应用到服务器；对于每个应用会限定它们的CPU、磁盘、内存需求，包括优先级，资源不足时优先级低的要让位于优先级高的；将低优先级的应用放到优先级应用声明但是没有使用的地方；

对于第二点，新需求增长迅速。SSD作为一种新资源被纳入管理；异常情况处理发生改变，在开始的设想中磁盘坏了，所有使用这块磁盘的应用都应被认为挂了，但现在不这么处理了，增加了允许磁盘丢失的代码路径。同时围绕这mater和borglet这样的基础核心，一系列组件开始被构建，包括检查工具、配置语言、自动预测资源需求、资源配额管理、跨服务器调度。最终，Borg系统变成了我们现在见到的这个样子。初始的一秒计算一次资源使用被内核的cgroups代替；因为用户不能理解他们看到的，所以我们重新修改了错误报告功能。只读的GUIs也开始被加入到系统中。

对于第三点，大多数参与Borg项目的工程师对整个Borg系统，并不是很了解。他们工作在各个细分的组件上，比如Borglet的内存管理等等，就算了解也只是对Borg背后的核心理念知道个大概。但是仍然有不少杰出的工程师，他们了解整个系统，理解它们是如何工作的。出现问题马上能精准定位到原因。需要注意的是本地级别的重构和架构级的改变，而不是一种。而这些改动，对于一个庞大而复杂的系统保持增长能力至关重要。

个人review：果然重构在一个大型系统里面极为重要，像Borg这样的大的系统，也是从一堆需求开始，不断实现新需求的同时，完成着本地重构(代码级)和架构重构，最终形成了如今这么大的规模。从kubernetes的代码和架构中可看出，这么大的系统没有因为规模而混乱不堪，没有因为新增的需求而导致代码东拼西凑，保持了强劲的可增长可扩展能力。

Tip

最近在看kubernetes的源码，调度器和控制器部分，代码重构是引起我关注最多的地方。kubernetes的代码大部分都已经完成了函数的抽象，部分未完成的也标记了TO-DO，想起了TDD的理念中的Refactoring，同时也提醒自己，在以后的代码中，要更注意代码的重构，相同功能的提取抽象。

分析这篇kubernetes deployment controller实现原理。

https://draveness.me/kubernetes-deployment

当初看deployment controller源码时，卡在 ReplicaSet 需要改变的副本数这里好久，一直绕不过去这个坎，然后搜到了这篇文章。

起因

Algorithm

Review

Tip

Share