levelDB 소스 코드 분석 - memtable

이 절 은 메모리 에 있 는 LevelDB 의 데이터 구조 인 Memtable, Memtable 이 전체 시스템 에서 중요 한 위 치 를 차지 하 는 것 도 자명 하 다.전체적으로 말 하면 모든 KV 데 이 터 는 Memtable, Immutable Memtable, SSTable 에 저 장 됩 니 다. Immutable Memtable 은 구조 적 으로 Memtable 과 똑 같 습 니 다. 차 이 는 읽 기 전용 이 고 기록 작업 이 허용 되 지 않 으 며 Memtable 은 기록 과 읽 기 를 허용 합 니 다.Memtable 이 기록 한 데이터 가 메모리 에서 지정 한 수량 (Options. write buffer size) 에 도달 하면 자동 으로 Immutable Memtable 로 변 환 됩 니 다. Dump 가 디스크 에 들 어 오 기 를 기다 리 면 시스템 은 자동 으로 새로운 Memtable 쓰기 동작 을 생 성하 여 새로운 데 이 터 를 기록 합 니 다. Memtable 을 이해 하면 Immutable Memtable 은 당연히 말 할 필요 가 없습니다. LevelDb 의 MemTable 은 KV 데 이 터 를 기록, 삭제, 읽 기 위 한 조작 인 터 페 이 스 를 제공 합 니 다. 그러나 사실 Memtable 은 실제 삭제 동작 이 존재 하지 않 습 니 다. 어떤 Key 의 Value 를 삭제 하 는 것 은 Memtable 에 기록 을 삽입 하 는 것 으로 실시 되 지만 Key 의 삭제 표 시 를 합 니 다. 진정한 삭제 작업 은 Lazy 입 니 다.앞으로 Compaction 과정 에서 이 KV 를 지 울 겁 니 다. 주의해 야 할 것 은 LevelDb 의 Memtable 에서 KV 쌍 은 Key 크기 에 따라 질서 있 게 저 장 됩 니 다. 시스템 에 새로운 KV 를 삽입 할 때 LevelDb 는 이 KV 를 적당 한 위치 에 꽂 아서 이러한 Key 질서 성 을 유지 해 야 합 니 다.사실 LevelDb 의 Memtable 클래스 는 하나의 인터페이스 클래스 일 뿐 이 고 진정한 조작 은 뒤에 있 는 SkipList 를 통 해 이 루어 집 니 다. 삽입 작업 과 읽 기 작업 등 을 포함 하기 때문에 Memtable 의 핵심 데이터 구 조 는 SkipList 입 니 다. SkipList 는 William Pugh 가 발명 했다.그 는 Communications of the ACM June 1990, 33 (6) 668 - 676 에서 Skip lists: a probabilistic alternative to balanced trees 를 발표 하고 이 논문 에서 SkipList 의 데이터 구조 와 삽입 삭제 작업 을 상세히 설명 했다.    SkipList 는 균형 트 리 의 대체 데이터 구조 이지 만 빨간색 과 검은색 트 리 와 달리 SkipList 는 트 리 의 균형 을 실현 하 는 데 랜 덤 화 된 알고리즘 을 바탕 으로 한다. 즉, SkipList 의 삽입 과 삭제 작업 은 비교적 간단 하 다 는 것 이다.    SkipList 에 대한 상세 한 소 개 는 'levelDB 소스 분석 - skiplist' 또는http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.htmlLevelDb 의 SkipList 는 기본적으로 구체 적 으로 실현 되 고 특별한 점 이 없다 는 것 을 잘 알 고 있다.SkipList 는 질 서 있 는 데 이 터 를 유지 하 는 간단 한 실현 일 뿐만 아니 라 균형 트 리 에 비해 데 이 터 를 삽입 할 때 빈번 한 트 리 노드 조정 작업 을 피 할 수 있 기 때문에 기록 효율 이 높 습 니 다. LevelDb 는 전체적으로 높 은 기록 시스템 이 고 SkipList 는 그 중에서 도 중요 한 역할 을 할 것 입 니 다.레 디 스 는 삽입 작업 을 가속 화하 기 위해 내부 구현 데이터 구조 로 SkipList 도 사용 했다.  다음은 MemTable 의 정의 와 소 개 를 소개 합 니 다.
MemTable 은 인용 수 를 기반 으로 사용 할 때마다 Ref () 를 먼저 호출 하고 사용 이 끝 났 을 때 Unref () 를 호출 합 니 다.

    class MemTable {
    public:
        // MemTables are reference counted.  The initial reference count
        // is zero and the caller must call Ref() at least once.
        explicit MemTable(const InternalKeyComparator& comparator);					//     ，     comparator（     ）

        // Increase reference count.
        void Ref() { ++refs_; }												//       

        // Drop reference count.  Delete if no more references exist.
        void Unref() {														//       
            --refs_;
            assert(refs_ >= 0);
            if (refs_ <= 0) {
                delete this;
            }
        }

        // Returns an estimate of the number of bytes of data in use by this
        // data structure.
        //
        // REQUIRES: external synchronization to prevent simultaneous
        // operations on the same MemTable.
        size_t ApproximateMemoryUsage();										//       

        // Return an iterator that yields the contents of the memtable.
        //
        // The caller must ensure that the underlying MemTable remains live
        // while the returned iterator is live.  The keys returned by this
        // iterator are internal keys encoded by AppendInternalKey in the
        // db/format.{h,cc} module.
        Iterator* NewIterator();												//    

        // Add an entry into memtable that maps key to value at the
        // specified sequence number and with the specified type.
        // Typically value will be empty if type==kTypeDeletion.
        void Add(SequenceNumber seq, ValueType type,								//     key/value MemTable 
        		   const Slice& key,											// type=kTypeDeletion ，value  
        		   const Slice& value);

        // If memtable contains a value for key, store it in *value and return true.
        // If memtable contains a deletion for key, store a NotFound() error
        // in *status and return true.
        // Else, return false.
        bool Get(const LookupKey& key, std::string* value, Status* s);				//     

    private:
        ~MemTable();  // Private since only Unref() should be used to delete it		//       ，   private，      

        struct KeyComparator {
            const InternalKeyComparator comparator;
            explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) { }
            int operator()(const char* a, const char* b) const;
            };
        friend class MemTableIterator;
        friend class MemTableBackwardIterator;

        typedef SkipList<const char*, KeyComparator> Table;	
        Table table_;														// Skiplist				

        KeyComparator comparator_;											//    comparator_

        Arena arena_;														//    
        
        int refs_;															//     

        // No copying allowed
        MemTable(const MemTable&);											//               
        void operator=(const MemTable&);
        };
 
           
    // Modules in this directory should keep internal keys wrapped inside
    // the following class instead of plain strings so that we do not
    // incorrectly use string comparisons instead of an InternalKeyComparator.
    class InternalKey {														//   Key
      private:
        std::string rep_;
      public:
        InternalKey() { }   // Leave rep_ as empty to indicate it is invalid
        InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
            AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
        }

        void DecodeFrom(const Slice& s) { rep_.assign(s.data(), s.size()); }			//    string
        Slice Encode() const {												//   string
            assert(!rep_.empty());
            return rep_;
        }

        Slice user_key() const { return ExtractUserKey(rep_); }					//   User Key

        void SetFrom(const ParsedInternalKey& p) {
            rep_.clear();
            AppendInternalKey(&rep_, p);
        }

        void Clear() { rep_.clear(); }

        std::string DebugString() const;
    };
    
    struct ParsedInternalKey {												//  InternalKey  :
        Slice user_key;             											//+   user key
        SequenceNumber sequence;    											//+   sequence
        ValueType type;             											//+   type: kTypeDeletion or kTypeValue

        ParsedInternalKey() { }  // Intentionally left uninitialized (for speed)
        ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)		//     
            : user_key(u), sequence(seq), type(t) { }
        std::string DebugString() const;
    }; 
    
    // Returns the user key portion of an internal key.
    inline Slice ExtractUserKey(const Slice& internal_key) {						//   User Key
        assert(internal_key.size() >= 8);
        return Slice(internal_key.data(), internal_key.size() - 8);
    }

    inline ValueType ExtractValueType(const Slice& internal_key) {					//   Type
        assert(internal_key.size() >= 8);
        const size_t n = internal_key.size();
        uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
        unsigned char c = num & 0xff;
        return static_cast<ValueType>(c);
    }
    void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {		//  InternalKey   string
        result->append(key.user_key.data(), key.user_key.size());
        PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
    }
    static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {				// sequence | type
        assert(seq <= kMaxSequenceNumber);
        assert(t <= kValueTypeForSeek);
        return (seq << 8) | t;
    }
    
    // A comparator for internal keys that uses a specified comparator for
    // the user key portion and breaks ties by decreasing sequence number.
    class InternalKeyComparator : public Comparator {
        private:
        const Comparator* user_comparator_;
        public:
        explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) { }
        virtual const char* Name() const;
        virtual int Compare(const Slice& a, const Slice& b) const;
        virtual void FindShortestSeparator(std::string* start,
        								const Slice& limit) const;
        virtual void FindShortSuccessor(std::string* key) const;

        const Comparator* user_comparator() const { return user_comparator_; }

        int Compare(const InternalKey& a, const InternalKey& b) const;
   };


    inline int InternalKeyComparator::Compare(const InternalKey& a, const InternalKey& b) const {
        return Compare(a.Encode(), b.Encode());	// Encode  string，    string      
    }
    int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
        // Order by:
        //    increasing user key (according to user-supplied comparator)
        //    decreasing sequence number
        //    decreasing type (though sequence# should be enough to disambiguate)
        int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
        if (r == 0) {
            const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
            const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
            if (anum > bnum) {
                r = -1;
                } else if (anum < bnum) {
                r = +1;
            }
        }
        return r;
    }


    inline bool ParseInternalKey(const Slice& internal_key,						//   InternalKey
    						    ParsedInternalKey* result) {				
        const size_t n = internal_key.size();
        if (n < 8) return false;
        uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
        unsigned char c = num & 0xff;											// type：1 byte
        result->sequence = num >> 8;											//    8  ，  1   type，   sequence
        result->type = static_cast<ValueType>(c);
        result->user_key = Slice(internal_key.data(), n - 8);						// User Key
        return (c <= static_cast<unsigned char>(kTypeValue));						//     ：type    
    }
   
 // A helper class useful for DBImpl::Get()
    class LookupKey {														//   LookupKey
        public:
        // Initialize *this for looking up user_key at a snapshot with
        // the specified sequence number.
        LookupKey(const Slice& user_key, SequenceNumber sequence);

        ~LookupKey();

        // Return a key suitable for lookup in a MemTable.
        Slice memtable_key() const { return Slice(start_, end_ - start_); }

        // Return an internal key (suitable for passing to an internal iterator)
        Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }

        // Return the user key
        Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }

        private:
        // We construct a char array of the form:
        //    klength  varint32               <-- start_
        //    userkey  char[klength]          <-- kstart_
        //    tag      uint64
        //                                    <-- end_
        // The array is a suitable MemTable key.
        // The suffix starting with "userkey" can be used as an InternalKey.
        const char* start_;
        const char* kstart_;
        const char* end_;
        char space_[200];      // Avoid allocation for short keys

        // No copying allowed
        LookupKey(const LookupKey&);
        void operator=(const LookupKey&);
        };

    inline LookupKey::~LookupKey() {
        if (start_ != space_) delete[] start_;
    }
    
    
    ：
   	class MemTableInserter : public WriteBatch::Handler {				// MemTableInserter    Memtable
            public:
            SequenceNumber sequence_;
            MemTable* mem_;

            virtual void Put(const Slice& key, const Slice& value) {		//     
                mem_->Add(sequence_, kTypeValue, key, value);
                sequence_++;
            }
            virtual void Delete(const Slice& key) {						//     
                mem_->Add(sequence_, kTypeDeletion, key, Slice());
                sequence_++;
            }
    };  
    Status WriteBatchInternal::InsertInto(const WriteBatch* b, MemTable* memtable) {	// 
        MemTableInserter inserter;
        inserter.sequence_ = WriteBatchInternal::Sequence(b);
        inserter.mem_ = memtable;
        return b->Iterate(&inserter);
    }
    
    

   요약:        1. SkipList 에 저 장 된 데이터 형식 은 Lookupkey + Value 에 대응 합 니 다. 그 형식 은:            (string) "internel - key - size + internal - key - data + value - size + value - data", \ # LookupKey 직렬 화 + 값            즉: (string) LookupKey + value - size + value - data                                      2. Internalkey 데이터 형식 은: (string) "user - key + sequence + type" 이 고 ParsedInternalkey 에 대응 합 니 다. 그 중에서 sequnce + type 은 8bytes 를 차지 하고 type 은 1 바이트 를 차지 합 니 다.                 ParsedInternalKey:             user key             sequence number             type         InternalKey:             string(ParsedInternalKey)   # Parse Internal Key 의 직렬 화 문자열             LookupKey:             internal-key-size + InternalKey         # InternalKey 길이 + InternalKey                  3. 의문: Memtable 의 추가 방법 은 table 를 호출 합 니 다.insert (buf) 시 buf 는 InternalKey + Value 입 니 다. 그러면 Skiplist 에서 key 의 정렬 은 value 부분 을 포함 합 니까?        Skiplist 가 템 플 릿 클래스 라 고 밝 히 고 Comparator 에 들 어 왔 기 때문에 InternalKeyComparator 대상 이 들 어 왔 습 니 다. Skiplist 에서 비교 할 때 InternalKeyComparator:: Comparator 함 수 를 실 행 했 습 니 다. 그 중에서 ExtractUserKey 를 호출 하여 user key 를 추출 했 기 때문에 최종 적 으로 비교 한 것 은 User Key 입 니 다. value 부분 은 비교 에 참여 하지 않 았 습 니 다.
        Skiplist 의 Node 데 이 터 는 InternalKey + Value - size + Value - data 입 니 다.