The Linux Scheduler: a Decade of Wasted Cores

https://blog.acolyer.org/2016/04/26/the-linux-scheduler-a-decade-of-wasted-cores/

The Linux Scheduler: a Decade of Wasted Cores – Lozi et al. 2016

This is the first in a series of papers from EuroSys 2016. There are three strands here: first of all, there’s some great background into how scheduling works in the Linux kernel; secondly, there’s a story about Software Aging and how changing requirements and maintenance can cause decay; and finally, the authors expose four bugs in Linux scheduling that caused cores to remain idle even when there was pressing work waiting to be scheduled. Hence the paper title, “A Decade of Wasted Cores.”

In our experiments, these performance bugs caused many-fold performance degradation for synchronization-heavy scientific applications, 13% higher latency for kernel make, and a 14-23% decrease in TPC-H throughput for a widely used commercial database.


参数估计:从频率学派到贝叶斯学派

很多时候我们有一堆数据,并且也知道数据的基本模型,但是不知道模型的参数是什么。这是基本的机器学习过程,这个过程就叫参数估计

比如我们现在就有一堆数据,模型是y = \beta_0 x + \beta_1 + \xi = \beta^T X + \xi,我们要求\beta

常见的计算\beta的手段有:

  1. 最小二乘法
  2. 最大似然估计
  3. 最大后验估计
  4. 贝叶斯估计

但是这几种估算方法的背后,其实代表了两类学术派别,也就是大家学习贝叶斯的时候经常听到的,频率学派和贝叶斯学派

今天来捋捋这两种学派的区别和联系


二项分类逻辑回归

线性回归产生的预测值y=\theta^T x是实值,而逻辑回归通常是要解决分类问题。用线性回归来解决分类问题效果是很差的

分类问题在生活中是很常见的,二项逻辑回归模型有如下的条件概率分布

  1. 成功概率:P(Y=1|X) = \frac {1}{1+e^{-\theta^T x}}
  2. 失败概率:P(Y=0|X) = 1- \frac {1}{1+e^{-\theta^T x}}

最大似然估计求解线性回归

之前我在讲理解最大似然估计 http://0fd.org/2017/06/10/understand-the-maximum-likelihood-estimation/ 的时候,讲了两个例子,不过都很简单,今天来讲讲怎么用最大似然估计来求解线性回归方程,不管是一元还是多元

线性回归方程如下:

y = \theta_1 x_1 + ... + \theta_n x_n = \sum_{i=1}^{n} \theta_i x_i

现在假设我们有 m 组样本数据,(y^1, x_{(1 \sim n)}^1), (y^2, x_{(1 \sim n)}^2), ..., (y^m, x_{(1 \sim n)}^m),我们怎么用最大似然估计来求解\theta呢?


理解最大似然估计

最大似然估计是传统机器学习里最常见的一种估计,简单来说,就是利用已知的样本结果,在确定模型的基础上,反推模型的参数

前面我们讲过泊努力分布、二项分布、泊松分布,都是日常生活中常见的模型。这些分布的模型就是他的概率函数,比如泊努力分布是单次实验,所以模型就是概率p,二项分布是P(X=i) = \binom{n}{i}P^i(1-P)^{n-1},泊松分布的模型就是P(X=k) = \frac {\lambda^k} {k!} e^{-\lambda}

这里面有3个关键点:

  1. 样本已知
  2. 模型已知
  3. 每个样本都是一次完全独立事件的结果

监督学习、无监督学习、半监督学习、强化学习

原文:https://cloud.tencent.com/developer/article/1099894

一般说来,训练深度学习网络的方式主要有四种:监督、无监督、半监督和强化学习。在接下来的文章中,计算机视觉战队将逐个解释这些方法背后所蕴含的理论知识。除此之外,计算机视觉战队将分享文献中经常碰到的术语,并提供与数学相关的更多资源。

1. 监督学习(Supervised Learning)

监督学习是使用已知正确答案的示例来训练网络的。想象一下,我们可以训练一个网络,让其从照片库中(其中包含你父母的照片)识别出你父母的照片。以下就是我们在这个假设场景中所要采取的步骤。


Mutilate: high-performance memcached load generator for tail latency analysis

multilate 是 leverich 在14年的时候,为了分析数据中心高密度混部场景下延迟敏感问题而开发出来的一个 memcached 性能压测工具,原论文可以了解一下:

https://jacob.leverich.org/papers/2014.mutilate.eurosys.slides.pdf

和 mcperf & memslap 等其他压测工具不太一样的是,multilate 非常适合分析长尾延迟问题,比如,multilate 的输出里面,可以非常直观的看到所有请求的平均延迟、最小延迟、最大延迟、10分位、90分位、95分位、99分位,当然,如果你想要更精确的数据,也可以改改代码,支持到99.9分位等等

代码在这里:https://github.com/leverich/mutilate


正态分布的前世今生

神说,要有正态分布,就有了正态分布。

神看正态分布是好的,就让随机误差服从了正态分布。

— 创世纪—数理统计

转载自:https://cosx.org/2013/01/story-of-normal-distribution-1

1. 正态分布,熟悉的陌生人

学过基础统计学的同学大都对正态分布非常熟悉。这个钟形的分布曲线不但形状优雅,它对应的密度函数写成数学表达式

\displaystyle f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{{(x-\mu})^2}{2\sigma^2}}

也非常具有数学的美感。其标准化后的概率密度函数

\displaystyle f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}

更加的简洁漂亮,两个最重要的数学常量 (\pi)(e) 都出现在这公式之中。在我个人的审美之中,它也属于 top-N 的最美丽的数学公式之一,如果有人问我数理统计领域哪个公式最能让人感觉到上帝的存在,那我一定投正态分布的票。因为这个分布戴着神秘的面纱,在自然界中无处不在,让你在纷繁芜杂的数据背后看到隐隐的秩序。


网络带宽限制之 – Traffic Control 流控原理

TC(Traffic Control)是Linux内核中目前用于网络带宽流控非常成熟的一个工具,通过使用TC灵活的创建各种队列、并定义队列中的数据包被发送的方式, 从而实现对流量的控制。比如开源的 mesos 使用tc来限制job流量,并在twitter公司内大规模推广

Linux高级路由控制:http://lartc.org/howto/

TC文档:http://tldp.org/HOWTO/Traffic-Control-HOWTO/index.html

1. 原理

TC中主要包含两种队列:一类是无类队列(classless qdiscs)规定, 另一类是分类队列(classful qdiscs)规定。 无类队列规定相对简单,而分类队列规定则引出了分类和过滤器等概念,使其流量控制功能增强。

无类队列规定是对进入网络设备的数据流不加区分统一对待的队列规定。使用无类队列规定形成的队列能够 接受数据包以及重新编排、延迟或丢弃数据包。这类队列规 定形成的队列可以对整个网络设备的流量进行整形, 但不能细分各种情况。


The pod and service of kubernetes

我们知道pod和service是kubernetes中非常核心的两个概念,要了解这两个东西,就需要看看它们解决了什么问题。

Pod要解决的问题是:数据共享和交互

而Service,是解决Naming问题的另一种思路

1. Pod要解决什么问题?

共享是Pod最原始的需求,早在google的borg论文里,我们就能看到类似的场景,例如borg中的alloc通常用来运行多个Job,举例:有两个Job,一个job是web server实例,另一个job是负责日志收集

1.1 数据共享

数据共享是最常见的一个场景,pod中有volume来解决这种问题,所谓volume,其实就是在不同的容器之间共享一块磁盘。docker里可以用 –volume= 等用法

1.2 容器交互

交互是更深一层次的共享

我们知道容器之间是天然隔离的,除非使用特别hack的方法,否则你根本就无法看到另外一个容器里的任何东西,事实上你除了能看到你自己之外根本就不知道别人的存在。

多容器共生是这个问题的原始需求,AB容器是一个服务下的两个模块,相互依赖共存亡,既需要做好容器间的隔离,例如CPU、内存、网络带宽等等,又需要解决模块间交互的问题。前面我们说的数据共享只是容器交互最简单的一种形式,除此之外,我们需要解决的共享需求有:

  • 网络
  • 进程体系
  • 文件系统

docker提供一些方法来解决这些问题,例如容器之间共享网络可以使用如下命令:

docker run --tty -i --net=container:11e9bc1b8f5be ubuntu /bin/bash

不过目前kubernetes似乎仅仅支持共享网络,还不支持进程体系、文件系统之间的共享