1 // Copyright (c) 2016 The btcsuite developers
2 // Use of this source code is governed by an ISC
3 // license that can be found in the LICENSE file.
11 "github.com/btcsuite/btcd/blockchain"
12 "github.com/btcsuite/btcd/chaincfg/chainhash"
13 "github.com/btcsuite/btcd/database"
14 "github.com/btcsuite/btcd/wire"
15 "github.com/btcsuite/btcutil"
19 // txIndexName is the human-readable name for the index.
20 txIndexName = "transaction index"
24 // txIndexKey is the key of the transaction index and the db bucket used
26 txIndexKey = []byte("txbyhashidx")
28 // idByHashIndexBucketName is the name of the db bucket used to house
29 // the block id -> block hash index.
30 idByHashIndexBucketName = []byte("idbyhashidx")
32 // hashByIDIndexBucketName is the name of the db bucket used to house
33 // the block hash -> block id index.
34 hashByIDIndexBucketName = []byte("hashbyididx")
36 // errNoBlockIDEntry is an error that indicates a requested entry does
37 // not exist in the block ID index.
38 errNoBlockIDEntry = errors.New("no entry in the block ID index")
41 // -----------------------------------------------------------------------------
42 // The transaction index consists of an entry for every transaction in the main
43 // chain. In order to significanly optimize the space requirements a separate
44 // index which provides an internal mapping between each block that has been
45 // indexed and a unique ID for use within the hash to location mappings. The ID
46 // is simply a sequentially incremented uint32. This is useful because it is
47 // only 4 bytes versus 32 bytes hashes and thus saves a ton of space in the
50 // There are three buckets used in total. The first bucket maps the hash of
51 // each transaction to the specific block location. The second bucket maps the
52 // hash of each block to the unique ID and the third maps that ID back to the
55 // NOTE: Although it is technically possible for multiple transactions to have
56 // the same hash as long as the previous transaction with the same hash is fully
57 // spent, this code only stores the most recent one because doing otherwise
58 // would add a non-trivial amount of space and overhead for something that will
59 // realistically never happen per the probability and even if it did, the old
60 // one must be fully spent and so the most likely transaction a caller would
61 // want for a given hash is the most recent one anyways.
63 // The serialized format for keys and values in the block hash to ID bucket is:
67 // hash chainhash.Hash 32 bytes
72 // The serialized format for keys and values in the ID to block hash bucket is:
77 // hash chainhash.Hash 32 bytes
81 // The serialized format for the keys and values in the tx index bucket is:
83 // <txhash> = <block id><start offset><tx length>
86 // txhash chainhash.Hash 32 bytes
87 // block id uint32 4 bytes
88 // start offset uint32 4 bytes
89 // tx length uint32 4 bytes
92 // -----------------------------------------------------------------------------
94 // dbPutBlockIDIndexEntry uses an existing database transaction to update or add
95 // the index entries for the hash to id and id to hash mappings for the provided
97 func dbPutBlockIDIndexEntry(dbTx database.Tx, hash *chainhash.Hash, id uint32) error {
98 // Serialize the height for use in the index entries.
99 var serializedID [4]byte
100 byteOrder.PutUint32(serializedID[:], id)
102 // Add the block hash to ID mapping to the index.
103 meta := dbTx.Metadata()
104 hashIndex := meta.Bucket(idByHashIndexBucketName)
105 if err := hashIndex.Put(hash[:], serializedID[:]); err != nil {
109 // Add the block ID to hash mapping to the index.
110 idIndex := meta.Bucket(hashByIDIndexBucketName)
111 return idIndex.Put(serializedID[:], hash[:])
114 // dbRemoveBlockIDIndexEntry uses an existing database transaction remove index
115 // entries from the hash to id and id to hash mappings for the provided hash.
116 func dbRemoveBlockIDIndexEntry(dbTx database.Tx, hash *chainhash.Hash) error {
117 // Remove the block hash to ID mapping.
118 meta := dbTx.Metadata()
119 hashIndex := meta.Bucket(idByHashIndexBucketName)
120 serializedID := hashIndex.Get(hash[:])
121 if serializedID == nil {
124 if err := hashIndex.Delete(hash[:]); err != nil {
128 // Remove the block ID to hash mapping.
129 idIndex := meta.Bucket(hashByIDIndexBucketName)
130 return idIndex.Delete(serializedID)
133 // dbFetchBlockIDByHash uses an existing database transaction to retrieve the
134 // block id for the provided hash from the index.
135 func dbFetchBlockIDByHash(dbTx database.Tx, hash *chainhash.Hash) (uint32, error) {
136 hashIndex := dbTx.Metadata().Bucket(idByHashIndexBucketName)
137 serializedID := hashIndex.Get(hash[:])
138 if serializedID == nil {
139 return 0, errNoBlockIDEntry
142 return byteOrder.Uint32(serializedID), nil
145 // dbFetchBlockHashBySerializedID uses an existing database transaction to
146 // retrieve the hash for the provided serialized block id from the index.
147 func dbFetchBlockHashBySerializedID(dbTx database.Tx, serializedID []byte) (*chainhash.Hash, error) {
148 idIndex := dbTx.Metadata().Bucket(hashByIDIndexBucketName)
149 hashBytes := idIndex.Get(serializedID)
150 if hashBytes == nil {
151 return nil, errNoBlockIDEntry
154 var hash chainhash.Hash
155 copy(hash[:], hashBytes)
159 // dbFetchBlockHashByID uses an existing database transaction to retrieve the
160 // hash for the provided block id from the index.
161 func dbFetchBlockHashByID(dbTx database.Tx, id uint32) (*chainhash.Hash, error) {
162 var serializedID [4]byte
163 byteOrder.PutUint32(serializedID[:], id)
164 return dbFetchBlockHashBySerializedID(dbTx, serializedID[:])
167 // putTxIndexEntry serializes the provided values according to the format
168 // described about for a transaction index entry. The target byte slice must
169 // be at least large enough to handle the number of bytes defined by the
170 // txEntrySize constant or it will panic.
171 func putTxIndexEntry(target []byte, blockID uint32, txLoc wire.TxLoc) {
172 byteOrder.PutUint32(target, blockID)
173 byteOrder.PutUint32(target[4:], uint32(txLoc.TxStart))
174 byteOrder.PutUint32(target[8:], uint32(txLoc.TxLen))
177 // dbPutTxIndexEntry uses an existing database transaction to update the
178 // transaction index given the provided serialized data that is expected to have
179 // been serialized putTxIndexEntry.
180 func dbPutTxIndexEntry(dbTx database.Tx, txHash *chainhash.Hash, serializedData []byte) error {
181 txIndex := dbTx.Metadata().Bucket(txIndexKey)
182 return txIndex.Put(txHash[:], serializedData)
185 // dbFetchTxIndexEntry uses an existing database transaction to fetch the block
186 // region for the provided transaction hash from the transaction index. When
187 // there is no entry for the provided hash, nil will be returned for the both
188 // the region and the error.
189 func dbFetchTxIndexEntry(dbTx database.Tx, txHash *chainhash.Hash) (*database.BlockRegion, error) {
190 // Load the record from the database and return now if it doesn't exist.
191 txIndex := dbTx.Metadata().Bucket(txIndexKey)
192 serializedData := txIndex.Get(txHash[:])
193 if len(serializedData) == 0 {
197 // Ensure the serialized data has enough bytes to properly deserialize.
198 if len(serializedData) < 12 {
199 return nil, database.Error{
200 ErrorCode: database.ErrCorruption,
201 Description: fmt.Sprintf("corrupt transaction index "+
202 "entry for %s", txHash),
206 // Load the block hash associated with the block ID.
207 hash, err := dbFetchBlockHashBySerializedID(dbTx, serializedData[0:4])
209 return nil, database.Error{
210 ErrorCode: database.ErrCorruption,
211 Description: fmt.Sprintf("corrupt transaction index "+
212 "entry for %s: %v", txHash, err),
216 // Deserialize the final entry.
217 region := database.BlockRegion{Hash: &chainhash.Hash{}}
218 copy(region.Hash[:], hash[:])
219 region.Offset = byteOrder.Uint32(serializedData[4:8])
220 region.Len = byteOrder.Uint32(serializedData[8:12])
225 // dbAddTxIndexEntries uses an existing database transaction to add a
226 // transaction index entry for every transaction in the passed block.
227 func dbAddTxIndexEntries(dbTx database.Tx, block *btcutil.Block, blockID uint32) error {
228 // The offset and length of the transactions within the serialized
230 txLocs, err := block.TxLoc()
235 // As an optimization, allocate a single slice big enough to hold all
236 // of the serialized transaction index entries for the block and
237 // serialize them directly into the slice. Then, pass the appropriate
238 // subslice to the database to be written. This approach significantly
239 // cuts down on the number of required allocations.
241 serializedValues := make([]byte, len(block.Transactions())*txEntrySize)
242 for i, tx := range block.Transactions() {
243 putTxIndexEntry(serializedValues[offset:], blockID, txLocs[i])
244 endOffset := offset + txEntrySize
245 err := dbPutTxIndexEntry(dbTx, tx.Hash(),
246 serializedValues[offset:endOffset:endOffset])
250 offset += txEntrySize
256 // dbRemoveTxIndexEntry uses an existing database transaction to remove the most
257 // recent transaction index entry for the given hash.
258 func dbRemoveTxIndexEntry(dbTx database.Tx, txHash *chainhash.Hash) error {
259 txIndex := dbTx.Metadata().Bucket(txIndexKey)
260 serializedData := txIndex.Get(txHash[:])
261 if len(serializedData) == 0 {
262 return fmt.Errorf("can't remove non-existent transaction %s "+
263 "from the transaction index", txHash)
266 return txIndex.Delete(txHash[:])
269 // dbRemoveTxIndexEntries uses an existing database transaction to remove the
270 // latest transaction entry for every transaction in the passed block.
271 func dbRemoveTxIndexEntries(dbTx database.Tx, block *btcutil.Block) error {
272 for _, tx := range block.Transactions() {
273 err := dbRemoveTxIndexEntry(dbTx, tx.Hash())
282 // TxIndex implements a transaction by hash index. That is to say, it supports
283 // querying all transactions by their hash.
284 type TxIndex struct {
289 // Ensure the TxIndex type implements the Indexer interface.
290 var _ Indexer = (*TxIndex)(nil)
292 // Init initializes the hash-based transaction index. In particular, it finds
293 // the highest used block ID and stores it for later use when connecting or
294 // disconnecting blocks.
296 // This is part of the Indexer interface.
297 func (idx *TxIndex) Init() error {
298 // Find the latest known block id field for the internal block id
299 // index and initialize it. This is done because it's a lot more
300 // efficient to do a single search at initialize time than it is to
301 // write another value to the database on every update.
302 err := idx.db.View(func(dbTx database.Tx) error {
303 // Scan forward in large gaps to find a block id that doesn't
304 // exist yet to serve as an upper bound for the binary search
306 var highestKnown, nextUnknown uint32
307 testBlockID := uint32(1)
308 increment := uint32(100000)
310 _, err := dbFetchBlockHashByID(dbTx, testBlockID)
312 nextUnknown = testBlockID
316 highestKnown = testBlockID
317 testBlockID += increment
319 log.Tracef("Forward scan (highest known %d, next unknown %d)",
320 highestKnown, nextUnknown)
322 // No used block IDs due to new database.
323 if nextUnknown == 1 {
327 // Use a binary search to find the final highest used block id.
328 // This will take at most ceil(log_2(increment)) attempts.
330 testBlockID = (highestKnown + nextUnknown) / 2
331 _, err := dbFetchBlockHashByID(dbTx, testBlockID)
333 nextUnknown = testBlockID
335 highestKnown = testBlockID
337 log.Tracef("Binary scan (highest known %d, next "+
338 "unknown %d)", highestKnown, nextUnknown)
339 if highestKnown+1 == nextUnknown {
344 idx.curBlockID = highestKnown
351 log.Debugf("Current internal block ID: %d", idx.curBlockID)
355 // Key returns the database key to use for the index as a byte slice.
357 // This is part of the Indexer interface.
358 func (idx *TxIndex) Key() []byte {
362 // Name returns the human-readable name of the index.
364 // This is part of the Indexer interface.
365 func (idx *TxIndex) Name() string {
369 // Create is invoked when the indexer manager determines the index needs
370 // to be created for the first time. It creates the buckets for the hash-based
371 // transaction index and the internal block ID indexes.
373 // This is part of the Indexer interface.
374 func (idx *TxIndex) Create(dbTx database.Tx) error {
375 meta := dbTx.Metadata()
376 if _, err := meta.CreateBucket(idByHashIndexBucketName); err != nil {
379 if _, err := meta.CreateBucket(hashByIDIndexBucketName); err != nil {
382 _, err := meta.CreateBucket(txIndexKey)
386 // ConnectBlock is invoked by the index manager when a new block has been
387 // connected to the main chain. This indexer adds a hash-to-transaction mapping
388 // for every transaction in the passed block.
390 // This is part of the Indexer interface.
391 func (idx *TxIndex) ConnectBlock(dbTx database.Tx, block *btcutil.Block, view *blockchain.UtxoViewpoint) error {
392 // Increment the internal block ID to use for the block being connected
393 // and add all of the transactions in the block to the index.
394 newBlockID := idx.curBlockID + 1
395 if err := dbAddTxIndexEntries(dbTx, block, newBlockID); err != nil {
399 // Add the new block ID index entry for the block being connected and
400 // update the current internal block ID accordingly.
401 err := dbPutBlockIDIndexEntry(dbTx, block.Hash(), newBlockID)
405 idx.curBlockID = newBlockID
409 // DisconnectBlock is invoked by the index manager when a block has been
410 // disconnected from the main chain. This indexer removes the
411 // hash-to-transaction mapping for every transaction in the block.
413 // This is part of the Indexer interface.
414 func (idx *TxIndex) DisconnectBlock(dbTx database.Tx, block *btcutil.Block, view *blockchain.UtxoViewpoint) error {
415 // Remove all of the transactions in the block from the index.
416 if err := dbRemoveTxIndexEntries(dbTx, block); err != nil {
420 // Remove the block ID index entry for the block being disconnected and
421 // decrement the current internal block ID to account for it.
422 if err := dbRemoveBlockIDIndexEntry(dbTx, block.Hash()); err != nil {
429 // TxBlockRegion returns the block region for the provided transaction hash
430 // from the transaction index. The block region can in turn be used to load the
431 // raw transaction bytes. When there is no entry for the provided hash, nil
432 // will be returned for the both the entry and the error.
434 // This function is safe for concurrent access.
435 func (idx *TxIndex) TxBlockRegion(hash *chainhash.Hash) (*database.BlockRegion, error) {
436 var region *database.BlockRegion
437 err := idx.db.View(func(dbTx database.Tx) error {
439 region, err = dbFetchTxIndexEntry(dbTx, hash)
445 // NewTxIndex returns a new instance of an indexer that is used to create a
446 // mapping of the hashes of all transactions in the blockchain to the respective
447 // block, location within the block, and size of the transaction.
449 // It implements the Indexer interface which plugs into the IndexManager that in
450 // turn is used by the blockchain package. This allows the index to be
451 // seamlessly maintained along with the chain.
452 func NewTxIndex(db database.DB) *TxIndex {
453 return &TxIndex{db: db}
456 // dropBlockIDIndex drops the internal block id index.
457 func dropBlockIDIndex(db database.DB) error {
458 return db.Update(func(dbTx database.Tx) error {
459 meta := dbTx.Metadata()
460 err := meta.DeleteBucket(idByHashIndexBucketName)
465 return meta.DeleteBucket(hashByIDIndexBucketName)
469 // DropTxIndex drops the transaction index from the provided database if it
470 // exists. Since the address index relies on it, the address index will also be
471 // dropped when it exists.
472 func DropTxIndex(db database.DB) error {
473 if err := dropIndex(db, addrIndexKey, addrIndexName); err != nil {
477 return dropIndex(db, txIndexKey, txIndexName)