Сергей Деревяго

Хеш-таблица с транзакциями на Go

1. Введение

Сегодня вашему вниманию предлагаются переводы двух классических текстов.

Да, можно бесконечно спорить о ненужности для тех, кто все читал в оригинале... Но ведь любой нормальный перевод мгновенно расширяет Аудиторию! И как глоток свежего воздуха, он способен спасти потерявших Надежду... (смахнул слезу пробелом)

С уважением, Сергей Деревяго.

2. Хеш-таблица с транзакциями

Любой мужчина в возрасте внезапно для себя осознает, что ему уже не хватает синхронизированной хеш-таблицы... Да, это Классика!

Ну а сейчас есть шанс и насладиться переводом. Внезапно, переводом с C++ на Go!

И что тут эдакого?

Ну, как сказать... Оригинальная хеш-таблица с транзакциями, внутри процесса, без плясок с бубнами да с ускорением в десятки раз... Это было совсем непросто! Можно даже сказать, Удивительно.

Суть в том, что удивительное НЕВОЗМОЖНО! При переходе с C++ на Go:

Вы когда-нибудь думали про unsafe и go:linkname? А в новоязе это мыслепреступление!

2.1. Пример использования

Так что же такое mdb.MemDb и с чем его едят?

Ну, в первом приближении, все выглядит примерно так:

lib\mdb\memdb.go 
func NewMemDb() MemDb { /* ... */ }

type MemDb interface {
    Close() error
    StartTrn() Transaction
}

type Transaction interface {
    Close() error

    Get(key Ptrsz) (Ptrsz, bool)
    All(getKeys bool, getVals bool) (keys []Ptrsz, vals []Ptrsz)

    Set(key Ptrsz, val Ptrsz)
    Del(key Ptrsz)

    DependVal(key Ptrsz, val Ptrsz)
    DependDel(key Ptrsz)

    Commit() error
    Rollback() error
}

А именно:

Продолжаем наблюдение:

lib\mdb\memdb.go 
type MemDb interface {
    // ...
    StartRdr() Reader
}

type Reader interface {
    Close() error

    Get(key Ptrsz) (Ptrsz, bool)
    All(getKeys bool, getVals bool) (keys []Ptrsz, vals []Ptrsz)
}

Так точно:

На месте, стой! Раз-два! Даю пример.

Как всегда, речь пойдет о деньгах: совершим пару-тройку транзакций. А для этого создадим минимальный Account с функциями сериализации/десериализации:

examples\memdb\account.go 
type Account struct {
    FirstName string
    LastName  string
    BirthDate time.Time
    Amt       int
}

func (my *Account) Write(to *lib.MemOutBuf, overwrite bool) lib.Ptrsz {
    if overwrite {
        to.Clear()
    }

    to.WriteString(my.FirstName)
    to.WriteString(my.LastName)
    {
        var un int64 = my.BirthDate.UnixNano()
        lib.WriteBytes(to, &un)
    }
    lib.WriteBytes(to, &my.Amt)

    return to.Get()
}

func (my *Account) Read(from lib.Ptrsz) {
    buf := lib.MemInBuf(from)

    my.FirstName = buf.ReadString()
    my.LastName = buf.ReadString()
    {
        var un int64
        lib.ReadBytes(&buf, &un)
        my.BirthDate = time.Unix(0, un).UTC()
    }
    lib.ReadBytes(&buf, &my.Amt)
}

Все очевидно. Шагом марш!

examples\memdb\main.go 
func main() {
    db := mdb.NewMemDb()
    defer func() { lib.AssertNil(db.Close()) }()

    Setup(db)
    Print(db)

    // ...
}

func Print(db mdb.MemDb) {
    rd := db.StartRdr()
    defer func() { lib.AssertNil(rd.Close()) }()

    keys, vals := rd.All(true, true)
    for i := 0; i < len(keys); i++ {
        var key int
        lib.PtrszAssign(&key, keys[i])

        var acc Account
        acc.Read(vals[i])

        fmt.Printf("%d\t%s\t%s\t%s\t%d\n",
            key, acc.FirstName, acc.LastName, acc.BirthDate.Format("2006-1-2"), acc.Amt)
    }

    fmt.Println()
}

Мы видим в деле MemDb и Reader: функция main() создает и закрывает MemDb, а Print() работает через Reader. И для старта имеем: 

1  First1  Last1  2000-1-21  100
2  First2  Last2  2000-2-22  200
3  First3  Last3  2000-3-23  300

А сейчас переведем 10 тугриков с первого на второй счет посредством Transfer1(db, 1, 2, 10):

examples\memdb\main.go 
func main() {
    // ...

    lib.AssertNil(Transfer1(db, 1, 2, 10))
    Print(db)
}

func Transfer1(db mdb.MemDb, keyFrom int, keyTo int, amt int) error {
    buf := lib.NewMemOutBuf(100)

    tr := db.StartTrn()
    defer func() { lib.AssertNil(tr.Close()) }()

    pk1 := lib.PtrToPtrsz(&keyFrom)
    val1, ok := tr.Get(pk1)
    if !ok {
        return fmt.Errorf("not found: %d", keyFrom)
    }

    var acc1 Account
    acc1.Read(val1)
    acc1.Amt -= amt

    tr.DependVal(pk1, val1)
    tr.Set(pk1, acc1.Write(&buf, true))

    pk2 := lib.PtrToPtrsz(&keyTo)
    val2, ok := tr.Get(pk2)
    if !ok {
        return fmt.Errorf("not found: %d", keyTo)
    }

    var acc2 Account
    acc2.Read(val2)
    acc2.Amt += amt

    tr.DependVal(pk2, val2)
    tr.Set(pk2, acc2.Write(&buf, true))

    {
        // concurrent transaction
        // lib.AssertNil(UpdateName(&buf, db, keyFrom, "From", "Here"))
        // lib.AssertNil(UpdateName(&buf, db, keyTo, "To", "There"))
        // Print(db)
    }

    VeryLongOperation()
    return tr.Commit(nil, nil)
}

Здесь очень много интересного:

В результате чего мы увидим: 

1  First1  Last1  2000-1-21  90
2  First2  Last2  2000-2-22  210
3  First3  Last3  2000-3-23  300

От кого-то кому-то ушло 10 тугриков. Что, в общем, не удивительно.

Но мы же хотим удивиться!

Хорошо. Все сейчас удивятся от действия DependVal(). А для этого раскомментируем параллельную транзакцию:

examples\memdb\main.go 
func Transfer1(db mdb.MemDb, keyFrom int, keyTo int, amt int) error {
    // ...

    {
        // concurrent transaction
        lib.AssertNil(UpdateName(&buf, db, keyFrom, "From", "Here"))
        lib.AssertNil(UpdateName(&buf, db, keyTo, "To", "There"))
        Print(db)
    }

    VeryLongOperation()
    return tr.Commit(nil, nil)
}

Тем самым, мы имитируем одновременное изменение счета кем-то еще, между нашими вызовами StartTrn() и Commit(). Причем, изменяется только имя! Что, по сути, на сумму влиять не должно, но: 

1  First1  Last1  2000-1-21  100
2  First2  Last2  2000-2-22  200
3  First3  Last3  2000-3-23  300

1  From    Here   2000-1-21  100
2  To      There  2000-2-22  200
3  First3  Last3  2000-3-23  300

panic: record updated

goroutine 1 [running]:
ders/lib.AssertNil(...)
	lib/assert.go:19
main.main()
	examples/memdb/main.go:26 +0xf3
exit status 2

Да, вы правильно поняли: апдейты сработали, но Commit() завершился ошибкой! Т.к. зависимость учитывает каждый байт.

Хорошо, а что будет, если мы дополнительно уберем DependVal()? Ну, давайте попробуем: 

1  First1  Last1  2000-1-21  100
2  First2  Last2  2000-2-22  200
3  First3  Last3  2000-3-23  300

1  From    Here   2000-1-21  100
2  To      There  2000-2-22  200
3  First3  Last3  2000-3-23  300

1  First1  Last1  2000-1-21  90
2  First2  Last2  2000-2-22  210
3  First3  Last3  2000-3-23  300

Несомненно, Commit() отработал. Но мы затерли имена!

В том и есть смысл зависимостей: проверяем нет ли параллельных изменений. А коль не проверить, то мы их отбросим!

Да, это мощно... А как выглядит UpdateName()?

Не вопрос! Я сейчас кое-что покажу:

lib\mdb\memdb.go 
type MemDb interface {
    // ...
    Write(writeCb func(Writer))
}

type Writer interface {
    Reader

    Set(key Ptrsz, val Ptrsz)
    Del(key Ptrsz)
}

Это функция Write(), предоставляющая прямой доступ к базе: вы передаете свой writeCb, и она его вызывает с аргументом Writer.

Тут очень важно понимать, что на время работы Write() база блокируется, и никто не может начинать и завершать транзакции. Вы фактически получаете прямой эксклюзивный доступ, чтобы быстро что-то поправить:

examples\memdb\main.go 
func UpdateName(buf *lib.MemOutBuf, db mdb.MemDb, key int, first string, last string) error {
    var err error
    db.Write(func(wr mdb.Writer) {
        var acc Account
        if !GetAccount(wr, key, &acc) {
            err = fmt.Errorf("not found: %d", key)
            return
        }

        acc.FirstName = first
        acc.LastName = last

        SetAccount(buf, wr, key, &acc)
    })

    return err
}

func GetAccount(rd mdb.Reader, key int, acc *Account) bool {
    val, ok := rd.Get(lib.PtrToPtrsz(&key))
    if !ok {
        return false
    }

    acc.Read(val)
    return true
}

func SetAccount(buf *lib.MemOutBuf, wr mdb.Writer, key int, acc *Account) {
    wr.Set(lib.PtrToPtrsz(&key), acc.Write(buf, true))
}

Удобно? Шикарно!

Только снова замечу, что внутри вызова Write() не должно быть и близко VeryLongOperation(), т.к. вы вынуждаете всех ожидать!

Хорошо, но а как бы нам тут изменить только деньги? Не мешая всем прочим играться с другими полями.

Можно? Можно!

Но для этого нам понадобятся дополнительные возможности:

lib\mdb\memdb.go 
type Transaction interface {
    Writer

    DependVal(key Ptrsz, val Ptrsz)
    DependDel(key Ptrsz)

    Commit(writeCb func(Writer), checkCb func(Reader) bool) CommitError
    Rollback() error
}

Как и Write(), наш Commit() принимает колбэки:

Так, и что это значит?

Ну, мы можем:

  1. Найти интересущие нас счета в самом начале транзакции и сохранить их суммы.
  2. Произвести любую VeryLongOperation() -- мы никому не мешаем!
  3. Передать в Commit() свой writeCb, который проверит суммы и произведет перевод.
Бинго!

examples\memdb\main.go 
func main() {
    db := mdb.NewMemDb()
    defer func() { lib.AssertNil(db.Close()) }()

    Setup(db)
    Print(db)

    lib.AssertNil(Transfer1(db, 1, 2, 10))
    Print(db)

    lib.AssertNil(Transfer2(db, 3, 2, 20))
    Print(db)
}

func Transfer2(db mdb.MemDb, keyFrom int, keyTo int, amt int) error {
    buf := lib.NewMemOutBuf(100)

    tr := db.StartTrn()
    defer func() { lib.AssertNil(tr.Close()) }()

    var acc1 Account
    if !GetAccount(tr, keyFrom, &acc1) {
        return fmt.Errorf("not found: %d", keyFrom)
    }
    oldAmt1 := acc1.Amt

    var acc2 Account
    if !GetAccount(tr, keyTo, &acc2) {
        return fmt.Errorf("not found: %d", keyTo)
    }
    oldAmt2 := acc2.Amt

    {
        // concurrent transaction
        lib.AssertNil(UpdateName(&buf, db, keyFrom, "From", "Here"))
        lib.AssertNil(UpdateName(&buf, db, keyTo, "To", "There"))
        Print(db)
    }

    var err error
    writeCb := func(wr mdb.Writer) {
        var acc1, acc2 Account
        if !(GetAccount(wr, keyFrom, &acc1) && acc1.Amt == oldAmt1 &&
            GetAccount(wr, keyTo, &acc2) && acc2.Amt == oldAmt2) {
            err = errors.New("concurrent modification")
            return
        }

        acc1.Amt -= amt
        SetAccount(&buf, wr, keyFrom, &acc1)

        acc2.Amt += amt
        SetAccount(&buf, wr, keyTo, &acc2)
    }

    VeryLongOperation()
    tr.Commit(writeCb, nil)

    return err
}

А вот вам и полный выхлоп: 

1  First1  Last1  2000-1-21  100
2  First2  Last2  2000-2-22  200
3  First3  Last3  2000-3-23  300

1  First1  Last1  2000-1-21  90
2  First2  Last2  2000-2-22  210
3  First3  Last3  2000-3-23  300

1  First1  Last1  2000-1-21  90
2  To      There  2000-2-22  210
3  From    Here   2000-3-23  300

1  First1  Last1  2000-1-21  90
2  To      There  2000-2-22  230
3  From    Here   2000-3-23  280

Transfer2(db, 3, 2, 20) успешно перевел все 20 тугриков, не потеряв при этом имена!

2.2. Производительность

Все это очень хорошо и интересно, но как дела с производительностью?

Ну, раз вы видите такой раздел, то можно смело быть уверенным: фсё чотка!

Мы будем сравнивать с оригиналом, и вот что стало с Записью Клиента:

perf\perf1\client.go 
type ClientRec struct {
    NumCred int
    NumDeb  int
    Amt     int
}

type ClientKey struct {
    buf [2]int64
}

func (my *ClientKey) Get(n int) lib.Ptrsz {
    my.buf[0] = int64(n)
    my.buf[1] = int64(-n)

    return lib.PtrToPtrsz(my)
}

Что-что? Нет, все не сложно: ClientKey -- это просто "какой-то ключ". Примитивный и быстрый. Можно вставить другой, если надо.

perf\perf1\main.go 
var (
    goMtx sync.RWMutex
    goDB  map[string]string
)

func goRun(l1, l2 lib.Latch) {
    var ck1, ck2 ClientKey
    var cr1, cr2 ClientRec

    l1.ArriveAndWait()
    for i := 1; i <= M; i++ {
        for {
            n1, n2 := randMnMx(1, N), randMnMx(1, N)
            key1, key2 := ck1.Get(n1), ck2.Get(n2)
            if float64(n1) <= N*float64(WRITE_PROB) {
                ok := func() bool {
                    goMtx.Lock()
                    defer goMtx.Unlock()

                    val1, ok1 := goDB[lib.PtrszToString(key1)]
                    lib.Assert(ok1)
                    lib.PtrszAssign(&cr1, *lib.StringAsPtrsz(&val1))

                    val2, ok2 := goDB[lib.PtrszToString(key2)]
                    lib.Assert(ok2)
                    lib.PtrszAssign(&cr2, *lib.StringAsPtrsz(&val2))

                    // ...

                    cr1.Amt -= amt
                    cr1.NumDeb++
                    cr2.Amt += amt
                    cr2.NumCred++

                    randSleep(sleep_in)

                    goDB[lib.PtrszToString(key1)] = lib.PtrszToString(lib.PtrToPtrsz(&cr1))
                    goDB[lib.PtrszToString(key2)] = lib.PtrszToString(lib.PtrToPtrsz(&cr2))

                    return true
                }()

                if !ok {
                    continue
                }
            } else {
                // ...
            }

            break
        }

        randSleep(sleep_out)
    }
    l2.ArriveAndWait()
}

Да, это функция goRun(), переводящая деньги с помощью синхронизированной хеш-таблицы. Полный аналог unordered_map<string, string>.

А вот как выглядит myRun1(), использующая myDB.Write():

perf\perf1\main.go 
var (
    myDB mdb.MemDb
)

func myRun1(l1, l2 lib.Latch) {
    var ck1, ck2 ClientKey
    var cr1, cr2 ClientRec

    l1.ArriveAndWait()
    for i := 1; i <= M; i++ {
        if float64(randMnMx(1, N)) <= N*float64(WRITE_PROB) {
            myDB.Write(func(wr mdb.Writer) {
                for {
                    n1, n2 := randMnMx(1, N), randMnMx(1, N)
                    key1, key2 := ck1.Get(n1), ck2.Get(n2)

                    val1, ok := wr.Get(key1)
                    lib.Assert(ok)
                    lib.PtrszAssign(&cr1, val1)

                    val2, ok := wr.Get(key2)
                    lib.Assert(ok)
                    lib.PtrszAssign(&cr2, val2)

                    // ...

                    cr1.Amt -= amt
                    cr1.NumDeb++
                    cr2.Amt += amt
                    cr2.NumCred++

                    wr.Set(key1, lib.PtrToPtrsz(&cr1))
                    wr.Set(key2, lib.PtrToPtrsz(&cr2))

                    randSleep(sleep_in)
                    break
                }
            })
        } else {
            // ...
        }

        randSleep(sleep_out)
    }
    l2.ArriveAndWait()
}

Как и синхронизированная хеш-таблица, она просто блокирует доступ. И, тем самым, позволяет нам оценить относительную эффективность реализации.

Ну и главное блюдо до кучи:

perf\perf1\main.go 
func myRun2(l1, l2 lib.Latch) {
    var ck1, ck2 ClientKey
    var cr1, cr2 ClientRec

    l1.ArriveAndWait()
    for i := 1; i <= M; i++ {
        for {
            n1, n2 := randMnMx(1, N), randMnMx(1, N)
            key1, key2 := ck1.Get(n1), ck2.Get(n2)
            if float64(n1) <= N*float64(WRITE_PROB) {
                ok := func() bool {
                    tr := myDB.StartTrn()
                    defer func() { lib.AssertNil(tr.Close()) }()

                    val1, ok := tr.Get(key1)
                    lib.Assert(ok)
                    lib.PtrszAssign(&cr1, val1)

                    val2, ok := tr.Get(key2)
                    lib.Assert(ok)
                    lib.PtrszAssign(&cr2, val2)

                    // ...

                    cr1.Amt -= amt
                    cr1.NumDeb++
                    cr2.Amt += amt
                    cr2.NumCred++

                    tr.DependVal(key1, val1)
                    tr.Set(key1, lib.PtrToPtrsz(&cr1))

                    tr.DependVal(key2, val2)
                    tr.Set(key2, lib.PtrToPtrsz(&cr2))

                    randSleep(sleep_in)

                    if err := tr.Commit(nil, nil); err != nil {
                        return false
                    }

                    return true
                }()

                if !ok {
                    continue
                }
            } else {
                // ...
            }

            break
        }

        randSleep(sleep_out)
    }
    l2.ArriveAndWait()
}

Это функция myRun2(), использующая транзакции.

И как я уже не раз упоминал, наш выигрыш в том, что блокирующими операциями здесь будут лишь начало и конец транзакции: myDB.StartTrn() и tr.Commit(). А все что между ними -- абсолютно параллельно!

Тем самым, все потоки одновременно треплют свои данные в транзакциях и отдыхают в randSleep(sleep_in). Красота? Красота!

А сейчас мы сравним то, что стало:

1ms 1ms Windows 10, go1.24.3
num_threads 1 2 3 4 8 16 32 64 128
go/my1 1.0 1.1 1.1 1.2 1.6 2.2 2.2 2.2 2.3
go/my2 1.0 1.2 1.3 1.5 2.6 5.1 10.0 19.5 28.4

и было:

1ms 1ms Ubuntu 16, g++ 5.4.0
num_threads 1 2 3 4 8 16 32 64 128
std/ders1 1.0 1.1 1.1 1.2 1.6 2.0 2.1 2.1 2.0
std/ders2 1.0 1.2 1.3 1.5 2.6 4.9 9.7 17.9 33.7

Ну как, ВПЕЧАТЛЯЕТ?!

Да, фактически то же самое. Поначалу, один в один!

Можно ли было мечтать о ТАКОМ результате на чистом Go?! Нет, практически невозможно.

Я не мечтал, а сел и сделал. Пользуйтесь на здоровье!

3. Структуры данных второго порядка

Мы сегодня окажем посильную помощь всем тем мужикам, кто нашел хеш-таблицу с транзакциями, но не знает, что дальше делать... Гмм, тоже ведь Классика!

Да, речь пойдет о структурах данных, реализованных внутри других структур данных. Да, теперь и на Go!

Скажите, полезно ли это?

Все гораздо полезней, чем кажется! А покуда коня за рога...

3.1. Дек mdb.Deque

Все практически то же самое:

lib\mdb\deque.go 
type DequeReader interface {
    Close() error
    IsEmpty() bool

    Beg() int32
    End() int32

    Get(pos int32) (Ptrsz, bool)
    Key(pos int32) Ptrsz

    GetFront() (Ptrsz, bool)
    GetBack() (Ptrsz, bool)
}

type Deque interface {
    DequeReader

    Resize(newBeg int32, newEnd int32)
    Clear()

    Set(pos int32, val Ptrsz)
    Del(pos int32)

    AddFront(val Ptrsz) int32
    AddBack(val Ptrsz) int32

    DelFront() bool
    DelBack() bool

    TrimFront()
    TrimBack()
}

func DequeExists(id Ptrsz, rd Reader) bool { /* ... */ }
func DequeRemove(id Ptrsz, wr Writer) bool { /* ... */ }

func DequeOpenRd(id Ptrsz, rd Reader) DequeReader { /* ... */ }
func DequeOpen(create bool, id Ptrsz, wr Writer) Deque { /* ... */ }

Пройдемся по функциям:

DequeExists(id Ptrsz, rd Reader) boolсуществует ли Дек id в rd
DequeRemove(id Ptrsz, wr Writer) boolудаляет Дек id из wr
DequeOpenRd(id Ptrsz, rd Reader) DequeReaderоткрывает Дек id для чтения, если он существует
DequeOpen(create bool, id lib.Ptrsz, wr Writer) Dequeсоздает/открывает Дек id для чтения/записи. будет создан, если create==true

И интерфейсам:

Интерфейс DequeReader
Close() errorдеструктор
IsEmpty() boolпустой ли
Beg() int32индекс первого элемента
End() int32индекс запоследнего элемента
Get(pos int32) (Ptrsz, bool)элемент pos, если он существует
Key(pos int32) Ptrszключ элемента pos
GetFront() (Ptrsz, bool)первый элемент, если он существует
GetBack() (Ptrsz, bool)последний элемент, если он существует

Интерфейс Deque
Resize(newBeg int32, newEnd int32)изменяет границы Дека, удаляя элементы за их пределами
Clear()удаляет все элементы и устанавливает нулевые границы
Set(pos int32, val Ptrsz)присваивает val элементу pos
Del(pos int32)удаляет элемент pos
AddFront(val Ptrsz) int32добавляет val в начало Дека и возвращает индекс. изменяет границу
AddBack(val Ptrsz) int32добавляет val в конец Дека и возвращает индекс. изменяет границу
DelFront() boolудаляет первый элемент, если он существует. изменяет границу
DelBack() boolудаляет последний элемент, если он существует. изменяет границу
TrimFront()изменяет начальную границу, отбрасывая несуществующие элементы
TrimBack()изменяет конечную границу, отбрасывая несуществующие элементы

Повторяться не буду, смотрите оригинал. Тема очень глубокая!

Но реальный пример приведу:

examples\deque\main.go 
func main() {
    db := mdb.NewMemDb()
    defer func() { lib.AssertNil(db.Close()) }()

    bk := AddCustomer(db, S2P("Brian Kernighan"))
    dr := AddCustomer(db, S2P("Dennis Ritchie"))
    bs := AddCustomer(db, S2P("Bjarne Stroustrup"))

    PrnDeques(db)
    PrnDb(db)

    AddOrder(db, bk, S2P("Somewhere Far Beyond"))
    AddOrder(db, bk, S2P("Imaginations from the Other Side"))

    AddOrder(db, dr, S2P("Seventh Son of a Seventh Son"))
    AddOrder(db, dr, S2P("Brave New World"))

    AddOrder(db, bs, S2P("Walls of Jericho"))
    AddOrder(db, bs, S2P("Keeper of the Seven Keys"))

    PrnDeques(db)
    PrnDb(db)

    SetCustomer(db, bk, S2P("updated customer"))
    SetOrder(db, bk, 1, S2P("updated order"))
    DelOrder(db, dr, 0)
    DelCustomer(db, bs)

    PrnDeques(db)
    PrnDb(db)
}

func SetOrder(db mdb.MemDb, custN int32, ordN int32, val lib.Ptrsz) {
    db.Write(func(wr mdb.Writer) {
        dqc := mdb.DequeOpenRd(DqName, wr)
        if dqc != nil {
            defer func() { lib.AssertNil(dqc.Close()) }()
        }

        CheckPos(dqc, custN)

        dqo := mdb.DequeOpen(false, dqc.Key(custN), wr)
        if dqo != nil {
            defer func() { lib.AssertNil(dqo.Close()) }()
        }

        CheckPos(dqo, ordN)
        dqo.Set(ordN, val)
    })
}

Все та же музыка, все те же лица: 

beg()=0	end()=3
0	Brian Kernighan
1	Dennis Ritchie
2	Bjarne Stroustrup

beg()=0	end()=3
0	Brian Kernighan
0	beg()=0	end()=2
0	0	Somewhere Far Beyond
0	1	Imaginations from the Other Side
1	Dennis Ritchie
1	beg()=0	end()=2
1	0	Seventh Son of a Seventh Son
1	1	Brave New World
2	Bjarne Stroustrup
2	beg()=0	end()=2
2	0	Walls of Jericho
2	1	Keeper of the Seven Keys

beg()=0	end()=3
0	updated customer
0	beg()=0	end()=2
0	0	Somewhere Far Beyond
0	1	updated order
1	Dennis Ritchie
1	beg()=1	end()=2
1	1	Brave New World
2

3.2. Список mdb.List

Список тоже похож:

lib\mdb\list.go 
type ListReader interface {
    Close() error

    IsEmpty() bool
    Belongs(key Ptrsz) bool

    KeyFront() (Ptrsz, bool)
    KeyBack() (Ptrsz, bool)

    KeyPrev(pos Ptrsz) (Ptrsz, bool)
    KeyNext(pos Ptrsz) (Ptrsz, bool)
}

type List interface {
    ListReader

    Clear() int

    AddFront(key Ptrsz)
    AddBack(key Ptrsz)

    AddBefore(pos Ptrsz, key Ptrsz)
    AddAfter(pos Ptrsz, key Ptrsz)

    DelFront() bool
    DelBack() bool
    Del(key Ptrsz)
}

func ListExists(id Ptrsz, rd Reader) bool { /* ... */ }
func ListRemove(id Ptrsz, wr Writer) bool { /* ... */ }

func ListOpenRd(id Ptrsz, rd Reader) ListReader { /* ... */ }
func ListOpen(create bool, id Ptrsz, wr Writer) List { /* ... */ }

И мы снова пройдемся по функциям:

ListExists(id Ptrsz, rd Reader) boolсуществует ли Список id в rd
ListRemove(id Ptrsz, wr Writer) boolудаляет Список id из wr
ListOpenRd(id Ptrsz, rd Reader) ListReaderоткрывает Список id для чтения, если он существует
ListOpen(create bool, id lib.Ptrsz, wr Writer) Listсоздает/открывает Список id для чтения/записи. будет создан, если create==true

И интерфейсам:

Интерфейс ListReader
Close() errorдеструктор
IsEmpty() boolпустой ли
Belongs(key Ptrsz) boolпринадлежит ли key
KeyFront() (Ptrsz, bool)первый ключ, если он существует
KeyBack() (Ptrsz, bool)последний ключ, если он существует
KeyPrev(pos Ptrsz) (Ptrsz, bool)предшествующий pos ключ, если он существует
KeyNext(pos Ptrsz) (Ptrsz, bool)следующий за pos ключ, если он существует

Интерфейс List
Clear() intудаляет все элементы и возвращает количество
AddFront(key Ptrsz)добавляет key в начало
AddBack(key Ptrsz)добавляет key в конец
AddBefore(pos Ptrsz, key Ptrsz)добавляет key перед pos
AddAfter(pos Ptrsz, key Ptrsz)добавляет key после pos
DelFront() boolудаляет первый ключ, если он существует
DelBack() boolудаляет последний ключ, если он существует
Del(key Ptrsz)удаляет key

И, конечно же, будет тот самый пример:

examples\list\main.go 
func main() {
    db := mdb.NewMemDb()
    defer func() { lib.AssertNil(db.Close()) }()

    db.Write(func(wr mdb.Writer) {
        lst1 := mdb.ListOpen(true, LstId1, wr)
        defer func() { lib.AssertNil(lst1.Close()) }()

        lst1.AddBack(S2P("key1"))
        lst1.AddBack(S2P("key2"))

        lst2 := mdb.ListOpen(true, LstId2, wr)
        defer func() { lib.AssertNil(lst2.Close()) }()

        lst2.AddBack(S2P("key2"))
        lst2.AddBack(S2P("key3"))
    })

    PrnLst(db, LstId1)
    PrnLst(db, LstId2)
    PrnDb(db)

    db.Write(func(wr mdb.Writer) {
        wr.Set(S2P("key1"), S2P("val1"))
        wr.Set(S2P("key2"), S2P("val2"))
        wr.Set(S2P("key3"), S2P("val3"))
    })

    PrnLst(db, LstId1)
    PrnLst(db, LstId2)
    PrnDb(db)

    db.Write(func(wr mdb.Writer) {
        wr.Set(S2P("key2"), S2P("updated"))

        lst1 := mdb.ListOpen(true, LstId1, wr)
        defer func() { lib.AssertNil(lst1.Close()) }()

        lst1.AddBefore(S2P("key2"), S2P("key1.5"))

        lst2 := mdb.ListOpen(true, LstId2, wr)
        defer func() { lib.AssertNil(lst2.Close()) }()

        lst2.Del(S2P("key3"))
    })

    PrnLst(db, LstId1)
    PrnLst(db, LstId2)
    PrnDb(db)
}

И получится все то же самое: 

PrnLst(list1)
key1
key2
PrnLst(list2)
key2
key3

PrnLst(list1)
key1	val1
key2	val2
PrnLst(list2)
key2	val2
key3	val3

PrnLst(list1)
key1	val1
key1.5
key2	updated
PrnLst(list2)
key2	updated

4. Адаптер mdb.BlobMap

Вот еще диво дивное, чудо чудное:

lib\mdb\blobmaprw.go 
func NewBlobMapReader(bm *BlobMap) Reader {
    return &blobMapRW{bm, nil}
}

func NewBlobMapWriter(bm *BlobMap) Writer {
    return &blobMapRW{bm, bm}
}

type blobMapRW struct {
    rd *BlobMap
    wr *BlobMap
}

Т.е. пара удобных функций, превращающих отдельно стоящий BlobMap в жутко полезные Reader и Writer.

Вау, офигеть! А зачем?

Ну, затем, что и Список и Дек теперь могут юзать наш BlobMap напрямую! И на Go это ОЧЕНЬ И ОЧЕНЬ полезно!!

А суть в том, что BlobMap не создает проблемы мусорщику: вы можете держать хоть сотни миллионов элементов.

Ох... И наверное что-то еще?

Несомненно! Ведь MemDb реализован тем же самым способом и может без Проблемы содержать такие же объемы данных... То есть ЛЮБЫЕ!!

5. Заключение

Мы получили больше, чем хотели!

Ведь Удивительная Магия mdb.OffPool зовет использовать Структуры в любом серьезном приложении.

Но для начала следует вкурить оригинал:

  1. Хеш-таблица с транзакциями.
  2. Структуры данных второго порядка.
Там сразу осознаете, что под крышечкой и как (не) надо действовать! Хотя можно и просто трясти.

Главное, вы увидели, что невозможное возможно! Don't let your thoughts be narrowed. Period.

Copyright © С. Деревяго, 2025

Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.