修改FTP用户密码

记得ftp账号,但不记得密码怎么办?

由于需要在wordpress站点里安装插件,但是ftp密码忘记了,所以需要修改ftp密码。

  1. 切换到root用户下:sudo su
  2. 更新密码:passwd bobo(ftp用户名),可以先cat /etc/shadow查看一下此用户是否存在
  3. 提示:
Enter new UNIX password:
Retype new UNIX password:
passwd: password updated successfully

修改完成。

PHP7变量的内部实现(一)

注:
1. 转载自这,方便留存查看
2. 转载文章翻译自Nikita的文章,欢迎指正查看原文
3. 我准备翻译第二部分


受篇幅限制,这篇文章将分为两个部分。本部分会讲解PHP5和PHP7在zval结构体的差异,同时也会讨论引用的实现。第二部分会深入探究一些数据类型如string和对象的实现。

PHP5中的zval
PHP5中zval结构体的定义如下:

typedef struct _zval_struct {
    zvalue_value value;
    zend_uint refcount__gc;
    zend_uchar type;
    zend_uchar is_ref__gc;
} zval;

可以看到,zval由value、type和一些额外的__gc信息组成。__gc与垃圾回收相关,我们稍后讨论。value是一个共用体,可以存储一个zval各种可能的值。

typedef union _zvalue_value {
    long lval;                 // For booleans, integers and resources
    double dval;               // For floating point numbers
    struct {                   // For strings
        char *val;
        int len;
    } str;
    HashTable *ht;             // For arrays
    zend_object_value obj;     // For objects
    zend_ast *ast;             // For constant expressions
} zvalue_value;

C语言中,共用体的尺寸与它最大的成员尺寸相同,在某一时刻只能有一个成员处于活动状态。共用体所有的成员都存储在相同的内存,根据你访问的成员不同,内容会被解释成不同的类型。以上面的共用体为例,如果访问lval,值将被解释为一个有符号整型;而访问dval将被解释成双精度浮点型。以此类推。

为了弄清结构体中哪个成员处于活动状态,zval会存储一个整型type来标识具体的数据类型。

#define IS_NULL     0      /* Doesn't use value */
#define IS_LONG     1      /* Uses lval */
#define IS_DOUBLE   2      /* Uses dval */
#define IS_BOOL     3      /* Uses lval with values 0 and 1 */
#define IS_ARRAY    4      /* Uses ht */
#define IS_OBJECT   5      /* Uses obj */
#define IS_STRING   6      /* Uses str */
#define IS_RESOURCE 7      /* Uses lval, which is the resource ID */

/* Special types used for late-binding of constants */
#define IS_CONSTANT 8
#define IS_CONSTANT_AST 9

PHP5中的引用计数
除少数例外,在PHP5中zval都是分配在堆内存的,PHP需要通过某种方式跟踪哪些zval在被使用,哪些应该被释放。为达到这个目的,引用计数被使用。引用计数即在结构体中用refcount__gc成员来记录该结构体被“引用”了多少次。例如,在$a = $b = 42中,42被两个变量引用,所以它的引用计数为2。如果引用计数变成0,则意味着该值没被使用,可以被释放。

需要注意的是引用计数的“引用”(即一个值被引用的次数)与“PHP引用”($a=&$b)毫无关系。在接下来的内容里,我会始终使用“引用”和“PHP引用”这两个术语来释疑这两个概念。就当前来说,我们先把“PHP引用”放在一边。

与引用计数密切相关的一个概念是“写时复制”(copy on write):zval只能在其内容未被修改的时候才能在多个变量间共享。要实现修改,zval必选被复制(分离),而改动只能在复制出的zval上进行。

以下例子展示了写时复制和zval销毁。

$a = 42;   // $a         -> zval_1(type=IS_LONG, value=42, refcount=1)
$b = $a;   // $a, $b     -> zval_1(type=IS_LONG, value=42, refcount=2)
$c = $b;   // $a, $b, $c -> zval_1(type=IS_LONG, value=42, refcount=3)

// 下一行操作会导致zval分离
$a += 1;   // $b, $c -> zval_1(type=IS_LONG, value=42, refcount=2)
           // $a     -> zval_2(type=IS_LONG, value=43, refcount=1)

unset($b); // $c -> zval_1(type=IS_LONG, value=42, refcount=1)
           // $a -> zval_2(type=IS_LONG, value=43, refcount=1)

unset($c); // zval_1 被销毁,因为其refcount=0
           // $a -> zval_2(type=IS_LONG, value=43, refcount=1)

引用计数有一个致命缺陷:它不能检测和释放循环引用。为解决这个问题,PHP额外使用了环收集器。当一个zval的引用计数减少的时候,它就有一定几率是循环引用的一部分,该zval就被写入到“根缓冲区”。当根缓冲区满后,可能的引用环将被标记并收集,同时启动垃圾回收。

为了支持这个环收集器,实际使用了如下的zval结构体:

typedef struct _zval_gc_info {
    zval z;
    union {
        gc_root_buffer       *buffered;
        struct _zval_gc_info *next;
    } u;
} zval_gc_info;

zval_gc_info结构体内置了普通zval和一个指针-注意u是一个共用体,也就是说实际上只有一个指针,它可能指向两种不同的类型。buffered指针用来存储zval在根缓冲区中的引用位置,如果zval在环收集器运行之前就被销毁(这是非常可能的),那么该指针将会从根缓冲区移除。next指针在收集器销毁值的时候会被用到,但是我不会深入讲解这一点。

改进的动机
先讨论一下基于64位系统的内存占用。首先,zvalue_value共用体占用16个字节,因为它的str和obj成员都那么大。整个zval结构体一共24个字节(由于内存对齐[padding]),而zval_gc_info是32字节。除此之外,在堆分配的过程中,又增加了16字节的分配开销。由此一个zval就占用48字节--尽管该zval可能在多个地方都被用到。

现在我们就可以分析下这种zval实现方式低效的地方。考虑用zval存储整数的情况,整数占用8个字节,另外类型标示是必需的,它本身占用一个字节,但是由于内存对齐,实际上就要加上8个字节。

这16字节是我们真正“需要”的空间(近似的),此外,为了处理引用计数和垃圾回收,我们增加了16字节;由于分配开销又增加了另外16字节。更不用提还要处理分配和后续的释放,这都是很昂贵的操作。

由此引发了一个问题:一个简单的整数真的需要存储为一个有引用计数、可垃圾回收,并且是堆分配的值吗?答案当然是不需要,这样做是没道理的。

以下概述了PHP5中zval实现方式的一些主要问题:

zval(几乎)总是需要堆分配。
zval总是会被引用计数且携带环收集信息,即使是在共享值不划算(比如整数)和不能形成引用环的情况下。
当处理对象和资源时,直接对zval进行引用计数会导致双重计数。原因会在下一部分讨论。
某些情况会引入很多的间接操作。比如为了访问一个对象,一共要进行4次指针跳转。这也将在下一篇中分析。
直接对zval进行引用计数意味着值只能在zval间共享。比如我们不能在zval和哈希表key之间共享一个字符串(不将哈希表key用zval变量存放)。
PHP7中的zval
通过以上讨论,我们引进了PHP7新的zval实现。最根本的改变是zval不再是堆分配且它自身不再存储引用计数。相反的,对zval指向的任何复杂类型值(如字符串、数组、对象),这些值将自己存储引用计数。这有以下优点:

简单值不需要分配且不用引用计数。
不再有双重引用计数。对对象来说,只有在对象本身存在引用计数。
由于引用计数保存在值中,这个可以独立于zval结构而被复用。同一个字符串能同时被zval和哈希表key引用。
间接操作少了很多,也就是说在获取一个值的时候需要跳转的指针数量变少了。
新的zval定义如下:

struct _zval_struct {
    zend_value value;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar type,
                zend_uchar type_flags,
                zend_uchar const_flags,
                zend_uchar reserved)
        } v;
        uint32_t type_info;
    } u1;
    union {
        uint32_t var_flags;
        uint32_t next;                 // hash collision chain
        uint32_t cache_slot;           // literal cache slot
        uint32_t lineno;               // line number (for ast nodes)
        uint32_t num_args;             // arguments number for EX(This)
        uint32_t fe_pos;               // foreach position
        uint32_t fe_iter_idx;          // foreach iterator index
    } u2;
};

第一个成员跟之前类似,也是一个value共同体。第二个成员是个整数,用来存储类型信息,它被一个共用体分隔成独立的字节空间(可忽略ZEND_ENDIAN_LOHI_4宏,它是用来保证在不同字节序平台上布局的一致性)。这个子结构中type(它跟之前类似)和type_flags比较重要,我将稍后讨论他们。

此时有一个小问题:value成员占8字节空间,由于结构体内存对齐,即使增加一个字节也会让zval内存增长到16字节。然而很明显我们不需要8个字节来仅仅存放类型信息。这就是为什么此zval包含了一个额外的u2共用体,它默认情况下是没被占用的,但是却可以根据需要存储4字节的数据。这个共用体中不同的成员用来实现该额外数据片段不同的用途。

PHP7中的value共用体看起来略有不同:

typedef union _zend_value {
    zend_long         lval;
    double            dval;
    zend_refcounted  *counted;
    zend_string      *str;
    zend_array       *arr;
    zend_object      *obj;
    zend_resource    *res;
    zend_reference   *ref;
    zend_ast_ref     *ast;

    // Ignore these for now, they are special
    zval             *zv;
    void             *ptr;
    zend_class_entry *ce;
    zend_function    *func;
    struct {
        ZEND_ENDIAN_LOHI(
            uint32_t w1,
            uint32_t w2)
    } ww;
} zend_value;

首先要注意到这个共用体占用8字节而不是16字节。它仅仅会直接存储整数(lval)和双精度浮点数(dval),对其它类型它都会存储对应指针。所有的指针类型(除了什么代码中标记为特殊的)都会引用计数并且有一个通用的头部,定义为zend_refcounted:

struct _zend_refcounted {
    uint32_t refcount;
    union {
        struct {
            ZEND_ENDIAN_LOHI_3(
                zend_uchar    type,
                zend_uchar    flags,
                uint16_t      gc_info)
        } v;
        uint32_t type_info;
    } u;
};

不用说这个结构会包含引用计数。另外,它还包含type、flags和gc_info。type是复制的zval的type,它使得GC在不存储zval的情况下就能区分不同的引用计数结构。根据类型的不同,flags有不同的使用目的,这些会在下一部分按类型分别讨论。

gc_info等同于老zval中的buffered成员。不同的是它存储了在根缓冲区中的索引,来代替之前的指针。因为跟缓冲区尺寸固定(10000个元素),用16字节的数子而不是64位的指针就足够了。gc_info还含有该节点的“颜色”信息,这在垃圾回收中用来标记节点。

zval内存管理
我已经提到zval不再是单独的堆分配。然而很明显它仍然需要被存在某个地方,那么这是怎么实现的呢?尽管zval大多数时候仍是堆分配数据结构的一部分,不过它们是直接嵌入到这些数据结构中的。比如哈希表就会直接内置zval而不是存放一个指向另一zval的指针。函数的编译变量表或者对象的属性表会直接保存为一个拥有连续内存的zval数组,而不再存储指向散落各处zval的指针。因此当前的zval存储通常都会少了一层的间接引用,也就是说现在的zval相当于之前的zval*。

当一个zval在新的地方被引用时,按照之前的方式,就意味着要复制zavl*并增加它的引用计数。现在则需要复制zval的内容,同时如果该zval指向的值用到引用计数的话则还要增加该值的引用计数。

PHP是如何知道一个值是否用到引用计数的呢?这不能仅仅依靠类型来判断,因为有些类型比如字符串和数组并不总是引用计数的。相反的,会根据构成zval的type_info的一个字节来判断是否引用计数。另外还有其它几个字节编码了该类型的一些特征。

#define IS_TYPE_CONSTANT            (1<<0)   /* special */
#define IS_TYPE_IMMUTABLE           (1<<1)   /* special */
#define IS_TYPE_REFCOUNTED          (1<<2)
#define IS_TYPE_COLLECTABLE         (1<<3)
#define IS_TYPE_COPYABLE            (1<<4)
#define IS_TYPE_SYMBOLTABLE         (1<<5)   /* special */

一个类型能拥有的三个主要特征是引用计数、可回收和可复制。引用计数的含义已讨论过,可回收意味着该zval可能参与循环引用。举例来说,字符串(通常)是引用计数的,但是却没法用字符串构造一个引用环。

可复制性决定了在为一个变量创建“副本”的时候它的值是否需要执行拷贝。副本是硬拷贝,比如复制指向数组的zval时,就不是简单的增加数组的引用计数,而是要创建该数组的一个新的独立拷贝。然而对对象和资源这些类型来说,复制应该仅仅增加引用计数--这些类型就是所谓的不可复制。这与对象和资源在进行传递时的语义相符(当前不是引用传递)。

以下表格展示了不同类型和它们所用的标识。“简单类型”指整数和布尔值这类不需要用指针指向一个单独结构的类型。同时还用一列展示了“不可变”标记,它用来标记不可变数组,这将在下一部分详细讨论。

refcounted collectable copyable immutable
simple types
string x x
interned string
array x x x
immutable array x
object x x
resource x
reference x

来看一下在实际中zval管理是如何工作的。先基于上文PHP5的例子来讨论一下整型实现:

$a = 42;   // $a = zval_1(type=IS_LONG, value=42)

$b = $a;   // $a = zval_1(type=IS_LONG, value=42)
           // $b = zval_2(type=IS_LONG, value=42)

$a += 1;   // $a = zval_1(type=IS_LONG, value=43)
           // $b = zval_2(type=IS_LONG, value=42)

unset($a); // $a = zval_1(type=IS_UNDEF)
           // $b = zval_2(type=IS_LONG, value=42)

这个例子挺无趣的。简单来说就是整型不会再被共用,这些变量都有单独的zval。不要忘了zval不再需要单独分配,它们是内嵌的,我通过把->换成=来表示这种变化。unset一个变量会把对应zval的type设置为IS_UNDEF。现在来考虑一下当涉及复杂类型时的情况,这种案例有趣的多。

$a = [];   // $a = zval_1(type=IS_ARRAY) -> zend_array_1(refcount=1, value=[])

$b = $a;   // $a = zval_1(type=IS_ARRAY) -> zend_array_1(refcount=2, value=[])
           // $b = zval_2(type=IS_ARRAY) ---^

// zval在这里发生了分离
$a[] = 1   // $a = zval_1(type=IS_ARRAY) -> zend_array_2(refcount=1, value=[1])
           // $b = zval_2(type=IS_ARRAY) -> zend_array_1(refcount=1, value=[])

unset($a); // $a = zval_1(type=IS_UNDEF) and zend_array_2 is destroyed
           // $b = zval_2(type=IS_ARRAY) -> zend_array_1(refcount=1, value=[])

本例中每个变量依然有单独的zval(内嵌的),但是这些zval都指向了同一个zend_array(引用计数的)结构。同PHP5一样,当发生修改时,数组需要被复制。

类型
看一下PHP7是如何支持各种数据类型的:

// regular data types
#define IS_UNDEF                    0
#define IS_NULL                     1
#define IS_FALSE                    2
#define IS_TRUE                     3
#define IS_LONG                     4
#define IS_DOUBLE                   5
#define IS_STRING                   6
#define IS_ARRAY                    7
#define IS_OBJECT                   8
#define IS_RESOURCE                 9
#define IS_REFERENCE                10

// constant expressions
#define IS_CONSTANT                 11
#define IS_CONSTANT_AST             12

// internal types
#define IS_INDIRECT                 15
#define IS_PTR                      17

这个列表跟PHP5类似,但有一些内容增加:

IS_UNDEF类型替代了之前的NULL zval指针(注意与IS_NULL zval区分),比如在上面引用计数的例子中,变量被unset时,zval的类型就被置为IS_UNDEF。
IS_BOOL类型被细分成了IS_FALSE和IS_TRUE。由此布尔变量的值就被编码在类型中,这就使得一些基于类型检查的优化成为可能。这个改变对用户层是透明的,仍然有一个“布尔”类型。
在zval上,PHP引用不再使用is_ref标识,而是用IS_REFERENCE类型。下一部分将会讨论。
IS_INDIRECT和IS_PTR是特殊的内部类型。
IS_LONG目前存储的是zend_long类型的值,而不是一个普通的C语言long整数。原因是在64位windows(LLP64)上,long型只有32位,于是在windows上PHP5的IS_LONG总是32位的。在64位操作系统上,即使你使用的是windows,PHP7都允许你使用64位的数字。

zend_refcounted类型相关的细节将在下一部分讨论,现在我们先看一下PHP引用的实现。

引用
PHP7处理PHP引用(&)的方式与PHP5完全不同(我可以告诉你这个改变是PHP7最大的bug来源之一)。PHP5中引用的实现如下:

通常,写时复制(COW)机制意味着在修改之前,zval要先进行分离,以保证不会把其它共用该zval的变量给一起修改了。这与值传递的语义相符。

对PHP引用来说,就不是这种情况了。如果一个值是引用,那么修改的时候就希望其它变量也同步被修改。PHP5用is_ref来判断一个值是不是PHP引用,以及在修改的时候是否要执行分离操作。看一个例子:

$a = [];  // $a     -> zval_1(type=IS_ARRAY, refcount=1, is_ref=0) -> HashTable_1(value=[])
$b =& $a; // $a, $b -> zval_1(type=IS_ARRAY, refcount=2, is_ref=1) -> HashTable_1(value=[])

$b[] = 1; // $a = $b = zval_1(type=IS_ARRAY, refcount=2, is_ref=1) -> HashTable_1(value=[1])

这种设计一个很重大的问题就是不能在普通变量和PHP引用之前共享一个值。考虑如下情形:

$a = [];  // $a         -> zval_1(type=IS_ARRAY, refcount=1, is_ref=0) -> HashTable_1(value=[])
$b = $a;  // $a, $b     -> zval_1(type=IS_ARRAY, refcount=2, is_ref=0) -> HashTable_1(value=[])
$c = $b   // $a, $b, $c -> zval_1(type=IS_ARRAY, refcount=3, is_ref=0) -> HashTable_1(value=[])

$d =& $c; // $a, $b -> zval_1(type=IS_ARRAY, refcount=2, is_ref=0) -> HashTable_1(value=[])
          // $c, $d -> zval_1(type=IS_ARRAY, refcount=2, is_ref=1) -> HashTable_2(value=[])
          // $d是$c的引用, 但不是$a和$b的引用,所以zval要复制。
          //现在就有了相同的zval,一个is_ref=0,一个is_ref=1

$d[] = 1; // $a, $b -> zval_1(type=IS_ARRAY, refcount=2, is_ref=0) -> HashTable_1(value=[])
          // $c, $d -> zval_1(type=IS_ARRAY, refcount=2, is_ref=1) -> HashTable_2(value=[1])
          // 由于有两个独立的zval $d[] = 1 不会修改到$a和$b.

这种行为就导致使用PHP引用通常比普通变量更慢。下面的例子就有这个问题:

$array = range(0, 1000000);
$ref =& $array;
var_dump(count($array)); // <-- 这里发生zval分离

因为count()的参数是按值传递的,而$array是一个引用变量,在把它传递给count()时,会对该数组执行完整的复制。如果$array不是引用,它的值就可以共用,在传递的时候就不会发生复制。

现在来看下PHP7中引用的实现。由于zval不再是独立分配,不再可能使用PHP5一样的方式。转而增加了IS_REFERENCEl类型,它的值是如下的zend_reference结构:

struct _zend_reference {
    zend_refcounted   gc;
    zval              val;
};

所以zend_reference本质上只是一个有引用计数的zval。在一个引用集合中所有的变量都会保存一份IS_REFERENCEl类型的zval,并且指向同一个zend_reference实例。val跟其他zval类似,特别是它可以共享其指向的复杂值。比如数组可以在普通变量和引用变量之间共享。

还是上面的示例代码,来看一下在PHP7下的情形。为了简洁性,我不会再写变量的zval,只展示它们指向的值。

$a = [];  // $a                                     -> zend_array_1(refcount=1, value=[])
$b =& $a; // $a, $b -> zend_reference_1(refcount=2) -> zend_array_1(refcount=1, value=[])

$b[] = 1; // $a, $b -> zend_reference_1(refcount=2) -> zend_array_1(refcount=1, value=[1])

引用赋值会创建一个zend_reference,该引用的引用计数是2(有两个变量用到了这个引用),但是值本身的引用计数是1(只有一个zend_reference指向了该值)。再考虑下引用变量和普通变量混合的情况:

$a = [];  // $a         -> zend_array_1(refcount=1, value=[])
$b = $a;  // $a, $b,    -> zend_array_1(refcount=2, value=[])
$c = $b   // $a, $b, $c -> zend_array_1(refcount=3, value=[])

$d =& $c; // $a, $b                                 -> zend_array_1(refcount=3, value=[])
          // $c, $d -> zend_reference_1(refcount=2) ---^
          // 注意所有的变量共享同一个zend_array, 即使有的是引用,有的不是。

$d[] = 1; // $a, $b                                 -> zend_array_1(refcount=2, value=[])
          // $c, $d -> zend_reference_1(refcount=2) -> zend_array_2(refcount=1, value=[1])
          // 只有当赋值发生的时候,zend_array才会复制,即写时分离。

与PHP5一个重要的不同是所有的变量都能共享同一个数组,即使有的是引用变量有的不是。只有当进行修改的时候才会发生分离。这意味着在PHP7中把一个很大的引用数组传递给count()是安全的,因为不会复制。但是引用仍然会比普通变量慢,因为需要分配zend_reference结构(以及由此产生的间接操作),而且机器码处理起来也不会很快。

总结

总的来说,PHP7主要的改变是zval不再是独立的堆分配且其本身不再存储引用计数。转而是它们指向的复杂类型的值(如字符串、数组、对象)会存储引用计数。这通常会带来更少的内存分配、间接操作和内存使用。

下一部分将会讨论其它复杂类型。

为什么有的地方拍卖价格是从高到低?

在我们常见的拍卖会上,一件物品的价格往往是由低向高叫价,但有些地方也会使用另一种方式,拍卖价由高往低叫,那你知道他们为什么要这么做吗?

要弄明白这个,就需要理解什么叫消费者剩余了。

假设你现在有一张纪念邮票,因为你不是邮票爱好者,所以你打算把邮票卖出,卖出的一种方法是举行一场拍卖会。

现在有四个集邮爱好者出现在拍卖会上:张三,李四,王五,赵六。

他们的支付意愿为:

买者 支付意愿(人民币)
张三 100
李四 80
王五 70
赵六 60

支付意愿:买者愿意为某种物品支付的最高价。

为了卖出你的纪念邮票,你从一个低价格开始叫价,比如30元。当价叫到80元(或略高一点)时,李四、王五、赵六都不愿意出更高的价格,这时张三80元获得了这张邮票。

在某种意义上来说,张三做了一笔划算的生意,本来他愿意为这张邮票出100元,而现在他只出了80元。对此我们说,张三获得了20元的消费者剩余

消费者剩余是指买者愿意为一种物品支付的价格减去其为此实际支付的价格。

在上个例子中,张三获得了20元的消费者剩余,而其他三人没有获得消费者剩余,因为他们没有得到邮票,也没有花一分钱。

现在我们把上面的情况修改一下,假如你有两张邮票,那么当张三与李四喊出70元(或略高一点)时,王五与赵六放弃,这时张三与李四花70元获得了邮票,那么张三的消费者剩余是30元,李四也获得了10元的消费者剩余

消费者剩余增加了,但你获得的利益减少了。理解了这个,我们现在看另一种拍卖方式,价格从高往低叫价:

你现在从200元开始叫价,当减少到100元时,张三愿意支付100元,交易成立,张三没有获得消费者剩余,而你获得的利益增多。这就是为什么很多地方会使用这种方式拍卖。

这种情况适用于拍卖物具有独特性,而且这也是一种理想情况,现实情况往往复杂的多。

读《经济学原理(微观)》第7章有感。

debugfs使用简述

知道具体文件,查看文件所存放的block号:
  1. 比如我现在要查看/home/sting/.Xauthority文件所占的block号,df -h 查看分区对应的系统目录
    Filesystem      Size  Used Avail Use% Mounted on
    udev            3.9G     0  3.9G   0% /dev
    tmpfs           789M   42M  748M   6% /run
    /dev/sda1        47G   32G   13G  72% /
    tmpfs           3.9G  423M  3.5G  11% /dev/shm
    tmpfs           5.0M  4.0K  5.0M   1% /run/lock
    tmpfs           3.9G     0  3.9G   0% /sys/fs/cgroup
    /dev/loop2      207M  207M     0 100% /snap/ubuntu-app-platform/34
    /dev/loop1       82M   82M     0 100% /snap/core/4206
    /dev/loop0       82M   82M     0 100% /snap/core/4017
    /dev/loop4       62M   62M     0 100% /snap/go/1473
    /dev/loop3       82M   82M     0 100% /snap/core/4110
    /dev/loop5       11M   11M     0 100% /snap/ipfs/335
    /dev/sda2       465M  396M   41M  91% /boot
    /dev/sda5       179G   59G  112G  35% /home
    /dev/sda4       976M  3.5M  972M   1% /boot/efi
    tmpfs           789M  140K  789M   1% /run/user/1000
    
  2. sudo debugfs /dev/sda5
    [sting@sting-snds]
    [:~]$ sudo debugfs /dev/sda5
    [sudo] password for sting:
    debugfs 1.42.13 (17-May-2015)
    debugfs:  pwd
    [pwd]   INODE:      2  PATH: /    # 由上一步所知,这时你所在的目录其实在/home下
    [root]  INODE:      2  PATH: /
    debugfs:  stat /sting/.Xauthority # 查看这个文件的信息,它的实际路径其实是 /home/sting/.Xauthority
        # 显示如下:
        Inode: 10485770   Type: regular    Mode:  0600   Flags: 0x80000
        Generation: 2100926769    Version: 0x00000000:00000001
        User:  1000   Group:  1000   Size: 55
        File ACL: 0    Directory ACL: 0
        Links: 1   Blockcount: 8
        Fragment:  Address: 0    Number: 0    Size: 0
         ctime: 0x5ab84844:5b09ecdc -- Mon Mar 26 09:09:24 2018
         atime: 0x5ac2db93:a9a86890 -- Tue Apr  3 09:40:35 2018
         mtime: 0x5ab84844:5b09ecdc -- Mon Mar 26 09:09:24 2018
        crtime: 0x599bcd3f:1183b45c -- Tue Aug 22 14:20:47 2017
        Size of extra inode fields: 32
        EXTENTS:
        (0):43769344  # 文件对应的块号
        (END)
    
知道block号,查看block对应的具体文件:
  1. 根据块号查找分区。查看分区情况,sudo fdisk -lu
    Device         Start       End   Sectors   Size Type
    /dev/sda1       2048  99999743  99997696  47.7G Linux filesystem
    /dev/sda2   99999744 100999167    999424   488M Linux filesystem
    /dev/sda3  100999168 117000191  16001024   7.6G Linux swap
    /dev/sda4  117000192 119001087   2000896   977M EFI System
    /dev/sda5  119001088 500117503 381116416 181.7G Linux filesystem  # End - Start = Sectors
    

    Block(4KB) = 8 * Sectors(0.5KB)b = (int)((L-S)*512/B)

    where:
    b = File System block number
    L = LBA(Logical Block Address)
    S = Starting sector of partition as shown by fdisk -lu and (int) denotes the integer part
    B = File system block size in bytes

    可知: L-S = b / (512 / B) = 43769344 / (512 / 4096) = 350154752。所以, L = 350154752 + 119001088('注:此值为/dev/sda5 Start位置') = 469155840,判断这个块号应该是在/dev/sda5里,在Start到End区间内(如果判断不了,使用下一步试一下也能知道)。

  2. 使用debugfs获取对应具体文件信息,sudo debugfs /dev/sda5

    [sting@sting-snds]
    [:~]$ sudo debugfs /dev/sda5
    [sudo] password for sting:
    debugfs 1.42.13 (17-May-2015)
    debugfs:  icheck 43769344  #如果不在这个分区,会提示 <block not found>
    Block   Inode number
    43769344    10485770
    debugfs:  ncheck 10485770
    Inode   Pathname
    10485770    /sting/.Xauthority # 文件路径
    debugfs:  q
    

archlinux下i3-wm突然登录不进去问题

今天i3-wm突然登录不进去问题(2018-03-31)

  1. 每次输入密码登录之后又回到登录界面,完全摸不着头脑,也没有看到错误信息。

  2. 后来发现是有错误提示信息,在我ctrl+alt+fx(f1~f6)切入到别的字符界面控制台之后,但是没有仔细研究这个提示,结合dmesg命令之后判断应该是磁盘有坏道造成的。

  3. 关键错误提示:

    Buffer I/O error on dev sda10, logical block 8421888print_req_error: I/O error, dev sda, sector 1449822208 这两点。

  4. 第一条信息是最关键的,可惜我一直没有重视,只看到第二条了。

  5. 看到网上有一篇文章是关于磁盘坏道修复的,使用到的工具为smartctl,安装yaourt -S gsmartcontrol

  6. 根据文章写的步骤,第一步我发现1449822208属于/dev/sda10,这时我发现了我这第3步关键错误信息提示里的与这里的/dev/sda10提示的是一样的,然后结合这篇文章,我有些明白了block 8421888的含义了。

  7. 根据上面文章里的第四步,使用工具debugfs,详见debugfs使用简述,我找到坏道这里损坏的文件是/home/sting/.Xauthority,这时突然就明白了为什么会登录不进去了

  8. Xauthority,是startx脚本记录文件。Xserver启动时,读文件~/.Xauthority,读入对应其display的记录。当一个需要显示的客户程序启动调用XOpenDisplay()也读这个文件,并把找到的magic code 发送给Xserver。当Xserver验证这个magic code正确以后,就同意连接啦。观察startx脚本也可以看到,每次startx运行,都在调用xinit以前使用了xauth的add命令添加了一个新的记录到~/.Xauthority,用来这次运行X使用认证

  9. 知道问题所在了就好办,使用startx自动生成.Xauthority文件

  10. crtl+alt+f7,重新登录果然进来了,问题解决。

总结:

  • 在登录界面登录不进来,不一定是这个问题,但这个问题会导致登录不了,又多了一个解题思路 🙂
  • 要仔细研究系统给出的错误提示信息

默克尔树(Merkle Tree)学习(转改)

Merkle Tree概念

Merkle Tree

Merkle Tree,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵树。Merkle树的叶子是数据块(例如,文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。[1]

  1. Hash
    Hash是一个把任意长度的数据映射成固定长度数据的函数[2]。例如,对于数据完整性校验,最简单的方法是对整个数据做Hash运算得到固定长度的Hash值,然后把得到的Hash值公布在网上,这样用户下载到数据之后,对数据再次进行Hash运算,比较运算结果和网上公布的Hash值进行比较,如果两个Hash值相等,说明下载的数据没有损坏。可以这样做是因为输入数据的稍微改变就会引起Hash运算结果的面目全非,而且根据Hash值反推原始输入数据的特征是困难的。[3]

    hashfunction

    如果从一个稳定的服务器进行下载,采用单一Hash是可取的。但如果数据源不稳定,一旦数据损坏,就需要重新下载,这种下载的效率是很低的。

  2. Hash List
    在点对点(p2p)网络中作数据传输的时候,会同时从多个机器上下载数据,而且很多机器可以认为是不稳定或者不可信的。为了校验数据的完整性,更好的办法是把大的文件分割成小的数据块(例如,分割成2K为单位的数据块)。这样的好处是,如果小块数据在传输过程中损坏了,那么只要重新下载这一块数据就行了,不用重新下载整个文件。

    怎么确定小的数据块有没有损坏呢?只需要为每个数据块做Hash。BT下载的时候,在下载到真正数据之前,我们会先下载一个Hash列表。那么问题又来了,怎么确定这个Hash列表本身是正确的呢?

    答案是把每个小块数据的Hash值拼到一起,然后对这个长字符串在做一次Hash运算,这样就得到Hash列表的根Hash(Top Hash or Root Hash)。下载数据的时候,首先从可信的数据源得到正确的根Hash,就可以用它来校验Hash列表了,然后通过校验后的Hash列表校验数据块。

    merkle

  3. Merkle Tree
    Merkle Tree可以看做Hash List的泛化(Hash List可以看作一种特殊的Merkle Tree,即树高为2的多叉Merkle Tree)。

    在最底层,和哈希列表一样,我们把数据分成小的数据块,有相应地哈希和它对应。但是往上走,并不是直接去运算根哈希,而是把相邻的两个哈希合并成一个字符串,然后运算这个字符串的哈希,这样每两个哈希就结婚生子,得到了一个”子哈希“。如果最底层的哈希总数是单数,那到最后必然出现一个单身哈希,这种情况就直接对它进行哈希运算,所以也能得到它的子哈希。于是往上推,依然是一样的方式,可以得到数目更少的新一级哈希,最终必然形成一棵倒挂的树,到了树根的这个位置,这一代就剩下一个根哈希了,我们把它叫做 Merkle Root[3]

    在p2p网络下载数据之前,先从可信的源获得文件的Merkle Tree树根。一旦获得了树根,就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接收到的Merkle Tree。如果Merkle Tree是损坏的或者虚假的,就从其他源获得另一个Merkle Tree,直到获得一个与可信树根匹配的Merkle Tree。

    Merkle Tree和Hash List的主要区别是,可以直接下载并立即验证Merkle Tree的一个分支。因为可以将文件切分成小的数据块,这样如果有一块数据损坏,仅仅重新下载这个数据块就行了。如果文件非常大,那么Merkle tree和Hash list都很多,但是Merkle tree可以一次下载一个分支,然后立即验证这个分支,如果分支验证通过,就可以下载数据了。而Hash list只有下载整个hash list才能验证。

    merkle

Merkle Tree的特点

MT是一种树,大多数是二叉树,也可以多叉树,无论是几叉树,它都具有树结构的所有特点;Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。非叶子节点的value是根据它下面所有的叶子节点值,然后按照Hash算法计算而得出的。[4][5]

通常,加密的hash方法像SHA-2和MD5用来做hash。但如果仅仅防止数据不是蓄意的损坏或篡改,可以改用一些安全性低但效率高的校验和算法,如CRC。

Second Preimage Attack: Merkle tree的树根并不表示树的深度,这可能会导致second-preimage attack,即攻击者创建一个具有相同Merkle树根的虚假文档。一个简单的解决方法在Certificate Transparency中定义:当计算叶节点的hash时,在hash数据前加0x00。当计算内部节点是,在前面加0x01。另外一些实现限制hash tree的根,通过在hash值前面加深度前缀。因此,前缀每一步会减少,只有当到达叶子时前缀依然为正,提取的hash链才被定义为有效。

Merkle Tree的操作
  1. 创建Merckle Tree
    假如最底层有9个数据块。

    step1:(红色线)对数据块做hash运算,Node0i = hash(Data0i), i=1,2,…,9

    step2: (橙色线)相邻两个hash块串联,然后做hash运算,Node1((i+1)/2) = hash(Node0i+Node0(i+1)), i=1,3,5,7;对于i=9, Node1((i+1)/2) = hash(Node0i)

    step3: (黄色线)重复step2

    step4:(绿色线)重复step2

    step5:(蓝色线)重复step2,生成Merkle Tree Root

    merkle

    易得,创建Merkle Tree是O(n)复杂度(这里指O(n)次hash运算),n是数据块的大小。得到Merkle Tree的树高是log(n)+1。

  2. 检索数据块
    为了更好理解,我们假设有A和B两台机器,A需要与B相同目录下有8个文件,文件分别是f1 f2 f3 ....f8。这个时候我们就可以通过Merkle Tree来进行快速比较。假设我们在文件创建的时候每个机器都构建了一个Merkle Tree。具体如下图:

    merkle

    从上图可得知,叶子节点node7的value = hash(f1),是f1文件的HASH;而其父亲节点node3的value = hash(v7, v8),也就是其子节点node7 node8的值得HASH。就是这样表示一个层级运算关系。root节点的value其实是所有叶子节点的value的唯一特征。

    假如A上的文件5与B上的不一样。我们怎么通过两个机器的merkle treee信息找到不相同的文件? 这个比较检索过程如下:

    Step1. 首先比较v0是否相同,如果不同,检索其孩子node1和node2.

    Step2. v1 相同,v2不同。检索node2的孩子node5 node6;

    Step3. v5不同,v6相同,检索比较node5的孩子node 11 和node 12

    Step4. v11不同,v12相同。node 11为叶子节点,获取其目录信息。

    Step5. 检索比较完毕。

    以上过程的理论复杂度是Log(N)。过程描述图如下:
    merkle

    从上图可以得知真个过程可以很快的找到对应的不相同的文件。

  3. 更新,插入和删除
    虽然网上有很多关于Merkle Tree的资料,但大部分没有涉及Merkle Tree的更新、插入和删除操作,讨论Merkle Tree的检索和遍历的比较多。我也是非常困惑,一种树结构的操作肯定不仅包括查找,也包括更新、插入和删除的啊。后来查到stackexchange上的一个问题,才稍微有点明白,原文见[6]

    对于Merkle Tree数据块的更新操作其实是很简单的,更新完数据块,然后接着更新其到树根路径上的Hash值就可以了,这样不会改变Merkle Tree的结构。但是,插入和删除操作肯定会改变Merkle Tree的结构,如下图,一种插入操作是这样的:

    merkle

    插入数据块0后(考虑数据块的位置),Merkle Tree的结构是这样的:

    merkle

    [6]中的同学在考虑一种插入的算法,满足下面条件:

    1. re-hashing操作的次数控制在log(n)以内
    2. 数据块的校验在log(n)+1以内
    3. 除非原始树的n是偶数,插入数据后的树没有孤儿,并且如果有孤儿,那么孤儿是最后一个数据块
    4. 数据块的顺序保持一致
    5. 插入后的Merkle Tree保持平衡
    

    然后上面的插入结果就会变成这样:
    merkle

    根据[6]中回答者所说,Merkle Tree的插入和删除操作其实是一个工程上的问题,不同问题会有不同的插入方法。如果要确保树是平衡的或者是树高是log(n)的,可以用任何的标准的平衡二叉树的模式,如AVL树,红黑树,伸展树,2-3树等。这些平衡二叉树的更新模式可以在O(lgn)时间内完成插入操作,并且能保证树高是O(lgn)的。那么很容易可以看出更新所有的Merkle Hash可以在O((lgn)2)时间内完成(对于每个节点如要更新从它到树根O(lgn)个节点,而为了满足树高的要求需要更新O(lgn)个节点)。如果仔细分析的话,更新所有的hash实际上可以在O(lgn)时间内完成,因为要改变的所有节点都是相关联的,即他们要不是都在从某个叶节点到树根的一条路径上,或者这种情况相近。

    [6]的回答者说实际上Merkle Tree的结构(是否平衡,树高限制多少)在大多数应用中并不重要,而且保持数据块的顺序也在大多数应用中也不需要。因此,可以根据具体应用的情况,设计自己的插入和删除操作。一个通用的Merkle Tree插入删除操作是没有意义的。

Merkle Tree的应用
  1. 数字签名
    最初Merkle Tree目的是高效的处理Lamport one-time signatures。 每一个Lamport key只能被用来签名一个消息,但是与Merkle tree结合可以来签名多条Merkle。这种方法成为了一种高效的数字签名框架,即Merkle Signature Scheme。

  2. P2P网络
    在P2P网络中,Merkle Tree用来确保从其他节点接受的数据块没有损坏且没有被替换,甚至检查其他节点不会欺骗或者发布虚假的块。大家所熟悉的BT下载就是采用了P2P技术来让客户端之间进行数据传输,一来可以加快数据下载速度,二来减轻下载服务器的负担。BT即BitTorrent,用于点对点文件共享(“P2P”)的通信协议,通过Internet分发数据和电子文件[7]

    要进下载必须从中心索引服务器获取一个扩展名为torrent的索引文件(即大家所说的种子),torrent文件包含了要共享文件的信息,包括文件名,大小,文件的Hash信息和一个指向Tracker的URL[8]。Torrent文件中的Hash信息是每一块要下载的文件内容的加密摘要,这些摘要也可运行在下载的时候进行验证。大的torrent文件是Web服务器的瓶颈,而且也不能直接被包含在RSS或gossiped around(用"流言传播协议"进行传播)[14][15]。一个相关的问题是大数据块的使用,因为为了保持torrent文件的非常小,那么数据块Hash的数量也得很小,这就意味着每个数据块相对较大。大数据块影响节点之间进行交易的效率,因为只有当大数据块全部下载下来并校验通过后,才能与其他节点进行交易。

    就解决上面两个问题是用一个简单的Merkle Tree代替Hash List。设计一个层数足够多的满二叉树,叶节点是数据块的Hash,不足的叶节点用0来代替。上层的节点是其对应孩子节点串联的hash。Hash算法和普通torrent一样采用SHA1。其数据传输过程和第一节中描述的类似。
    p2p

  3. Trusted Computing
    可信计算是可信计算组为分布式计算环境中参与节点的计算平台提供端点可信性而提出的。可信计算技术在计算平台的硬件层引入可信平台模块(Trusted Platform,TPM),实际上为计算平台提供了基于硬件的可信根(Root of trust,RoT)。从可信根出发,使用信任链传递机制,可信计算技术可对本地平台的硬件及软件实施逐层的完整性度量,并将度量结果可靠地保存再TPM的平台配置寄存器(Platform configuration register,PCR)中,此后远程计算平台可通过远程验证机制(Remote Attestation)比对本地PCR中度量结果,从而验证本地计算平台的可信性。可信计算技术让分布式应用的参与节点摆脱了对中心服务器的依赖,而直接通过用户机器上的TPM芯片来建立信任,使得创建扩展性更好、可靠性更高、可用性更强的安全分布式应用成为可能[10]。可信计算技术的核心机制是远程验证(remote attestation),分布式应用的参与结点正是通过远程验证机制来建立互信,从而保障应用的安全。
    Trusted Computing

    文献[10]提出了一种基于Merkle Tree的远程验证机制,其核心是完整性度量值哈希树。

    首先,RAMT 在内核中维护的不再是一张完整性度量值列表(ML),而是一棵完整性度量值哈希树(integrity measurement hash tree,简称IMHT).其中,IMHT的叶子结点存储的数据对象是待验证计算平台上被度量的各种程序的完整性哈希值,而其内部结点则依据Merkle 哈希树的构建规则由子结点的连接的哈希值动态生成。

    其次,为了维护IMHT 叶子结点的完整性,RAMT 需要使用TPM 中的一段存储器来保存IMHT 可信根哈希的值。

    再次,RAMT 的完整性验证过程基于认证路径(authentication path)实施.认证路径是指IMHT 上从待验证叶子结点到根哈希的路径。

  4. IPFS
    IPFS(InterPlanetary File System)是很多NB的互联网技术的综合体,如DHT( Distributed HashTable,分布式哈希表),Git版本控制系统,Bittorrent等。它创建了一个P2P的集群,这个集群允许IPFS对象的交换。全部的IPFS对象形成了一个被称作Merkle DAG的加密认证数据结构。

    IPFS对象是一个含有两个域的数据结构:

    Data – 非结构的二进制数据,大小小于256kB
    Links – 一个Link数据结构的数组。IPFS对象通过他们链接到其他对象
    

    Link数据结构包含三个域:

    Name – Link的名字
    Hash – Link链接到对象的Hash
    Size – Link链接到对象的累积大小,包括它的Links
    

    ipfs

    通过Name和Links,IPFS的集合组成了一个Merkle DAG(有向无环图)。
    ipfs-dag

    对于小文件(小于256kB),是一个没有Links的IPFS对象。
    no-links

    对于大文件,被表示为一个文件块(小于256kB)的集合。只有拥有最小的Data的对象来代表这个大文件。这个对象的Links的名字都为空字符串。

    big-file
    ipfs

    目录结构:目录是没有数据的IPFS对象,它的链接指向其包含的文件和目录。
    ipfs-dir

    IPFS可以表示Git使用的数据结构,Git Commit Object。Commit Object主要的特点是他有一个或多个名为’parent0’和‘parent1’等的链接(这些链接指向前一个版本),以及一个名为object的对象(在Git中成为tree)指向引用这个commit的文件系统结构。
    git-commit

  5. BitCoin和Ethereum[12][13]
    Merkle Proof最早的应用是Bitcoin,它是由中本聪在2009年描述并创建的。Bitcoin的Blockchain利用Merkle proofs来存储每个区块的交易。
    merkle-proofs

    而这样做的好处,也就是中本聪描述到的“简化支付验证”(Simplified Payment Verification,SPV)的概念:一个“轻客户端”(light client)可以仅下载链的区块头即每个区块中的80byte的数据块,仅包含五个元素,而不是下载每一笔交易以及每一个区块:

    上一区块头的哈希值
    时间戳
    挖矿难度值
    工作量证明随机数(nonce)
    包含该区块交易的Merkle Tree的根哈希
    

    如果客户端想要确认一个交易的状态,它只需简单的发起一个Merkle proof请求,这个请求显示出这个特定的交易在Merkle trees的一个之中,而且这个Merkle Tree的树根在主链的一个区块头中。

    但是Bitcoin的轻客户端有它的局限。一个局限是,尽管它可以证明包含的交易,但是它不能进行涉及当前状态的证明(如数字资产的持有,名称注册,金融合约的状态等)。

    Bitcoin如何查询你当前有多少币?一个比特币轻客户端,可以使用一种协议,它涉及查询多个节点,并相信其中至少会有一个节点会通知你,关于你的地址中任何特定的交易支出,而这可以让你实现更多的应用。但对于其他更为复杂的应用而言,这些远远是不够的。一笔交易影响的确切性质(precise nature),可以取决于此前的几笔交易,而这些交易本身则依赖于更为前面的交易,所以最终你可以验证整个链上的每一笔交易。为了解决这个问题,Ethereum的Merkle Tree的概念,会更进一步。

    Ethereum的Merkle Proof

    每个以太坊区块头不是包括一个Merkle树,而是为三种对象设计的三棵树:

    交易Transaction
    收据Receipts(本质上是显示每个交易影响的多块数据)
    状态State
    

    eth-head

    这使得一个非常先进的轻客户端协议成为了可能,它允许轻客户端轻松地进行并核实以下类型的查询答案:

    这笔交易被包含在特定的区块中了么?
    告诉我这个地址在过去30天中,发出X类型事件的所有实例(例如,一个众筹合约完成了它的目标)
    目前我的账户余额是多少?
    这个账户是否存在?
    假如在这个合约中运行这笔交易,它的输出会是什么?
    

    第一种是由交易树(transaction tree)来处理的;第三和第四种则是由状态树(state tree)负责处理,第二种则由收据树(receipt tree)处理。计算前四个查询任务是相当简单的。服务器简单地找到对象,获取Merkle分支,并通过分支来回复轻客户端。

    第五种查询任务同样也是由状态树处理,但它的计算方式会比较复杂。这里,我们需要构建一个Merkle状态转变证明(Merkle state transition proof)。从本质上来讲,这样的证明也就是在说“如果你在根S的状态树上运行交易T,其结果状态树将是根为S',log为L,输出为O” (“输出”作为存在于以太坊的一种概念,因为每一笔交易都是一个函数调用;它在理论上并不是必要的)。

    为了推断这个证明,服务器在本地创建了一个假的区块,将状态设为 S,并在请求这笔交易时假装是一个轻客户端。也就是说,如果请求这笔交易的过程,需要客户端确定一个账户的余额,这个轻客户端(由服务器模拟的)会发出一个余额查询请求。如果需要轻客户端在特点某个合约的存储中查询特定的条目,这个轻客户端就会发出这样的请求。也就是说服务器(通过模拟一个轻客户端)正确回应所有自己的请求,但服务器也会跟踪它所有发回的数据。

    然后,服务器从上述的这些请求中把数据合并并把数据以一个证明的方式发送给客户端。

    客户端会进行相同的步骤,但会将服务器提供的证明作为一个数据库来使用。如果客户端进行步骤的结果和服务器提供的是一样的话,客户端就接受这个证明。

    MPT
    MPT(Merkle Patricia Trees)

    前面我们提到,最为简单的一种Merkle Tree大多数情况下都是一棵二叉树。然而,Ethereum所使用的Merkle Tree则更为复杂,我们称之为“梅克尔.帕特里夏树”(Merkle Patricia tree)。

    对于验证属于list格式(本质上来讲,它就是一系列前后相连的数据块)的信息而言,二叉Merkle Tree是非常好的数据结构。对于交易树来说,它们也同样是不错的,因为一旦树已经建立,花多少时间来编辑这棵树并不重要,树一旦建立了,它就会永远存在并且不会改变。

    但是,对于状态树,情况会更复杂些。以太坊中的状态树基本上包含了一个键值映射,其中的键是地址,而值包括账户的声明、余额、随机数nounce、代码以及每一个账户的存储(其中存储本身就是一颗树)。例如,摩登测试网络(the Morden testnet)的创始状态如下所示:
    the morden testnet

    然而,不同于交易历史记录,状态树需要经常地进行更新:账户余额和账户的随机数nonce经常会更变,更重要的是,新的账户会频繁地插入,存储的键( key)也会经常被插入以及删除。我们需要这样的数据结构,它能在一次插入、更新、删除操作后快速计算到树根,而不需要重新计算整个树的Hash。这种数据结构同样得包括两个非常好的第二特征:

    树的深度是有限制的,即使考虑攻击者会故意地制造一些交易,使得这颗树尽可能地深。不然,攻击者可以通过操纵树的深度,执行拒绝服务攻击(DOS attack),使得更新变得极其缓慢。
    树的根只取决于数据,和其中的更新顺序无关。换个顺序进行更新,甚至重新从头计算树,并不会改变根。
    

    MPT是最接近同时满足上面的性质的的数据结构。MPT的工作原理的最简单的解释是,值通过键来存储,键被编码到搜索树必须要经过的路径中。每个节点有16个孩子,因此路径又16进制的编码决定:例如,键‘dog’的16进制编码是6 4 6 15 6 7,所以从root开始到第六个分支,然后到第四个,再到第六个,再到第十五个,这样依次进行到达树的叶子。

    在实践中,当树稀少时也会有一些额外的优化,我们会使过程更为有效,但这是基本的原则。

  6. 其他应用
    用到Merkle Tree的应用还有很多,比如Git,Amazon Dynamo,Apache Wave Protocol,Tahoe-LAFS backup system,Certificate Transparency framework,NoSQL systems like Apache Cassadra and Riak等


原文出自这里,有部分修改,如有侵权请联系删除!

参考:
[1]https://en.wikipedia.org/wiki/Merkle_tree

[2]https://en.wikipedia.org/wiki/Hash_function#Hash_function_algorithms

[3]http://www.jianshu.com/p/458e5890662f

[4]http://blog.csdn.net/xtu_xiaoxin/article/details/8148237

[5]http://blog.csdn.net/yuanrxdu/article/details/22474697?utm_source=tuicool&utm_medium=referral

[6]http://crypto.stackexchange.com/questions/22669/merkle-hash-tree-updates

[7]https://en.wikipedia.org/wiki/BitTorrent

[8] 梁成仁, 李健勇, 黄道颖, 等. 基于 Merkle 树的 BT 系统 torrent 文件优化策略[J]. 计算机工程, 2008, 34(3): 85-87.

[9]http://bittorrent.org/beps/bep_0030.html

[10] 徐梓耀, 贺也平, 邓灵莉. 一种保护隐私的高效远程验证机制[J]. Journal of Software, 2011, 22(2).

[11]http://whatdoesthequantsay.com/2015/09/13/ipfs-introduction-by-example/

[12]https://www.weusecoins.com/what-is-a-merkle-tree/

[13]http://www.8btc.com/merkling-in-ethereum

[14]https://en.wikipedia.org/wiki/Gossip_protocol

[15]http://blog.csdn.net/cloudresearch/article/details/23127985

IPFS初识体验

本示例所用环境
* 机器:普通电脑 ideapad Y410
* 系统:ArchLinux
什么是IPFS? 以下内容来自维基百科

注意:IPFS官网已经被墙!!!

星际文件系统(InterPlanetary File System,缩写IPFS)是一个旨在创建持久且分布式存储和共享文件的网络传输协议。它是一种内容可寻址的对等超媒体分发协议。在IPFS网络中的节点将构成一个分布式文件系统。它是一个开放源代码项目,自2014年开始由Protocol Labs在开源社区的帮助下发展。其最初由Juan Benet设计。

IPFS是一个对等的分布式文件系统,它尝试为所有计算设备连接同一个文件系统。在某些方面,IPFS类似于万维网,但它也可以被视作一个独立的BitTorrent群、在同一个Git仓库中交换对象。换种说法,IPFS提供了一个高吞吐量、按内容寻址的块存储模型,及与内容相关超链接。这形成了一个广义的Merkle有向无环图(DAG)。IPFS结合了分布式散列表、鼓励块交换和一个自我认证的命名空间。IPFS没有单点故障,并且节点不需要相互信任。分布式内容传递可以节约带宽,和防止HTTP方案可能遇到的DDoS攻击。

该文件系统可以通过多种方式访问,包括FUSE与HTTP。将本地文件添加到IPFS文件系统可使其面向全世界可用。文件表示基于其哈希,因此有利于缓存。文件的分发采用一个基于BitTorrent的协议。其他查看内容的用户也有助于将内容提供给网络上的其他人。IPFS有一个称为IPNS的名称服务,它是一个基于PKI的全局命名空间,用于构筑信任链,这与其他NS兼容,并可以映射DNS、.onion、.bit等到IPNS。

安装

github提供的几种安装方式

怎么使用

简单使用可以参考这篇博方如何使用星际文件传输网络(IPFS)搭建区块链服务,虽然它是转载自这,但它的格式要好太多:) 。

几点疑问
  1. 目前看到的都是用来存储静态文件,感觉和FTP或者CDN有点像,当然也有人在IPFS上写了一个分布式的点对点聊天应用程序。我主要是用PHP来做动态站的,HTTP协议用在客户端与服务端之间的通讯,至于服务端是怎么处理的它并不开心,可是如果用IPFS取代HTTP协议,它怎样处理这种到服务器的请求呢?因为基于IPFS的请求都是返回一个文件,而HTTP请求到服务器后可以通过不同的Web Server进行处理。

  2. 今天写了一个小demo,一个静态页面,加上一些js效果,增加到IPFS结点后都能访问,但是当我通过ajax去请求后端脚本时,POST请求直接405错误,GET请求返回的是整个脚本文件的内容,因为它没有通过对应脚本文件的服务去解析它。我在想它到底怎么才能满足这个需求呢?还是说它已经可以满足了而我还不知道?我的IPFS线上示例

  3. To Be Continue...


补一张本地运行webui后的图,感觉这个地球不错!
webui

敏捷开发

敏捷开发:
迭代开发,价值优先
分解任务,真实进度

站立会议,交流畅通
用户参与,调整方向

结对编程,代码质量
测试驱动,安全可靠

持续集成,尽早反馈
自动部署,一键安装

定期回顾,持续改进
不断学习,提高能力

  • 脱离实际的反方观点会使用争论变味。若对一个想法有成见,你很容易提出一堆不太可能发生或不太实际的情形去批驳它。这是你扪心自问:类似问题以前发生过吗?是否经常发生?
  • 例:我们不能采用这个方案,因为数据库厂商可能会倒闭;用户绝对不会接受这个那个方案。你必须要评判那些场景发生的可能性有多大。

享有盛名的爵士吉他手Pat Methany说过这位一句话:“总是要成为你所在的那个乐队中最差的乐手”

Don't build what you can download;(不要开发你能下载到的东西)
如果你发现自己在做一些花哨的东西(比如从头创建自己的框架),那就醒醒吧,闻闻烟味有多大,马上该起火了。你的代码写的越少,需要维护的东西就越少。

使用tesseract进行验证码识别初体验

本示例所用环境
* 机器:普通电脑 ThinkPad E470c
* 系统:Ubuntu 16.04 LTS
为什么要做验证码自动识别
你被验证码折磨的还不够惨吗!?:)
什么是ocr和tesseract
OCR是Optical Character Rcognition的缩写,意思是光学字符识别,针对印刷体字符,采用光学的方式将纸质文档中的文字转换成为黑白点阵的图像文件,并通过识别软件将图像中的文字转换成文本格式,供文字处理软件进一步编辑加工的技术。

Tesseract是一个跨平台的ocr引擎,适于多种操作系统。它是一款免费软件,根据Apache许可证2.0版发布,当前(2018-03-06)稳定版为3.05.01,自2006年开发以来一直由Google赞助,2006年,Tesseract被认为是当时最准确的开源OCR引擎之一。
怎么使用
我是在Python脚本里使用,先安装相关库,在Debian / Ubuntu上:

sudo apt install tesseract-ocr libtesseract-dev libleptonica-dev
sudo pip3 install tesseroc
sudo pip3 install pillow

pillow fork自PIL库,PIL是Python Imaging Library的缩写,Python图片处理库。

代码片段:

import tesserocr
from PIL import Image

print(tesserocr.tesseract_version())
print(tesserocr.get_languages())

image = Image.open('sample.jpg'))
print(tesserocr.image_to_text(image))

print(tesserocr.file_to_text('sample.jpg'))
更高级的功能
以上功能只能识别简单验证码,稍微复杂一点的验证码都识别不出来,更高级的使用则需要对图片进行各种处理,一般是对图片进行二值化、降噪、切割等,然后对Tesseract进行训练,提高识别率,我没有实践过,就不班门弄斧啦!

完结

从企业人员调整看开去

临近年关(腊月廿二),今天(二零一八年二月七号)公司人事调整,身边几个熟悉的同事突然被撤,心中不禁感慨万千。在北京,这事儿虽然每天都在上演,但搁在自己身边依然会令人五味杂陈,更何况亲身体会的他们呢?

在此记录一下由这事得到的一些体会吧!

  • 企业或者说资本,都是无情的

    从两个方面反映的这点:

    1. 我的后端同事是经历了一个繁忙时刻过来的,现在年底稍较清闲了,然后给别人裁了,是很有卸磨杀驴之嫌的。

    2. 临近年关,真是年关,他们这一“关”就没有过去。从传统意义上来说,裁员一般不会选择在此时,而且是让立即走人,仅补偿一个月薪资。即使是在此时,也应有比较好的补偿,身边也有这样的案例的,正规N+2的补偿,然后可以在年后来办理离职。

    唉,这个年他们可能过的并不那么开心了。

  • 仅仅只靠工作生活是不行的

    不能只靠工资生活,这一点已经非常明晰了,如果你没有负债可能还好点,假如你有房贷、车贷,突然工作又丢了,一旦你不能立马找到与你现在工资相当或更高的工作,你一下子就会陷入焦虑当中,生活很可能出现混乱,导致连锁反应。

    每个人都需要一份副业,可以当作是业余时间的锻炼与自身的扩展,当然最好是有一定的存款,这样就能做到泰然自若,处变不惊。

  • 需要提高自己的综合实力

    不断提升自己的综合实力,不仅仅是技术上,还有为人处事上,有时候被淘汰可能不是技术能力上的问题,有可能问题出在沟通与处理事情的方式上,对于这一点,只要是工作3年以上的人都会深有体会。

    同一件事情,处理的人不一样,给人的感受也会大不一样,一定要避免把事情做了还得罪人的情况出现,但很多人难免这样,包括我自己也是,以后切记。

记于当晚 21:54