LevelDB源码之SkipList原理


分类： LevelDB源码系列2013-08-15
 22:01 402人阅读 评论(0) 收藏 举报

LevelDB源码系列

感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight()




[cpp] view
 plaincopy






template<typename Key, class Comparator>  

int SkipList<Key,Comparator>::RandomHeight() {  

  // Increase height with probability 1 in kBranching  

  static const unsigned int kBranching = 4;  

  int height = 1;  

  while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {  

    height++;  

  }  

  assert(height > 0);  

  assert(height <= kMaxHeight);  

  return height;  

}  


插入操作：




[cpp] view
 plaincopy






template<typename Key, class Comparator>  

void SkipList<Key,Comparator>::Insert(const Key& key) {  

  // TODO(opt): We can use a barrier-free（(屏蔽，障碍/无障碍） variant(变种) of FindGreaterOrEqual()  

  // here since Insert() is externally synchronized.  

  //prev为各层的前置节点  

  Node* prev[kMaxHeight];  

  //查找插入的节点  

  Node* x = FindGreaterOrEqual(key, prev);  

  

  // Our data structure does not allow duplicate insertion  

  assert(x == NULL || !Equal(key, x->key));  

  //随机生成节点高度  

  int height = RandomHeight();  

  if (height > GetMaxHeight()) {  

    for (int i = GetMaxHeight(); i < height; i++) {  

      prev[i] = head_;  

    }  

    //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);  

  

    // It is ok to mutate max_height_ without any synchronization  

    // with concurrent readers.  A concurrent reader that observes  

    // the new value of max_height_ will see either the old value of  

    // new level pointers from head_ (NULL), or a new value set in  

    // the loop below.  In the former case the reader will  

    // immediately drop to the next level since NULL sorts after all  

    // keys.  In the latter case the reader will use the new node.  

    //设置最大高度  

    max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));  

  }  

  //生成一个新的Node  

  x = NewNode(key, height);  

  for (int i = 0; i < height; i++) {  

    // NoBarrier_SetNext() suffices since we will add a barrier when  

    // we publish a pointer to "x" in prev[i].  

    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));  

    prev[i]->SetNext(i, x);  

  }  

}  

查找操作：





[cpp] view
 plaincopy






template<typename Key, class Comparator>  

typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)  

    const {  

  Node* x = head_;  

  //从最顶层开始查找  

  int level = GetMaxHeight() - 1;  

  while (true) {  

    Node* next = x->Next(level);  

    //向右查找  

    if (KeyIsAfterNode(key, next)) {  

      // Keep searching in this list  

      x = next;  

    } else {  

        //向下查找  

      if (prev != NULL) prev[level] = x;  

      if (level == 0) {  

        return next;  

      } else {  

        // Switch to next list  

        level--;  

      }  

    }  

  }  

}  

整个SkipList.h源码：





[cpp] view
 plaincopy






// Copyright (c) 2011 The LevelDB Authors. All rights reserved.  

// Use of this source code is governed by a BSD-style license that can be  

// found in the LICENSE file. See the AUTHORS file for names of contributors.  

//  

// Thread safety  

// -------------  

//  

// Writes require external synchronization, most likely a mutex.  

// Reads require a guarantee that the SkipList will not be destroyed  

// while the read is in progress.  Apart from that, reads progress  

// without any internal locking or synchronization.  

//  

// Invariants:  

//  

// (1) Allocated nodes are never deleted until the SkipList is  

// destroyed.  This is trivially guaranteed by the code since we  

// never delete any skip list nodes.  

//  

// (2) The contents of a Node except for the next/prev pointers are  

// immutable after the Node has been linked into the SkipList.  

// Only Insert() modifies the list, and it is careful to initialize  

// a node and use release-stores to publish the nodes in one or  

// more lists.  

//  

// ... prev vs. next pointer ordering ...  

  

#include <assert.h>  

#include <stdlib.h>  

#include "port/port.h"  

#include "util/arena.h"  

#include "util/random.h"  

/** 

 * SkipList应用概率来保证平衡，平衡树采用严格的旋转来保证平衡 

 * 使用SkipList是的查找特定值得时间复杂度是O(logN)，与平衡树有着相同的复杂度，节省空间，每个检点平均1.33个指针 

 * leveldb的最高层数为12，只允许插入和修改，Record的key不允许重复，添加一个Sequene Num 

 * 规范：参数使用引用，返回值使用指针 

 * 

 */  

namespace leveldb {  

  

class Arena;  

  

template<typename Key, class Comparator>  

class SkipList {  

 private:  

  struct Node;  

  

 public:  

  // Create a new SkipList object that will use "cmp" for comparing keys,  

  // and will allocate memory using "*arena".  Objects allocated in the arena  

  // must remain allocated for the lifetime of the skiplist object.  

  explicit SkipList(Comparator cmp, Arena* arena);  

  

  // Insert key into the list.  

  // REQUIRES: nothing that compares equal to key is currently in the list.  

  void Insert(const Key& key);  

  

  // Returns true iff an entry that compares equal to key is in the list.  

  bool Contains(const Key& key) const;  

  

  // Iteration over the contents of a skip list  

  class Iterator {  

   public:  

    // Initialize an iterator over the specified list.  

    // The returned iterator is not valid.  

    explicit Iterator(const SkipList* list);  

  

    // Returns true iff the iterator is positioned at a valid node.  

    bool Valid() const;  

  

    // Returns the key at the current position.  

    // REQUIRES: Valid()  

    const Key& key() const;  

  

    // Advances to the next position.  

    // REQUIRES: Valid()  

    void Next();  

  

    // Advances to the previous position.  

    // REQUIRES: Valid()  

    void Prev();  

  

    // Advance to the first entry with a key >= target  

    void Seek(const Key& target);  

  

    // Position at the first entry in list.  

    // Final state of iterator is Valid() iff list is not empty.  

    void SeekToFirst();  

  

    // Position at the last entry in list.  

    // Final state of iterator is Valid() iff list is not empty.  

    void SeekToLast();  

  

   private:  

    const SkipList* list_;  

    Node* node_;  

    // Intentionally copyable  

  };  

  

  //跳表的最高level数  

 private:  

  enum { kMaxHeight = 12 };  

  

  // Immutable(不可变) after construction  

  Comparator const compare_;  

  //舞台，竞技场，场所（只负责申请空间的内存池）  

  Arena* const arena_;    // Arena used for allocations of nodes  

  

  Node* const head_;  

  

  // Modified only by Insert().  Read racily by readers, but stale  

  // values are ok.  

  port::AtomicPointer max_height_;   // Height of the entire list  

  

  inline int GetMaxHeight() const {  

    return static_cast<int>(  

        reinterpret_cast<intptr_t>(max_height_.NoBarrier_Load()));  

  }  

  

  // Read/written only by Insert().  

  Random rnd_;  

  

  Node* NewNode(const Key& key, int height);  

  int RandomHeight();  

  bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }  

  

  // Return true if key is greater than the data stored in "n"  

  bool KeyIsAfterNode(const Key& key, Node* n) const;  

  

  // Return the earliest node that comes at or after key.  

  // Return NULL if there is no such node.  

  //  

  // If prev is non-NULL, fills prev[level] with pointer to previous  

  // node at "level" for every level in [0..max_height_-1].  

  Node* FindGreaterOrEqual(const Key& key, Node** prev) const;  

  

  // Return the latest node with a key < key.  

  // Return head_ if there is no such node.  

  Node* FindLessThan(const Key& key) const;  

  

  // Return the last node in the list.  

  // Return head_ if list is empty.  

  Node* FindLast() const;  

  

  // No copying allowed  

  SkipList(const SkipList&);  

  void operator=(const SkipList&);  

};  

  

// Implementation details follow  

template<typename Key, class Comparator>  

struct SkipList<Key,Comparator>::Node {  

  explicit Node(const Key& k) : key(k) { }  

  

  Key const key;  

  

  // Accessors/mutators for links.  Wrapped in methods so we can  

  // add the appropriate barriers as necessary.  

  Node* Next(int n) {  

    assert(n >= 0);  

    // Use an 'acquire load' so that we observe a fully initialized  

    // version of the returned Node.  

    return reinterpret_cast<Node*>(next_[n].Acquire_Load());  

  }  

  void SetNext(int n, Node* x) {  

    assert(n >= 0);  

    // Use a 'release store' so that anybody who reads through this  

    // pointer observes a fully initialized version of the inserted node.  

    next_[n].Release_Store(x);  

  }  

  

  // No-barrier variants that can be safely used in a few locations.  

  Node* NoBarrier_Next(int n) {  

    assert(n >= 0);  

    return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());  

  }  

  void NoBarrier_SetNext(int n, Node* x) {  

    assert(n >= 0);  

    next_[n].NoBarrier_Store(x);  

  }  

  

 private:  

  // Array of length equal to the node height.  next_[0] is lowest level link.  

  port::AtomicPointer next_[1];  

};  

  

template<typename Key, class Comparator>  

typename SkipList<Key,Comparator>::Node*  

SkipList<Key,Comparator>::NewNode(const Key& key, int height) {  

  char* mem = arena_->AllocateAligned(  

      sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));  

  return new (mem) Node(key);  

}  

  

template<typename Key, class Comparator>  

inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) {  

  list_ = list;  

  node_ = NULL;  

}  

  

template<typename Key, class Comparator>  

inline bool SkipList<Key,Comparator>::Iterator::Valid() const {  

  return node_ != NULL;  

}  

  

template<typename Key, class Comparator>  

inline const Key& SkipList<Key,Comparator>::Iterator::key() const {  

  assert(Valid());  

  return node_->key;  

}  

  

template<typename Key, class Comparator>  

inline void SkipList<Key,Comparator>::Iterator::Next() {  

  assert(Valid());  

  node_ = node_->Next(0);  

}  

  

template<typename Key, class Comparator>  

inline void SkipList<Key,Comparator>::Iterator::Prev() {  

  // Instead of using explicit "prev" links, we just search for the  

  // last node that falls before key.  

  assert(Valid());  

  node_ = list_->FindLessThan(node_->key);  

  if (node_ == list_->head_) {  

    node_ = NULL;  

  }  

}  

  

template<typename Key, class Comparator>  

inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) {  

  node_ = list_->FindGreaterOrEqual(target, NULL);  

}  

  

template<typename Key, class Comparator>  

inline void SkipList<Key,Comparator>::Iterator::SeekToFirst() {  

  node_ = list_->head_->Next(0);  

}  

  

template<typename Key, class Comparator>  

inline void SkipList<Key,Comparator>::Iterator::SeekToLast() {  

  node_ = list_->FindLast();  

  if (node_ == list_->head_) {  

    node_ = NULL;  

  }  

}  

  

template<typename Key, class Comparator>  

int SkipList<Key,Comparator>::RandomHeight() {  

  // Increase height with probability 1 in kBranching  

  static const unsigned int kBranching = 4;  

  int height = 1;  

  while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {  

    height++;  

  }  

  assert(height > 0);  

  assert(height <= kMaxHeight);  

  return height;  

}  

  

template<typename Key, class Comparator>  

bool SkipList<Key,Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {  

  // NULL n is considered infinite  

  return (n != NULL) && (compare_(n->key, key) < 0);  

}  

/** 

 * 查找，从左向右，从上向下查找 

 */  

template<typename Key, class Comparator>  

typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)  

    const {  

  Node* x = head_;  

  //从最顶层开始查找  

  int level = GetMaxHeight() - 1;  

  while (true) {  

    Node* next = x->Next(level);  

    //向右查找  

    if (KeyIsAfterNode(key, next)) {  

      // Keep searching in this list  

      x = next;  

    } else {  

        //向下查找  

      if (prev != NULL) prev[level] = x;  

      if (level == 0) {  

        return next;  

      } else {  

        // Switch to next list  

        level--;  

      }  

    }  

  }  

}  

  

template<typename Key, class Comparator>  

typename SkipList<Key,Comparator>::Node*  

SkipList<Key,Comparator>::FindLessThan(const Key& key) const {  

  Node* x = head_;  

  int level = GetMaxHeight() - 1;  

  while (true) {  

    assert(x == head_ || compare_(x->key, key) < 0);  

    Node* next = x->Next(level);  

    if (next == NULL || compare_(next->key, key) >= 0) {  

      if (level == 0) {  

        return x;  

      } else {  

        // Switch to next list  

        level--;  

      }  

    } else {  

      x = next;  

    }  

  }  

}  

  

template<typename Key, class Comparator>  

typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindLast()  

    const {  

  Node* x = head_;  

  int level = GetMaxHeight() - 1;  

  while (true) {  

    Node* next = x->Next(level);  

    if (next == NULL) {  

      if (level == 0) {  

        return x;  

      } else {  

        // Switch to next list  

        level--;  

      }  

    } else {  

      x = next;  

    }  

  }  

}  

/** 

 * SkipList初始化 

 * 

 */  

template<typename Key, class Comparator>  

SkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena)  

    : compare_(cmp),  

      arena_(arena),  

      head_(NewNode(0 /* any key will do */, kMaxHeight)),  

      max_height_(reinterpret_cast<void*>(1)),  

      rnd_(0xdeadbeef) {  

  for (int i = 0; i < kMaxHeight; i++) {  

    head_->SetNext(i, NULL);  

  }  

}  

/** 

 * 插入一个新的key 

 * 

 */  

template<typename Key, class Comparator>  

void SkipList<Key,Comparator>::Insert(const Key& key) {  

  // TODO(opt): We can use a barrier-free（(屏蔽，障碍/无障碍） variant(变种) of FindGreaterOrEqual()  

  // here since Insert() is externally synchronized.  

  //prev为各层的前置节点  

  Node* prev[kMaxHeight];  

  //查找插入的节点  

  Node* x = FindGreaterOrEqual(key, prev);  

  

  // Our data structure does not allow duplicate insertion  

  assert(x == NULL || !Equal(key, x->key));  

  //随机生成节点高度  

  int height = RandomHeight();  

  if (height > GetMaxHeight()) {  

    for (int i = GetMaxHeight(); i < height; i++) {  

      prev[i] = head_;  

    }  

    //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);  

  

    // It is ok to mutate max_height_ without any synchronization  

    // with concurrent readers.  A concurrent reader that observes  

    // the new value of max_height_ will see either the old value of  

    // new level pointers from head_ (NULL), or a new value set in  

    // the loop below.  In the former case the reader will  

    // immediately drop to the next level since NULL sorts after all  

    // keys.  In the latter case the reader will use the new node.  

    //设置最大高度  

    max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));  

  }  

  //生成一个新的Node  

  x = NewNode(key, height);  

  for (int i = 0; i < height; i++) {  

    // NoBarrier_SetNext() suffices since we will add a barrier when  

    // we publish a pointer to "x" in prev[i].  

    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));  

    prev[i]->SetNext(i, x);  

  }  

}  

/** 

 * 包含 

 */  

template<typename Key, class Comparator>  

bool SkipList<Key,Comparator>::Contains(const Key& key) const {  

  Node* x = FindGreaterOrEqual(key, NULL);  

  if (x != NULL && Equal(key, x->key)) {  

    return true;  

  } else {  

    return false;  

  }  

}  

  

}  // namespace leveldb  

阅读本文可参考：

LevelDB源码分析之一：coding


LevelDB源码分析之二：comparator

LevelDB源码分析之三：arena

LevelDB源码分析之四：AtomicPointer

LevelDb源码分析之五：skiplist（1）

LevelDb源码分析之六：skiplist（2）


LevelDB源码分析之七：Random
        在LevelDB中所有KV数据都是存储在Memtable，Immutable Memtable和SSTable中的，Immutable Memtable从结构上讲和Memtable是完全一样的，区别仅仅在于其是只读的，不允许写入操作，而Memtable则是允许写入和读取的。当Memtable写入的数据占用内存到达指定数量，则自动转换为Immutable Memtable，等待Dump到磁盘中，系统会自动生成新的Memtable供写操作写入新数据，理解了Memtable，那么Immutable
 Memtable自然不在话下。
        LevelDB的MemTable提供了将KV数据写入，删除以及读取KV记录的操作接口，但是事实上Memtable并不存在真正的删除操作，删除某个Key的Value在Memtable内是作为插入一条记录实施的，但是会打上一个Key的删除标记，真正的删除操作是延后的，会在以后的Compaction过程中去掉这个KV。 需要注意的是，LevelDB的Memtable中KV对是根据Key大小有序存储的，在系统插入新的KV时，LevelDB要把这个KV插到合适的位置上以保持这种Key有序性。其实，LevelDb的Memtable类只是一个接口类，真正的操作是通过背后的SkipList来做的，包括插入操作和读取操作等，所以Memtable的核心数据结构是一个SkipList。
        Memtable主要作用是对skiplist、arena、comparator进行组合和管理，接口函数屏蔽了底层操作，对使用者更加优雅。
一.构造函数

MemTable::MemTable(const InternalKeyComparator& cmp)
    : comparator_(cmp),
      refs_(0),
      table_(comparator_, &arena_) {
}
构造函数对私有成员变量进行了初始化，table_是SkipList类型，将&aerna_当做key传入，arena_是Arena类型。

二.内存估算函数

size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }
这里直接调用的是Arena类的MemoryUsage方法，该方法返回整个内存池使用内存的总大小（不精确）。

三.添加函数

void MemTable::Add(SequenceNumber s, ValueType type,
                   const Slice& key,
                   const Slice& value) {
  // Format of an entry is concatenation of:
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]
  size_t key_size = key.size();
  size_t val_size = value.size();
  // 参考LevelDB源码分析之二：comparator中关于Internal Key的介绍，
  // 因为Internal Key由user_key、sequence和type三个字段组成，user_key
  // 也就是这里的key，sequence和type会打包成一个uint64_t类型的数据，
  // 所以这里的长度为key_size+8
  size_t internal_key_size = key_size + 8;
  // 参考LevelDB源码分析之一：coding，为了节约空间，数字都是编码存储的，
  // VarintLength方法求出的是编码后的长度。关于encoded_len的组成详见下图。
  const size_t encoded_len =
      VarintLength(internal_key_size) + internal_key_size +
      VarintLength(val_size) + val_size;
  // 分配内存
  char* buf = arena_.Allocate(encoded_len);
  // 编码internal_key_size，编码后存放到buf中，p指向internal_key_size的结尾
  char* p = EncodeVarint32(buf, internal_key_size);
  // 将key拷贝到buf中，占用key_size大小
  memcpy(p, key.data(), key_size);
  p += key_size;
  // 将sequence和type打包后存放到buf中，大小为8字节，EncodeFixed64只是进行了简单的拷贝（考虑的大端或小端）。
  EncodeFixed64(p, (s << 8) | type);
  p += 8;
  // 编码val_size，编码后存放到buf中，p指向val_size的结尾
  p = EncodeVarint32(p, val_size);
  // 将value拷贝到buf中，占用val_size大小
  memcpy(p, value.data(), val_size);
  // 判断存储完后所占内存的大小，是否与初始计算的大小相等
  assert((p + val_size) - buf == encoded_len);
  // 插入到SkipList中
  table_.Insert(buf);
}
一个完整的buf内容如下图所示。



四.获取函数

// 如果能找到key对应的value, 将该value存储到*value参数中，返回值为true。
// 如果这个key中的有删除标识,存放一个NotFound()错误到*status参数中，返回值为true。
// 否则返回值为false
bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
  // 得到memkey，memkey中实际上包含了klength|userkey|tag，也就是说它包含了internal_key_size
  // 和internal_key
  Slice memkey = key.memtable_key();
  Table::Iterator iter(&table_);
  // 找到SkipList中大于等于memkey的结点
  iter.Seek(memkey.data());
  // 如果找到了这个结点
  if (iter.Valid()) {
	// 一个结点的结构如下所示
    // entry format is:
    //    klength  varint32
    //    userkey  char[klength]
    //    tag      uint64
    //    vlength  varint32
    //    value    char[vlength]
    // Check that it belongs to same user key.  We do not check the
    // sequence number since the Seek() call above should have skipped
    // all entries with overly large sequence numbers.
    const char* entry = iter.key();
    uint32_t key_length;
	// 取出klength，并将key_ptr指到klength之后
	// 为什么加5？参考LevelDB源码分析之一：coding
    const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);
	// 比较结点中的userkey和LookupKey中的userkey是否相等，如果相等，说明找到了这个结点。
    if (comparator_.comparator.user_comparator()->Compare(
            Slice(key_ptr, key_length - 8),
            key.user_key()) == 0) {
      // 获取tag，tag等于(sequence<<8)|type
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
	  // 取出type并判断
      switch (static_cast<ValueType>(tag & 0xff)) {
        case kTypeValue: {
		  // 取出value的大小和内容
          Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
          value->assign(v.data(), v.size());
          return true;
        }
        case kTypeDeletion:
          *s = Status::NotFound(Slice());
          return true;
      }
    }
  }
  return false;
}

}
获取函数的第一个参数是LookupKey类型，LookupKey是一个帮助类，通过它可以更方便的对Memtable进行操作。由于LookupKey的官方注释特别详细，这里就不分析了。



参考链接：http://www.360doc.com/content/14/0325/16/15064667_363619194.shtml











     

Leveldb源码分析

在阅读log文件的时候，会发现使用了Status这个类，可以用它来得到函数返回的状态，比如：
Status s = Function();
if (!s.ok()) return false;
return true

今天就来认真学习一下相关实现方法。
1. 私有


state_，一个指向字符常数的指针。如果是成功的那么state_是null，否则，他是一个数组，索引0~3位是消息长度，4位是状态码，5位以后是消息本身。


返回的状态是可以枚举的，在Status类中，这些可枚举状态是私有变量Code，一共定义了成功、没找到、出错、不支持、不合法的参数、IO错误六种情况。


code函数，通过state_的第四位及状态值返回是哪种可枚举值


带参数的构造函数。这个是很重要的一个函数，因为public函数中主要使用这个函数返回状态和类型。


Status::Status(Code code, const Slice& msg, const Slice& msg2) 

主要是使用了memcpy内存拷贝，把msg按照字节拷贝到返回结果中，具体过程如下：


CopyState函数，对状态进行深拷贝，即开辟了新的内存。


可以看到这里也使用了memcpy函数，我查了一下官方文档，有这样一句评论：

std::memcpy 理应是最快的内存到内存复制子程序。它通常比必须扫描其所复制数据的 std::strcpy ，或必须预防以处理重叠输入的 std::memmove 更高效。

2. public
2.1 the big three

构造函数
析构函数
拷贝构造函数-传参是const
赋值函数-传参是const
拷贝构造函数-传参是非const
赋值构造函数-传参是非const

2.2 是不是某一种状态
我们之前说过，一共有6种可枚举的状态，所以这里有六个公有成员函数，返回的都是布尔类型，来判断状态是不是OK的或者出错了等。主要使用的就是我们之前说的Code函数。
2.3 把某种状态和相关信息封装返回
也是六个函数，使用的就是我们之前说的带参数的构造函数。
2.4 转字符串
把state转成字符串，方便打印。