精华内容
下载资源
问答
  • 基本概念 数据库主要包括cache、日志文件、数据文件、CURRENT文件和manifest文件几大块。 所有文件都是依照类型+文件号命名规则,文件号非常重要,类似oraclesequence#。 其中...


    基本概念
    数据库主要包括cache、日志文件、数据文件、CURRENT文件和manifest文件几大块。


    所有文件都是依照类型+文件号的命名规则,文件号非常重要,类似oracle的sequence#。
    其中cache是当前写入的数据缓存,写入数据时
    1 将数据写入日志文件
    2 将数据放入cache
    当达到一定条件,如cache里的数据够多时
    1 将cache转成只读cache,供查询用。
    2 新建一个读写cache和一个新日志文件。
    3 将只读cache里的数据写到数据文件里,这种新生成的数据文件称为level 0。


    由于每次写文件后都会启用新的cache,写入的key可能和已有数据重复,将来也会落地成文件。
    因此leveldb会对文件进行“压缩,在多个level 0文件中给key去重,称为level 1。
    随着数据库运行,level 1还会进一步和level n+1的文件合并,以此类推。
    每次合并后删除老文件。
    这样做的结果就是从level 1开始,每层的文件不会有重复的key,层与层之间的文件也不会有重复的key,大大提高从文件查询的效率。
    由于所有文件的内容都是排序的,并且记录了key的范围,因此这些操作的成本非常可控。

    当数据库重启时会根据日志文件重新构建cache并将cache里的数据写到level 0文件里。


    上述所有信息称为数据库的一个Version。
    Version的增量叫VersionEdit,VersionEdit记录了增加哪些文件,减少哪些文件,以及文件的概要信息等。
    version1 + versionedit1 = version2
    数据库里可能会保存多个version信息,所有version的载体是VersionSet。

    这些信息还记录在manifest文件内,相当于oracle的控制文件。
    CURRENT文件记录数据库当前manifest文件的文件名。

    数据库宕机后,实例恢复的流程就是
    1 根据文件命名规则,在文件夹寻找之前的CURRENT 
    2 寻找之前的manifest 
    3 定位logfile 
    4 将logfile数据复原到cache 
    5 将cache里的数据写到level 0数据文件


    下面看代码
    初始化数据库包括新建数据库和打开已关闭的数据库两种情况
    功能入口是DB::Open

    点击(此处)折叠或打开

    1. Status DB::Open(const Options& options, const std::string& dbname,
    2.                 DB** dbptr) {
    3.   *dbptr = NULL;


    4.   /*
    5.   DBImpl是leveldb的“主类”,初始化配置信息
    6.   dbname是数据库的所在目录
    7.   */
    8.   DBImpl* impl = new DBImpl(options, dbname);
    9.   impl->mutex_.Lock();


    10.   /*
    11.   打开数据库,如果不存在就创建。
    12.   如果存在就检查manifest文件,并根据其中的信息创建一个VersionEdit,用这个VersionEdit还原数据库的Version。
    13.   */
    14.   VersionEdit edit;
    15.   Status s = impl->Recover(&edit); // Handles create_if_missing, error_if_exists
    16.   if (s.ok()) {
    17.     uint64_t new_log_number = impl->versions_->NewFileNumber();
    18.     WritableFile* lfile;


    19.     /*
    20.     以w选项打开一个新logfile。
    21.     lfile就是打开的文件,类型是PosixWritableFile,封装了一些IO操作。
    22.     */
    23.     s = options.env->NewWritableFile(LogFileName(dbname, new_log_number),
    24.                                      &lfile);
    25.     if (s.ok()) {
    26.       // 初始化当前logfile文件号
    27.       edit.SetLogNumber(new_log_number);
    28.       impl->logfile_ = lfile;
    29.       impl->logfile_number_ = new_log_number;
    30.       // log::Writer用来写日志,公共函数就一个AddRecord
    31.       impl->log_ = new log::Writer(lfile);


    32.       /*
    33.       1 结合VersionSet,进一步设置VersionEdit,
    34.       2 根据当前logfile号创建一个新version作为current version
    35.       3 创建manifest文件
    36.       4 创建一个snapshot
    37.       */
    38.       s = impl->versions_->LogAndApply(&edit, &impl->mutex_);
    39.     }
    40.     if (s.ok()) {
    41.       // 根据文件号等条件,删除不再需要的文件。
    42.       impl->DeleteObsoleteFiles();
    43.       // 进行一次压缩,把重复键值的文件由低级向高级合并。
    44.       impl->MaybeScheduleCompaction();
    45.     }
    46.   }
    47.   impl->mutex_.Unlock();
    48.   if (s.ok()) {
    49.     *dbptr = impl;
    50.   } else {
    51.     delete impl;
    52.   }
    53.   return s;
    54. }


    下面是Open函数一上来调用的构造函数

    点击(此处)折叠或打开

    1. DBImpl::DBImpl(const Options& raw_options, const std::string& dbname)
    2.       /*
    3.       leveldb将系统相关的操作封装到env里,
    4.       linux版的env是PosixEnv类,在util/env_posix.cc里
    5.       */
    6.     : env_(raw_options.env),
    7.       // comparator用来比较key的大小,可以自己实现,也可以用leveldb默认的
    8.       internal_comparator_(raw_options.comparator),
    9.       // 定义过滤数据的算法,比如布隆过滤等
    10.       internal_filter_policy_(raw_options.filter_policy),
    11.       // SanitizeOptions函数用来对参数raw_options的选项进行必要的处理,并封装成一个处理后的Options
    12.       options_(SanitizeOptions(dbname, &internal_comparator_,
    13.                                &internal_filter_policy_, raw_options)),
    14.       owns_info_log_(options_.info_log != raw_options.info_log),
    15.       owns_cache_(options_.block_cache != raw_options.block_cache),
    16.       // dbname其实是指定数据库的文件夹,所有数据文件都会放到这个文件夹下。
    17.       dbname_(dbname),


    18.       // 用于锁文件,linux的是PosixFileLock类,里面有一个文件描述符和一个字符串
    19.       db_lock_(NULL),
    20.       shutting_down_(NULL),


    21.       // 管理后台线程的并发
    22.       bg_cv_(&mutex_),


    23.       /*
    24.       下面两个memtable,是对SkipList类的封装。
    25.       关于SkipList, 参考我之前的博客 http://blog.itpub.net/26239116/viewspace-1839630/
    26.       具体封装方式是在memtable.h里定义typedef,并设置为成员变量
    27.       typedef SkipList<const char*, KeyComparator> Table;
    28.       ...
    29.       Table table_;
    30.       */
    31.       mem_(new MemTable(internal_comparator_)),
    32.       imm_(NULL),
    33.       logfile_(NULL),
    34.       logfile_number_(0),
    35.       log_(NULL),
    36.       seed_(0),
    37.       // 文件IO的工具
    38.       tmp_batch_(new WriteBatch),
    39.       bg_compaction_scheduled_(false),
    40.       manual_compaction_(NULL) {
    41.   mem_->Ref();
    42.   has_imm_.Release_Store(NULL);


    43.   // Reserve ten files or so for other uses and give the rest to TableCache.
    44.   /*
    45.   最大文件数减去预留的辅助文件数,需要维护数据的文件数
    46.   在创建TableCache的时候,这个文件数对应的是TableCache里lrucache的数量
    47.   关于lrucache,参考文献之前的博客 http://blog.itpub.net/26239116/viewspace-1842049/
    48.   */
    49.   const int table_cache_size = options_.max_open_files - kNumNonTableCacheFiles;
    50.   table_cache_ = new TableCache(dbname_, &options_, table_cache_size);


    51.   // 初始化VersionSet,用于存放数据库里所有version
    52.   versions_ = new VersionSet(dbname_, &options_, table_cache_,
    53.                              &internal_comparator_);
    54. }





    构造函数里调的SanitizeOptions的具体内容。对option做了一下预处理

    点击(此处)折叠或打开

    1. Options SanitizeOptions(const std::string& dbname,
    2.                         const InternalKeyComparator* icmp,
    3.                         const InternalFilterPolicy* ipolicy,
    4.                         const Options& src) {
    5.   // 复制一份调用者提供的Options,做返回值用。
    6.   Options result = src;
    7.   result.comparator = icmp;
    8.   result.filter_policy = (src.filter_policy != NULL) ? ipolicy : NULL;


    9.   // 校验数值型参数,太大的设置为最大值,太小的设置为最小值
    10.   ClipToRange(&result.max_open_files, 64 + kNumNonTableCacheFiles, 50000);
    11.   ClipToRange(&result.write_buffer_size, 64<<10, 1<<30);
    12.   ClipToRange(&result.block_size, 1<<10, 4<<20);


    13.   // 如果没有指定日志,创建一个。
    14.   if (result.info_log == NULL) {
    15.     // Open a log file in the same directory as the db
    16.     src.env->CreateDir(dbname); // In case it does not exist
    17.     /*
    18.     日志文件的命名规则是 dbname + "/LOG"
    19.     创建之前需要先原有的重命名为 dbname + "/LOG.old"
    20.     */
    21.     src.env->RenameFile(InfoLogFileName(dbname), OldInfoLogFileName(dbname));


    22.     /*
    23.     创建一个logger,对于linux平台,是创建一个PosixLogger
    24.     */
    25.     Status s = src.env->NewLogger(InfoLogFileName(dbname), &result.info_log);
    26.     if (!s.ok()) {
    27.       // No place suitable for logging
    28.       result.info_log = NULL;
    29.     }
    30.   }


    31.   /*
    32.   创建一个lru cache
    33.   关于lru cache,参考我前面的博客 http://blog.itpub.net/26239116/viewspace-1842049/
    34.   */
    35.   if (result.block_cache == NULL) {
    36.     result.block_cache = NewLRUCache(8 << 20);
    37.   }
    38.   return result;
    39. }



    数据库初始化的主要工作由DBImpl::Recover函数完成

    点击(此处)折叠或打开

    1. Status DBImpl::Recover(VersionEdit* edit) {
    2.   mutex_.AssertHeld();


    3.   // Ignore error from CreateDir since the creation of the DB is
    4.   // committed only when the descriptor is created, and this directory
    5.   // may already exist from a previous failed creation attempt.
    6.   env_->CreateDir(dbname_);
    7.   assert(db_lock_ == NULL);


    8.   /*
    9.     创建文件锁,格式是"dbname_/LOC"
    10.     linux版的env是env_posix.cc
    11.     大致过程是
    12.     1 对文件信息进行一系列记录,如记录到PosixFileLock类里。
    13.     2 创建一个“锁”文件,写入flock结构体写进去。flock定义在fcntl.h里。
    14.   */
    15.   Status s = env_->LockFile(LockFileName(dbname_), &db_lock_);
    16.   if (!s.ok()) {
    17.     return s;
    18.   }
    19.   
    20.   /*
    21.   判断current文件是否存在,格式是“dbname_/CURRENT”
    22.   用来记录当前的manifest文件名,madifest文件里记录当前数据库的概要信息,类似oracle的控制文件
    23.   */
    24.   if (!env_->FileExists(CurrentFileName(dbname_))) {
    25.     if (options_.create_if_missing) {
    26.       // 初始化一个新的VersionEdit,设置logfile信息,然后写入manifest文件。
    27.       s = NewDB();
    28.       if (!s.ok()) {
    29.         return s;
    30.       }
    31.     } else {
    32.       return Status::InvalidArgument(
    33.           dbname_, "does not exist (create_if_missing is false)");
    34.     }
    35.   } else {
    36.     if (options_.error_if_exists) {
    37.       return Status::InvalidArgument(
    38.           dbname_, "exists (error_if_exists is true)");
    39.     }
    40.   }


    41.   // 如果之前存在这个数据库,打开时需要做恢复工作,manifest文件里的信息应用的当前version。
    42.   s = versions_->Recover();
    43.   if (s.ok()) {
    44.     SequenceNumber max_sequence(0);


    45.     // Recover from all newer log files than the ones named in the
    46.     // descriptor (new log files may have been added by the previous
    47.     // incarnation without registering them in the descriptor).
    48.     //
    49.     // Note that PrevLogNumber() is no longer used, but we pay
    50.     // attention to it in case we are recovering a database
    51.     // produced by an older version of leveldb.
    52.     const uint64_t min_log = versions_->LogNumber();
    53.     const uint64_t prev_log = versions_->PrevLogNumber();
    54.     std::vector<std::string> filenames;
    55.     s = env_->GetChildren(dbname_, &filenames);
    56.     if (!s.ok()) {
    57.       return s;
    58.     }
    59.     std::set<uint64_t> expected;


    60.     // 从所有version里获得所有文件号
    61.     versions_->AddLiveFiles(&expected);
    62.     uint64_t number;
    63.     FileType type;
    64.     std::vector<uint64_t> logs;


    65.     /*
    66.     从文件夹内所有文件名中提取文件类型和文件号
    67.     从versions_提取的expected中移除这些文件号
    68.     同时记录其中有哪些log文件
    69.     */
    70.     for (size_t i = 0; i < filenames.size(); i++) {
    71.       if (ParseFileName(filenames[i], &number, &type)) {
    72.         expected.erase(number);
    73.         if (type == kLogFile && ((number >= min_log) || (number == prev_log)))
    74.           logs.push_back(number);
    75.       }
    76.     }


    77.     // 如果expected的内容么有全部清空,说明丢失文件了。
    78.     if (!expected.empty()) {
    79.       char buf[50];
    80.       snprintf(buf, sizeof(buf), "%d missing files; e.g.",
    81.                static_cast<int>(expected.size()));
    82.       return Status::Corruption(buf, TableFileName(dbname_, *(expected.begin())));
    83.     }


    84.     // 按顺序逐个恢复log文件
    85.     // Recover in the order in which the logs were generated
    86.     std::sort(logs.begin(), logs.end());
    87.     for (size_t i = 0; i < logs.size(); i++) {
    88.       s = RecoverLogFile(logs[i], edit, &max_sequence);


    89.       // The previous incarnation may not have written any MANIFEST
    90.       // records after allocating this log number. So we manually
    91.       // update the file number allocation counter in VersionSet.
    92.       versions_->MarkFileNumberUsed(logs[i]);
    93.     }


    94.     if (s.ok()) {
    95.       if (versions_->LastSequence() < max_sequence) {
    96.         versions_->SetLastSequence(max_sequence);
    97.       }
    98.     }
    99.   }


    100.   return s;
    101. }



    由于DBImpl::Recover前面已经判断过CURRENT文件是否存在,如果不存在就创建新数据库了,
    因此这里就是要处理新的或者曾经关闭过的数据库。

    点击(此处)折叠或打开

    1. Status VersionSet::Recover() {
    2.   struct LogReporter : public log::Reader::Reporter {
    3.     Status* status;
    4.     virtual void Corruption(size_t bytes, const Status& s) {
    5.       if (this->status->ok()) *this->status = s;
    6.     }
    7.   };


    8.   // Read "CURRENT" file, which contains a pointer to the current manifest file
    9.   std::string current;
    10.   // 从CURRENT文件把当前的manifest文件名读到字符串里current里
    11.   Status s = ReadFileToString(env_, CurrentFileName(dbname_), &current);
    12.   if (!s.ok()) {
    13.     return s;
    14.   }


    15.   /*
    16.   CURRENT文件应该只有一行,就是当前manifest文件名。
    17.   要求CURRENT文件必须以换行符结尾
    18.   这样resize后就只剩文件名了。
    19.   */
    20.   if (current.empty() || current[current.size()-1] != '\n') {
    21.     return Status::Corruption("CURRENT file does not end with newline");
    22.   }
    23.   current.resize(current.size() - 1);
    24.   
    25.   // 打开manifest文件
    26.   std::string dscname = dbname_ + "/" + current;
    27.   SequentialFile* file;
    28.   s = env_->NewSequentialFile(dscname, &file);
    29.   if (!s.ok()) {
    30.     return s;
    31.   }
    32.  
    33.   // 初始化logfile信息,构建一个新的Version作为current version
    34.   bool have_log_number = false;
    35.   bool have_prev_log_number = false;
    36.   bool have_next_file = false;
    37.   bool have_last_sequence = false;
    38.   uint64_t next_file = 0;
    39.   uint64_t last_sequence = 0;
    40.   uint64_t log_number = 0;
    41.   uint64_t prev_log_number = 0;


    42.   /*
    43.   此时的current_,也就是current version是之前在构造函数里初始化的
    44.   AppendVersion(new Version(this));
    45.   在AppendVersion中会把新初始化的Version作为current version
    46.   current_ = v;
    47.   因此到builder这一步,一切都值是初始化,还没有正式开始真正恢复操作
    48.   */
    49.   Builder builder(this, current_);


    50.   {
    51.     LogReporter reporter;
    52.     reporter.status = &s;
    53.     log::Reader reader(file, &reporter, true/*checksum*/, 0/*initial_offset*/);
    54.     Slice record;
    55.     std::string scratch;
    56.     // 解析manifest的内容,还原出上次关闭的数据库的logfile等信息,装入VersionEdit
    57.     while (reader.ReadRecord(&record, &scratch) && s.ok()) {
    58.       /*
    59.       创建一个edit,要改变Version的状态,就需要用VersionEdit
    60.       version1 + edit1 = verion2
    61.       */
    62.       VersionEdit edit;


    63.       /*
    64.       leveldb的存储是按一定格式的,需要decode还原
    65.       将manifest中读到的信息decode后放入edit,后面恢复会用到。
    66.       只是概要信息,比如新文件,删除了哪些文件等。
    67.       */
    68.       s = edit.DecodeFrom(record);
    69.       if (s.ok()) {
    70.         if (edit.has_comparator_ &&
    71.             edit.comparator_ != icmp_.user_comparator()->Name()) {
    72.           s = Status::InvalidArgument(
    73.               edit.comparator_ + " does not match existing comparator ",
    74.               icmp_.user_comparator()->Name());
    75.         }
    76.       }


    77.       if (s.ok()) {
    78.         /*
    79.         将edit的内容封装到builder里。
    80.         */
    81.         builder.Apply(&edit);
    82.       }


    83.       if (edit.has_log_number_) {
    84.         log_number = edit.log_number_;
    85.         have_log_number = true;
    86.       }


    87.       if (edit.has_prev_log_number_) {
    88.         prev_log_number = edit.prev_log_number_;
    89.         have_prev_log_number = true;
    90.       }


    91.       if (edit.has_next_file_number_) {
    92.         next_file = edit.next_file_number_;
    93.         have_next_file = true;
    94.       }


    95.       if (edit.has_last_sequence_) {
    96.         last_sequence = edit.last_sequence_;
    97.         have_last_sequence = true;
    98.       }
    99.     }
    100.   }
    101.   delete file;
    102.   file = NULL;


    103.   if (s.ok()) {
    104.     if (!have_next_file) {
    105.       s = Status::Corruption("no meta-nextfile entry in descriptor");
    106.     } else if (!have_log_number) {
    107.       s = Status::Corruption("no meta-lognumber entry in descriptor");
    108.     } else if (!have_last_sequence) {
    109.       s = Status::Corruption("no last-sequence-number entry in descriptor");
    110.     }


    111.     if (!have_prev_log_number) {
    112.       prev_log_number = 0;
    113.     }


    114.     MarkFileNumberUsed(prev_log_number);
    115.     MarkFileNumberUsed(log_number);
    116.   }


    117.   if (s.ok()) {
    118.     // 利用builder的信息封装一个新的version,追加到VersionSet里
    119.     Version* v = new Version(this);


    120.     /*
    121.     builder前面从edit里读了manifest文件,
    122.     SaveTo会将从manifest文件里读到的文件添加到Version.files_里
    123.     在打开数据库操作的后面步骤里,会读取files_里的文件信息,与目录下的实体文件进行对照,看文件全不全。
    124.     这个过程就是version + edit,只不过这个version是新建的空version。
    125.     最终得到的是上次关闭的数据库version
    126.     */
    127.     builder.SaveTo(v);
    128.     // Install recovered version
    129.     // 根据各level的文件大小计算一个“得分”,以后影响压缩行为
    130.     Finalize(v);
    131.     // 将新封装好的Version放到VersionSet里,作为current version
    132.     AppendVersion(v);
    133.     manifest_file_number_ = next_file;
    134.     next_file_number_ = next_file + 1;
    135.     last_sequence_ = last_sequence;
    136.     log_number_ = log_number;
    137.     prev_log_number_ = prev_log_number;
    138.   }


    139.   return s;
    140. }


    逐个恢复logfile

    点击(此处)折叠或打开

    1. Status DBImpl::RecoverLogFile(uint64_t log_number,
    2.                               VersionEdit* edit,
    3.                               SequenceNumber* max_sequence) {
    4.   struct LogReporter : public log::Reader::Reporter {
    5.     Env* env;
    6.     Logger* info_log;
    7.     const char* fname;
    8.     Status* status; // NULL if options_.paranoid_checks==false
    9.     virtual void Corruption(size_t bytes, const Status& s) {
    10.       Log(info_log, "%s%s: dropping %d bytes; %s",
    11.           (this->status == NULL ? "(ignoring error) " : ""),
    12.           fname, static_cast<int>(bytes), s.ToString().c_str());
    13.       if (this->status != NULL && this->status->ok()) *this->status = s;
    14.     }
    15.   };


    16.   mutex_.AssertHeld();


    17.   // Open the log file
    18.   std::string fname = LogFileName(dbname_, log_number);
    19.   SequentialFile* file;
    20.   // 只读打开logfile
    21.   Status status = env_->NewSequentialFile(fname, &file);
    22.   if (!status.ok()) {
    23.     MaybeIgnoreError(&status);
    24.     return status;
    25.   }


    26.   // Create the log reader.
    27.   LogReporter reporter;
    28.   reporter.env = env_;
    29.   reporter.info_log = options_.info_log;
    30.   reporter.fname = fname.c_str();
    31.   reporter.status = (options_.paranoid_checks ? &status : NULL);
    32.   // We intentionally make log::Reader do checksumming even if
    33.   // paranoid_checks==false so that corruptions cause entire commits
    34.   // to be skipped instead of propagating bad information (like overly
    35.   // large sequence numbers).
    36.   log::Reader reader(file, &reporter, true/*checksum*/,
    37.                      0/*initial_offset*/);
    38.   Log(options_.info_log, "Recovering log #%llu",
    39.       (unsigned long long) log_number);


    40.   // Read all the records and add to a memtable
    41.   std::string scratch;
    42.   Slice record;
    43.   WriteBatch batch;
    44.   MemTable* mem = NULL;
    45.   /*
    46.   逐行读取logfile
    47.   将得到的数据放入memtable mm里
    48.   */
    49.   while (reader.ReadRecord(&record, &scratch) &&
    50.          status.ok()) {
    51.     if (record.size() < 12) {
    52.       reporter.Corruption(
    53.           record.size(), Status::Corruption("log record too small"));
    54.       continue;
    55.     }
    56.     WriteBatchInternal::SetContents(&batch, record);


    57.     if (mem == NULL) {
    58.       mem = new MemTable(internal_comparator_);
    59.       mem->Ref();
    60.     }
    61.     status = WriteBatchInternal::InsertInto(&batch, mem);
    62.     MaybeIgnoreError(&status);
    63.     if (!status.ok()) {
    64.       break;
    65.     }
    66.     const SequenceNumber last_seq =
    67.         WriteBatchInternal::Sequence(&batch) +
    68.         WriteBatchInternal::Count(&batch) - 1;
    69.     if (last_seq > *max_sequence) {
    70.       *max_sequence = last_seq;
    71.     }
    72.     
    73.     // 当memtable使用量超过设置的值时,将数据刷到level 0 数据文件里。
    74.     // 这样在恢复过程中不会将内存撑爆
    75.     if (mem->ApproximateMemoryUsage() > options_.write_buffer_size) {
    76.       status = WriteLevel0Table(mem, edit, NULL);
    77.       if (!status.ok()) {
    78.         // Reflect errors immediately so that conditions like full
    79.         // file-systems cause the DB::Open() to fail.
    80.         break;
    81.       }
    82.       mem->Unref();
    83.       mem = NULL;
    84.     }
    85.   }


    86.   if (status.ok() && mem != NULL) {
    87.     status = WriteLevel0Table(mem, edit, NULL);
    88.     // Reflect errors immediately so that conditions like full
    89.     // file-systems cause the DB::Open() to fail.
    90.   }


    91.   if (mem != NULL) mem->Unref();
    92.   delete file;
    93.   return status;
    94. }



















    来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/26239116/viewspace-1846192/,如需转载,请注明出处,否则将追究法律责任。

    转载于:http://blog.itpub.net/26239116/viewspace-1846192/

    展开全文
  • C: Consistency 一致性 • A: Availability 可用性(指是快速获取数据)...10年前,Eric Brewer教授指出了著名CAP理论,后来Seth Gilbert 和 Nancy lynch两人证明了CAP理论正确性。CAP理论告诉我们,一个分布式...

     C: Consistency 一致性

    • A: Availability 可用性(指的是快速获取数据)

    • P: Tolerance of network Partition 分区容忍性(分布式)

    10年前,Eric Brewer教授指出了著名的CAP理论,后来Seth Gilbert 和 Nancy lynch两人证明了CAP理论的正确性。CAP理论告诉我们,一个分布式系统不可能满足一致性,可用性和分区容错性这三个需求,最多只能同时满足两个。

    BASE模型反ACID模型,完全不同ACID模型,牺牲高一致性,获得可用性或可靠性: BasicallyAvailable基本可用。支持分区失败(e.g. sharding碎片划分数据库) Soft state软状态状态可以有一段时间不同步,异步。 Eventually consistent最终一致,最终数据是一致的就可以了,而不是时时一致

    Cassandra是什么

    Cassandra 的名称来源于希腊神话,是特洛伊的一位悲剧性的女先知的名字,因此项目的Logo是一只放光的眼睛。

    Cassandra是一个高可靠的大规模分布式存储系统。高度可伸缩的、一致的、分布式的结构化key-value存储方案,集Google BigTable的数据模型与Amazon Dynamo的完全分布式的架构于一身。2007由facebook开发,2009年成为Apache的孵化项目。

    Cassandra使用了Google BigTable的数据模型,与面向行的传统的关系型数据库不同,这是一种面向列的数据库,列被组织成为列族(Column Family),在数据库中增加一列非常方便。对于搜索和一般的结构化数据存储,这个结构足够丰富和有效。

    Cassandra的系统架构与Dynamo一脉相承,是基于O(1)DHT(分布式哈希表)的完全P2P架构,与传统的基于Sharding的数据库集群相比,Cassandra可以几乎无缝地加入或删除节点,非常适于对于节点规模变化比较快的应用场景。

    Cassandra的数据会写入多个节点,来保证数据的可靠性,在一致性、可用性和网络分区耐受能力(CAP)的折衷问题上,Cassandra比较灵活,用户在读取时可以指定要求所有副本一致(高一致性)、读到一个副本即可(高可用性)或是通过选举来确认多数副本一致即可(折衷)。这样,Cassandra可以适用于有节点、网络失效,以及多数据中心的场景。

    3. Cassandra特点

    总结Cassandra的主要特点如下:

    (1) 列表数据结构

    在混合模式可以将超级列添加到5维的分布式Key-Value存储系统。

    (2) 模式灵活

    使用Cassandra,你不必提前解决记录中的字段。你可以在系统运行时随意的添加或移除字段。

    (3) 真正的可扩展性

    Cassandra是纯粹意义上的水平扩展。为给集群添加更多容量,可以增加动态添加节点即可。你不必重启任何进程,改变应用查询,或手动迁移任何数据。

    (4) 多数据中心识别

    你可以调整节点布局来避免某一个数据中心起火,一个备用的数据中心将至少有每条记录的完全复制。

    (5) 范围查询

    如果你不喜欢全部的键值查询,则可以设置键的范围来查询。

    (6) 分布式写操作

    你以在任何地方任何时间集中读或写任何数据。并且不会有任何单点失败。

     

    吸引我选择Cassandra作为NoSQL的原因主要有如下三点:

    极高的读写性能

    Cassandra写数据时,首先会将请求写入Commit Log以确保数据不会丢失,然后再写入内存中的Memtable,超过内存容量后再将内存中的数据刷到磁盘的SSTable,并定期异步对SSTable做数据合并(Compaction)以减少数据读取时的查询时间。因为写入操作只涉及到顺序写入和内存操作,因此有非常高的写入性能。而进行读操作时,Cassandra支持像LevelDB一样的实现机制,数据分层存储,将热点数据放在Memtable和相对小的SSTable中,所以能实现非常高的读性能。

    简单的部署结构

    相对Hbase等的主从结构,Cassandra是去中心化的P2P结构,所有节点完全一样没有单点,对小公司来说,我完全可以选择数据复制份数为2,先用两三台机器把Cassandra搭起来,既能保证数据的可靠性也方便今后机器的扩展,而Hbase起码得四五台机器吧。以后为了更好地支持客户可能需要在多个地方建立数据中心,而Cassandra对多数据中心的支持也很好,可以方便地部署多个数据中心,今早还看到一个俄罗斯最大电信公司的案例。另外我们的机器现在托管在一个小机房里,万一到时机器满了无法增加要考虑搬迁机房时,使用多数据中心的方式也能做到无缝迁移。

    和Spark的结合

    Cassandra作为一个底层的存储系统,能够方便地和Spark集成进行实时计算,这一点对我们的业务场景有致命的吸引力,我看到国外有很多使用案例就是用Spark+Cassandra来实现Velocity计算,比如Ooyala

     

    有时间再细看下其架构和底层原理:

    http://blog.jobbole.com/98970/

    http://zqhxuyuan.github.io/2015/08/25/2015-08-25-Cassandra-Architecture/

    转载于:https://www.cnblogs.com/bonelee/p/6211661.html

    展开全文
  • 百度链接处理系统每天处理万亿级超链数据,在过去,这是一系列Mapreduce批量过程,对时效性收录很不友好。在新一代搜索引擎架构设计中,我们采用流式、增量处理替代了之前批量、全量处理。链接从被发现到...

    转自:https://my.oschina.net/u/2982571/blog/775452 

    设计背景

    百度的链接处理系统每天处理万亿级的超链数据,在过去,这是一系列Mapreduce的批量过程,对时效性收录很不友好。在新一代搜索引擎架构设计中,我们采用流式、增量处理替代了之前的批量、全量处理。链接从被发现到存入链接库再到被调度程序选出,变成一个全实时的过程。在这个实时处理过程中,无论链接的入库还是选取,都需要对链接库进行修改,存储系统需要支持千万甚至上亿QPS的随机读写。旧的存储系统无论在单机性能,还是在扩展性方面,都无法满足,所以我们设计了Tera。

    链接存储的需求

    1. 数据按序存储

            支持主域、站点和前缀等多维度统计、读取。

    2. 自动负载均衡  

            分区可以动态调整,在一个分区数据量变大或者访问频率过高时,可以自动切分,小的分区也可以自动合并。

    3. 记录包含时间戳和多个版本

            对于链接历史抓取状态等记录,需要保留多个版本,对于策略回灌等场景,需要根据时间戳判断,避免旧的数据覆盖新的。

    4. 强一致性

            写入成功,立即可被所有的用户看到。

    5. 支持列存储  

            在用户只访问固定的少数几列时,能使用更小的IO,提供更高的性能(相对于访问全记录),要求底层存储将这部分列在物理上单独存储。

    设计目标

    功能目标

    1. 全局有序  

            key可以是任意字符串(二进制串),不限长度,比较逻辑可由用户定义,按Key的范围分区,分区内由单机维护有序,分区间由Master维护有序。

    2. 多版本  

            每个字段(单元格)都可以保留指定多个版本,系统自动回收过期版本,用户可以按时间戳存取

    3. 自动分片  

            用户不需要关心分片信息,系统自动处理热点区间的分裂,数据稀疏区间的合并。
            单个分区的数据量超过阈值,自动切分为多个,单个分区的读写频率增高时,自动切分

    4. 自动负载均衡和扩容  

            单机上保存多个分区,分区的总大小和总访问量达到阈值时,可以触发将部分分区迁移到空闲的机器。

     

    性能指标

    Tera设计使用SSD+SATA磁盘混布机型。  

    1. 单机吞吐  

            顺序读写: 100MB/S  
            随机读1KB: 30000QPS  
            随机写1KB: 30000QPS  

    2. 延迟  

            延迟和吞吐需要折衷考虑,在延迟敏感性不高的场合,使用延迟换吞吐策略,延迟定位在10ms级,写操作延迟<50ms,读延迟<10ms。  
            对于对延迟要求高的场合,读写延迟定位在<1ms,但吞吐会有损失,初期不做优化重点。  

    3. 扩展性  

            水平扩展至万台级别机器,单机管理百级别数据分片。

     数据量系统吞吐
    站点信息服务 10TB 百亿次/天
    用户行为分析 1PB 百亿次/天
    超链存储 10PB 万亿次/天
    页面存储 100PB 万亿次/天

    设计思路

    数据存储

    1. 数据持久性

            为保证数据安全性,要使用三副本存储,但维护副本的一致性与副本丢失恢复需要处理大量细节,基于一个分布式的文件系统构建,可以显著降低开发代价,所以我们选择了使用DFS(如BFS)
            系统的所有数据(用户数据和系统元数据)都存储在DFS上,通过DFS+WriteAheadLog保证数据的持久性,每次写入,保证在DFS上三副本落地后,才返回成功。

    2. 强一致性

            数据会按key分区存储在DFS上,分区信息由Master统一管理,Master保证每个分区同一时间只由一个数据节点提供读写服务,保证一致性

    3. 延迟换吞吐

            每次写操作落地一次导致的性能问题可以通过批量落地实现,比如每10ms数据落地一次,在数据落地前写操作不返回,代价是增加了5ms的平均响应时间

    4. 存储接口封装

            Tera不会以某一种DFS作为唯一选择,而是通过底层存储接口的封装,使其可搭建在其他分布式存储之上,方便用户根据个性化需求灵活地部署Tera。

     

    希望了解更多?请点击 https://github.com/baidu/tera

    转载于:https://www.cnblogs.com/bonelee/p/6211789.html

    展开全文
  • LevelDB

    2021-04-09 09:55:02
      LevelDB是Google开源持久化KV单机数据库,具有很高随机写,顺序读/写性能,但是随机读性能很一般,即LevelDB很适合应用在查询较少,而写很多场景。LevelDB应用了LSM (Log Structured Merge) 策略,lsm_...

    LevelDB基础

      LevelDB是Google开源的持久化KV单机数据库,具有很高的随机写,顺序读/写性能,但是随机读的性能很一般,即LevelDB很适合应用在查询较少,而写很多的场景。LevelDB应用了LSM (Log Structured Merge) 策略,lsm_tree对索引变更进行延迟及批量处理,并通过一种类似于归并排序的方式高效地将更新迁移到磁盘,降低索引插入开销。LevelDB具有以下特点和限制:

    特点:
    1、key和value都是任意长度的字节数组;
    2、entry(即一条K-V记录)默认是按照key的字典顺序存储的,当然开发者也可以重载这个排序函数;
    3、提供的基本操作接口:Put()、Delete()、Get()、Batch()4、支持批量操作以原子操作进行;
    5、可以创建数据全景的snapshot(快照),并允许在快照中查找数据;
    6、可以通过前向(或后向)迭代器遍历数据(迭代器会隐含的创建一个snapshot);
    7、自动使用Snappy压缩数据;
    8、可移植性;
    
    限制:
    1、非关系型数据模型(NoSQL),不支持sql语句,也不支持索引;
    2、一次只允许一个进程访问一个特定的数据库;
    3、没有内置的C/S架构,但开发者可以使用LevelDB库自己封装一个server;
    

      下图是LevelDB运行一段时间后的存储模型快照:内存中的MemTable和Immutable MemTable以及磁盘上的几种主要文件:Current文件,Manifest文件,log文件以及SSTable文件,以上六个文件和数据结构是LevelDb的主体构成元素。
    在这里插入图片描述
    log文件、MemTable、SSTable文件都是用来存储k-v记录的。针对于manifest和Current文件的作用,SSTable中的某个文件属于特定层级,而且其存储的记录是key有序的,那么必然有文件中的最小key和最大key,这是非常重要的信息,Manifest 就记载了SSTable各个文件的管理信息,比如属于哪个Level,文件名称叫啥,最小key和最大key各自是多少。下图是Manifest所存储内容的示意:
    在这里插入图片描述
      另外,在LevleDb的运行过程中,随着Compaction的进行,SSTable文件会发生变化,会有新的文件产生,老的文件被废弃,Manifest也会跟着反映这种变化,此时往往会新生成Manifest文件来记载这种变化,而Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。

    读写数据

    写操作流程:
    1、顺序写入磁盘log文件;
    2、写入内存memtable(采用skiplist结构实现);
    3、写入磁盘SST文件(sorted string table files),这步是数据归档的过程(永久化存储);

    注意:

    • log文件的作用是是用于系统崩溃恢复而不丢失数据,假如没有Log文件,因为写入的记录刚开始是保存在内存中的,此时如果系统崩溃,内存中的数据还没有来得及Dump到磁盘,所以会丢失数据;
    • 在写memtable时,如果其达到check point(满员)的话,会将其改成immutable memtable(只读),然后等待dump到磁盘SST文件中,此时也会生成新的memtable供写入新数据;
    • memtable和sst文件中的key都是有序的,log文件的key是无序的;
    • LevelDB删除操作也是插入,只是标记Key为删除状态,真正的删除要到Compaction的时候才去做真正的操作;
    • LevelDB没有更新接口,如果需要更新某个Key的值,只需要插入一条新纪录即可;或者先删除旧记录,再插入也可;

    读操作流程:
    1、在内存中依次查找memtable、immutable memtable;
    2、如果配置了cache,查找cache;
    3、根据mainfest索引文件,在磁盘中查找SST文件;
    在这里插入图片描述
      举个例子:我们先往levelDb里面插入一条数据 {key=“www.samecity.com” value=“我们”},过了几天,samecity网站改名为:69同城,此时我们插入数据{key=“www.samecity.com” value=“69同城”},同样的key,不同的value;逻辑上理解好像levelDb中只有一个存储记录,即第二个记录,但是在levelDb中很可能存在两条记录,即上面的两个记录都在levelDb中存储了,此时如果用户查询key=“www.samecity.com”,我们当然希望找到最新的更新记录,也就是第二个记录返回,因此,查找的顺序应该依照数据更新的新鲜度来,对于SSTable文件来说,如果同时在level L和Level L+1找到同一个key,level L的信息一定比level L+1的要新。

    log文件

      log文件在LevelDb中的主要作用是系统故障恢复时,能够保证不会丢失数据。因为在将记录写入内存的Memtable之前,会先写入Log文件,这样即使系统发生故障,Memtable中的数据没有来得及Dump到磁盘的SSTable文件,LevelDB也可以根据log文件恢复内存的Memtable数据结构内容,不会造成系统丢失数据,在这点上LevelDb和Bigtable是一致的。
      关于log文件的具体物理和逻辑布局,LevelDb对于一个log文件,会把它切割成以32K为单位的物理Block,每次读取的单位以一个Block作为基本读取单位,下图展示的log文件由3个Block构成,所以从物理布局来讲,一个log文件就是由连续的32K大小Block构成的。
    在这里插入图片描述
    在应用的视野里是看不到这些Block的,应用看到的是一系列的Key:Value对,在LevelDb内部,会将一个Key:Value对看做一条记录的数据,另外在这个数据前增加一个记录头,用来记载一些管理信息,以方便内部处理。
      记录头包含三个字段,CheckSum是对“类型”和“数据”字段的校验码,为了避免处理不完整或者是被破坏的数据,当LevelDb读取记录数据时候会对数据进行校验,如果发现和存储的CheckSum相同,说明数据完整无破坏,可以继续后续流程。“记录长度”记载了数据的大小,“数据”则是上面讲的Key:Value数值对,“类型”字段则指出了每条记录的逻辑结构和log文件物理分块结构之间的关系,主要有以下四种类型:FULL/FIRST/MIDDLE/LAST。如果记录类型是FULL,代表了当前记录内容完整地存储在一个物理Block里,没有被不同的物理Block切割开;如果记录被相邻的物理Block切割开,则类型会是其他三种类型中的一种。

    SSTable文件

      LevelDb不同层级有很多SSTable文件(以后缀.sst为特征),所有.sst文件内部布局都是一样的。Log文件是物理分块的,SSTable也一样会将文件划分为固定大小的物理存储块,但是两者逻辑布局大不相同,根本原因是:Log文件中的记录是Key无序的,即先后记录的key大小没有明确大小关系,而.sst文件内部则是根据记录的Key由小到大排列的。SST文件并不是平坦的结构,而是分层组织的,这也是LevelDB名称的来源。SST文件的一些实现细节:
    1、每个SST文件大小上限为2MB,所以,LevelDB通常存储了大量的SST文件;
    2、SST文件由若干个4K大小的blocks组成,block也是读/写操作的最小单元;
    3、SST文件的最后一个block是一个index,指向每个data block的起始位置,以及每个block第一个entry的key值(block内的key有序存储);
    4、使用Bloom filter加速查找,只要扫描index,就可以快速找出所有可能包含指定entry的block。
    5、同一个block内的key可以共享前缀(只存储一次),这样每个key只要存储自己唯一的后缀就行了。如果block中只有部分key需要共享前缀,在这部分key与其它key之间插入"reset"标识。
    在这里插入图片描述
      上图展示了一个.sst文件的物理划分结构,同Log文件一样,也是划分为固定大小的存储块,每个Block分为三个部分,肉色部分是数据存储区, 蓝色的Type区用于标识数据存储区是否采用了数据压缩算法(Snappy压缩或者无压缩两种),CRC部分则是数据校验码,用于判别数据是否在生成和传输中出错。下图展示了.sst文件的内部逻辑解释。
    在这里插入图片描述
      从大的方面,可以将.sst文件划分为数据存储区和数据管理区,数据存储区存放实际的Key:Value数据,数据管理区则提供一些索引指针等管理数据,目的是更快速便捷的查找相应的记录。两个区域都是在上述的分块基础上的,就是说文件的前面若干块实际存储KV数据,后面数据管理区存储管理数据。管理数据又分为四种不同类型:紫色的Meta Block,红色的MetaBlock 索引和蓝色的数据索引块以及一个文件尾部块。
      由log直接读取的entry会写到Level 0的SST中(最多4个文件);当Level 0的4个文件都存储满了,会选择其中一个文件Compact到Level 1的SST中;注意:Level 0的SSTable文件和其它Level的文件相比有特殊性:这个层级内的.sst文件,两个文件可能存在key重叠,比如有两个level 0的sst文件,文件A和文件B,文件A的key范围是:{bar, car},文件B的Key范围是{blue,samecity},那么很可能两个文件都存在key=”blood”的记录。对于其它Level的SSTable文件来说,则不会出现同一层级内.sst文件的key重叠现象,就是说Level L中任意两个.sst文件,可以保证它们的key值是不会重叠的。

    Log:最大4MB (可配置), 会写入Level 0;
    Level 0:最多4SST文件,;
    Level 1:总大小不超过10MB;
    Level 2:总大小不超过100MB;
    Level 3+:总大小不超过上一个Level ×10的大小。
    

      在读操作中,要查找一条entry,先查找log,如果没有找到,然后在Level 0中查找,如果还是没有找到,再依次往更底层的Level顺序查找;如果查找了一条不存在的entry,则要遍历一遍所有的Level才能返回"Not Found"的结果。在写操作中,新数据总是先插入开头的几个Level中,开头的这几个Level存储量也比较小,因此,对某条entry的修改或删除操作带来的性能影响就比较可控。可见,SST采取分层结构是为了最大限度减小插入新entry时的开销。

    Compaction操作

      对于LevelDb来说,写入记录操作很简单,删除记录仅仅写入一个删除标记就算完事,但是读取记录比较复杂,需要在内存以及各个层级文件中依照新鲜程度依次查找,代价很高。为了加快读取速度,levelDb采取了compaction的方式来对已有的记录进行整理压缩,通过这种方式,来删除掉一些不再有效的KV数据,减小数据规模,减少文件数量等。
      LevelDb的compaction机制和过程与Bigtable所讲述的是基本一致的,Bigtable中讲到三种类型的compaction:minor ,major和full:

    • minor Compaction,就是把memtable中的数据导出到SSTable文件中;
    • major compaction就是合并不同层级的SSTable文件;
    • full compaction就是将所有SSTable进行合并;

    LevelDb包含其中两种,minor和major。Minor compaction 的目的是当内存中的memtable大小到了一定值时,将内容保存到磁盘文件中,如下图:
    在这里插入图片描述
      immutable memtable其实是一个SkipList,其中的记录是根据key有序排列的,遍历key并依次写入一个level 0 的新建SSTable文件中,写完后建立文件的index 数据,这样就完成了一次minor compaction。从图中也可以看出,对于被删除的记录,在minor compaction过程中并不真正删除这个记录,原因也很简单,这里只知道要删掉key记录,但是这个KV数据在哪里?那需要复杂的查找,所以在minor compaction的时候并不做删除,只是将这个key作为一个记录写入文件中,至于真正的删除操作,在以后更高层级的compaction中会去做。
      当某个level下的SSTable文件数目超过一定设置值后,levelDb会从这个level的SSTable中选择一个文件(level>0),将其和高一层级的level+1的SSTable文件合并,这就是major compaction。
      在大于0的层级中,每个SSTable文件内的Key都是由小到大有序存储的,而且不同文件之间的key范围(文件内最小key和最大key之间)不会有任何重叠。Level 0的SSTable文件有些特殊,尽管每个文件也是根据Key由小到大排列,但是因为level 0的文件是通过minor compaction直接生成的,所以任意两个level 0下的两个sstable文件可能再key范围上有重叠。所以在做major compaction的时候,对于大于level 0的层级,选择其中一个文件就行,但是对于level 0来说,指定某个文件后,本level中很可能有其他SSTable文件的key范围和这个文件有重叠,这种情况下,要找出所有有重叠的文件和level 1的文件进行合并,即level 0在进行文件选择的时候,可能会有多个文件参与major compaction。
      LevelDb在选定某个level进行compaction后,还要选择是具体哪个文件要进行compaction,比如这次是文件A进行compaction,那么下次就是在key range上紧挨着文件A的文件B进行compaction,这样每个文件都会有机会轮流和高层的level 文件进行合并。
      如果选好了level L的文件A和level L+1层的文件进行合并,那么问题又来了,应该选择level L+1哪些文件进行合并?levelDb选择L+1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。也就是说,选定了level L的文件A,之后在level L+1中找到了所有需要合并的文件B,C,D……等等。剩下的问题就是具体是如何进行major 合并的?就是说给定了一系列文件,每个文件内部是key有序的,如何对这些文件进行合并,使得新生成的文件仍然Key有序,同时抛掉哪些不再有价值的KV 数据。
    在这里插入图片描述
      Major compaction的过程如下:对多个文件采用多路归并排序的方式,依次找出其中最小的Key记录,也就是对多个文件中的所有记录重新进行排序。之后采取一定的标准判断这个Key是否还需要保存,如果判断没有保存价值,那么直接抛掉,如果觉得还需要继续保存,那么就将其写入level L+1层中新生成的一个SSTable文件中。就这样对KV数据一一处理,形成了一系列新的L+1层数据文件,之前的L层文件和L+1层参与compaction 的文件数据此时已经没有意义了,所以全部删除。这样就完成了L层和L+1层文件记录的合并过程。
      那么在major compaction过程中,判断一个KV记录是否抛弃的标准是什么呢?其中一个标准是:对于某个key来说,如果在小于L层中存在这个Key,那么这个KV在major compaction过程中可以抛掉。因为对于层级低于L的文件中如果存在同一Key的记录,那么说明对于Key来说,有更新鲜的Value存在,那么过去的Value就等于没有意义了,所以可以删除。

    Cache

      对于levelDb来说,读取操作如果没有在内存的memtable中找到记录,要多次进行磁盘访问操作。假设最优情况,即第一次就在level 0中最新的文件中找到了这个key,那么也需要读取2次磁盘,一次是将SSTable的文件中的index部分读入内存,这样根据这个index可以确定key是在哪个block中存储;第二次是读入这个block的内容,然后在内存中查找key对应的value。
      LevelDb中引入了两个不同的Cache:Table Cache和Block Cache。其中Block Cache是配置可选的,即在配置文件中指定是否打开这个功能。
    在这里插入图片描述
      如上图,在Table Cache中,key值是SSTable的文件名称,Value部分包含两部分,一个是指向磁盘打开的SSTable文件的文件指针,这是为了方便读取内容;另外一个是指向内存中这个SSTable文件对应的Table结构指针,table结构在内存中,保存了SSTable的index内容以及用来指示block cache用的cache_id ,当然除此外还有其它一些内容。
      比如在get(key)读取操作中,如果levelDb确定了key在某个level下某个文件A的key range范围内,那么需要判断是不是文件A真的包含这个KV。此时,levelDb会首先查找Table Cache,看这个文件是否在缓存里,如果找到了,那么根据index部分就可以查找是哪个block包含这个key。如果没有在缓存中找到文件,那么打开SSTable文件,将其index部分读入内存,然后插入Cache里面,去index里面定位哪个block包含这个Key 。如果确定了文件哪个block包含这个key,那么需要读入block内容,这是第二次读取。
    在这里插入图片描述
      Block Cache是为了加快这个过程的,其中的key是文件的cache_id加上这个block在文件中的起始位置block_offset。而value则是这个Block的内容。
      如果levelDb发现这个block在block cache中,可以直接在cache里的block内容里面查找key的value就行,如果没找到呢?那么读入block内容并把它插入block cache中。
      levelDb就是这样通过两个cache来加快读取速度的。可以看出,如果读取的数据局部性比较好,即要读的数据大部分在cache里面都能读到,那么读取效率较高,而如果是对key进行顺序读取效率也不错,因为一次读入后可以多次被复用。但是如果是随机读取,其效率会很低下。

    版本控制

      在Leveldb中,Version就代表了一个版本,它包括当前磁盘及内存中的所有文件信息。在所有的version中,只有一个是CURRENT(当前版本),其它都是历史版本。当执行一次compaction 或者 创建一个Iterator后,Leveldb将在当前版本基础上创建一个新版本,当前版本就变成了历史版本。VersionSet 是所有Version的集合,管理着所有存活的Version。VersionEdit 表示Version之间的变化,相当于delta 增量,表示有增加了多少文件,删除了文件:

    Version0 + VersionEdit --> Version1 
    Version0->Version1->Version2->Version3
    

    VersionEdit会保存到MANIFEST文件中,当做数据恢复时就会从MANIFEST文件中读出来重建数据。
      Leveldb的这种版本的控制,类似于双buffer切换。比如我们的服务器上有一个字典库,每天我们需要更新这个字典库,我们可以新开一个buffer,将新的字典库加载到这个新buffer中,等到加载完毕,将字典的指针指向新的字典库。Leveldb的version管理和双buffer切换类似,但是如果原version被某个iterator引用,那么这个version会一直保持,直到没有被任何一个iterator引用,此时就可以删除这个version。

    展开全文
  • levelDB的效率

    千次阅读 2017-10-11 22:27:18
    nosql数据库大多采用leveldb或者类似leveldb的存储引擎,我们来看看它为什么能够这么快。 levelDB则采用了一种全新数据结构,叫做log structured merge tree(LSMT),写入数据时,一方面会把数据保存到内存,另一...
  • 目的 leveldb-tools提供了一种简单的方法来以常规的,易于解析的格式转储LevelDB(尤其是 )数据库。...例如,cznic的数据库可以cdbmake格式转储: kvaudit -d my.kvdb | leveldb-tools load my.leveldb
  • Leveldb 内部实现

    2014-07-26 16:41:00
    原文链接:leveldb.googlecode.com Files LevelDB的实现本质上类似于Bigtable中tablet(参见Bigtable论文5.3节)。但是,与论文中具体文件组织方式稍有不同,解释如下: 每个数据库由一组存储在指定目录下一个...
  • LevelDB详解

    2019-08-28 15:33:27
    LevelDB是Google开源持久化KV单机数据库,具有很高随机写,顺序读/写性能,但是随机读性能很一般,也就是说,LevelDB很适合应用在查询较少,而写很多场景。LevelDB应用了LSM(Log Structured Merge) 策略,...
  • 简介:Leveldb是一个google实现非常高效kv数据库,能够支持billion级别数据量了。 在这个数量级别下还有着非常高性能,主要归功于它良好设计。特别是LSM算法。LevelDB 是单进程服务,性能非常之高,在...
  • LevelDB初识

    2020-02-09 11:54:55
    LevelDB是Google开源持久化KV单机数据库,具有很高随机写,顺序读/写性能,但是随机读性能很一般,也就是说,LevelDB很适合应用在查询较少,而写很多场景。LevelDB应用了LSM(Log Structured Merge) 策略,...
  • SSDB是一个开源高性能数据库服务器, 使用Google LevelDB作为存储引擎, 大家有可能没听过leveldb的名字,但是淘宝开源nosql tair大家应该有所耳闻吧,他也是基于leveldb开发。ssdb支持T级别数据, 同时...
  • LevelDB介绍

    2018-10-08 14:39:35
    LevelDB是Google开源持久化KV单机数据库,具有很高随机写,顺序读/写性能,但是随机读性能很一般,也就是说,LevelDB很适合应用在查询较少,而写很多场景。LevelDB应用了LSM (Log Structured Merge) 策略,...
  • leveldb原理汇编

    2021-03-13 14:30:22
    LevelDB是Google开源持久化KV单机数据库,具有很高随机写,顺序读/写性能,但是随机读性能很一般,也就是说,LevelDB很适合应用在查询较少,而写很多场景。LevelDB应用了LSM(Log Structured Merge) 策略,...
  • LedisDB 是一个参考ssdb,采用go实现,底层基于leveldb类似redis高性能nosql数据库,提供了kv,list,hash以及zset数据结构支持。 最开始源于ssdb,在使用了一段时间之后,因为兴趣原因,决定用go实现一个...
  • LevelDB库简介

    2014-10-15 15:28:00
    LevelDB是Google开源持久化KV单机数据库,具有很高随机写,顺序读/写性能,但是随机读性能很一般,也就是说,LevelDB很适合应用在查询较少,而写很多场景。LevelDB应用了LSM (Log Structured Merge) 策略,...
  • leveldb深入浅出

    2019-09-15 11:45:13
    LevelDB 是一个快速提供持久化存储 key/value(byte array) 存储数据库,可以把它理解为一个存储在本地磁盘超大 map<string, string>。 其局限性有: 不是一个关系型数据库,不支持 sql 查询,不支持...

空空如也

空空如也

1 2 3 4 5 6
收藏数 113
精华内容 45
关键字:

leveldb类似的数据库