AlexiaChen.github.io

AlexiaChen.github.io copied to clipboard

这里特别是对于工作3-5年的程序员 做了区块链以后，才算真正意义上通过好奇（需求驱动），去阅读了世界上顶尖开源项目的源码，比如BTC的源码。会好奇，别人是怎么做的，以前的读源码漫无目的，枯燥无味，所以还是跟做英语阅读理解一样，首先要解决问题，而解决问题最快的办法就是带着疑问，问题，去看比你牛逼无数倍的人到底是怎么做的。这样阅读源码的效率就高多了，也有收获。 但是其中也有点问题就是，源码告诉了你How，就是它们怎么解决的，但是大部分你不会理解How的背后Why是怎样的，就是他们这些牛人是怎样随着项目发展演进，设计上有什么样的取舍。看似笨拙的方法，到底为什么这样设计？如果能看到详细的内部设计文档，讨论（mailing list）会更好些。所以读issue和Pull Request，研究社区各类牛人的讨论过程，代码评审，在某种程度上又比读源码本身更加重要。 所以，最终的方法是，平时follow社区的讨论issue，PR，这个优先级最高，掌握取舍，高层次的设计是最好的，这是理解Why的最好办法。其次才是源码细节， 也就是How。 之前在知乎写过一个回答 https://www.zhihu.com/question/372800830/answer/1036416740 里面提到我的前Boss，非常厉害的人物，擅长在不短的时间内写复杂系统，包括区块链，BPMN引擎，编解码器。而且复杂度已经远远超过玩具，我请教了他，他说关键还是要看代码，看多了，有体会了，自然就能写比较成品的复杂系统了。 以下摘录一些牛人或非牛人的有价值的语录或者方法论： - 烂程序员关心的是代码。好程序员关心的是数据结构和它们之间的关系。-----linus - 读懂开源项目代码，会改开源项目代码，会重写开源项目，是三个渐进式体验。 ----- 褚霸，余锋 - 先把项目编译运行起来，打日志或者加断点调试。------------- 不清楚来源 - 看大项目，首先要看Happy Path，也就是一般来说是对于对于某个模块来说，是BFS的看，而不是DFS。先不要管corner case或错误异常处理，先看主要正常流程。也就是自顶向下。 ------------- 陈硕 - 大项目，不要从最新的commit开始看，不然容易陷入无限细节，从软件的0.0.x版本看，看懂了再逐步跳跃式的看。（但也有人说，从最新的版本开始看，因为热门开源项目，后期会重构多次，重构代码可读性更高）------- 不清楚来源 -...

AlexiaChen

呼，断断续续持续了几周吧，大约从收假公司远程办公开始写的（2月1号），上周把持久化写好了，今天把游标实现了，准备后面开始好好设计并实现B+树索引了（明天3月16日正式去办公室上班复工，哈哈，正好我生日）。至于本地事务ACID的支持，掉电保护，Write-ahead log这些实现，后面再琢磨吧。先把B+ 树做好，现在数据页的大小是4kb，与InnoDB默认的一致。等有点样子了再开源，github actions还挺好用私有仓库都可以用，我还以为只能开源才能用actions呢。 说起事务的实现，SQLite是支持ACID的，只不过隔离性是串行的，也就是事务不能并发处理，而且早期版本事务实现没有WAL。有两篇官方文章参考，到时候对我的玩具是个不错的资料: - https://sqlite.org/atomiccommit.html - https://sqlite.org/wal.html 最后，Golang虽然长得丑，但是撸起来是真的爽，拿来写基础设施刚好，生态够用，部署测试，可读性，可维护性都方便。慢慢体会到知乎上布丁大神(Google L6工程师)说的: "worse is better"的优点。 Golang真的挺适合写非特别特别强调压榨性能的基础设施软件的，然而大部分基础设施都够用，比如数据库，区块链，编译器，分布式系统等等，不太适合写后端强业务应用的东西（特别是企业级应用），简单的Web API对接，简单的CRUD倒挺适合Golang的，比如围绕着DevOps体系展开的运维监控等工具。

AlexiaChen

# 多项式学习笔记 因为后面学习算子的时候会用到这个内容，所以要提到下。这里主要是理解概念为主，相关证明可以暂时不关心。所以学习笔记也没有提到证明，一般这套学习笔记，我是尽量不接触证明的。因为我不是数学专业。 还是老样子，Ｆ表示Ｒ或Ｃ，Ｒ表示实数域，Ｃ表示复数域。注意，根据域公理，没有整数域这样的概念。 ## 复共轭与绝对值 多项式的系数有复系数或者实系数，所以要“回顾”下高中所学的概念： > 对于复数ｚ，设ｚ = a + b*i, 其中ａ和ｂ均为实数 > - z的实部(real part)定义为 Re z = a > - ｚ的虚部(Imaginary part)定义为 Im z = b...

AlexiaChen

# 线性映射 线代有趣的部分之一就是线性映射了，有些时候也被称作线性变换。还是跟之前一样，F表示实数域或复数域，V表示F上的向量空间，W也是F上的向量空间 ## 向量空间的线性映射 接下来给线性映射（linear map）下个定义： > 从V到W的线性映射是具有下列性质的函数T：V -> W: > 加性（additivity）： 对于所有 u, v ∈ V 都有T（u + v） = T(u) + T(v) > 齐性（homogeneity）： 对所有 λ ∈...

AlexiaChen

可能有人做了几年工程，入门门槛高一点的领域的时候就遇到各种各样的数学，又看不懂怎么办。他们可能脑袋里就会蹦出各种各样的问题，比如： - 数字图像处理，计算机图形学，音视频处理，机器学习里面涉及到矩阵论，概率论，线代，傅里叶变换，小波变换，凸优化，卷积等等。这些数学都看不懂，怎么办？ - 入门密码学，里面涉及抽象代数（群环域）内容不会怎么办？ - 入门程序语言理论，里面涉及抽象代数，数理逻辑，这些内容不会怎么办？ 很多不同领域的业内人士，可能就让这些入门的人直接去补数学，打相应的基础，看书，做题去了。 但是我想说，面对那么多内容的数学，真得能学得完么？其实完全没必要一股脑扎进去补习基础，因为基础是永远打不牢的，不要钻牛角尖，不要深度优先的去学习基础，要广度优先，数学也有API，也有抽象层。我为什么会这么说，因为近一段时间的补数学和密码学，还有结合抽象代数的概念学习线性代数，最重要的我今天在知乎上看到了一位答主的话（多位知名大佬点赞，包括何钦尧），深有感触，答主之前是从事科研的，但是现在转行做了算法工程师。 那位答主说： > 如果你不是纯数学专业，请不要研究纯数学，不要花时间研究数学证明，不要做数学上的习题，不要解偏怪难的问题。只理解通法通则，只关心意义和实际用途。对于科研而言，知道什么问题可解什么问题不可解，可解的问题大概要用到什么数学知识，要比具体解这个问题来得重要得多。抓框架，放细节，让数学成为你科研的“灵机一动”，这就够了。至于深入研究，书到用时方能读。不以应用为目的而纯以“打一个牢固的基础”为目的的学习，大概会有两种结果：一是容易烦，学不下去。二是好不容易学下去了，然后长期没用到，全部忘光了。 别干这种傻事。真一本本去看各种数学书籍，你就傻了。真正的研究路数是：掌握基本的数学知识（以知道论文，教材里的数学名词含义为准）后，选择一个领域方向，直接上手搞，搞的过程中如果发现某个应用必须有某个数学背景才能理解，你就快速去补一下，记得找最薄的书补习，不需要太多太深，然后继续看，你就会发现，你即跟上了业界的步伐，数学水平（主要是广度）也有了很大提高，而且学到的东西都比较牢固。 其实我就是这样感觉，入门学习椭圆曲线密码的时候，我只要简单了解，群环域，有限域的概念，其实就可以入门了，没必要从头把《抽象代数》补习一遍，把”基础打牢，再去入门“，搞得我好像要把抽象代数考八九十分一样才可以入门似的。学习本来就是螺旋式，迂回式的步进，我在知乎上也发现一个密码学博士，有些时候他说没把《抽象代数》学好，看论文的时候，有些要时不时的复习下本科的内容，就是这么个道理了。 说个例子，我本科有个同学，考了硕士研究生，毕业了，是做数据挖掘的。他就没抓住过重点，我稍微学个《抽象代数》他也说没必要，说是抽代太难了，要搞懂其中个中关系，没个一年半载是不行的，他话里的意思貌似是要《抽代》学到八九十分那样的程度才可以找得到事情做。其实现实工程真不是这样的，因为工程的应用，你真不需要学到太深太好。多好才算好？基础是永远打不牢的，你可以根据自己的感觉来，基础学到刚刚好就可以，不够的时候再去补嘛。难道大部分人学习椭圆曲线还要去学习黎曼几何吗？还要去看懂费马大定理证明吗？椭圆曲线与爱德华曲线是怎样等价的？为了搞懂怎样等价的，弄懂双有理映射，难道我还要去学《代数几何》吗？ 代数几何可是弦理论的基础。记住，不要死抠牛角尖，要懂得适可而止。 当然，我这位同学还说过，计算机科学所用到的数学还达到不了本科数学专业，其实这个就是不了解CS，CS的数学，理论起来，要深的可以很深，很纯数学。浅的也就是概率论，线代，微积分这些。不过嘛，综合下来，计算机，特别是工程领域，涉及的数学，平均下来都不深。另外，我个人认为不要被一些数学名词吓到，不懂就去学就是了。 刚开始学密码学的时候，我觉得好难，那么多数学概念，那么多艰深的数学，怎么学啊。然后一个密码学群里的人就回答：其实密码学就是一些公式，你搞懂一些基础的概念就可以学了，但是这不是意味着你就直接用结论公式就可以了，根据自己的学习进展和水平可以试着推下公式，稍微深入点，一步一步来。 最后，切记，不要以”先打一个牢固的基础，再去入门学习“这样的理念去学习，要迂回式前进。我前BOSS他是搞理论物理的呢，数理基础够好了吧？还是数学竞赛保送。但是有些领域依赖的数学，你稍微多问个为什么，他自己都不一定答的上来。一个是即使回答了你也听不懂，二就是他也回答不了，因为他说过，没办法，任何一个领域深入了就是一大堆东西，但其实拿来一小部分就够用了。

AlexiaChen

# 网络相关梳理 网络协议有很多，但是对于互联网用的最多的就是Http，https和TCP协议了。所以重点会梳理这方面的知识点。 ## HTTP 1.0 http的基本特点就是“一来一回”。就是Client发起一个TCP连接，在连接上面发一个http request到server，server返回一个http response，然后TCP连接关闭。 这样导致了性能问题，TCP连接的建立和关闭是耗时操作，一个请求一个连接太耗费资源。还有一个问题就是服务端不能主动推送消息。 当然，http 1.0有解决方案了，设计了一个Keep-Alive机制来实现TCP连接的复用，客户端根据需求选择性的在http request header加一个Connecion:Keep-Alive。Http Server收到这个字段在处理完成请求后不会主动关闭连接，同时在http的Response里也会加上该字段，等待客户端在该连接上发送下一个请求。 又因为连接复用的问题，怕把服务器连接耗光，所以会有一个Keep-Alive timeout参数，超时关闭连接。连接复用还会有一个问题，就是连接不关闭的情况下，Client如何知道某个Request对应Response完毕呢？答案是，http response的header返回了一个Content-Length:xxx 的字段表示响应了多少字节。 ## HTTP 1.1 ### 连接复用与Chunk机制 因为连接复用的必要性，http 1.1标准直接默认复用了，你即使不加Keep-Alive，Server也不会主动关闭连接，除非你在Request header中显式加入Connection:Close，Server才会主动关闭连接。 上一小节说明了用Content-Length判断Response大小，但是这个有问题，如果server返回的内容是动态语言生成的内容，要计算该字段，对于服务器负荷略大，所以在http 1.1中引用了Chunk机制（Http Streaming）。具体来说就是，在Response的header中加入Transfer-Encoding:Chunked，目的是告诉client，Reponse...

AlexiaChen

F的定义在上一篇笔记中有说到，F是实数域或复数域。V则是F上的向量空间。 线性代数一般关注的是有限维的向量空间，而不是任意维的向量空间。 ## 张成空间（span） 好了，为了引入之后会提到的线性组合和张成空间（Span），需要引入一个向量组的概念，其实就是一组向量从v1 ～ vn，有了这个概念以后，就可以定义线性组合的概念，定义如下： > 一个线性组合就是在向量空间V里的一组向量“合成”的一个新向量，满足a1v1 + ... + an*vn,且a1 ～ an ∈ F。 引入以上线性组合的概念，又定义了张成空间的概念： > 一组在V上的向量v1 ～ vn构成的所有线性组合的集合叫做v1 ～ vn的张成空间： span(v1,...,vn) = {a1v1 + ... +...

AlexiaChen

由于大学老师是复读机，大学的《线性代数》只讲行列式和矩阵的计算技巧，没有提到向量空间（线性空间）这种概念，直接忽视了体系的引入和过渡。 设R为实数集合，C为复数集合，根据域的[公理性质](https://github.com/AlexiaChen/AlexiaChen.github.io/issues/15)得出：R和C都是域（Field），分别为实数域和复数域，把两个域，暂且用符号记为F。（记住了，F以后就代表R或C）。F中的元素称为标量（scalar）。 然后，把F推广到更高的维度n，记作F^n, F^n 的定义是从F中选任意n个标量组成的n元组的集合，这里可以简单看成“n维空间”（非物理上的，没有实际意义）上的点或向量。n维空间的向量可以进行加减，也就是有加法逆元。F中的标量也能与空间中的向量做乘法，也就是空间上可以进行标量乘法，即kv ∈ F^n, 且k ∈ F，v ∈ F^n 因为F^n为一个n元组集合，并且该集合上能进行加法和标量乘法，且运算是封闭的，那么该集合就是向量空间，我们可以记作符号V。比如，当n=4是，F^4就是4维实数（复数）向量空间，当然，n可以是无穷，叫无穷维向量空间。向量空间中的元素就是向量，这个向量（vector）比较抽象，可能是元组，向量，也可能是函数或者其他奇怪的东西（暂时不用管）。 如果你之前看到我写的椭圆曲线那篇文章，你就知道阿贝尔群的概念，这会你突然明白了，向量空间也是一个关于加法构成的阿贝尔群（交换群）。 向量空间是一个集合，所以它也有子集，设V的子集U，子集U如果也是向量空间的话，那么U也是V的子空间，并且U自身也是一个交换群。 既然提到了子空间的概念，那么不同子空间的和也构成一个包含这些子空间的最小子空间，和定义为每个子空间的元素所有可能的和构成的集合。由和也引出了直和，直和就是两个子空间U，W，它们的加法U+W是直和，那么U集合交W集合就是空集，也就是U ∩ W = {0}。 最后说下，看到上面提到群的内容，先说下不好意思，我是先学了点抽象代数的东西才来复习线性代数的，按理来说，科班课程安排是线性代数是在抽象代数之前修的。虽然学抽象代数严格来说，不要求先修课，但是还是学点集合论和线性代数再入门抽代会比较好点。另外，文章是我自己的学习笔记，不是科普专门讲给别人看懂的。看不懂我也无能为力。

AlexiaChen

有一次聊天的时候，他说不要被有限域（finite field）给吓唬住，实际上就是模运算（mod）而已。其实他的理解还是有些许错误，模运算还要是模的素数，才能算有限域，其实是一个整数集合Z，模上一个素数才构造了一个有限域。如果模上的是非素数，是其他的正整数，那么实质上构造的就是一个剩余类环（residue class ring）。有限域是剩余类环的一个特例。 如果不明白我这篇文章有[详细推导](https://github.com/AlexiaChen/AlexiaChen.github.io/issues/15) 如果你明白了你也就知道了，剩余类环是交换环的微缩模型，从抽象代数的观点来看，设R是一个交换环，P是R上的一个[素理想](https://en.wikipedia.org/wiki/Prime_ideal)（prime ideal），同时也是R上的一个[极大理想](https://en.wikipedia.org/wiki/Maximal_ideal), 那么R/P就没有0因子，如果把R变为一个剩余类环，并且限定在P上，那么这个剩余类环就是一个有限域Fp。 至于0因子这个关系是来源于数论的[Bézout's identity](https://en.wikipedia.org/wiki/B%C3%A9zout's_identity)， 如果a，b两个数有一个最大公约数d，那么就有x和y满足以下公式ax + by = d， 此时GCD(a,b)就是a和b的线性组合,也就推导出ax全等于d mod b，也就是说除了a=0外，a都有对应的乘法逆元。 其实细节还是蛮难的，大部分人只知道整数集合mod一个prime number就是一个有限域了，这就是构造一个有限域的方法而已。工程上直接用就可以了。

AlexiaChen

# 程序员应该了解的操作系统各种IO知识 对于现在流行的什么大数据，分布式，消息队列等互联网系统，I/O是绕不过去的一个话题，之前也写过网络编程相关的IO话题 https://github.com/AlexiaChen/AlexiaChen.github.io/issues/79， 但是这次打算更加深入地讨论下。 ## Buffered I/O 和 Direct I/O 一般开发者或许没有注意到这两者的区别，缓冲IO和直接IO是不太一样的： - 缓冲IO： C语言的fopen fclose fwrite fread fflush fprintf fscanf等 - 直接IO： Linux的原生API，比如open close fsync read write pwrite pread等...

AlexiaChen