← Back to branch summary

~ubuntu-branches/ubuntu/trusty/leveldb/trusty

« back to all changes in this revision

Viewing changes to db/version_set.cc

  • Committer: Package Import Robot
  • Author(s): Alessio Treglia
  • Date: 2011-11-30 12:06:07 UTC
  • mfrom: (7.1.2 sid)
  • Revision ID: package-import@ubuntu.com-20111130120607-e973e9fkwp0re29b
Tags: 0+20111031.git36a5f8e-2
http://bugs.debian.org/647105
http://bugs.debian.org/648248
* Fix build failure with --as-needed flag enabled (Closes: #647105).
* Re-introduce Cristoph Egger's patch to allow compilation
  on kFreeBSD (Closes: #648248).

Show diffs side-by-side

added added

removed removed

Lines of Context:
db/version_set.cc
41
41
  return kTargetFileSize;  // We could vary per level to reduce number of files?
42
42
}
43
43
 
 
44
static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) {
 
45
  int64_t sum = 0;
 
46
  for (size_t i = 0; i < files.size(); i++) {
 
47
    sum += files[i]->file_size;
 
48
  }
 
49
  return sum;
 
50
}
 
51
 
44
52
namespace {
45
53
std::string IntSetToString(const std::set<uint64_t>& s) {
46
54
  std::string result = "{";
53
61
  result += "}";
54
62
  return result;
55
63
}
56
 
}
 
64
}  // namespace
57
65
 
58
66
Version::~Version() {
59
67
  assert(refs_ == 0);
96
104
  return right;
97
105
}
98
106
 
 
107
static bool AfterFile(const Comparator* ucmp,
 
108
                      const Slice* user_key, const FileMetaData* f) {
 
109
  // NULL user_key occurs before all keys and is therefore never after *f
 
110
  return (user_key != NULL &&
 
111
          ucmp->Compare(*user_key, f->largest.user_key()) > 0);
 
112
}
 
113
 
 
114
static bool BeforeFile(const Comparator* ucmp,
 
115
                       const Slice* user_key, const FileMetaData* f) {
 
116
  // NULL user_key occurs after all keys and is therefore never before *f
 
117
  return (user_key != NULL &&
 
118
          ucmp->Compare(*user_key, f->smallest.user_key()) < 0);
 
119
}
 
120
 
99
121
bool SomeFileOverlapsRange(
100
122
    const InternalKeyComparator& icmp,
 
123
    bool disjoint_sorted_files,
101
124
    const std::vector<FileMetaData*>& files,
102
 
    const Slice& smallest_user_key,
103
 
    const Slice& largest_user_key) {
104
 
  // Find the earliest possible internal key for smallest_user_key
105
 
  InternalKey small(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
106
 
  const uint32_t index = FindFile(icmp, files, small.Encode());
107
 
  return ((index < files.size()) &&
108
 
          icmp.user_comparator()->Compare(
109
 
              largest_user_key, files[index]->smallest.user_key()) >= 0);
 
125
    const Slice* smallest_user_key,
 
126
    const Slice* largest_user_key) {
 
127
  const Comparator* ucmp = icmp.user_comparator();
 
128
  if (!disjoint_sorted_files) {
 
129
    // Need to check against all files
 
130
    for (int i = 0; i < files.size(); i++) {
 
131
      const FileMetaData* f = files[i];
 
132
      if (AfterFile(ucmp, smallest_user_key, f) ||
 
133
          BeforeFile(ucmp, largest_user_key, f)) {
 
134
        // No overlap
 
135
      } else {
 
136
        return true;  // Overlap
 
137
      }
 
138
    }
 
139
    return false;
 
140
  }
 
141
 
 
142
  // Binary search over file list
 
143
  uint32_t index = 0;
 
144
  if (smallest_user_key != NULL) {
 
145
    // Find the earliest possible internal key for smallest_user_key
 
146
    InternalKey small(*smallest_user_key, kMaxSequenceNumber,kValueTypeForSeek);
 
147
    index = FindFile(icmp, files, small.Encode());
 
148
  }
 
149
 
 
150
  if (index >= files.size()) {
 
151
    // beginning of range is after all files, so no overlap.
 
152
    return false;
 
153
  }
 
154
 
 
155
  return !BeforeFile(ucmp, largest_user_key, files[index]);
110
156
}
111
157
 
112
158
// An internal iterator.  For a given version/level pair, yields
207
253
// If "*iter" points at a value or deletion for user_key, store
208
254
// either the value, or a NotFound error and return true.
209
255
// Else return false.
210
 
static bool GetValue(Iterator* iter, const Slice& user_key,
 
256
static bool GetValue(const Comparator* cmp,
 
257
                     Iterator* iter, const Slice& user_key,
211
258
                     std::string* value,
212
259
                     Status* s) {
213
260
  if (!iter->Valid()) {
218
265
    *s = Status::Corruption("corrupted key for ", user_key);
219
266
    return true;
220
267
  }
221
 
  if (parsed_key.user_key != user_key) {
 
268
  if (cmp->Compare(parsed_key.user_key, user_key) != 0) {
222
269
    return false;
223
270
  }
224
271
  switch (parsed_key.type) {
314
361
          f->number,
315
362
          f->file_size);
316
363
      iter->Seek(ikey);
317
 
      const bool done = GetValue(iter, user_key, value, &s);
 
364
      const bool done = GetValue(ucmp, iter, user_key, value, &s);
318
365
      if (!iter->status().ok()) {
319
366
        s = iter->status();
320
367
        delete iter;
358
405
}
359
406
 
360
407
bool Version::OverlapInLevel(int level,
361
 
                             const Slice& smallest_user_key,
362
 
                             const Slice& largest_user_key) {
363
 
  return SomeFileOverlapsRange(vset_->icmp_, files_[level],
364
 
                               smallest_user_key,
365
 
                               largest_user_key);
 
408
                             const Slice* smallest_user_key,
 
409
                             const Slice* largest_user_key) {
 
410
  return SomeFileOverlapsRange(vset_->icmp_, (level > 0), files_[level],
 
411
                               smallest_user_key, largest_user_key);
 
412
}
 
413
 
 
414
int Version::PickLevelForMemTableOutput(
 
415
    const Slice& smallest_user_key,
 
416
    const Slice& largest_user_key) {
 
417
  int level = 0;
 
418
  if (!OverlapInLevel(0, &smallest_user_key, &largest_user_key)) {
 
419
    // Push to next level if there is no overlap in next level,
 
420
    // and the #bytes overlapping in the level after that are limited.
 
421
    InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
 
422
    InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
 
423
    std::vector<FileMetaData*> overlaps;
 
424
    while (level < config::kMaxMemCompactLevel) {
 
425
      if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
 
426
        break;
 
427
      }
 
428
      GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
 
429
      const int64_t sum = TotalFileSize(overlaps);
 
430
      if (sum > kMaxGrandParentOverlapBytes) {
 
431
        break;
 
432
      }
 
433
      level++;
 
434
    }
 
435
  }
 
436
  return level;
 
437
}
 
438
 
 
439
// Store in "*inputs" all files in "level" that overlap [begin,end]
 
440
void Version::GetOverlappingInputs(
 
441
    int level,
 
442
    const InternalKey* begin,
 
443
    const InternalKey* end,
 
444
    std::vector<FileMetaData*>* inputs) {
 
445
  inputs->clear();
 
446
  Slice user_begin, user_end;
 
447
  if (begin != NULL) {
 
448
    user_begin = begin->user_key();
 
449
  }
 
450
  if (end != NULL) {
 
451
    user_end = end->user_key();
 
452
  }
 
453
  const Comparator* user_cmp = vset_->icmp_.user_comparator();
 
454
  for (size_t i = 0; i < files_[level].size(); ) {
 
455
    FileMetaData* f = files_[level][i++];
 
456
    const Slice file_start = f->smallest.user_key();
 
457
    const Slice file_limit = f->largest.user_key();
 
458
    if (begin != NULL && user_cmp->Compare(file_limit, user_begin) < 0) {
 
459
      // "f" is completely before specified range; skip it
 
460
    } else if (end != NULL && user_cmp->Compare(file_start, user_end) > 0) {
 
461
      // "f" is completely after specified range; skip it
 
462
    } else {
 
463
      inputs->push_back(f);
 
464
      if (level == 0) {
 
465
        // Level-0 files may overlap each other.  So check if the newly
 
466
        // added file has expanded the range.  If so, restart search.
 
467
        if (begin != NULL && user_cmp->Compare(file_start, user_begin) < 0) {
 
468
          user_begin = file_start;
 
469
          inputs->clear();
 
470
          i = 0;
 
471
        } else if (end != NULL && user_cmp->Compare(file_limit, user_end) > 0) {
 
472
          user_end = file_limit;
 
473
          inputs->clear();
 
474
          i = 0;
 
475
        }
 
476
      }
 
477
    }
 
478
  }
366
479
}
367
480
 
368
481
std::string Version::DebugString() const {
381
494
      AppendNumberTo(&r, files[i]->number);
382
495
      r.push_back(':');
383
496
      AppendNumberTo(&r, files[i]->file_size);
384
 
      r.append("['");
385
 
      AppendEscapedStringTo(&r, files[i]->smallest.Encode());
386
 
      r.append("' .. '");
387
 
      AppendEscapedStringTo(&r, files[i]->largest.Encode());
388
 
      r.append("']\n");
 
497
      r.append("[");
 
498
      r.append(files[i]->smallest.DebugString());
 
499
      r.append(" .. ");
 
500
      r.append(files[i]->largest.DebugString());
 
501
      r.append("]\n");
389
502
    }
390
503
  }
391
504
  return r;
540
653
          const InternalKey& this_begin = v->files_[level][i]->smallest;
541
654
          if (vset_->icmp_.Compare(prev_end, this_begin) >= 0) {
542
655
            fprintf(stderr, "overlapping ranges in same level %s vs. %s\n",
543
 
                    EscapeString(prev_end.Encode()).c_str(),
544
 
                    EscapeString(this_begin.Encode()).c_str());
 
656
                    prev_end.DebugString().c_str(),
 
657
                    this_begin.DebugString().c_str());
545
658
            abort();
546
659
          }
547
660
        }
814
927
  }
815
928
}
816
929
 
817
 
static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) {
818
 
  int64_t sum = 0;
819
 
  for (size_t i = 0; i < files.size(); i++) {
820
 
    sum += files[i]->file_size;
821
 
  }
822
 
  return sum;
823
 
}
824
 
 
825
930
void VersionSet::Finalize(Version* v) {
826
931
  // Precomputed best level for next compaction
827
932
  int best_level = -1;
967
1072
  for (int level = 1; level < config::kNumLevels - 1; level++) {
968
1073
    for (size_t i = 0; i < current_->files_[level].size(); i++) {
969
1074
      const FileMetaData* f = current_->files_[level][i];
970
 
      GetOverlappingInputs(level+1, f->smallest, f->largest, &overlaps);
 
1075
      current_->GetOverlappingInputs(level+1, &f->smallest, &f->largest,
 
1076
                                     &overlaps);
971
1077
      const int64_t sum = TotalFileSize(overlaps);
972
1078
      if (sum > result) {
973
1079
        result = sum;
977
1083
  return result;
978
1084
}
979
1085
 
980
 
// Store in "*inputs" all files in "level" that overlap [begin,end]
981
 
void VersionSet::GetOverlappingInputs(
982
 
    int level,
983
 
    const InternalKey& begin,
984
 
    const InternalKey& end,
985
 
    std::vector<FileMetaData*>* inputs) {
986
 
  inputs->clear();
987
 
  Slice user_begin = begin.user_key();
988
 
  Slice user_end = end.user_key();
989
 
  const Comparator* user_cmp = icmp_.user_comparator();
990
 
  for (size_t i = 0; i < current_->files_[level].size(); i++) {
991
 
    FileMetaData* f = current_->files_[level][i];
992
 
    if (user_cmp->Compare(f->largest.user_key(), user_begin) < 0 ||
993
 
        user_cmp->Compare(f->smallest.user_key(), user_end) > 0) {
994
 
      // Either completely before or after range; skip it
995
 
    } else {
996
 
      inputs->push_back(f);
997
 
    }
998
 
  }
999
 
}
1000
 
 
1001
1086
// Stores the minimal range that covers all entries in inputs in
1002
1087
// *smallest, *largest.
1003
1088
// REQUIRES: inputs is not empty
1113
1198
    // Note that the next call will discard the file we placed in
1114
1199
    // c->inputs_[0] earlier and replace it with an overlapping set
1115
1200
    // which will include the picked file.
1116
 
    GetOverlappingInputs(0, smallest, largest, &c->inputs_[0]);
 
1201
    current_->GetOverlappingInputs(0, &smallest, &largest, &c->inputs_[0]);
1117
1202
    assert(!c->inputs_[0].empty());
1118
1203
  }
1119
1204
 
1127
1212
  InternalKey smallest, largest;
1128
1213
  GetRange(c->inputs_[0], &smallest, &largest);
1129
1214
 
1130
 
  GetOverlappingInputs(level+1, smallest, largest, &c->inputs_[1]);
 
1215
  current_->GetOverlappingInputs(level+1, &smallest, &largest, &c->inputs_[1]);
1131
1216
 
1132
1217
  // Get entire range covered by compaction
1133
1218
  InternalKey all_start, all_limit;
1137
1222
  // changing the number of "level+1" files we pick up.
1138
1223
  if (!c->inputs_[1].empty()) {
1139
1224
    std::vector<FileMetaData*> expanded0;
1140
 
    GetOverlappingInputs(level, all_start, all_limit, &expanded0);
 
1225
    current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0);
1141
1226
    if (expanded0.size() > c->inputs_[0].size()) {
1142
1227
      InternalKey new_start, new_limit;
1143
1228
      GetRange(expanded0, &new_start, &new_limit);
1144
1229
      std::vector<FileMetaData*> expanded1;
1145
 
      GetOverlappingInputs(level+1, new_start, new_limit, &expanded1);
 
1230
      current_->GetOverlappingInputs(level+1, &new_start, &new_limit,
 
1231
                                     &expanded1);
1146
1232
      if (expanded1.size() == c->inputs_[1].size()) {
1147
1233
        Log(options_->info_log,
1148
1234
            "Expanding@%d %d+%d to %d+%d\n",
1163
1249
  // Compute the set of grandparent files that overlap this compaction
1164
1250
  // (parent == level+1; grandparent == level+2)
1165
1251
  if (level + 2 < config::kNumLevels) {
1166
 
    GetOverlappingInputs(level + 2, all_start, all_limit, &c->grandparents_);
 
1252
    current_->GetOverlappingInputs(level + 2, &all_start, &all_limit,
 
1253
                                   &c->grandparents_);
1167
1254
  }
1168
1255
 
1169
1256
  if (false) {
1170
1257
    Log(options_->info_log, "Compacting %d '%s' .. '%s'",
1171
1258
        level,
1172
 
        EscapeString(smallest.Encode()).c_str(),
1173
 
        EscapeString(largest.Encode()).c_str());
 
1259
        smallest.DebugString().c_str(),
 
1260
        largest.DebugString().c_str());
1174
1261
  }
1175
1262
 
1176
1263
  // Update the place where we will do the next compaction for this level.
1183
1270
 
1184
1271
Compaction* VersionSet::CompactRange(
1185
1272
    int level,
1186
 
    const InternalKey& begin,
1187
 
    const InternalKey& end) {
 
1273
    const InternalKey* begin,
 
1274
    const InternalKey* end) {
1188
1275
  std::vector<FileMetaData*> inputs;
1189
 
  GetOverlappingInputs(level, begin, end, &inputs);
 
1276
  current_->GetOverlappingInputs(level, begin, end, &inputs);
1190
1277
  if (inputs.empty()) {
1191
1278
    return NULL;
1192
1279
  }
1193
1280
 
 
1281
  // Avoid compacting too much in one shot in case the range is large.
 
1282
  const uint64_t limit = MaxFileSizeForLevel(level);
 
1283
  uint64_t total = 0;
 
1284
  for (int i = 0; i < inputs.size(); i++) {
 
1285
    uint64_t s = inputs[i]->file_size;
 
1286
    total += s;
 
1287
    if (total >= limit) {
 
1288
      inputs.resize(i + 1);
 
1289
      break;
 
1290
    }
 
1291
  }
 
1292
 
1194
1293
  Compaction* c = new Compaction(level);
1195
1294
  c->input_version_ = current_;
1196
1295
  c->input_version_->Ref();
1284
1383
  }
1285
1384
}
1286
1385
 
1287
 
}
 
1386
}  // namespace leveldb