Skip to content

Latest commit

 

History

History
99 lines (88 loc) · 5.5 KB

tip-476.md

File metadata and controls

99 lines (88 loc) · 5.5 KB
Raw
tip: 476
title: Delegate Data Structure Optimization
author: lxcmyf@gmail.com
discussions to: https://github.com/tronprotocol/tips/issues/476
status: Final
type: Standards Track
category: Core
created: 2022-11-14

Simple Summary

This TIP aims to optimize the account index storage structure of resource delegating, to improve transaction execution performance and throughput.

Abstract

During the execution of the existing delegating transaction, when an owner delegates resources to others, it is necessary to maintain the delegate relationship between each other and store it persistently. The read performance of the delegate relationship will drop sharply when the delegate relationship of a single owner increases, and even seriously affect the execution efficiency of the transactions. This paper introduces the optimization of the delegate relationship storage data structure in detail.

Motivation

According to the latest pressure test, the increment of the delegate relationship to a single account will linearly increase the transaction execution time as below,

Number of account relationships Avg. execution time (ms)
1 5
20000 74
180000 620

By applying an optimized storage structure, the transaction execution time almost remains with the account relationship increasing.

Number of account relationships Avg. execution time (ms)
1 5
20000 6
180000 8

To improve the network performance, and cut down the transaction execution time, the optimized storage structure utilized above should be implemented.

Rationale

The current delegate account relationship structure is as below,

message DelegatedResourceAccountIndex {
  bytes account = 1;
  repeated bytes fromAccounts = 2;
  repeated bytes toAccounts = 3;
}

account is defined as the subject account. fromAccounts is the list of the addresses that have delegated resources to the subject account. toAccounts is the list of the recipient addresses that the subject address has delegated its resources to. When storing the delegate account relationship, the subject account address is used as the key, and the structure is stored as the value. When maintaining a new delegate relationship, it is necessary to read the fromAccounts or toAccounts of the subject account to determine whether the new delegate relationship is in these lists. If there is, just Ignore it, otherwise, add it to the list accordingly. This reading method will drastically reduce the system performance when the list data is expanded.

To cope with that, the storage is optimized for fromAccounts and toAccounts, with the key-value paradigm applied. Please check the following,

public void delegate(byte[] from, byte[] to, long time) {
    byte[] fromKey = createKey(fromPrefix, from, to);
    DelegatedResourceAccountIndexCapsule toIndexCapsule =
        new DelegatedResourceAccountIndexCapsule(ByteString.copyFrom(to));
    toIndexCapsule.setTimestamp(time);
    this.put(fromKey, toIndexCapsule);

    byte[] toKey = createKey(toPrefix, to, from);
    DelegatedResourceAccountIndexCapsule fromIndexCapsule =
        new DelegatedResourceAccountIndexCapsule(ByteString.copyFrom(from));
    fromIndexCapsule.setTimestamp(time);
    this.put(toKey, fromIndexCapsule);
  }

private byte[] createKey(byte[] prefix, byte[] address1, byte[] address2) {
    byte[] key = new byte[prefix.length + address1.length + address2.length];
    System.arraycopy(prefix, 0, key, 0, prefix.length);
    System.arraycopy(address1, 0, key, prefix.length, address1.length);
    System.arraycopy(address2, 0, key, prefix.length + address1.length, address2.length);
    return key;
  }

In the new method, by adding fromPrefix to the addresses in toAccounts, we correlate them with the subject account together as fromKey and pack toAccounts to new DelegatedResourceAccountIndexCapsule(ByteString.copyFrom(to)) as value and then store them.

toPrefixis added to the addresses in fromAccounts, and correlate them with the subject account as toKey, and pack fromAccounts to DelegatedResourceAccountIndexCapsule(ByteString.copyFrom(from)) as value, then store them.

After the proposal is activated, when the first delegating is made, all the addresses in fromAccounts and toAccounts will migrate and be stored in the new data structure,

public void convert(byte[] address) {
    DelegatedResourceAccountIndexCapsule indexCapsule = this.get(address);
    if (indexCapsule == null) {
      // convert complete or have no delegate
      return;
    }
    // convert old data
    List<ByteString> toList = indexCapsule.getToAccountsList();
    for (int i = 0; i < toList.size(); i++) {
      // use index as the timestamp, just to keep index in order
      this.delegate(address, toList.get(i).toByteArray(), i + 1L);
    }

    List<ByteString> fromList = indexCapsule.getFromAccountsList();
    for (int i = 0; i < fromList.size(); i++) {
      // use index as the timestamp, just to keep index in order
      this.delegate(fromList.get(i).toByteArray(), address, i + 1L);
    }
    this.delete(address);
  }

All delegating afterward will be stored through the new structure.