11029364698

Committed 25 Sep 2024 08:33AM UTC coverage: 87.246% (+0.008%) from 87.238%

Build # 11029364698

Build Type

push

github

Committed by

locker

Commit Message

vinyl: fix crash when empty PK DDL races with DML

Vinyl doesn't support altering the primary index of a non-empty space,
but the check forbidding this isn't entirely reliable - the DDL function
may yield to wait for pending WAL writes to finish after ensuring that
the space doesn't contain any tuples. If a new tuples is inserted into
the space in the meantime, the DDL operation will proceed rebuilding
the primary index and trigger a crash because the code is written on
the assumption that it's rebuilding a secondary index:

```
./src/box/vinyl.c:1572: vy_check_is_unique_secondary_one: Assertion `lsm->index_id > 0' failed.
```

Let's fix this by moving the check after syncing on WAL.

Closes #10603

NO_DOC=bug fix

(cherry picked from commit 955537b57)

Run Details

68452 of 121721 branches covered (56.24%)

3 of 3 new or added lines in 1 file covered. (100.0%)

30 existing lines in 15 files now uncovered.

101059 of 115832 relevant lines covered (87.25%)

2485488.53 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.28

/src/box/vy_range.c

/*
 * Copyright 2010-2017, Tarantool AUTHORS, please see AUTHORS file.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *
 * 1. Redistributions of source code must retain the above
 *    copyright notice, this list of conditions and the
 *    following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above
 *    copyright notice, this list of conditions and the following
 *    disclaimer in the documentation and/or other materials
 *    provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY AUTHORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
 * AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
#include "vy_range.h"

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define RB_COMPACT 1
#include <small/rb.h>
#include <small/rlist.h>

#include "diag.h"
#include "iterator_type.h"
#include "key_def.h"
#include "trivia/util.h"
#include "tuple.h"
#include "vy_run.h"
#include "vy_stat.h"
#include "vy_stmt.h"

int
vy_range_tree_cmp(struct vy_range *range_a, struct vy_range *range_b)
{
        if (range_a == range_b)
                return 0;

        /* Any key > -inf. */
        if (range_a->begin.stmt == NULL)
                return -1;
        if (range_b->begin.stmt == NULL)
                return 1;

        assert(range_a->cmp_def == range_b->cmp_def);
        return vy_entry_compare(range_a->begin, range_b->begin,
                                range_a->cmp_def);
}

int
vy_range_tree_key_cmp(struct vy_entry entry, struct vy_range *range)
{
        /* Any key > -inf. */
        if (range->begin.stmt == NULL)
                return 1;
        return vy_entry_compare(entry, range->begin, range->cmp_def);
}

struct vy_range *
vy_range_tree_find_by_key(vy_range_tree_t *tree,
                          enum iterator_type iterator_type,
                          struct vy_entry key)
{
        if (vy_stmt_is_empty_key(key.stmt)) {
                switch (iterator_type) {
                case ITER_LT:
                case ITER_LE:
                case ITER_REQ:
                        return vy_range_tree_last(tree);
                case ITER_GT:
                case ITER_GE:
                case ITER_EQ:
                        return vy_range_tree_first(tree);
                default:
                        unreachable();
                        return NULL;
                }
        }
        struct vy_range *range;
        if (iterator_type == ITER_GE || iterator_type == ITER_GT ||
            iterator_type == ITER_EQ) {
                /**
                 * Case 1. part_count == 1, looking for [10]. ranges:
                 * {1, 3, 5} {7, 8, 9} {10, 15 20} {22, 32, 42}
                 *                      ^looking for this
                 * Case 2. part_count == 1, looking for [10]. ranges:
                 * {1, 2, 4} {5, 6, 7, 8} {50, 100, 200}
                 *            ^looking for this
                 * Case 3. part_count == 2, looking for [10]. ranges:
                 * {[1, 2], [2, 3]} {[9, 1], [10, 1], [10 2], [11 3]} {[12,..}
                 *                   ^looking for this
                 * Case 4. part_count == 2, looking for [10]. ranges:
                 * {[1, 2], [10, 1]} {[10, 2] [10 3] [11 3]} {[12, 1]..}
                 *  ^looking for this
                 * Case 5. part_count does not matter, looking for [10].
                 * ranges:
                 * {100, 200}, {300, 400}
                 * ^looking for this
                 */
                /**
                 * vy_range_tree_psearch finds least range with begin == key
                 * or previous if equal was not found
                 */
                range = vy_range_tree_psearch(tree, key);
                /* switch to previous for case (4) */
                if (range != NULL && range->begin.stmt != NULL &&
                    !vy_stmt_is_full_key(key.stmt, range->cmp_def) &&
                    vy_entry_compare(key, range->begin, range->cmp_def) == 0)
                        range = vy_range_tree_prev(tree, range);
                /* for case 5 or subcase of case 4 */
                if (range == NULL)
                        range = vy_range_tree_first(tree);
        } else {
                assert(iterator_type == ITER_LT || iterator_type == ITER_LE ||
                       iterator_type == ITER_REQ);
                /**
                 * Case 1. part_count == 1, looking for [10]. ranges:
                 * {1, 3, 5} {7, 8, 9} {10, 15 20} {22, 32, 42}
                 *                      ^looking for this
                 * Case 2. part_count == 1, looking for [10]. ranges:
                 * {1, 2, 4} {5, 6, 7, 8} {50, 100, 200}
                 *            ^looking for this
                 * Case 3. part_count == 2, looking for [10]. ranges:
                 * {[1, 2], [2, 3]} {[9, 1], [10, 1], [10 2], [11 3]} {[12,..}
                 *                   ^looking for this
                 * Case 4. part_count == 2, looking for [10]. ranges:
                 * {[1, 2], [10, 1]} {[10, 2] [10 3] [11 3]} {[12, 1]..}
                 *                    ^looking for this
                 * Case 5. part_count does not matter, looking for [10].
                 * ranges:
                 * {1, 2}, {3, 4, ..}
                 *          ^looking for this
                 */
                /**
                 * vy_range_tree_nsearch finds most range with begin == key
                 * or next if equal was not found
                 */
                range = vy_range_tree_nsearch(tree, key);
                if (range != NULL) {
                        /* fix curr_range for cases 2 and 3 */
                        if (range->begin.stmt != NULL &&
                            vy_entry_compare(key, range->begin,
                                             range->cmp_def) != 0) {
                                struct vy_range *prev;
                                prev = vy_range_tree_prev(tree, range);
                                if (prev != NULL)
                                        range = prev;
                        }
                } else {
                        /* Case 5 */
                        range = vy_range_tree_last(tree);
                }
        }
        return range;
}

struct vy_range *
vy_range_new(int64_t id, struct vy_entry begin, struct vy_entry end,
             struct key_def *cmp_def)
{
        struct vy_range *range = calloc(1, sizeof(*range));
        if (range == NULL) {
                diag_set(OutOfMemory, sizeof(*range),
                         "malloc", "struct vy_range");
                return NULL;
        }
        range->id = id;
        range->begin = begin;
        if (begin.stmt != NULL)
                tuple_ref(begin.stmt);
        range->end = end;
        if (end.stmt != NULL)
                tuple_ref(end.stmt);
        range->cmp_def = cmp_def;
        rlist_create(&range->slices);
        heap_node_create(&range->heap_node);
        return range;
}

void
vy_range_delete(struct vy_range *range)
{
        if (range->begin.stmt != NULL)
                tuple_unref(range->begin.stmt);
        if (range->end.stmt != NULL)
                tuple_unref(range->end.stmt);

        struct vy_slice *slice, *next_slice;
        rlist_foreach_entry_safe(slice, &range->slices, in_range, next_slice)
                vy_slice_delete(slice);

        TRASH(range);
        free(range);
}

int
vy_range_snprint(char *buf, int size, const struct vy_range *range)
{
        int total = 0;
        SNPRINT(total, snprintf, buf, size, "(");
        if (range->begin.stmt != NULL)
                SNPRINT(total, tuple_snprint, buf, size, range->begin.stmt);
        else
                SNPRINT(total, snprintf, buf, size, "-inf");
        SNPRINT(total, snprintf, buf, size, "..");
        if (range->end.stmt != NULL)
                SNPRINT(total, tuple_snprint, buf, size, range->end.stmt);
        else
                SNPRINT(total, snprintf, buf, size, "inf");
        SNPRINT(total, snprintf, buf, size, ")");
        return total;
}

void
vy_range_add_slice(struct vy_range *range, struct vy_slice *slice)
{
        rlist_add_entry(&range->slices, slice, in_range);
        range->slice_count++;
        vy_disk_stmt_counter_add(&range->count, &slice->count);
        range->version++;
}

void
vy_range_add_slice_before(struct vy_range *range, struct vy_slice *slice,
                          struct vy_slice *next_slice)
{
        rlist_add_tail(&next_slice->in_range, &slice->in_range);
        range->slice_count++;
        vy_disk_stmt_counter_add(&range->count, &slice->count);
        range->version++;
}

void
vy_range_remove_slice(struct vy_range *range, struct vy_slice *slice)
{
        assert(range->slice_count > 0);
        assert(!rlist_empty(&range->slices));
        rlist_del_entry(slice, in_range);
        range->slice_count--;
        vy_disk_stmt_counter_sub(&range->count, &slice->count);
        range->version++;
}

/**
 * To reduce write amplification caused by compaction, we follow
 * the LSM tree design. Runs in each range are divided into groups
 * called levels:
 *
 *   level 1: runs 1 .. L_1
 *   level 2: runs L_1 + 1 .. L_2
 *   ...
 *   level N: runs L_{N-1} .. L_N
 *
 * where L_N is the total number of runs, N is the total number of
 * levels, older runs have greater numbers. Runs at each subsequent
 * are run_size_ratio times larger than on the previous one. When
 * the number of runs at a level exceeds run_count_per_level, we
 * compact all its runs along with all runs from the upper levels
 * and in-memory indexes.  Including  previous levels into
 * compaction is relatively cheap, because of the level size
 * ratio.
 *
 * Given a range, this function computes the maximal level that needs
 * to be compacted and sets @compaction_priority to the number of runs
 * in this level and all preceding levels.
 */
void
vy_range_update_compaction_priority(struct vy_range *range,
                                    const struct index_opts *opts)
{
        assert(opts->run_count_per_level > 0);
        assert(opts->run_size_ratio > 1);

        range->compaction_priority = 0;
        vy_disk_stmt_counter_reset(&range->compaction_queue);

        if (range->slice_count <= 1) {
                /* Nothing to compact. */
                range->needs_compaction = false;
                return;
        }

        if (range->needs_compaction) {
                range->compaction_priority = range->slice_count;
                range->compaction_queue = range->count;
                return;
        }

        /* Total number of statements in checked runs. */
        struct vy_disk_stmt_counter total_stmt_count;
        vy_disk_stmt_counter_reset(&total_stmt_count);
        /* Total number of checked runs. */
        uint32_t total_run_count = 0;
        /* Estimated size of a compacted run, if compaction is scheduled. */
        uint64_t est_new_run_size = 0;
        /* The number of runs at the current level. */
        uint32_t level_run_count = 0;
        /*
         * The target (perfect) size of a run at the current level.
         * Calculated recurrently: the size of the next level equals
         * the size of the previous level times run_size_ratio.
         *
         * For the last level we want it to be slightly greater
         * than the size of the last (biggest, oldest) run so that
         * all newer runs are at least run_size_ratio times smaller,
         * because in conjunction with the fact that we never store
         * more than one run at the last level, this will keep space
         * amplification below 2 provided run_count_per_level is not
         * greater than (run_size_ratio - 1).
         *
         * So to calculate the target size of the first level, we
         * divide the size of the oldest run by run_size_ratio until
         * it exceeds the size of the newest run. Note, DIV_ROUND_UP
         * is important here, because if we used integral division,
         * then after descending to the last level we would get a
         * value slightly less than the last run size, not slightly
         * greater, as we wanted to, which could increase space
         * amplification by run_count_per_level in the worse case
         * scenario.
         */
        uint64_t target_run_size;

        uint64_t size;
        struct vy_slice *slice;
        slice = rlist_last_entry(&range->slices, struct vy_slice, in_range);
        size = MAX(slice->count.bytes, 1);
        slice = rlist_first_entry(&range->slices, struct vy_slice, in_range);
        do {
                target_run_size = size;
                size = DIV_ROUND_UP(target_run_size, opts->run_size_ratio);
        } while (size > (uint64_t)MAX(slice->count.bytes, 1));

        rlist_foreach_entry(slice, &range->slices, in_range) {
                size = slice->count.bytes;
                level_run_count++;
                total_run_count++;
                vy_disk_stmt_counter_add(&total_stmt_count, &slice->count);
                while (size > target_run_size) {
                        /*
                         * The run size exceeds the threshold
                         * set for the current level. Move this
                         * run down to a lower level. Switch the
                         * current level and reset the level run
                         * count.
                         */
                        level_run_count = 1;
                        /*
                         * If we have already scheduled
                         * a compaction of an upper level, and
                         * estimated compacted run will end up at
                         * this level, include the new run into
                         * this level right away to avoid
                         * a cascading compaction.
                         */
                        if (est_new_run_size > target_run_size)
                                level_run_count++;
                        /*
                         * Calculate the target run size for this
                         * level.
                         */
                        target_run_size *= opts->run_size_ratio;
                        /*
                         * Keep pushing the run down until
                         * we find an appropriate level for it.
                         */
                }
                /*
                 * Since all ranges constituting an LSM tree have
                 * the same configuration, they tend to get compacted
                 * simultaneously, leading to IO load spikes and, as
                 * a result, distortion of the LSM tree shape and
                 * increased read amplification. To prevent this from
                 * happening, we constantly randomize compaction pace
                 * among ranges by deferring compaction at each LSM
                 * tree level with some fixed small probability.
                 *
                 * Note, we can't use rand() directly here, because
                 * this function is called on every memory dump and
                 * scans all LSM tree levels. Instead we use the
                 * value of rand() from the slice creation time.
                 */
                uint32_t max_run_count = opts->run_count_per_level;
                if (slice->seed < RAND_MAX / 10)
                        max_run_count++;
                if (level_run_count > max_run_count) {
                        /*
                         * The number of runs at the current level
                         * exceeds the configured maximum. Arrange
                         * for compaction. We compact all runs at
                         * this level and upper levels.
                         */
                        range->compaction_priority = total_run_count;
                        range->compaction_queue = total_stmt_count;
                        est_new_run_size = total_stmt_count.bytes;
                }
        }

        if (level_run_count > 1) {
                /*
                 * Do not store more than one run at the last level
                 * to keep space amplification low.
                 */
                range->compaction_priority = total_run_count;
                range->compaction_queue = total_stmt_count;
        }
}

void
vy_range_update_dumps_per_compaction(struct vy_range *range)
{
        if (!rlist_empty(&range->slices)) {
                struct vy_slice *slice = rlist_last_entry(&range->slices,
                                                struct vy_slice, in_range);
                range->dumps_per_compaction = slice->run->dump_count;
        } else {
                range->dumps_per_compaction = 0;
        }
}

/**
 * Return true and set split_key accordingly if the range needs to be
 * split in two.
 *
 * - We should never split a range until it was merged at least once
 *   (actually, it should be a function of run_count_per_level/number
 *   of runs used for the merge: with low run_count_per_level it's more
 *   than once, with high run_count_per_level it's once).
 * - We should use the last run size as the size of the range.
 * - We should split around the last run middle key.
 * - We should only split if the last run size is greater than
 *   4/3 * range_size.
 */
bool
vy_range_needs_split(struct vy_range *range, int64_t range_size,
                     const char **p_split_key)
{
        struct vy_slice *slice;

        /* The range hasn't been merged yet - too early to split it. */
        if (range->n_compactions < 1)
                return false;

        /* Find the oldest run. */
        assert(!rlist_empty(&range->slices));
        slice = rlist_last_entry(&range->slices, struct vy_slice, in_range);

        /* The range is too small to be split. */
        if (slice->count.bytes < range_size * 4 / 3)
                return false;

        /* Find the median key in the oldest run (approximately). */
        struct vy_page_info *mid_page;
        mid_page = vy_run_page_info(slice->run, slice->first_page_no +
                                    (slice->last_page_no -
                                     slice->first_page_no) / 2);

        struct vy_page_info *first_page = vy_run_page_info(slice->run,
                                                slice->first_page_no);

        /* No point in splitting if a new range is going to be empty. */
        if (vy_key_compare(first_page->min_key, first_page->min_key_hint,
                           mid_page->min_key, mid_page->min_key_hint,
                           range->cmp_def) == 0)
                return false;
        /*
         * In extreme cases the median key can be < the beginning
         * of the slice, e.g.
         *
         * RUN:
         * ... |---- page N ----|-- page N + 1 --|-- page N + 2 --
         *     | min_key = [10] | min_key = [50] | min_key = [100]
         *
         * SLICE:
         * begin = [30], end = [70]
         * first_page_no = N, last_page_no = N + 1
         *
         * which makes mid_page_no = N and mid_page->min_key = [10].
         *
         * In such cases there's no point in splitting the range.
         */
        if (slice->begin.stmt != NULL &&
            vy_entry_compare_with_raw_key(slice->begin, mid_page->min_key,
                                          mid_page->min_key_hint,
                                          range->cmp_def) >= 0)
                return false;
        /*
         * The median key can't be >= the end of the slice as we
         * take the min key of a page for the median key.
         */
        assert(slice->end.stmt == NULL ||
               vy_entry_compare_with_raw_key(slice->end, mid_page->min_key,
                                             mid_page->min_key_hint,
                                             range->cmp_def) > 0);
        *p_split_key = mid_page->min_key;
        return true;
}

/**
 * Check if a range should be coalesced with one or more its neighbors.
 * If it should, return true and set @p_first and @p_last to the first
 * and last ranges to coalesce, otherwise return false.
 *
 * We coalesce ranges together when they become too small, less than
 * half the target range size to avoid split-coalesce oscillations.
 */
bool
vy_range_needs_coalesce(struct vy_range *range, vy_range_tree_t *tree,
                        int64_t range_size, struct vy_range **p_first,
                        struct vy_range **p_last)
{
        struct vy_range *it;

        /* Size of the coalesced range. */
        uint64_t total_size = range->count.bytes;
        /* Coalesce ranges until total_size > max_size. */
        uint64_t max_size = range_size / 2;

        /*
         * We can't coalesce a range that was scheduled for dump
         * or compaction, because it is about to be processed by
         * a worker thread.
         */
        assert(!vy_range_is_scheduled(range));

        *p_first = *p_last = range;
        for (it = vy_range_tree_next(tree, range);
             it != NULL && !vy_range_is_scheduled(it);
             it = vy_range_tree_next(tree, it)) {
                uint64_t size = it->count.bytes;
                if (total_size + size > max_size)
                        break;
                total_size += size;
                *p_last = it;
        }
        for (it = vy_range_tree_prev(tree, range);
             it != NULL && !vy_range_is_scheduled(it);
             it = vy_range_tree_prev(tree, it)) {
                uint64_t size = it->count.bytes;
                if (total_size + size > max_size)
                        break;
                total_size += size;
                *p_first = it;
        }
        return *p_first != *p_last;
}

1	/*
2	* Copyright 2010-2017, Tarantool AUTHORS, please see AUTHORS file.
3	*
4	* Redistribution and use in source and binary forms, with or
5	* without modification, are permitted provided that the following
6	* conditions are met:
7	*
8	* 1. Redistributions of source code must retain the above
9	* copyright notice, this list of conditions and the
10	* following disclaimer.
11	*
12	* 2. Redistributions in binary form must reproduce the above
13	* copyright notice, this list of conditions and the following
14	* disclaimer in the documentation and/or other materials
15	* provided with the distribution.
16	*
17	* THIS SOFTWARE IS PROVIDED BY AUTHORS ``AS IS'' AND
18	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
19	* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
21	* AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
22	* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
25	* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
26	* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
28	* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29	* SUCH DAMAGE.
30	*/
31	#include "vy_range.h"
32
33	#include <assert.h>
34	#include <stdbool.h>
35	#include <stddef.h>
36	#include <stdint.h>
37	#include <stdio.h>
38	#include <stdlib.h>
39
40	#define RB_COMPACT 1
41	#include <small/rb.h>
42	#include <small/rlist.h>
43
44	#include "diag.h"
45	#include "iterator_type.h"
46	#include "key_def.h"
47	#include "trivia/util.h"
48	#include "tuple.h"
49	#include "vy_run.h"
50	#include "vy_stat.h"
51	#include "vy_stmt.h"
52
53	int
54	vy_range_tree_cmp(struct vy_range range_a, struct vy_range range_b)	30,084✔
55	{
56	if (range_a == range_b)	30,084✔
57	return 0;	16,565✔
58
59	/* Any key > -inf. */
60	if (range_a->begin.stmt == NULL)	13,519✔
61	return -1;	3,819✔
62	if (range_b->begin.stmt == NULL)	9,700✔
63	return 1;	81✔
64
65	assert(range_a->cmp_def == range_b->cmp_def);	9,619!
66	return vy_entry_compare(range_a->begin, range_b->begin,	9,619✔
67	range_a->cmp_def);
68	}
69
70	int
71	vy_range_tree_key_cmp(struct vy_entry entry, struct vy_range *range)	1,451,940✔
72	{
73	/* Any key > -inf. */
74	if (range->begin.stmt == NULL)	1,451,940✔
75	return 1;	1,225,210✔
76	return vy_entry_compare(entry, range->begin, range->cmp_def);	226,721✔
77	}
78
79	struct vy_range *
80	vy_range_tree_find_by_key(vy_range_tree_t *tree,	1,354,480✔
81	enum iterator_type iterator_type,
82	struct vy_entry key)
83	{
84	if (vy_stmt_is_empty_key(key.stmt)) {	1,354,480✔
85	switch (iterator_type) {	61,094!
86	case ITER_LT:	2,723✔
87	case ITER_LE:
88	case ITER_REQ:
89	return vy_range_tree_last(tree);	2,723✔
90	case ITER_GT:	58,371✔
91	case ITER_GE:
92	case ITER_EQ:
93	return vy_range_tree_first(tree);	58,371✔
94	default:	×
95	unreachable();	×
96	return NULL;
97	}
98	}
99	struct vy_range *range;
100	if (iterator_type == ITER_GE \|\| iterator_type == ITER_GT \|\|	1,293,380✔
101	iterator_type == ITER_EQ) {
102	/**
103	* Case 1. part_count == 1, looking for [10]. ranges:
104	* {1, 3, 5} {7, 8, 9} {10, 15 20} {22, 32, 42}
105	* ^looking for this
106	* Case 2. part_count == 1, looking for [10]. ranges:
107	* {1, 2, 4} {5, 6, 7, 8} {50, 100, 200}
108	* ^looking for this
109	* Case 3. part_count == 2, looking for [10]. ranges:
110	* {[1, 2], [2, 3]} {[9, 1], [10, 1], [10 2], [11 3]} {[12,..}
111	* ^looking for this
112	* Case 4. part_count == 2, looking for [10]. ranges:
113	* {[1, 2], [10, 1]} {[10, 2] [10 3] [11 3]} {[12, 1]..}
114	* ^looking for this
115	* Case 5. part_count does not matter, looking for [10].
116	* ranges:
117	* {100, 200}, {300, 400}
118	* ^looking for this
119	*/
120	/**
121	* vy_range_tree_psearch finds least range with begin == key
122	* or previous if equal was not found
123	*/
124	range = vy_range_tree_psearch(tree, key);	1,285,700✔
125	/* switch to previous for case (4) */
126	if (range != NULL && range->begin.stmt != NULL &&	1,285,700!
127	!vy_stmt_is_full_key(key.stmt, range->cmp_def) &&	73,889✔
128	vy_entry_compare(key, range->begin, range->cmp_def) == 0)	10,316✔
129	range = vy_range_tree_prev(tree, range);	3,995✔
130	/* for case 5 or subcase of case 4 */
131	if (range == NULL)	1,285,700!
132	range = vy_range_tree_first(tree);	×
133	} else {
134	assert(iterator_type == ITER_LT \|\| iterator_type == ITER_LE \|\|	7,685!
135	iterator_type == ITER_REQ);
136	/**
137	* Case 1. part_count == 1, looking for [10]. ranges:
138	* {1, 3, 5} {7, 8, 9} {10, 15 20} {22, 32, 42}
139	* ^looking for this
140	* Case 2. part_count == 1, looking for [10]. ranges:
141	* {1, 2, 4} {5, 6, 7, 8} {50, 100, 200}
142	* ^looking for this
143	* Case 3. part_count == 2, looking for [10]. ranges:
144	* {[1, 2], [2, 3]} {[9, 1], [10, 1], [10 2], [11 3]} {[12,..}
145	* ^looking for this
146	* Case 4. part_count == 2, looking for [10]. ranges:
147	* {[1, 2], [10, 1]} {[10, 2] [10 3] [11 3]} {[12, 1]..}
148	* ^looking for this
149	* Case 5. part_count does not matter, looking for [10].
150	* ranges:
151	* {1, 2}, {3, 4, ..}
152	* ^looking for this
153	*/
154	/**
155	* vy_range_tree_nsearch finds most range with begin == key
156	* or next if equal was not found
157	*/
158	range = vy_range_tree_nsearch(tree, key);	7,685✔
159	if (range != NULL) {	7,685✔
160	/* fix curr_range for cases 2 and 3 */
161	if (range->begin.stmt != NULL &&	241!
162	vy_entry_compare(key, range->begin,	241!
163	range->cmp_def) != 0) {
164	struct vy_range *prev;
165	prev = vy_range_tree_prev(tree, range);	241✔
166	if (prev != NULL)	241!
167	range = prev;	241✔
168	}
169	} else {
170	/* Case 5 */
171	range = vy_range_tree_last(tree);	7,444✔
172	}
173	}
174	return range;	1,293,380✔
175	}
176
177	struct vy_range *
178	vy_range_new(int64_t id, struct vy_entry begin, struct vy_entry end,	9,358✔
179	struct key_def *cmp_def)
180	{
181	struct vy_range range = calloc(1, sizeof(range));	9,358✔
182	if (range == NULL) {	9,358!
183	diag_set(OutOfMemory, sizeof(*range),	×
184	"malloc", "struct vy_range");
185	return NULL;	×
186	}
187	range->id = id;	9,358✔
188	range->begin = begin;	9,358✔
189	if (begin.stmt != NULL)	9,358✔
190	tuple_ref(begin.stmt);	387✔
191	range->end = end;	9,358✔
192	if (end.stmt != NULL)	9,358✔
193	tuple_ref(end.stmt);	388✔
194	range->cmp_def = cmp_def;	9,358✔
195	rlist_create(&range->slices);	9,358✔
196	heap_node_create(&range->heap_node);	9,358✔
197	return range;	9,358✔
198	}
199
200	void
201	vy_range_delete(struct vy_range *range)	7,422✔
202	{
203	if (range->begin.stmt != NULL)	7,422✔
204	tuple_unref(range->begin.stmt);	339✔
205	if (range->end.stmt != NULL)	7,422✔
206	tuple_unref(range->end.stmt);	340✔
207
208	struct vy_slice slice, next_slice;
209	rlist_foreach_entry_safe(slice, &range->slices, in_range, next_slice)	18,050!
210	vy_slice_delete(slice);	1,603✔
211
212	TRASH(range);	7,422✔
213	free(range);	7,422✔
214	}	7,422✔
215
216	int
217	vy_range_snprint(char buf, int size, const struct vy_range range)	14✔
218	{
219	int total = 0;	14✔
220	SNPRINT(total, snprintf, buf, size, "(");	14!
221	if (range->begin.stmt != NULL)	14✔
222	SNPRINT(total, tuple_snprint, buf, size, range->begin.stmt);	3!
223	else
224	SNPRINT(total, snprintf, buf, size, "-inf");	11!
225	SNPRINT(total, snprintf, buf, size, "..");	14!
226	if (range->end.stmt != NULL)	14✔
227	SNPRINT(total, tuple_snprint, buf, size, range->end.stmt);	5!
228	else
229	SNPRINT(total, snprintf, buf, size, "inf");	9!
230	SNPRINT(total, snprintf, buf, size, ")");	14!
231	return total;	14✔
232	}
233
234	void
235	vy_range_add_slice(struct vy_range range, struct vy_slice slice)	4,887✔
236	{
237	rlist_add_entry(&range->slices, slice, in_range);	4,887✔
238	range->slice_count++;	4,887✔
239	vy_disk_stmt_counter_add(&range->count, &slice->count);	4,887✔
240	range->version++;	4,887✔
241	}	4,887✔
242
243	void
244	vy_range_add_slice_before(struct vy_range range, struct vy_slice slice,	1,023✔
245	struct vy_slice *next_slice)
246	{
247	rlist_add_tail(&next_slice->in_range, &slice->in_range);	1,023✔
248	range->slice_count++;	1,023✔
249	vy_disk_stmt_counter_add(&range->count, &slice->count);	1,023✔
250	range->version++;	1,023✔
251	}	1,023✔
252
253	void
254	vy_range_remove_slice(struct vy_range range, struct vy_slice slice)	3,462✔
255	{
256	assert(range->slice_count > 0);	3,462!
257	assert(!rlist_empty(&range->slices));	6,924!
258	rlist_del_entry(slice, in_range);	3,462✔
259	range->slice_count--;	3,462✔
260	vy_disk_stmt_counter_sub(&range->count, &slice->count);	3,462✔
261	range->version++;	3,462✔
262	}	3,462✔
263
264	/**
265	* To reduce write amplification caused by compaction, we follow
266	* the LSM tree design. Runs in each range are divided into groups
267	* called levels:
268	*
269	* level 1: runs 1 .. L_1
270	* level 2: runs L_1 + 1 .. L_2
271	* ...
272	* level N: runs L_{N-1} .. L_N
273	*
274	* where L_N is the total number of runs, N is the total number of
275	* levels, older runs have greater numbers. Runs at each subsequent
276	* are run_size_ratio times larger than on the previous one. When
277	* the number of runs at a level exceeds run_count_per_level, we
278	* compact all its runs along with all runs from the upper levels
279	* and in-memory indexes. Including previous levels into
280	* compaction is relatively cheap, because of the level size
281	* ratio.
282	*
283	* Given a range, this function computes the maximal level that needs
284	* to be compacted and sets @compaction_priority to the number of runs
285	* in this level and all preceding levels.
286	*/
287	void
288	vy_range_update_compaction_priority(struct vy_range *range,	4,765✔
289	const struct index_opts *opts)
290	{
291	assert(opts->run_count_per_level > 0);	4,765!
292	assert(opts->run_size_ratio > 1);	4,765!
293
294	range->compaction_priority = 0;	4,765✔
295	vy_disk_stmt_counter_reset(&range->compaction_queue);	4,765!
296
297	if (range->slice_count <= 1) {	4,765✔
298	/* Nothing to compact. */
299	range->needs_compaction = false;	1,945✔
300	return;	2,172✔
301	}
302
303	if (range->needs_compaction) {	2,820✔
304	range->compaction_priority = range->slice_count;	227✔
305	range->compaction_queue = range->count;	227✔
306	return;	227✔
307	}
308
309	/* Total number of statements in checked runs. */
310	struct vy_disk_stmt_counter total_stmt_count;
311	vy_disk_stmt_counter_reset(&total_stmt_count);	2,593!
312	/* Total number of checked runs. */
313	uint32_t total_run_count = 0;	2,593✔
314	/* Estimated size of a compacted run, if compaction is scheduled. */
315	uint64_t est_new_run_size = 0;	2,593✔
316	/* The number of runs at the current level. */
317	uint32_t level_run_count = 0;	2,593✔
318	/*
319	* The target (perfect) size of a run at the current level.
320	* Calculated recurrently: the size of the next level equals
321	* the size of the previous level times run_size_ratio.
322	*
323	* For the last level we want it to be slightly greater
324	* than the size of the last (biggest, oldest) run so that
325	* all newer runs are at least run_size_ratio times smaller,
326	* because in conjunction with the fact that we never store
327	* more than one run at the last level, this will keep space
328	* amplification below 2 provided run_count_per_level is not
329	* greater than (run_size_ratio - 1).
330	*
331	* So to calculate the target size of the first level, we
332	* divide the size of the oldest run by run_size_ratio until
333	* it exceeds the size of the newest run. Note, DIV_ROUND_UP
334	* is important here, because if we used integral division,
335	* then after descending to the last level we would get a
336	* value slightly less than the last run size, not slightly
337	* greater, as we wanted to, which could increase space
338	* amplification by run_count_per_level in the worse case
339	* scenario.
340	*/
341	uint64_t target_run_size;
342
343	uint64_t size;
344	struct vy_slice *slice;
345	slice = rlist_last_entry(&range->slices, struct vy_slice, in_range);	2,593✔
346	size = MAX(slice->count.bytes, 1);	2,593✔
347	slice = rlist_first_entry(&range->slices, struct vy_slice, in_range);	5,186✔
348	do {
349	target_run_size = size;	7,470✔
350	size = DIV_ROUND_UP(target_run_size, opts->run_size_ratio);	7,470✔
351	} while (size > (uint64_t)MAX(slice->count.bytes, 1));	7,470✔
352
353	rlist_foreach_entry(slice, &range->slices, in_range) {	22,498✔
354	size = slice->count.bytes;	8,656✔
355	level_run_count++;	8,656✔
356	total_run_count++;	8,656✔
357	vy_disk_stmt_counter_add(&total_stmt_count, &slice->count);	8,656!
358	while (size > target_run_size) {	13,819✔
359	/*
360	* The run size exceeds the threshold
361	* set for the current level. Move this
362	* run down to a lower level. Switch the
363	* current level and reset the level run
364	* count.
365	*/
366	level_run_count = 1;	5,163✔
367	/*
368	* If we have already scheduled
369	* a compaction of an upper level, and
370	* estimated compacted run will end up at
371	* this level, include the new run into
372	* this level right away to avoid
373	* a cascading compaction.
374	*/
375	if (est_new_run_size > target_run_size)	5,163✔
376	level_run_count++;	730✔
377	/*
378	* Calculate the target run size for this
379	* level.
380	*/
381	target_run_size *= opts->run_size_ratio;	5,163✔
382	/*
383	* Keep pushing the run down until
384	* we find an appropriate level for it.
385	*/
386	}
387	/*
388	* Since all ranges constituting an LSM tree have
389	* the same configuration, they tend to get compacted
390	* simultaneously, leading to IO load spikes and, as
391	* a result, distortion of the LSM tree shape and
392	* increased read amplification. To prevent this from
393	* happening, we constantly randomize compaction pace
394	* among ranges by deferring compaction at each LSM
395	* tree level with some fixed small probability.
396	*
397	* Note, we can't use rand() directly here, because
398	* this function is called on every memory dump and
399	* scans all LSM tree levels. Instead we use the
400	* value of rand() from the slice creation time.
401	*/
402	uint32_t max_run_count = opts->run_count_per_level;	8,656✔
403	if (slice->seed < RAND_MAX / 10)	8,656✔
404	max_run_count++;	900✔
405	if (level_run_count > max_run_count) {	8,656✔
406	/*
407	* The number of runs at the current level
408	* exceeds the configured maximum. Arrange
409	* for compaction. We compact all runs at
410	* this level and upper levels.
411	*/
412	range->compaction_priority = total_run_count;	2,862✔
413	range->compaction_queue = total_stmt_count;	2,862✔
414	est_new_run_size = total_stmt_count.bytes;	2,862✔
415	}
416	}
417
418	if (level_run_count > 1) {	2,593✔
419	/*
420	* Do not store more than one run at the last level
421	* to keep space amplification low.
422	*/
423	range->compaction_priority = total_run_count;	1,122✔
424	range->compaction_queue = total_stmt_count;	1,122✔
425	}
426	}
427
428	void
429	vy_range_update_dumps_per_compaction(struct vy_range *range)	4,945✔
430	{
431	if (!rlist_empty(&range->slices)) {	9,890✔
432	struct vy_slice *slice = rlist_last_entry(&range->slices,	4,724✔
433	struct vy_slice, in_range);
434	range->dumps_per_compaction = slice->run->dump_count;	4,724✔
435	} else {
436	range->dumps_per_compaction = 0;	221✔
437	}
438	}	4,945✔
439
440	/**
441	* Return true and set split_key accordingly if the range needs to be
442	* split in two.
443	*
444	* - We should never split a range until it was merged at least once
445	* (actually, it should be a function of run_count_per_level/number
446	* of runs used for the merge: with low run_count_per_level it's more
447	* than once, with high run_count_per_level it's once).
448	* - We should use the last run size as the size of the range.
449	* - We should split around the last run middle key.
450	* - We should only split if the last run size is greater than
451	* 4/3 * range_size.
452	*/
453	bool
454	vy_range_needs_split(struct vy_range *range, int64_t range_size,	1,323✔
455	const char **p_split_key)
456	{
457	struct vy_slice *slice;
458
459	/* The range hasn't been merged yet - too early to split it. */
460	if (range->n_compactions < 1)	1,323✔
461	return false;	634✔
462
463	/* Find the oldest run. */
464	assert(!rlist_empty(&range->slices));	1,378!
465	slice = rlist_last_entry(&range->slices, struct vy_slice, in_range);	689✔
466
467	/* The range is too small to be split. */
468	if (slice->count.bytes < range_size * 4 / 3)	689✔
469	return false;	483✔
470
471	/* Find the median key in the oldest run (approximately). */
472	struct vy_page_info *mid_page;
473	mid_page = vy_run_page_info(slice->run, slice->first_page_no +	412✔
474	(slice->last_page_no -	206✔
475	slice->first_page_no) / 2);	206✔
476
477	struct vy_page_info *first_page = vy_run_page_info(slice->run,	206✔
478	slice->first_page_no);
479
480	/* No point in splitting if a new range is going to be empty. */
481	if (vy_key_compare(first_page->min_key, first_page->min_key_hint,	206!
482	mid_page->min_key, mid_page->min_key_hint,	206✔
483	range->cmp_def) == 0)
484	return false;	×
485	/*
486	* In extreme cases the median key can be < the beginning
487	* of the slice, e.g.
488	*
489	* RUN:
490	* ... \|---- page N ----\|-- page N + 1 --\|-- page N + 2 --
491	* \| min_key = [10] \| min_key = [50] \| min_key = [100]
492	*
493	* SLICE:
494	* begin = [30], end = [70]
495	* first_page_no = N, last_page_no = N + 1
496	*
497	* which makes mid_page_no = N and mid_page->min_key = [10].
498	*
499	* In such cases there's no point in splitting the range.
500	*/
501	if (slice->begin.stmt != NULL &&	206✔
502	vy_entry_compare_with_raw_key(slice->begin, mid_page->min_key,	7!
503	mid_page->min_key_hint,
504	range->cmp_def) >= 0)
UNCOV 505	return false;	×
506	/*
507	* The median key can't be >= the end of the slice as we
508	* take the min key of a page for the median key.
509	*/
510	assert(slice->end.stmt == NULL \|\|	206!
511	vy_entry_compare_with_raw_key(slice->end, mid_page->min_key,
512	mid_page->min_key_hint,
513	range->cmp_def) > 0);
514	*p_split_key = mid_page->min_key;	206✔
515	return true;	206✔
516	}
517
518	/**
519	* Check if a range should be coalesced with one or more its neighbors.
520	* If it should, return true and set @p_first and @p_last to the first
521	* and last ranges to coalesce, otherwise return false.
522	*
523	* We coalesce ranges together when they become too small, less than
524	* half the target range size to avoid split-coalesce oscillations.
525	*/
526	bool
527	vy_range_needs_coalesce(struct vy_range range, vy_range_tree_t tree,	1,118✔
528	int64_t range_size, struct vy_range **p_first,
529	struct vy_range **p_last)
530	{
531	struct vy_range *it;
532
533	/* Size of the coalesced range. */
534	uint64_t total_size = range->count.bytes;	1,118✔
535	/* Coalesce ranges until total_size > max_size. */
536	uint64_t max_size = range_size / 2;	1,118✔
537
538	/*
539	* We can't coalesce a range that was scheduled for dump
540	* or compaction, because it is about to be processed by
541	* a worker thread.
542	*/
543	assert(!vy_range_is_scheduled(range));	1,118!
544
545	p_first = p_last = range;	1,118✔
546	for (it = vy_range_tree_next(tree, range);	1,122✔
547	it != NULL && !vy_range_is_scheduled(it);	606✔
548	it = vy_range_tree_next(tree, it)) {	4✔
549	uint64_t size = it->count.bytes;	539✔
550	if (total_size + size > max_size)	539✔
551	break;	535✔
552	total_size += size;	4✔
553	*p_last = it;	4✔
554	}
555	for (it = vy_range_tree_prev(tree, range);	1,119✔
556	it != NULL && !vy_range_is_scheduled(it);	598✔
557	it = vy_range_tree_prev(tree, it)) {	1✔
558	uint64_t size = it->count.bytes;	445✔
559	if (total_size + size > max_size)	445✔
560	break;	444✔
561	total_size += size;	1✔
562	*p_first = it;	1✔
563	}
564	return p_first != p_last;	1,118✔
565	}

tarantool / tarantool / 11029364698

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous