← Back to branch summary

~pbeaman/akiban-persistit/release-notes-3.2.2

« back to all changes in this revision

Viewing changes to src/test/java/com/persistit/ExchangeRebalanceTest.java

merge pbeaman: This is a replacement for the original fix-rebalance-exception branch.

https://code.launchpad.net/~pbeaman/akiban-persistit/fix-rebalance-exception2/+merge/136225

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/test/java/com/persistit/ExchangeRebalanceTest.java
 
1
/**
 
2
 * Copyright © 2012 Akiban Technologies, Inc.  All rights reserved.
 
3
 * 
 
4
 * This program and the accompanying materials are made available
 
5
 * under the terms of the Eclipse Public License v1.0 which
 
6
 * accompanies this distribution, and is available at
 
7
 * http://www.eclipse.org/legal/epl-v10.html
 
8
 * 
 
9
 * This program may also be available under different license terms.
 
10
 * For more information, see www.akiban.com or contact licensing@akiban.com.
 
11
 * 
 
12
 * Contributors:
 
13
 * Akiban Technologies, Inc.
 
14
 */
 
15
 
 
16
package com.persistit;
 
17
 
 
18
import static org.junit.Assert.assertEquals;
 
19
 
 
20
import org.junit.Test;
 
21
 
 
22
import com.persistit.exception.PersistitException;
 
23
import com.persistit.policy.SplitPolicy;
 
24
 
 
25
public class ExchangeRebalanceTest extends PersistitUnitTestCase {
 
26
 
 
27
    final StringBuilder sb = new StringBuilder();
 
28
 
 
29
    @Override
 
30
    public void setUp() throws Exception {
 
31
        super.setUp();
 
32
        while (sb.length() < Buffer.MAX_BUFFER_SIZE) {
 
33
            sb.append(RED_FOX);
 
34
        }
 
35
    }
 
36
 
 
37
    /**
 
38
     * Construct a tree with two adjacent pages that are nearly full such that
 
39
     * the second key B of the right page is long and has very small elided byte
 
40
     * count relative to the first key A on that page. Removing key A requires
 
41
     * the left sibling to have B as its max key. If B won't fit on the left
 
42
     * page, then Persistit splits the left page to make room for it. Note that
 
43
     * changes in key or page structure will likely break this test.
 
44
     * 
 
45
     * @throws Exception
 
46
     */
 
47
    @Test
 
48
    public void testRebalanceException() throws Exception {
 
49
        final Exchange exchange = _persistit.getExchange("persistit", "rebalance", true);
 
50
        exchange.setSplitPolicy(SplitPolicy.LEFT_BIAS);
 
51
        setUpPrettyFullBuffers(exchange, false, RED_FOX.length(), true);
 
52
        System.out.printf("\ntestRebalanceException\n");
 
53
        _persistit.checkAllVolumes();
 
54
        final int beforeRemove = countSiblings(exchange, 0);
 
55
        exchange.clear().append("b").previous(true);
 
56
        exchange.remove();
 
57
        _persistit.getCleanupManager().poll();
 
58
        _persistit.checkAllVolumes();
 
59
        final int afterRemove = countSiblings(exchange, 0);
 
60
        assertEquals("Remove should have caused rebalance", beforeRemove + 1, afterRemove);
 
61
    }
 
62
 
 
63
    /**
 
64
     * Similar logic to {@link #testRebalanceException()} except that the keys
 
65
     * are carefully constructed on the index leaf level rather than the data
 
66
     * level. To do this we use three long-ish records per major key in the data
 
67
     * pages so that the key pattern in the index leaf table aligns as desired.
 
68
     * 
 
69
     * @throws Exception
 
70
     */
 
71
    @Test
 
72
    public void testRebalanceIndexException() throws Exception {
 
73
        final Exchange exchange = _persistit.getExchange("persistit", "rebalance", true);
 
74
        exchange.setSplitPolicy(SplitPolicy.LEFT_BIAS);
 
75
        setUpPrettyFullBuffers(exchange, true, 0, true);
 
76
        System.out.printf("\ntestRebalanceIndexException\n");
 
77
        _persistit.checkAllVolumes();
 
78
        final int beforeRemove = countSiblings(exchange, 1);
 
79
 
 
80
        exchange.clear().append("b").previous(true);
 
81
        exchange.cut();
 
82
        exchange.remove(Key.GT);
 
83
        _persistit.getCleanupManager().poll();
 
84
        _persistit.checkAllVolumes();
 
85
        final int afterRemove = countSiblings(exchange, 1);
 
86
        assertEquals("Remove should have caused rebalance", beforeRemove + 1, afterRemove);
 
87
 
 
88
    }
 
89
 
 
90
    private void setUpPrettyFullBuffers(final Exchange ex, final boolean asIndex, final int valueLength,
 
91
            final boolean discontinuous) throws PersistitException {
 
92
 
 
93
        final int depth = asIndex ? 1 : 0;
 
94
        int a, b;
 
95
        long leftPage = 0;
 
96
 
 
97
        // load page A with keys of increasing length
 
98
        for (a = 10;; a++) {
 
99
            setUpDeepKey(ex, 'a', a);
 
100
            storeValue(ex, valueLength, asIndex);
 
101
            if (ex.getTree().getDepth() > depth) {
 
102
                final Buffer b1 = ex.fetchBufferCopy(depth);
 
103
                // Stop when nearly full
 
104
                if (b1.getAvailableSize() < valueLength + 20) {
 
105
                    break;
 
106
                }
 
107
                leftPage = b1.getPageAddress();
 
108
            }
 
109
        }
 
110
 
 
111
        // load additional keys into page B
 
112
        for (b = a + 1;; b++) {
 
113
            if (ex.getTree().getDepth() > depth) {
 
114
                final Buffer b2 = ex.fetchBufferCopy(depth);
 
115
                if (b2.getPageAddress() != leftPage && b2.getAvailableSize() < valueLength + 20) {
 
116
                    break;
 
117
                }
 
118
            }
 
119
            setUpDeepKey(ex, discontinuous && b > a ? 'b' : 'a', b);
 
120
            storeValue(ex, valueLength, asIndex);
 
121
        }
 
122
    }
 
123
 
 
124
    private void setUpDeepKey(final Exchange ex, final char fill, final int n) {
 
125
        ex.getKey().clear().append(keyString(fill, n, n - 34, 4, n)).append(1);
 
126
    }
 
127
 
 
128
    private void setupValue(final Exchange ex, final int valueLength) {
 
129
        ex.getValue().put(sb.toString().substring(0, valueLength));
 
130
    }
 
131
 
 
132
    private void storeValue(final Exchange ex, final int valueLength, final boolean asIndex) throws PersistitException {
 
133
        if (asIndex) {
 
134
            // Fill up one data page so that the base key will be inserted into
 
135
            // an index page
 
136
            setupValue(ex, ex.getBufferPool().getBufferSize() / 4);
 
137
            for (int i = 1; i < 4; i++) {
 
138
                ex.cut().append(i).store();
 
139
            }
 
140
        } else {
 
141
            setupValue(ex, valueLength);
 
142
            ex.store();
 
143
        }
 
144
    }
 
145
 
 
146
    String keyString(final char fill, final int length, final int prefix, final int width, final int k) {
 
147
        final StringBuilder sb = new StringBuilder();
 
148
        for (int i = 0; i < prefix && i < length; i++) {
 
149
            sb.append(fill);
 
150
        }
 
151
        sb.append(String.format("%0" + width + "d", k));
 
152
        for (int i = length - sb.length(); i < length; i++) {
 
153
            sb.append(fill);
 
154
        }
 
155
        sb.setLength(length);
 
156
        return sb.toString();
 
157
    }
 
158
 
 
159
    private int countSiblings(final Exchange exchange, final int level) throws PersistitException {
 
160
        int count = 0;
 
161
        exchange.clear().append(Key.BEFORE);
 
162
        Buffer b = exchange.fetchBufferCopy(level);
 
163
        while (true) {
 
164
            count++;
 
165
            final long rightSibling = b.getRightSibling();
 
166
            if (rightSibling != 0) {
 
167
                b = exchange.getBufferPool().getBufferCopy(exchange.getVolume(), rightSibling);
 
168
            } else {
 
169
                break;
 
170
            }
 
171
        }
 
172
        return count;
 
173
    }
 
174
 
 
175
}