基本上所有正而八经的算法教材都会解释像 快速排序 quicksort 和 堆排序 heapsort 这样的排序算法有多快，但并不需要复杂的数学就能证明你可以逐渐趋近的速度有多快。

关于标记的一个严肃说明：

大多数计算机专业的科学家使用大写字母 O 标记来指代“趋近，直到到达一个常数比例因子”，这与数学专业所指代的意义是有所区别的。这里我使用的大 O 标记的含义与计算机教材所指相同，但至少不会和其他数学符号混用。

基于比较的排序

先来看个特例，即每次比较两个值大小的算法（快速排序、堆排序，及其它通用排序算法）。这种思想后续可以扩展至所有排序算法。

一个简单的最差情况下的计数角度

假设有 4 个互不相等的数，且顺序随机，那么，可以通过只比较一对数字完成排序吗？显然不能，证明如下：根据定义，要对该数组排序，需要按照某种顺序重新排列数字。换句话说，你需要知道用哪种排列方式？有多少种可能的排列？第一个数字可以放在四个位置中的任意一个，第二个数字可以放在剩下三个位置中的任意一个，第三个数字可以放在剩下两个位置中的任意一个，最后一个数字只有剩下的一个位置可选。这样，共有 4×3×2×1=4!=24 种排列可供选择。通过一次比较大小，只能产生两种可能的结果。如果列出所有的排列，那么“从小到大”排序对应的可能是第 8 种排列，按“从大到小”排序对应的可能是第 24 种排列，但无法知道什么时候需要的是其它 22 种排列。

通过 2 次比较，可以得到 2×2=4 种可能的结果，这仍然不够。只要比较的次数少于 5（对应 2 ⁵ = 32 种输出），就无法完成 4 个随机次序的数字的排序。如果 W(N) 是最差情况下对 N 个不同元素进行排序所需要的比较次数，那么，

两边取以 2 为底的对数，得：

N! 的增长近似于 N<sup> N</sup> （参阅 Stirling 公式），那么，

这就是最差情况下从输出计数的角度得出的 O(N log N) 上限。

从信息论角度的平均状态的例子

使用一些信息论知识，就可以从上面的讨论中得到一个更有力的结论。下面，使用排序算法作为信息传输的编码器：

1. 任取一个数，比如 15
2. 从 4 个数字的排列列表中查找第 15 种排列
3. 对这种排列运行排序算法，记录所有的“大”、“小”比较结果
4. 用二进制编码发送比较结果
5. 接收端重新逐步执行发送端的排序算法，需要的话可以引用发送端的比较结果
6. 现在接收端就可以知道发送端如何重新排列数字以按照需要排序，接收端可以对排列进行逆算，得到 4 个数字的初始顺序
7. 接收端在排列表中检索发送端的原始排列，指出发送端发送的是 15

确实，这有点奇怪，但确实可以。这意味着排序算法遵循着与编码方案相同的定律，包括理论所证明的不存在通用的数据压缩算法。算法中每次比较发送 1 比特的比较结果编码数据，根据信息论，比较的次数至少是能表示所有数据的二进制位数。更技术语言点，平均所需的最小比较次数是输入数据的香农熵，以比特为单位。熵是衡量信息等不可预测量的数学度量。

包含 N 个元素的数组，元素次序随机且无偏时的熵最大，其值为 log<sub> 2</sub>​ N! 个比特。这证明 O(N log N) 是一个基于比较的对任意输入排序的最优平均值。

以上都是理论说法，那么实际的排序算法如何做比较的呢？下面是一个数组排序所需比较次数均值的图。我比较的是理论值与快速排序及 Ford-Johnson 合并插入排序 的表现。后者设计目的就是最小化比较次数（整体上没比快速排序快多少，因为生活中相对于最大限度减少比较次数，还有更重要的事情）。又因为 合并插入排序 merge-insertion sort 是在 1959 年提出的，它一直在调整，以减少了一些比较次数，但图示说明，它基本上达到了最优状态。

一点点理论导出这么实用的结论，这感觉真棒！

小结

证明了：

1. 如果数组可以是任意顺序，在最坏情况下至少需要 O(N log N) 次比较。
2. 数组的平均比较次数最少是数组的熵，对随机输入而言，其值是 O(N log N) 。

注意，第 2 个结论允许基于比较的算法优于 O(N log N)，前提是输入是低熵的（换言之，是部分可预测的）。如果输入包含很多有序的子序列，那么合并排序的性能接近 O(N)。如果在确定一个位之前，其输入是有序的，插入排序性能接近 O(N)。在最差情况下，以上算法的性能表现都不超出 O(N log N)。

一般排序算法

基于比较的排序在实践中是个有趣的特例，但从理论上讲，计算机的 CMP 指令与其它指令相比，并没有什么特别之处。在下面两条的基础上，前面两种情形都可以扩展至任意排序算法：

1. 大多数计算机指令有多于两个的输出，但输出的数量仍然是有限的。
2. 一条指令有限的输出意味着一条指令只能处理有限的熵。

这给出了 O(N log N) 对应的指令下限。任何物理上可实现的计算机都只能在给定时间内执行有限数量的指令，所以算法的执行时间也有对应 O(N log N) 的下限。

什么是更快的算法？

一般意义上的 O(N log N) 下限，放在实践中来看，如果听人说到任何更快的算法，你要知道，它肯定以某种方式“作弊”了，其中肯定有圈套，即它不是一个可以处理任意大数组的通用排序算法。可能它是一个有用的算法，但最好看明白它字里行间隐含的东西。

一个广为人知的例子是 基数排序 radix sort 算法，它经常被称为 O(N) 排序算法，但它只能处理所有数字都能放入 k 比特的情况，所以实际上它的性能是 O(kN)。

什么意思呢？假如你用的 8 位计算机，那么 8 个二进制位可以表示 2 ⁸=256 个不同的数字，如果数组有上千个数字，那么其中必有重复。对有些应用而言这是可以的，但对有些应用就必须用 16 个二进制位来表示，16 个二进制位可以表示 2 ¹⁶=65,536 个不同的数字。32 个二进制位可以表示 2 ³²=4,294,967,296 不同的数字。随着数组长度的增长，所需要的二进制位数也在增长。要表示 N 个不同的数字，需要 k ≥ log<sub> 2</sub>​ N 个二进制位。所以，只有允许数组中存在重复的数字时， O(kN) 才优于 O(N log N)。

一般意义上输入数据的 O(N log N) 的性能已经说明了全部问题。这个讨论不那么有趣因为很少需要在 32 位计算机上对几十亿整数进行排序，如果有谁的需求超出了 64 位计算机的极限，他一定没有告诉别人。

via: https://theartofmachinery.com/2019/01/05/sorting_is_nlogn.html

作者：Simon Arneaud 选题：lujun9972 译者：silentdawn-zz 校对：wxy

本文由 LCTT 原创编译，Linux中国 荣誉推出

Firefox 探索没有 Google 的未来

Mozilla 的绝大部分收入来自与 Google 达成的搜索交易合同。与 Google 的合作对 Mozilla 而言是不舒服的，不仅仅是因为两家公司在浏览器市场是竞争关系，而且还因为两家公司的价值观存在差异。Google 的绝大部分收入来自于在线广告，而 Firefox 的开发者则努力创造工具去阻止广告。Mozilla 认为，隐私并不是一种产品，而是所有用户都应该享有的权利。

来源：solidot

拍一拍：相比 Mozilla，Google 真是丑陋。不知道现在有多少人已经从喜爱 Google 转变为厌恶？

AWS 推出用 Rust 开发的容器发行版 Bottlerocket

亚马逊 AWS 服务发布了主要用 Rust 语言开发的发行版 Bottlerocket，设计用于托管容器。源代码发布在 GitHub 上。作为一种专注于安全、速度和并发的系统级编程语言，Rust 能避免常见的编程错误如访问无效的内存区和竞态条件。

来源：solidot

拍一拍：用 Rust 语言开发一个发行版，这是个不错的消息，就是不知道 Rust 的成分有多少？

C++20 标准草案获得批准

相比 C++17，C++20 是一次重大的更新，引入了新的语言概念、模块、操作符“<=>”、协程、指定初始化、新标准属性等等。C++20 库标准还加入了范围、特性测试宏和位操作等。

来源：solidot

拍一拍：我想，很多人还留在很老的 C++ 标准吧。

根据一位理论物理学家的说法，由于创建和存储数字信息所使用的能源和资源数量，数据应该被视为物理的，而不仅仅是看不见的一和零。

一位大学学者建议，数字内容应该与气体、液体、等离子体和固体一样，被视为第五种物质状态。

英国朴茨茅斯大学高级讲师、发表在《AIP Advances》杂志上的《信息灾难》一文的作者 Melvin Vopson 称，由于以物理和数字方式创建、存储和分发数据所使用的能量和资源，数据已经发生了演变，现在应该被视为质量。

Vopson 还声称，数字比特正在走向压倒地球的道路，最终将超过原子的数量。

给数字信息分配质量的想法建立在一些现有数据点的基础之上。Vopson 引用了 IBM 的一项估计，发现数据每天以 2.5 万亿字节的速度产生。他还将每英寸超过 1 太比特 terabit 的数据存储密度考虑在内，将比特的大小与原子的大小进行比较。

假设数据生成量每年增长 50%，根据宣布 Vopson 研究的媒体发布，“比特的数量将在大约 150 年内等于地球上的原子数量。”

新闻稿中写道：“大约 130 年后，维持数字信息创造所需的动力将等于地球上目前产生的所有动力，到 2245 年，地球上一半的质量将转化为数字信息质量。”

Vopson 补充说，COVID-19 大流行正在提高数字数据创造的速度，并加速这一进程。

他警告说，一个饱和点即将到来：“即使假设未来的技术进步将比特大小降低到接近原子本身的大小，这个数字信息量所占的比重将超过地球的大小，从而导致我们所定义的‘信息灾难’。”Vopson 在论文中写道。

“我们正在一点一点地改变这个星球，这是一场看不见的危机，”Vopson 说，他是希捷科技公司的前研发科学家。

Vopson 并不是一个人在探索，信息并不是简单的不可察觉的 1 和 0。根据发布的消息，Vopson 借鉴了爱因斯坦广义相对论中的质能对比；将热力学定律应用于信息的 Rolf Landauer 的工作；以及数字比特的发明者 Claude Shannon 的工作。

“当一个人将信息内容带入现有的物理理论中时，这几乎就像物理学中的一切都多了一个维度，”Vopson 说。

他的论文总结道，随着增长速度似乎不可阻挡，数字信息生产“将消耗地球上大部分的电力能源，从而导致道德和环境问题。”他的论文总结道。

有趣的是，除此以外，Vopson 还提出，如果像他所预测的那样，未来地球的质量主要由信息位组成，并且有足够的动力创造出来（不确定），那么“可以设想未来的世界主要由计算机模拟，并由数字比特和计算机代码主导，”他写道。

via: https://www.networkworld.com/article/3570438/information-could-be-half-the-worlds-mass-by-2245-says-researcher.html

作者：Patrick Nelson 选题：lujun9972 译者：wxy 校对：wxy

本文由 LCTT 原创编译，Linux中国 荣誉推出

集中日志并结构化待处理的日志数据可缓解与缺少日志相关的风险

日志记录和日志分析对于保护基础设施安全来说至关重要，尤其是当我们考虑到通用漏洞的时候。这篇文章基于我在 FOSDEM'19 上的闪电秀《Let's use centralized log collection to make incident response teams happy》，目的是提高大家对日志匮乏这种安全问题的重视，提供一种避免风险的方法，并且倡议更多的安全实践（利益声明: 我为 NXLog 工作）。

为什么要收集日志？为什么要集中日志记录？

确切的说，日志是写入磁盘的仅追加的记录序列。在实际生活中，日志可以在你尝试寻找异常的根源时帮助你调查基础设施的问题。当你有多个使用自己的标准与格式的日志的异构系统，并且想用一种可靠的方法来接收和处理它们的时候，挑战就来临了。这通常以元数据为代价的。集中日志记录解决方案需要共性，这种共性常常会去除许多开源日志记录工具所提供的丰富的元数据。

日志记录与监控匮乏的安全风险

开源 Web 应用程序安全项目 Open Web Application Security Project （OWASP）是一个为业界贡献了许多杰出项目（包括许多专注于软件安全的工具）的非营利组织。OWASP 定期为应用开发人员和维护者报告最危险的安全挑战。在最新一版《10 项最严重的 Web 应用程序安全风险》中，OWASP 将日志记录和监控匮乏加入了列表中。OWASP 警告下列情况会导致日志记录、检测、监控和主动响应的匮乏：

• 未记录重要的可审计性事件，如：登录、登录失败和高额交易。
• 告警和错误事件未能产生、产生不足或不清晰的日志信息。
• 日志信息仅在本地存储。
• 对于实时或准实时的主动攻击，应用程序无法检测、处理和告警。

可以通过集中日志记录（例如，不仅将日志本地存储）和结构化日志数据以进一步分析来缓解上述情形（例如，在告警仪表盘和安全套件中）。

举例来说, 假设一个 DNS 查询会导向名为 hacked.badsite.net 的恶意网站。通过 DNS 监控，管理员监控并且主动的分析 DNS 请求与响应。DNS 监控的效果依赖于充足的日志记录与收集来发现潜在问题，同样也依赖于结构化 DNS 日志的结果来进一步分析。

2019-01-29
Time (GMT)      Source                  Destination             Protocol-Info
12:42:42.112898 SOURCE_IP               xxx.xx.xx.x             DNS     Standard query 0x1de7  A hacked.badsite.net

你可以在 NXLog 社区版 中自己尝试一下这个例子，也可以尝试其他例子和代码片段。 （再次声明：我为 NXLog 工作）

重要的一点：非结构化数据与结构化数据

花费一点时间来考虑下日志数据格式是很重要的。例如，让我们来考虑以下日志消息：

debug1: Failed password for invalid user amy from SOURCE_IP port SOURCE_PORT ssh2

这段日志包含了一个预定义的结构，例如冒号前面的元数据关键词（debug1）然而，余下的日志字段是一个未结构化的字符串（Failed password for invalid user amy from SOURCE_IP port SOURCE_PORT ssh2）。因此，即便这个消息是人类可轻松阅读的格式，但它不是一个计算机容易解析的格式。

非结构化的事件数据存在局限性，包括难以解析、搜索和分析日志。重要的元数据通常以一种自由字符串的形式作为非结构化数据字段，就像上面的例子一样。日志管理员会在他们尝试标准化/归一化日志数据与集中日志源的过程中遇到这个问题。

接下来怎么做

除了集中和结构化日志之外，确保你收集了正确的日志数据——Sysmon、PowerShell、Windows 事件日志、DNS 调试日志、ETW、内核监控、文件完整性监控、数据库日志、外部云日志等等。同样也要选用适当的工具和流程来来收集、汇总和帮助理解数据。

希望这对你从不同日志源中集中日志收集提供了一个起点：将日志发送到仪表盘、监控软件、分析软件以及像安全性资讯与事件管理（SIEM）套件等外部源。

你的集中日志策略会是怎么样？请在评论中分享你的想法。

via: https://opensource.com/article/19/2/reducing-security-risks-centralized-logging

作者：Hannah Suarez 选题：lujun9972 译者：leommxj 校对：wxy

本文由 LCTT 原创编译，Linux中国 荣誉推出

ARM 公司新的处理器使驱动器既能存储也能处理数据

这是一款旨在实现新一代存储设备的芯片，存储驱动器不是将信息发送到一个单独的芯片进行处理，而是使用其内置的控制器在本地进行处理。Arm 公司的新 Cortex-R82 被设计成作为计算存储设备的控制器。它以芯片设计的形式提供。额外的计算能力使得该芯片可以运行完整的 Linux 发行版以及应用程序，所有这些都可以直接在存储驱动器内运行。

来源：slashdot

拍一拍：所以，以后会有硬盘式的“电脑”了？

调查发现只有 3% 的 Ruby on Rails 开发者使用 Windows

共有来自 92 个国家的 2049 名 Rails 社区成员参加了调查。24% 的受访者主要在 Linux 上开发，而 73% 的受访者使用 Mac OS X。然而最受欢迎的编辑器是微软的 Visual Studio Code（32%），其次是基于 Vim 的编辑器（21%）。大多数受访的开发者认为 Rails 仍然具有现实意义，不过他们对 Rails 核心团队是否在朝着正确的方向发展存在分歧，48% 的人完全同意这种观点。

来源：slashdot

拍一拍：Windows 没赢，Linux 桌面也算不上胜利。

大多数网络安全报告只关注酷炫的威胁

在过去十年中发表的 629 份商业网络安全报告中，只有 82 份（13%）讨论了对公民社会的威胁，其余的报告侧重于网络犯罪、民族国家黑客、经济间谍活动。这造成了对实际网络威胁状况的扭曲看法，而后影响了政策制定者和学术工作。研究者认为，这是因为商业网络安全公司是当今大多数网络安全报告的幕后推手，他们追逐大型企业客户和政府合同，因而主要关注调查网络犯罪、经济间谍和关键基础设施破坏。

来源：zdnet

拍一拍：所以你看到的各种令人震惊的安全威胁报告，其背后都有自己的出发点。

在 Linux 相关的文章、新闻和讨论中，你会经常遇到 显示服务器 display server 、Xorg、Wayland 等名词。

在这篇解释文章中，我将讨论 Linux 中的显示服务器。

什么是显示服务器？

显示服务器是一个程序，它负责协调其客户端与操作系统的其他部分之间，以及硬件和操作系统之间的输入和输出。基本上，多亏了显示服务器，你才能以图形化的方式使用你的计算机（GUI）。如果没有显示服务器，你只能局限于命令行界面（TTY）。

显示服务器提供了一个图形环境的框架，使你可以使用鼠标和键盘与应用程序进行交互。

显示服务器通过显示服务器协议（如 X11）与客户端进行通信。显示服务器是图形用户界面 —— 特别是窗口系统 —— 中的一个关键组件。

不要把显示服务器和桌面环境混淆。桌面环境的下层使用的是显示服务器。

听起来很熟悉，但又不完全清楚？让我来解释一下。

Linux 上的显示服务器协议

Linux 中有三种显示服务器协议，分别是 X11、Wayland 和 Mir。下面我就给大家简单介绍一下这些显示服务器。

X11

X11（也称 X）是已经存在多年的传统显示服务器。它是 Linux 发行版中最常用的显示服务器。

X11 通信协议，使用显示服务器 X.org 服务器。它接收来自设备驱动程序的输入事件，并将它们提供给它的一个客户端。

显示服务器也从客户端接收数据，它处理数据并进行合成，在 Linux 上，它将数据传递给三个内核组件之一：DRM、gem 或 KMS 驱动。

X.Org 服务器是一个显示服务器，它依靠第二个程序：合成窗口管理器，来进行合成。例如 Mutter) 或 KWin。GNOME 使用的是 Mutter。

Wayland

按照其网站的说法，Wayland “旨在作为 X 的更简单的替代品，更容易开发和维护”。

而事实上 Wayland 就是现代的显示服务器，它应该取代传统的 X 显示服务器。

对它的采用还在普及中。Ubuntu 曾试图在 17.10 版本中改用 Wayland 作为默认的显示服务器，但这个尝试遭到了负面反馈。

很多 GUI 应用程序及其框架都依赖于 X 服务器。这些应用程序在 Wayland 上无法正常工作。

这迫使 Ubuntu 继续使用 X 作为默认显示服务器。它仍然提供了使用 Wayland 的选项，但不再是默认的了。

即使在今天，绝大多数的发行版都默认使用 X 显示服务器。

实施 Wayland 显示服务器协议的显示服务器，被称为 Wayland 合成器。和 X11 上的一样，Wayland 合成器负责处理其客户端的输入和输出，但同时也进行合成，这与 X11 相反。

几个 Wayland 合成器是 Weston)、Mutter)、KWin 或 Enlightenment)。

Mir

Mir 显示服务器自带的 Mir 显示服务器协议，与 X11 和 Wayland 使用的协议不同。它是由 Canonical 开发的，作为 Unity 开发的一部分，打算成为 Ubuntu 的首选显示服务器。

但在 2017 年，它已经被 [Ubuntu] 桌面版的 Wayland 显示服务器所取代，不过 Mir 的开发还在继续，用于物联网（IoT）应用。

为什么我们还在使用 Xorg？

Wayland 作为比较新的产品，相比 Xorg 来说，还不是很稳定。作为客户端的程序，必须知道如何与显示服务器进行通信。

因此，很多程序在使用 Wayland 时可能无法运行。Ubuntu 默认切换到 Wayland 的实验证实了这一点。

结束语

我希望你对 Linux 中的显示服务器概念有了更好的理解。我已经尽量不谈太多的技术细节，但我无法完全避免。

欢迎你的反馈和建议。

via: https://itsfoss.com/display-server/

作者：Dimitrios Savvopoulos 选题：lujun9972 译者：wxy 校对：wxy

本文由 LCTT 原创编译，Linux中国 荣誉推出