换底规则的证明

发表于 2020-12-28 分类于数学，基础数学

对数换底公式的表达

对数的换底法则，或者称为换底公式表达为:

\[ \log_{a}b = \frac{\log_{c}{b}}{\log_{c}{a}} (c \neq 0,1) \]

此公式中， c的取值是无关的，无论c取何值，它总是成立。

换底法则的证明过程

换底法则先变形一下：

设

\[ \begin{eqnarray*} \log_{x}{y} &= m \tag{1} \\ \log_{c}{y} &= n \tag{2} \\ \log_{c}{x} &= p \tag{3} \\ \end{eqnarray*} \]

由式(1)得出

\[ y = x^m \tag{4} \]

由式(2)得出

\[ y = c^n \tag{5} \]

由式(3)得出

\[ x = c^p \tag{6} \]

联合式(4)式(5)得到

\[ x^m = c^n \tag{7} \]

将式(6)代入式(7)得到

\[ \begin{eqnarray*} (c^p)^m &= c^n \\ \rightarrow c^{pm} &= c^n \\ \rightarrow pm &= n \tag{8} \end{eqnarray*} \]

将式(1)(2)(3) 结果带入(8)

\[ \log_{c}{x} \cdot \log_{x}{y} = \log_{c}{y} \rightarrow \log_{x}{y} = \frac{\log_{c}{y}}{\log_{c}{x}} \tag{9} \]

上式在 $c \notin \{ 0, 1\}$ 时成立。

综上，换底法则得证。

这里写个拓展。对于对数函数 $f(x) = \log_{a}x$ 和函数 $g(x) = \log_{b}x$ 存在常数 $k$ 使得 $f(x) = k \cdot g(x)$ 。通俗点说，就是，一个对数函数的图像，将它在y轴方向上拉伸或者压缩，它可以与任意的对数图像重合。利用换底公式可以很容易的证得。

CDN中的初始拥塞控制

发表于 2020-11-18 更新于 2020-11-23 分类于事实与标准，网络

在调优网络参数时查阅参考资料，发现一篇收获颇多的文，特做翻译本文原文出自Neeldhwaj Pathak, 我在翻译过程中稍作修改。

CDN中的初始拥塞控制

抽象

本文是对内容交付网络（CDN）的TCP initcwnd值的比较研究，该值多年来一直在增长。互联网在不断发展；全球平均网络速度已达到十年前从未想过的程度。同样，网站空间；包括网络对象在内的大小也在不断增长。在我们的实验过程中，我们分析了各种CDN的initcwnd值以及它们多年来的变化。在转向我们的结果和观察之前，先介绍了所涉及概念的背景。

什么是TCP拥塞控制？

网络拥塞控制有四种相互交织的算法，_即。_慢启动，避免拥塞，快速重传和快速恢复。让我简要地解释这四种算法，然后我们可以尝试了解拥塞窗口在确定整个网络性能方面的重要性。

注意：要有效地理解本文，需要了解与TCP相关的各种定义。然而，下面解释了两个重要的定义。

cwnd（拥塞窗口）是一个TCP状态变量，用于控制在收到确认之前可以发送到网络的数据量。另外，rwnd（接收方窗口）是一个TCP变量，用于告诉接收方可以接收的数据量。两者都有助于TCP拥塞和流量控制。

慢启动是一种算法，可逐渐增加注入网络的数据量并找到网络的最佳数据承载能力。它与发送方和接收方之间的连接进行协商，以确定最佳窗口大小。拥塞窗口（cwnd）是发送方限制，而接收方的广告窗口（rwnd）是接收方限制。最初，发送方以较小的拥塞窗口（initcwnd）值发送数据。只要接收方不断确认每个数据包或任一数据包，发送方就不断增加窗口值，达到了ssthresh限制。当这种情况发生时，避免拥塞就接管了。

在慢速启动过程中，TCP实现根据以下公式增加cwnd值。

cwnd + =分钟（N，SMSS）

N –传入ACK中已确认的先前未确认的字节数。

SMSS (Sender's Max Segment Size)–发送方的最大段大小。

当cwnd值大于初始设置的 ssthresh 值时，避免拥塞。在避免拥塞阶段，每个RTT的cwnd大约增加1个分段。以下等式可用于相同的公式。

cwnd + = SMSS * SMSS / cwnd

快速重传和快速恢复 通过使用三重重复ack的概念来帮助提高数据速率发送。当收到乱序的段时，接收方立即将重复的ack发送给发送方。当发送方收到同一数据包的三重dup确认时，它立即发送丢失之间的段，而无需等待重传计时器到期。

CDN如何运作？

对于以Web为中心的公司或Web服务，性能和可靠性是直接影响用户体验并进而提高公司盈利能力的两个主要问题。商业CDN帮助他们缓存并将Web内容交付给用户。Web内容可以包括静态内容（例如，图像，视频，javascript文件等）到动态内容（例如，实时流或多人在线游戏）。CDN服务器位于主要地理区域，使内容更接近用户。

CDN在一个区域或世界各地的各种地理位置（使用边缘缓存或POP）缓存静态（以及动态）内容，从而使资源更接近用户，从而减少了往返时间。因此，当坐在印度的用户尝试访问对象时，最近的服务器可以将其发送给用户，从而减少了RTT，从而减少了页面加载时间并提高了效率。

工作流程： 考虑下图的示例。域名为 tianxun.com 的 Skyscanner（China）已注册CDN。ChinaCache（Skyscanner中国的CDN提供商）向他们提供CDN URL，例如 res.tianxun.com 。然后，开发人员配置为从CDN URL加载静态内容。因此，当坐在中国的用户A尝试访问 tianxun.com 时，浏览器使用链接的CDN URL请求任何对象。然后，CDN将请求分发到最近的CDN服务器，并且从位于最靠近它的位置A的该服务器提供内容。类似地，当用户B尝试访问Skyscanner时，它是由CDN服务器提供的，该CDN服务器位于位置D，因为它离它最近。这有助于提高网站性能，减少原始服务器上的负载，从而改善整体客户使用体验。

CDN使用包括Anycast路由在内的各种技术来分发请求。

任播路由

Anycast是路由和寻址策略的网络技术，可确定客户端向服务器请求资源之间的最佳路径，这些路径在地理位置上是分布的。Anycast通过从托管在多个位置的服务器发布相同的IP地址来工作。网络层的动态路由有助于将数据包路由到最近的服务器（跳数最少）。我们可以将其称为单播到最近的地址，因为从所有可用的接收器中仅选择了一个接收器（最近的接收器）。

我们知道，当客户端在其数据包标头中发送带有任播IP地址的请求时，是路由器会从运行同一服务的多台服务器中选择最佳（最近）目的地。Anycast是使用边界网关协议（BGP）实现的。BGP将自治系统编号用于其域间路由。要深入了解任播的实现，我们需要了解域间路由和BGP的工作。要了解有关此内容的更多信息，请参阅BGP rfc 4271。

TCP Anycast之所以在CDN中脱颖而出的主要原因是，它有助于减少延迟，从而加快了页面加载时间，从而提高了网站的性能。这是CDN受欢迎的主要原因。

TCP初始拥塞窗口的重要性

TCP初始拥塞窗口或initcwnd在启动TCP连接期间使用。在HTTP会话开始期间，当客户端请求资源时，服务器initcwnd确定在初始数据突发期间将发送多少个数据包。

如果initcwnd值较大，则下载同一文件所需的RTT将会更少。但是由于网络环境，我们不能将initcwnd设置为一个巨大的值，并且路由器还具有有限的缓冲区的限制。如果设置的值过大，则可能导致路由器缓冲区溢出，数据包丢失，数据包重传。因此，我们需要为initcwnd设置一个与网络带宽成正比的最佳值。

自从引入此tcp参数以来，由于大多数现代Web交易的寿命很短，并且全球网络的平均速度已在相当长的时间内发展，因此RFC 6928在Google于2010年发表研究报告后才引入，以将initcwnd的默认值增加到10个细分（最多14600字节）。

现代网络和网络空间

如今，互联网以运行在短暂TCP连接之上的网络流量为主导。甚至在慢启动算法退出之前，很大一部分Internet流量就已经完成。

网络空间正在不断增长，并且正以指数级的速度增长。Web对象已明显变大。只有一小部分网络对象（约占所有Google响应的10％）可以容纳4KB的空间。

同时，网络速度和速度也都在发展。即使有相当数量的并发会话，十个网段也可能适合任何宽带访问链路上可用的队列空间。

Google发表了一篇论文，他们在其中量化了通过大规模实验使用较大的initcwnd带来的延迟收益和成本。此后，主要的商业CDN在那里增加了其服务器中的initcwnd值。

主要CDN的Initcwnd设置

2014年初，CDNPlanet发布了一系列主要CDN的initcwnd值的结果。我们想看看在过去三年中发生了什么变化。使用CDNPlanet开源的脚本，我们找出了一些主要CDN的当前initcwnd值。我们还观察到了一些有趣的行为，我们将在观察部分中介绍。

实验装置

我们在五个不同的地理区域中设置了五个EC2实例。俄勒冈州，弗吉尼亚州，悉尼，伦敦和新加坡覆盖全球大部分地区。我们使用这些实例使用不同的CDN将请求发送到不同的网站。我们配置并运行了Turbobytes提供的initcwnd checker的go脚本。

结果

这是我们根据2017年1月通过实验收集的值和CDNPlanet在2014年8月发布的值绘制的比较图。我们可以看到，大多数CDN随时间增加了initcwnd值。这可能是由于我们之前讨论的原因。该聚集结果也予以公布。

主要CDN的Initcwnd值

观察结果

大多数CDN都增加了其initcwnd的价值。随着全球平均网络带宽的不断增长，增加initcwnd值只会减少往返时间，页面加载时间并总体上提高性能。

我们为每个请求收集了目标服务器的IP地址。并观察到，即使我们请求来自不同地区（俄勒冈，弗吉尼亚，悉尼，伦敦和新加坡）的资源，大多数CDN的目标IP仍然保持不变。下表中对此进行了描述。

CDN	俄勒冈州IP	悉尼知识产权	伦敦知识产权	新加坡知识产权
高风	69.16.175.10	69.16.175.10	69.16.175.10	69.16.175.10
最大CDN	108.161.189.85	108.161.189.85	108.161.189.85	108.161.189.85

我们进行了另一项测试，以确认它们是否为任播IP地址。我们从不同区域进行了traceroute到相同ip地址的操作，并观察了数据包经过的中间和最后一跳区域。我们注意到，当请求来自不同区域时，过渡和最后一跳地理区域是不同的。因此，我们可以得出结论，它们是任播IP地址。

对于MaxCDN，从弗吉尼亚州，俄勒冈州，悉尼伦敦，新加坡返回的请求资源的目的地IP为108.161.189.85。上表描述了来自多个位置的临时和最后一跳区域。研究该表得出的结论是，MaxCDN从不同区域通告的IP是任播IP。实际上，大多数主要CDN现在都在其体系结构中使用任播ip地址。

对于列表中的两个CDN。我们在上面进行实验的Akamai和ChinaCache观察到，对于不同类型的请求，initcwnd值是不同的。例如，Skyscanner china（tianxun.com），苏富比和EnglishCentral China使用ChinaCache作为其CDN。我们获得的initcwnd值分别为10、16和20。Paytm，Flipkart和ESPN使用Akamai作为其主要CDN，我们发现的值分别为10、16和32。因此，我们认为他们可能会根据客户提供initcwnd定制。但是随后我们又做了一个有趣的观察。对于美国《福布斯》而言，initcwnd为16，而《福布斯》印度版initcwnd为32。因此，即使对于相同的客户，但在不同的地区（具有不同的域），initcwnd的值也不同。同样，对于特定请求，所有这些值都是一致的，而与源位置无关。

结论

我们可以从整个实验中得出三个主要结论。

随着网络空间和Web环境的发展，CDN多年来不断更新其initcwnd值。
许多CDN在其体系结构中实施了Anycast IP路由，以提高速度，减少延迟并提高其客户网站的性能。
根据客户或地理区域，某些CDN（例如Akamai）能够提供自定义的initcwnd值。

Neeldhwaj Pathak

快速幂算法

发表于 2020-11-14 分类于算法简述

快速幂算法

大数幂的模问题

快速幂算法用于高效的计算大数次幂，实际上对于绝对值大于1的数的大数次幂，我们常常只关心其低位部分，因为它结果的精确值趋向于一个我们无法直接使用的超级大数字。对于绝对值小于1的数进行高幂次运算，它将趋向于0，实际用处也不是很大。而快速幂算法也正是立足于我们只关心结果的尾数部分来实现高效计算的。

常规的求幂算法

对于一个求幂问题 $base^{pow}\%N$按照最直接的求幂过程，我们需要把base做pow-1次乘法运算, 然后再做一次取模运算，其时间复杂度为O(n)。

其中，对于时间复杂度，尚处于我们可以接受的程度，即使pow的值很大，我们总可以在线性的时间内计算完。但是，对于其结果来说，对于我们常用的编程语言种的数据类型来说，几乎是不可承受的。

就当下最流行的高级编程语言C语言来说，其最大的整数类型长度为64位(long long 类型), 所能表示的最大数值是 $18,446,744,073,709,551,615$ ，这个看起来相当大的数字在幂运算面前却不值一提，我们取比1大的最小整数2作为base的值，当exp的值为64时，就已经比这个数字还大了，64确实不能算作一个“大数”，然而，这已经是我们CPU的运算器所能计算的极限了。一旦超出了这个值，就遭遇了计算机领域常见的错误“溢出”，在cpu的寄存器中所存储的计算结果就已经是不正确的了。

所以，常规的求幂算法在计算大数幂中是不适用的。

常规求幂算法使用python表达：

~~要注意这个方法在计算数稍微大一点之后就会溢出，其结果不正确。~~

def pow_mod(base, pow, mod):
    product = 1
    for idx in range(pow):
        product = product * base
    return product % mod

1	`pow_mod(321, 1234567, 1000)`

在我的i56500cpu上，这个算法需要314秒才结束。

快速幂算法

快速幂算法是一种相对于常规的求幂算法更加高效准确的求幂算法。它无法准确的计算幂的结果，退而求其次它可以高效的计算出大数幂的模。而往往，在大数幂的相关问题中，我们也更关注结果的尾数部分，它恰恰是一个大数幂的模的计算。

快速幂算法的理论基础

我们在取模运算中，有一些性质。

\[ \begin{aligned} (a+b) \% p &= (a\%p + b\%p) \% p \\ (a \times b)\%p &= (a\%p \times b\%p) \% p \end{aligned} \]

在快速幂算法种，使用了性质2。

拓展一下性质2的表达, 通俗语言来讲，有任意项连续相乘的表达式，其结果对p取余，可以写成它们每一项对p取余然后再相乘，最后对p取余的形式，在这期间，任意步骤中都可以插入一个对p取余的计算而不影响其结果:

\[ (a\times b\times ... \times n) \% p = (a\%p \times b\%p \times ... \times n\%p)\%p \]

由以上性质可知，要简化幂运算防止其结果溢出，那么可以在常规幂算法的每一次乘法运算后即进行采模。

def pow_mod(base, pow, mod):
    product = 1
    for idx in range(pow):
        product = product * base % mod
    return product

这一步改进，我们额外引入了pow次取模运算，但至少，近乎能保证不会溢出，结果基本可以正确了。

结合幂运算的性质:

\[ \begin{aligned} base^{pow1 + pow2} &= base^{pow1} \times base^{pow2} \\ base^{pow1 \times pow2} &= {(base^{pow1})}^{pow2} \end{aligned} \]

再进一步的优化一下运算，那么现在可以拆指数来减少计算次数了。对指数pow进行因式分解，我们无法保证pow是否是素数，也不好说如何分解才最优，干脆就用计算机算法领域常用的二分法，每次将指数减小一半，此时又出分歧，要区分指数每次是偶数还是奇数时采用不同的处理。

当exp为偶数时:

\[ base^{pow} = (base^{2})^{\frac{pow}{2}} \]

当exp为奇数时:

\[ base^{pow} = (base^{2})^{\frac{pow}{2}} \times base \]

python代码表达一下:

def pow_mod(base, pow, mod):
    result = 1
    while pow > 0:
        if pow & 1 == 0:
            result = result * base % mod
        base = base * base % mod
        pow = pow >> 1
    return result

基本也能讲清楚快速幂算法的思想了，就记到这里吧。

Java远程调试

发表于 2020-10-29 分类于应用技巧， Java

Java平台远程调试

背景

最近我们做的AI决策算法作为服务器逻辑为诛仙2项目提供服务。由于公司采用了内外网分离的开发策略，我们的服务器在内网进行开发，项目组的服务器是严谨进入外网的。到了联调的时候就特别头疼。因为我们大多数的逻辑都是一场战役的逻辑处理和NPC行为的决策展现，使用log调试的方式分外艰难。所以，就想法在测试服进行调试，测试服属于运维网段，是项目组游戏服务器除了它的开发环境和最终生产环境唯一能接触的生产环境了。这个服务器上，我们偷偷钻个洞进行远程调试。

Java的远程调试

JPDA 体系

对于 Java 虚拟机接口熟悉的人来说，您一定还记得 Java 提供了两个接口体系，JVMPI（Java Virtual Machine Profiler Interface）和 JVMDI（Java Virtual Machine Debug Interface），而它们，以及在 Java SE 5 中准备代替它们的 JVMTI（Java Virtual Machine Tool Interface），都是 Java 平台调试体系（Java Platform Debugger Architecture，JPDA）的重要组成部分。

JPDA 组成模块

JPDA 定义了一个完整独立的体系，它由三个相对独立的层次共同组成，而且规定了它们三者之间的交互方式，或者说定义了它们通信的接口。这三个层次由低到高分别是 - Java 虚拟机工具接口（JVMTI） - Java 调试线协议（JDWP） - Java 调试接口（JDI）

这三个模块把调试过程分解成几个很自然的概念：调试者（debugger）和被调试者（debuggee），以及他们中间的通信器。

在调试者和被调试着之间，调试命令和调试结果，都是通过 JDWP 的通讯协议传输的。所有的命令被封装成 JDWP 命令包，通过传输层发送给被调试者，被调试者接收到 JDWP 命令包后，解析这个命令并转化为 JVMTI 的调用，在被调试者上运行。类似的，JVMTI 的运行结果，被格式化成 JDWP 数据包，发送给调试者并返回给 JDI 调用。而调试器开发人员就是通过 JDI 得到数据，发出指令。

模块	层次	编程语言	作用
JVMTI	底层	C	获取及控制当前虚拟机状态
JDWP	中介层	C	定义 JVMTI 和 JDI 交互的数据格式
JDI	高层	Java	提供 Java API 来远程控制被调试虚拟机

Java 调试连接模式

按照工作方式来分，Java调试工作模式有两种，Socket套接字或者共享内存。

在远程调试中，显然共享内存是无法工作的，它只适应于同一台机器上的调试。所以，接下来只讨论基于网络套接字的工作模式。

站在调试器(JDI)的视角，把调试分为两种类别，分别是：

主动调试：jvm启动时设置调试端口并监听，在调试器发来调试信息时进行命令响应。这种模式在调试过程中很常用，适用于跟踪一些可重复性的逻辑bug。
被动模式：jvm启动时设置调试器端口，在jvm启动时会尝试建立链接并停下等待命令。这种模式主要用于调试应用无法正常启动的情况。（主动调试无效，因为启动不起来我们没有机会做连接）

主动调试

主动调试时，对jvm添加参数

1	`-Xdebug -Xrunjdwp:transport=dt_socket,server=y,suspend=n,address=${port}`

被动调试

被动调试时，对jvm添加参数

1	`-Xdebug -Xrunjdwp:transport=dt_socket,address=${ip}:${port},suspend=y`

在IDEA上实践

菜单->Run->EditConfigurations...

左侧点击+，添加Remote，右侧选择 Use module classpath为要调试的项目， Debugger mode进行选择后，虚拟机参数会提示给出，按照给出的参数启动虚拟机即可。

一元二次方程求根公式推导

发表于 2020-10-28 分类于数学，基础数学

一元二次方程求根公式推导

最近在阅读微积分相关的一个题目时，需要求解一个一元二次方程组，大概是上了年纪和许久不求解一元二次方程，竟然一时想不起求根公式，所以决定推导一遍，记录以加深印象。

一元二次函数

说到一元二次方程先回顾一下一元二次函数。

\[ f(x) = ax^2 + bx + c (a \neq 0) \]

其中 a, b, c 分别为其二次项系数，一次项系数和常数项。

而一元二次方程就是函数值为0的情况。

推导

\[ ax^2 + bx + c = 0 \]

将自变量项提公因式a:

\[ a(x^2+ \frac{b}{a}x) = -c \]

移项，并使用平方和公式构造自变量平方项:

\[ \begin{aligned} &x^2 + \frac{b}{a}x + \frac{b^2}{4a^2} = -\frac{c}{a} + \frac{b^2}{4a^2} \\ &\rightarrow (x+\frac{b}{2a})^2 = \frac{b^2-4ac}{4a^2} \\ &\rightarrow x+\frac{b}{2a} = \pm \sqrt{\frac{b^2-4ac}{4a^2}} = \pm \frac {\sqrt{b^2-4ac}}{2a} \\ &\rightarrow x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} \end{aligned} \]

整个变换过程中，因为a不为0，且只有a会出现在分母中，所以这里是没问题的。关键是 $b^2-4ac$ 出现在开平方操作中，我们知道，在实数中，负数是没有平方根的，所以，一元二次方程有实根的条件是 $b^2-4ac $, 且当 $b^2-4ac = 0 $ 时，方程存在唯一解。