关于不可变系统的构想 lispclojureOS
程序员文章站
2022-04-16 20:57:35
...
为什么会想到操作系统
大概一年以前，我有一个想法，就是基于不可变值实现OpenGL的渲染器。我把这个想法发到博客上了，并且在Hacker News和Reddit上得到了不少关注。还有些人甚至给我发来了邮件。
在吊床上思考了很长一段时间后，最后这个想法转移了操作系统的身上。大致是：如果操作系统是由不可变值组成的会是怎样的呢？
不可变的操作系统？世界都是一直改变的
不可变值是观察世界来说是一个非常合理的方式。作为一个观察者，你看着这个世界随着时间流逝在不停的变化。当你想要做些什么的时候，你会拍下张照片。这个照片是静止的，你愿意花多长时间去分析它都无所谓。
再回到操作系统这个话题上来。在这里唯一可变的只有一个交换操作。你会有一个叫原子(atom)这么个东西，它会指向一个不可变的值。你可以随时获取到它当前指向的不可变值。从原子这总能获取到一个完整的值，正如它名字所说的，它是个原子。你可以给它赋值，这样的话这个原子会指向另一个新的不可变值。你不能够直接修改某个值。原子应该有某些机制来保证，上次读完后没人进行更新的话，才能对它进行修改，这样的话，它会更可控些。
细心的读者会发现，我刚才说的其实就是Clojure里面的状态模型。这也正是我这个操作系统将要实现的，状态就是由一系列的不可变值组成的。
不可变的内存模型
那么，一个进程会拥有很多指向不可变值的原子，而所有这些值都是无法修改的。没错，这里我说的就是所有。你可以将字节序列存储到一个值里，不过这些字节是不可变的。位移操作？创建一个新的值来完成。要修改第四个字节？也是创建新值。
在这个模型里面，内存可以在进程间安全的进行共享。把一个不可变值传给另外一个进程有什么关系呢？没事。非常安全。这里也不需要什么保护性拷贝或者别的保护机制。只有原子本身需要保护。应该有一个机制来管理进程间原子共享，只有创建这个原子的进程可以去共享它。
创建进程几乎就没有任何开销。在Linux里面，fork操作有个非常聪明的写时复制（C0W）的机制，因此fork操作一开始什么也不干，一旦这两个进程有人开始修改内存里的值的时候，才会发生拷贝操作。当然这也有有一定的开销的。但如果值是不可变的话，这就完全没有任何开销了，根本就不需要进行拷贝。不可变的就是不可变的！唯一的开销就是原子本身了，可以用拷贝模式（时间复杂度是O(n)），也可以使用Linux系统的COW的机制。
如果可以进行指针运算的话就一切都完蛋了。解决方法就是对于这个操作系统上的开发语言而言，它是没有指针的。指针还会占内存，我们可不喜欢占地方的东西。我们要存储的只是值。
当然了，还可以进行许多优化。Clojure有一个transients的概念，它的意思是”当你在一个函数里创建一个值的时候，你可以对它进行修改，一旦它从函数里返回了，它就是不可变的。因此从外面看来，函数没有修改任何范西，因为这个可变的值只是函数内部可见的。我会替你自动检测这个。我们还可以监测是否有别人引用了你的值，如果没有的话，你可以对这些值进行修改。这只是一个优化，对程序员来说完全是不可见的。
垃圾回收
一个不可变值组成的系统也是需要垃圾回收的。这些都会在系统底层来完成。
如果垃圾回收器知道所有这些值都是不可变的，那么事情就非常有意思了。一般来说，垃圾回收器在整理老生代堆的内存碎片的时候，会暂停所有的操作（stop the world)。当所有值都不可变的时候，如果要碎片整理，你就把一个值拷贝到另一块区域，然后更新下内部的指针就好了。
还有一点，通过这种拷贝并交换指针的方式，你还可以优化内部的字节编码，而不用暂停程序的运行。假设我们发现老生代中的值X是一个map，并且它已经很久没有更新了。或话我们可以把它优化成某种结构，也就是把它拷贝到内存中另外一个地方，不过用一种不同的可能是更高效的方式来进行存储。除了内核没人知道这事，也不需要暂停程序的执行。
性能
我们一直都在努力能更好的与硬件进行协作以提升性能。事实上，尽可能把操作系统的C代码来硬件来实现。我有一个荒谬的想法就是让英特尔在硬件层来实现我这个操作系统，观众席上有人大声高喊，”我们终于可以用XXX换掉我们的内存啦！“或者类似的。我不是一个硬件工程师。那么在硬件里实现不可变值的垃圾回收？想想罢了。
这并不是说我自己不去提升性能。也许这个操作系统在某些方面比传统的操作系统性能要好，因为它不需要写时复制或者保护性拷贝，它的值可以*的共享。在处理器看来，代码也是不可变的，缓存了代码的处理器的效率可比缓存了数据的要快得多。如果CPU知道内存中的哪些数据页是不可变的话，那么一级缓存和二级缓存应该会高效得多。或许我们可以通过将数据拷贝到不同的芯片上来解决冯诺依曼体系的瓶颈问题？因为这是完全不可变的数据，你可以放心的去拷贝。不过谁知道的，时间或许能证明这一切。
文件系统
这块想的不是很多。说实话我自己很少在程序中使用文件，我一般直接访问数据库。所以我想这个系统的持久层应该是一个key/value的数据库。或许跟Datomic那样只能追加数据，不能修改？又或者在这个不可变系统里，文件系统也存储在一个不可变的地方？好吧，谁知道呢。
开发语言
当然是Lisp。我会为Lisp定制一种字节码格式，可能会和EDN很像。这不完全是编译后的字节码，所以字节码这个说法可能欠妥。我的想法是Lisp的抽象语法树（AST)应该用一种编码后的巧妙的格式存储，而不仅仅是纯文本。纯文本太痛苦了。最后会有一个JIT编译器来读取这种格式，然后编译成本地的机器码。
代码当然是不可变的。因此可以放心去做热部署，已有的代码会继续运行，新的调用会分发到新部署的代码上。
没想好应该用静态语言还是动态语言。哪个更容易实现就用哪个吧。
再强调一遍，这个系统看起来很像是Clojure的一个衍生物。我也不太确定是不是就用Clojure作为开发语言就好了（Clojure已经移植到不同的平台上了，JS,JVM,CLR)。还是那句话，谁知道呢。
这很可能是个错误的想法
这是我写的第一个操作系统。
很有可能我讲的每一点都是错的。这也正是我实现它的原因。这只是一个研究性的项目，没有什么实际的目的，比如解决程序缺陷过多什么的。我只能说，这只是一个爱好，不会像GNU那样那么专业全面。在我证明这个想法可行之前，不会考虑到什么会议上去分享这些想法。
这个系统还有很长的路要走，因此现在实现的东西还不多。等我先把进程和GC这块搞完再向大家汇报进度吧。
原创文章转载请注明出处：http://it.deepinmind.com
英文原文链接
大概一年以前，我有一个想法，就是基于不可变值实现OpenGL的渲染器。我把这个想法发到博客上了，并且在Hacker News和Reddit上得到了不少关注。还有些人甚至给我发来了邮件。
在吊床上思考了很长一段时间后，最后这个想法转移了操作系统的身上。大致是：如果操作系统是由不可变值组成的会是怎样的呢？
不可变的操作系统？世界都是一直改变的
不可变值是观察世界来说是一个非常合理的方式。作为一个观察者，你看着这个世界随着时间流逝在不停的变化。当你想要做些什么的时候，你会拍下张照片。这个照片是静止的，你愿意花多长时间去分析它都无所谓。
再回到操作系统这个话题上来。在这里唯一可变的只有一个交换操作。你会有一个叫原子(atom)这么个东西，它会指向一个不可变的值。你可以随时获取到它当前指向的不可变值。从原子这总能获取到一个完整的值，正如它名字所说的，它是个原子。你可以给它赋值，这样的话这个原子会指向另一个新的不可变值。你不能够直接修改某个值。原子应该有某些机制来保证，上次读完后没人进行更新的话，才能对它进行修改，这样的话，它会更可控些。
细心的读者会发现，我刚才说的其实就是Clojure里面的状态模型。这也正是我这个操作系统将要实现的，状态就是由一系列的不可变值组成的。
不可变的内存模型
那么，一个进程会拥有很多指向不可变值的原子，而所有这些值都是无法修改的。没错，这里我说的就是所有。你可以将字节序列存储到一个值里，不过这些字节是不可变的。位移操作？创建一个新的值来完成。要修改第四个字节？也是创建新值。
在这个模型里面，内存可以在进程间安全的进行共享。把一个不可变值传给另外一个进程有什么关系呢？没事。非常安全。这里也不需要什么保护性拷贝或者别的保护机制。只有原子本身需要保护。应该有一个机制来管理进程间原子共享，只有创建这个原子的进程可以去共享它。
创建进程几乎就没有任何开销。在Linux里面，fork操作有个非常聪明的写时复制（C0W）的机制，因此fork操作一开始什么也不干，一旦这两个进程有人开始修改内存里的值的时候，才会发生拷贝操作。当然这也有有一定的开销的。但如果值是不可变的话，这就完全没有任何开销了，根本就不需要进行拷贝。不可变的就是不可变的！唯一的开销就是原子本身了，可以用拷贝模式（时间复杂度是O(n)），也可以使用Linux系统的COW的机制。
如果可以进行指针运算的话就一切都完蛋了。解决方法就是对于这个操作系统上的开发语言而言，它是没有指针的。指针还会占内存，我们可不喜欢占地方的东西。我们要存储的只是值。
当然了，还可以进行许多优化。Clojure有一个transients的概念，它的意思是”当你在一个函数里创建一个值的时候，你可以对它进行修改，一旦它从函数里返回了，它就是不可变的。因此从外面看来，函数没有修改任何范西，因为这个可变的值只是函数内部可见的。我会替你自动检测这个。我们还可以监测是否有别人引用了你的值，如果没有的话，你可以对这些值进行修改。这只是一个优化，对程序员来说完全是不可见的。
垃圾回收
一个不可变值组成的系统也是需要垃圾回收的。这些都会在系统底层来完成。
如果垃圾回收器知道所有这些值都是不可变的，那么事情就非常有意思了。一般来说，垃圾回收器在整理老生代堆的内存碎片的时候，会暂停所有的操作（stop the world)。当所有值都不可变的时候，如果要碎片整理，你就把一个值拷贝到另一块区域，然后更新下内部的指针就好了。
还有一点，通过这种拷贝并交换指针的方式，你还可以优化内部的字节编码，而不用暂停程序的运行。假设我们发现老生代中的值X是一个map，并且它已经很久没有更新了。或话我们可以把它优化成某种结构，也就是把它拷贝到内存中另外一个地方，不过用一种不同的可能是更高效的方式来进行存储。除了内核没人知道这事，也不需要暂停程序的执行。
性能
我们一直都在努力能更好的与硬件进行协作以提升性能。事实上，尽可能把操作系统的C代码来硬件来实现。我有一个荒谬的想法就是让英特尔在硬件层来实现我这个操作系统，观众席上有人大声高喊，”我们终于可以用XXX换掉我们的内存啦！“或者类似的。我不是一个硬件工程师。那么在硬件里实现不可变值的垃圾回收？想想罢了。
这并不是说我自己不去提升性能。也许这个操作系统在某些方面比传统的操作系统性能要好，因为它不需要写时复制或者保护性拷贝，它的值可以*的共享。在处理器看来，代码也是不可变的，缓存了代码的处理器的效率可比缓存了数据的要快得多。如果CPU知道内存中的哪些数据页是不可变的话，那么一级缓存和二级缓存应该会高效得多。或许我们可以通过将数据拷贝到不同的芯片上来解决冯诺依曼体系的瓶颈问题？因为这是完全不可变的数据，你可以放心的去拷贝。不过谁知道的，时间或许能证明这一切。
文件系统
这块想的不是很多。说实话我自己很少在程序中使用文件，我一般直接访问数据库。所以我想这个系统的持久层应该是一个key/value的数据库。或许跟Datomic那样只能追加数据，不能修改？又或者在这个不可变系统里，文件系统也存储在一个不可变的地方？好吧，谁知道呢。
开发语言
当然是Lisp。我会为Lisp定制一种字节码格式，可能会和EDN很像。这不完全是编译后的字节码，所以字节码这个说法可能欠妥。我的想法是Lisp的抽象语法树（AST)应该用一种编码后的巧妙的格式存储，而不仅仅是纯文本。纯文本太痛苦了。最后会有一个JIT编译器来读取这种格式，然后编译成本地的机器码。
代码当然是不可变的。因此可以放心去做热部署，已有的代码会继续运行，新的调用会分发到新部署的代码上。
没想好应该用静态语言还是动态语言。哪个更容易实现就用哪个吧。
再强调一遍，这个系统看起来很像是Clojure的一个衍生物。我也不太确定是不是就用Clojure作为开发语言就好了（Clojure已经移植到不同的平台上了，JS,JVM,CLR)。还是那句话，谁知道呢。
这很可能是个错误的想法
这是我写的第一个操作系统。
很有可能我讲的每一点都是错的。这也正是我实现它的原因。这只是一个研究性的项目，没有什么实际的目的，比如解决程序缺陷过多什么的。我只能说，这只是一个爱好，不会像GNU那样那么专业全面。在我证明这个想法可行之前，不会考虑到什么会议上去分享这些想法。
这个系统还有很长的路要走，因此现在实现的东西还不多。等我先把进程和GC这块搞完再向大家汇报进度吧。
原创文章转载请注明出处：http://it.deepinmind.com
英文原文链接
上一篇： ThreadSafe:诊断并发问题的利器 java
下一篇： mongdb之mapreduce操作