xiaodang's blog|

今天研究了一下Node使用的异步IO框架libuv,下面一张图显示了livuv在Node架构中的位置。

libuv是什么

libuv是一个高性能的，事件驱动的I/O库，并且提供了跨平台（如windows, linux）的API。

libuv架构

左侧部分是网络I/O相关的请求，右侧部分是由文件I/O, DNS Ops以及User code组成的请求。对于Network I/O和以File I/O为代表的另一类请求，异步处理的机制是不一样的。

对于Network I/O相关的请求， 根据OS平台不同，分别使用Linux上的epoll，OSX和BSD类OS上的kqueue，SunOS上的event ports以及Windows上的IOCP机制。

而对于File I/O为代表的请求，则使用thread pool。利用thread pool的方式实现异步请求处理，在各类OS上都能获得很好的支持。

I/O loop

在并发场景下，经常需要对某些资源进行互斥的操作。在单服务器系统我们常用本地锁来避免并发带来的问题，然而，当服务采用集群方式部署时，本地锁无法在多个服务器之间生效，这时候保证数据的一致性就需要分布式锁来实现。

比如用户在网页和手机端同时下单，对余额进行减操作，如果没有合理的锁对余额进行保护，那最终用户对余额很有可能就会变得错乱。

1
2
3
4
5
6
7

用户A网页端                               用户A手机端

1 balance=db.getUserBalance()
2                                        balance=db.getUserBalance()
3 db.saveUserBalance(balance-100)
4                                        db.saveUserBalance(balance-100)

redis单例模式下的正确实现

要正确的实现锁，必须保证:

• 互斥 - 同一时间只能有一个客户端持有锁
• 无死锁 - 即使锁定资源的客户端崩溃了，其他客户端也可以获得锁
• 锁的身份验证 - 锁的释放必须由锁的持有客户端释放，保证锁的安全释放

在redis中可以通过设置SET NX PX 给资源上锁，NX表示只会在资源不存在的情况下设置成功，PX表示这个资源的过期时间(单位:毫秒),同时key的值被设置成了一个随机的值，这个值必须在所有的客户端中保证唯一。

1

SET resource_name my_random_value NX PX 30000

NX保证了资源的互斥

PX保证了无死锁。即便持有锁的客户端崩溃了，也会在过期时间之后，释放锁

在计算机程序设计中，哈希函数(又名散列函数)把文本或者其他数据映射为整数。通常不同的输入对应不同的输出，但是有时候会发生碰撞(collision碰撞就是不同的输入对应相同的输出)。

加密哈希函数把文本或者二进制数据转化为固定长度的哈希值，并且具有抗碰撞性和不可逆性。

软件工程里的哈希

在程序中哈希函数通常被用来实现数据结构hash-table（哈希表，或者关联数组，或者字典）。

python中的数据类型dict：

1

dict={"name":"xiaoye","age":29}

加密哈希函数

在密码学中，哈希函数将任意大小的输入数据(例如文本消息)转换为固定大小的结果(例如256位)，被称为哈希值(或哈希码、消息摘要)。在计算机密码学中使用的哈希函数(哈希算法)被称为“加密哈希函数”。SHA3-256就是一个加密哈希函数，把任意输入转化为256位，例如，我们可以使用它计算helloworld的哈希值。

1
2
3
4

import hashlib,binascii
sha3_256hash=hashlib.sha3_256('helloworld'.encode('ascii')).digest()
print("SHA3-256('helloworld') =", binascii.hexlify(sha3_256hash))
# output:92dad9443e4dd6d70a7f11872101ebff87e21798e4fbb26fa4bf590eb440e71b

安全哈希函数

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

1
2
3
4
5
6
7
8

            1
          /   \
         2      3
        / \    / \ 
       4   5  6   7
                   \
                    8
output: 4

1
2
3
4
5
6
7
8
9

//递归实现
function maxDepth(node){
    if(node==null){//终止条件terminating case
        return 0;
    }
    let lefeDepth=maxDepth(node.left);
    let rightDepth=maxDepth(node.right);
    return Math.max(lefeDepth,rightDepth)+1;
}

今天花了一下午时间看了一个JavaScript编译器的实现，并且自己亲手实现了一遍。非常简单的微型编译器，但是却包含了编译器基本的工作流程。一般我们几乎不太能接触到开发编译器工作，但是通过了解编译器的实现原理对我们还是非常有帮助。

编译器介绍

compiler是将一种语言转换为另外一种语言的程序。

编译器原理

大部分编译器的工作可以分为三个阶段：

1. Parsing解析 - 解析分为词法分析(Lexical Analysis)和语法分析(Syntactic Analysis)。解析的主要工作是把源代码转换为更加抽象的代码(Abstract Syntax Tree 简称 AST)
2. Transformation 转换 - 转换是对AST进行处理，方便后续的代码生成
3. Code Generation 代码生成 - 这一步将新的AST转化为新的代码

   1 2 3 4 5 6 7 8

   //编译流程 function compiler(input) { let tokens = tokenize(input);//词法分析 let ast = parser(tokens);//语法分析 let newAst = transformer(ast);//ast转换 let output = codeGenerator(newAst);//代码生成 return output; }

实现目标

目标是把lisp代码编译为C的代码

1
2

*   算术            LISP                      C
*   3 + (4 - "2")    (add 3 (subtract 4 "2"))    add(3, subtract(4, "2"))

解析

由于最近换了新的电脑(MacBookPro 16inch),许多开发环境需要重新配置，记录一下安装的软件。

环境配置原则

• 软件方便统一管理，安装、升级
• 优先选择开源的软件
• 尽量不污染系统环境

软件

brew

macOS上的包管理工具，很多软件(包括GUI)都可以通过brew来进行安装，卸载，更新。$ brew install用来安装命令行工具，$ brew cask install用来安装GUI工具。

clashx

一款开源的代理软件 安装:$ brew cask install clashx

neofetch