From f9df522b4e16227e34c8eb70e3a369c00db37f17 Mon Sep 17 00:00:00 2001 From: Paladz Date: Fri, 20 Jul 2018 10:13:29 +0800 Subject: [PATCH] add utxo_opt algorithm (#1149) * add utxo_opt algorithm * edit the unit test * edit the comment --- account/utxo_keeper.go | 46 +++++++++-- account/utxo_keeper_test.go | 185 +++++++++++++++++++++++++++++++++++++------- 2 files changed, 197 insertions(+), 34 deletions(-) diff --git a/account/utxo_keeper.go b/account/utxo_keeper.go index 151c6122..f0fdf156 100644 --- a/account/utxo_keeper.go +++ b/account/utxo_keeper.go @@ -1,6 +1,7 @@ package account import ( + "container/list" "encoding/json" "sort" "sync" @@ -14,6 +15,8 @@ import ( "github.com/bytom/protocol/bc" ) +const desireUtxoCount = 5 + // pre-define error types var ( ErrInsufficient = errors.New("reservation found insufficient funds") @@ -247,23 +250,54 @@ func (uk *utxoKeeper) findUtxo(outHash bc.Hash, useUnconfirmed bool) (*UTXO, err } func (uk *utxoKeeper) optUTXOs(utxos []*UTXO, amount uint64) ([]*UTXO, uint64, uint64) { + //sort the utxo by amount, bigger amount in front + var optAmount, reservedAmount uint64 sort.Slice(utxos, func(i, j int) bool { - return utxos[i].Amount < utxos[j].Amount + return utxos[i].Amount > utxos[j].Amount }) - var optAmount, reservedAmount uint64 - optUtxos := []*UTXO{} + //push all the available utxos into list + utxoList := list.New() for _, u := range utxos { if _, ok := uk.reserved[u.OutputID]; ok { reservedAmount += u.Amount continue } + utxoList.PushBack(u) + } - optAmount += u.Amount - optUtxos = append(optUtxos, u) - if optAmount >= amount { + optList := list.New() + for node := utxoList.Front(); node != nil; node = node.Next() { + //append utxo if we haven't reached the required amount + if optAmount < amount { + optList.PushBack(node.Value) + optAmount += node.Value.(*UTXO).Amount + continue + } + + largestNode := optList.Front() + replaceList := list.New() + replaceAmount := optAmount - largestNode.Value.(*UTXO).Amount + + for ; node != nil && replaceList.Len() <= desireUtxoCount-optList.Len(); node = node.Next() { + replaceList.PushBack(node.Value) + if replaceAmount += node.Value.(*UTXO).Amount; replaceAmount >= amount { + optList.Remove(largestNode) + optList.PushBackList(replaceList) + optAmount = replaceAmount + break + } + } + + //largestNode remaining the same means that there is nothing to be replaced + if largestNode == optList.Front() { break } } + + optUtxos := []*UTXO{} + for e := optList.Front(); e != nil; e = e.Next() { + optUtxos = append(optUtxos, e.Value.(*UTXO)) + } return optUtxos, optAmount, reservedAmount } diff --git a/account/utxo_keeper_test.go b/account/utxo_keeper_test.go index dde1ee7c..066af515 100644 --- a/account/utxo_keeper_test.go +++ b/account/utxo_keeper_test.go @@ -498,14 +498,14 @@ func TestReserve(t *testing.T) { id: 2, utxos: []*UTXO{ &UTXO{ - OutputID: bc.NewHash([32]byte{0x02}), + OutputID: bc.NewHash([32]byte{0x03}), AccountID: "testAccount", - Amount: 5, + Amount: 7, }, &UTXO{ - OutputID: bc.NewHash([32]byte{0x03}), + OutputID: bc.NewHash([32]byte{0x02}), AccountID: "testAccount", - Amount: 7, + Amount: 5, }, }, change: 4, @@ -1017,10 +1017,7 @@ func TestOptUTXOs(t *testing.T) { }, }, input: []*UTXO{ - &UTXO{ - OutputID: bc.NewHash([32]byte{0x01}), - Amount: 1, - }, + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, }, inputAmount: 13, wantUtxos: []*UTXO{}, @@ -1034,33 +1031,165 @@ func TestOptUTXOs(t *testing.T) { }, }, input: []*UTXO{ - &UTXO{ - OutputID: bc.NewHash([32]byte{0x01}), - Amount: 1, - }, - &UTXO{ - OutputID: bc.NewHash([32]byte{0x02}), - Amount: 3, - }, - &UTXO{ - OutputID: bc.NewHash([32]byte{0x03}), - Amount: 5, - }, + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 3}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 5}, }, inputAmount: 13, wantUtxos: []*UTXO{ - &UTXO{ - OutputID: bc.NewHash([32]byte{0x02}), - Amount: 3, - }, - &UTXO{ - OutputID: bc.NewHash([32]byte{0x03}), - Amount: 5, - }, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 5}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 3}, }, optAmount: 8, reservedAmount: 1, }, + { + uk: utxoKeeper{ + reserved: map[bc.Hash]uint64{ + bc.NewHash([32]byte{0x01}): 1, + bc.NewHash([32]byte{0x02}): 2, + bc.NewHash([32]byte{0x03}): 3, + }, + }, + input: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 3}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 5}, + }, + inputAmount: 1, + wantUtxos: []*UTXO{}, + optAmount: 0, + reservedAmount: 9, + }, + { + uk: utxoKeeper{}, + input: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 3}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 5}, + }, + inputAmount: 1, + wantUtxos: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + }, + optAmount: 1, + reservedAmount: 0, + }, + { + uk: utxoKeeper{}, + input: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 2}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 3}, + &UTXO{OutputID: bc.NewHash([32]byte{0x05}), Amount: 5}, + }, + inputAmount: 5, + wantUtxos: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 3}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 2}, + }, + optAmount: 5, + reservedAmount: 0, + }, + { + uk: utxoKeeper{}, + input: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x04}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x05}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x06}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x08}), Amount: 6}, + }, + inputAmount: 6, + wantUtxos: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x08}), Amount: 6}, + }, + optAmount: 6, + reservedAmount: 0, + }, + { + uk: utxoKeeper{}, + input: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x04}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x05}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x06}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x08}), Amount: 6}, + }, + inputAmount: 5, + wantUtxos: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x04}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x05}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x06}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + }, + optAmount: 5, + reservedAmount: 0, + }, + { + uk: utxoKeeper{}, + input: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 3}, + &UTXO{OutputID: bc.NewHash([32]byte{0x05}), Amount: 5}, + &UTXO{OutputID: bc.NewHash([32]byte{0x07}), Amount: 7}, + &UTXO{OutputID: bc.NewHash([32]byte{0x11}), Amount: 11}, + &UTXO{OutputID: bc.NewHash([32]byte{0x13}), Amount: 13}, + &UTXO{OutputID: bc.NewHash([32]byte{0x23}), Amount: 23}, + &UTXO{OutputID: bc.NewHash([32]byte{0x31}), Amount: 31}, + }, + inputAmount: 13, + wantUtxos: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x07}), Amount: 7}, + &UTXO{OutputID: bc.NewHash([32]byte{0x05}), Amount: 5}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 3}, + }, + optAmount: 15, + reservedAmount: 0, + }, + { + uk: utxoKeeper{}, + input: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + }, + inputAmount: 1, + wantUtxos: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + }, + optAmount: 1, + reservedAmount: 0, + }, + { + uk: utxoKeeper{}, + input: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 2}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 3}, + &UTXO{OutputID: bc.NewHash([32]byte{0x04}), Amount: 4}, + &UTXO{OutputID: bc.NewHash([32]byte{0x05}), Amount: 5}, + &UTXO{OutputID: bc.NewHash([32]byte{0x06}), Amount: 6}, + &UTXO{OutputID: bc.NewHash([32]byte{0x07}), Amount: 7}, + &UTXO{OutputID: bc.NewHash([32]byte{0x08}), Amount: 8}, + &UTXO{OutputID: bc.NewHash([32]byte{0x09}), Amount: 9}, + &UTXO{OutputID: bc.NewHash([32]byte{0x10}), Amount: 10}, + &UTXO{OutputID: bc.NewHash([32]byte{0x11}), Amount: 11}, + &UTXO{OutputID: bc.NewHash([32]byte{0x12}), Amount: 12}, + }, + inputAmount: 15, + wantUtxos: []*UTXO{ + &UTXO{OutputID: bc.NewHash([32]byte{0x05}), Amount: 5}, + &UTXO{OutputID: bc.NewHash([32]byte{0x04}), Amount: 4}, + &UTXO{OutputID: bc.NewHash([32]byte{0x03}), Amount: 3}, + &UTXO{OutputID: bc.NewHash([32]byte{0x02}), Amount: 2}, + &UTXO{OutputID: bc.NewHash([32]byte{0x01}), Amount: 1}, + }, + optAmount: 15, + reservedAmount: 0, + }, } for i, c := range cases { -- 2.11.0