Documentation
¶
Overview ¶
Package chunks is an append-only general purpose file-backed blob Store.
Goals ¶
- Simple detection and recovery from partial writes and unexpected shutdowns. This is facilitated by using an append-only write strategy, using explicit Checkpoint chunks to mark where Store.Flush was called, by aligning Chunks at 128 byte boundaries, and by checksum protections for everything.
- Effective write batching with minimal disk write amplification. No series of Write calls is considered finished until they are followed with a Flush call, which writes a Checkpoint chunk and forces all pending writes to disk. If a Flush call returns without error, all writes that started before the Flush call will be on disk.
- Resilience in the face of out-of-space and disk write errors. This is accomplished by growing the Store in 16 megabyte chunks whenever a requested write would result in the Store having less than 64 K free after all data was written to disk. Data is not copied into the Store until there is enough space free to hold it all. Expanding the Store always involves filling the newly-added space with zeros to catch potential write errors before actual data is written.
- At-rest data safety All user data is encrypted at rest unless explicitly overridden using random keys that are reset every time the Store is cleared. Users can pass in an additional encryption key that will be mixed in with the random key for added security.
- Fast iteration over Chunks in the store. Each and EachAfter are designed to perform only large linear reads for the common pattern of iterating over each Chunk and then doing something with its payload.
Anti-Goals ¶
- Sorting, searching, or really indexing of any kind. The only method we provide for reading a Chunk is Store.ReadAt, and the only method we provide for discovering Chunks is Store.Each and Store.EachAfter.
- Space efficiency. This library never automatically releases disk space once it has been allocated. If you want to do that, you will need to call one of the Shrink() methods.
- Deleting individual Chunks. Once a Chunk has been written and flushed, the only way to delete it is to Clear() the Store, which forgets everything and starts all new Writes at the beginning of the Store.
Layout ¶
Each Chunk is written to memory at 128 byte aligned offsets to facilitate corruption detection and recovery. The layout is as follows:
[0:128]: First chunk. It establishes the generation number that all subsequent
chunks in the Store must have to be considered valid.
[n:m]: Any number of user specified chunks added to the Store by Write.
[m:m+128]: Checkpoint chunk. Indicates that all previous chunks were Flushed to disk.
If this Chunk and all previous Chunks are valid and have the same generation
as the First chunk, they are considered to be valid.
[m+128:m+256]: If this chunk consists of all zeros, that indicates there is no more valid
data in the Store.
On initial creation, the Store is grown to be 16 megabytes in size, the initial First record is written to establish the initial Generation (1) and then Flushed to disk. Subsequent Writes and Flushes add data to the Store and checkpoint it until one would leave the Store with less than 64K of writable space. At that point, the Store will be expanded by another 16 megabytes.
On Open of an already created Store, the Chunks will be read to verify that they are valid and of the same generation as the First chunk. Any uncommitted Chunks will be discarded, and the presence of any invalid data (Chunks from a different Generation or chunks with an invalid CRC) that is covered by a valid Checkpoint will indicate that the Store needs recovery.
Once you no longer need the data in the Store, you can Clear it, which will increment the current Generation to yield the new Generation, write,and then flush a new First chunk at the beginning of the Store.
If Open indicates that a Store needs recovery, you can copy the valid Chunks into a new Store using the Recover function.
Encryption ¶
By default, all user data will be encrypted at rest using AES-128 in CTR mode. This encryption is intended to defeat casual searching for information using standard forensics tools by default. For added security, pass in an additional key.
Each blob of user data is encrypted using AES-128 using a key defined from the following sources: - 96 bytes of cryptographic random data recorded in the first chunk which establishes the generation of the chunks store. - The optional user-supplied key present in the Open options. - The offset and size that the Chunk is at in the file.
If the first chunk does not contain random data, then no chunks in the Store will be encrypted.
Caveats:
- Data is not actually flushed to disk until Flush() is called. You should not expect ReadAt (either on the Store or on an unflushed Chunk) to return the data you wrote until after it has been Flushed to disk.
Index ¶
- Constants
- Variables
- func Recover(into, from *Store) (err error)
- type Buffer
- type Chunk
- func (c *Chunk) Crc() uint32
- func (c *Chunk) Equal(other *Chunk) bool
- func (c *Chunk) Gen() uint64
- func (c *Chunk) Magic() string
- func (c *Chunk) Offset() int64
- func (c *Chunk) OnDiskSize() int64
- func (c *Chunk) Payload(buf []byte) error
- func (c *Chunk) ReadAt(p []byte, off int64) (int, error)
- func (c *Chunk) Size() int64
- func (c *Chunk) TargetSlice(s []byte) []byte
- func (c *Chunk) Zero() bool
- type Options
- type Store
- func (s *Store) CheckAt(offset int64) error
- func (s *Store) Clear() error
- func (s *Store) Close() (err error)
- func (s *Store) CopyInto(src []Chunk) (res []Chunk, err error)
- func (s *Store) Each(thunk func(Chunk, Buffer) error) error
- func (s *Store) EachAfter(start Chunk, thunk func(Chunk, Buffer) error) (err error)
- func (s *Store) Expand(target int64) error
- func (s *Store) Flush() error
- func (s *Store) Open(readOnly bool) error
- func (s *Store) OpenAndClear() (err error)
- func (s *Store) ReadAt(gen uint64, offset int64) (Chunk, error)
- func (s *Store) ResizeTo(target int64) error
- func (s *Store) Shrink() error
- func (s *Store) ShrinkTo(target int64) error
- func (s *Store) Size() int64
- func (s *Store) StreamInto(target *Store, after Chunk) (next Chunk, err error)
- func (s *Store) Write(magic string, src Buffer) (Chunk, error)
- func (s *Store) WriteBatch(magic string, res []Chunk, chunkBufs []Buffer) error
- type Thunk
Constants ¶
const ( // Alignment of Chunks in the file. Chunks are aligned on 128 byte boundaries to facilitate file checking. Alignment = 128 // SegmentPower is the number of bits to shift to mask out when rounding a segment size. SegmentPower = 24 // SegmentSize is the size of a segment in the file. The file is grown by this much when more space is required. SegmentSize = 1 << SegmentPower // ChunkHeaderSize is the size of the Chunk metadata. ChunkHeaderSize = 32 // First is the magic number of the first Chunk in the Store. It establishes the chunk generation and // holds the random key material all user data will be encrypted with. First = `1sT!` // Checkpoint is the magic number of a Chunk indicating that a sequence of writes has been committed to disk. Checkpoint = `cKpT` )
Variables ¶
var ( // ErrBadTargetSize is returned when a read buffer for reading a Chunk is not the exact size // of the chunk as returned by chunk.Size(). ErrBadTargetSize = errors.New("Target slice for Payload not correct size") // ErrBadFirstChunk is returned when the chunk at offset 0 is not a valid First chunk and the // chunk at offset 128 is not avalid Checkpoint chunk of the same generation as the First chunk. ErrBadFirstChunk = errors.New("First chunk in the Store is not a First chunk!") // ErrChunkTooShort is returned when the size of the Chunk on disk is smaller than Alignment bytes. ErrChunkTooShort = errors.New("Chunk too short") // ErrChunkTruncated is returned when the expected size of the Chunk on disk would cause it to be larger than // the remaining space on the Store. ErrChunkTruncated = errors.New("Chunk truncated") // ErrChunkCorrupt is returned if the checksum recorded in the Chunk header does not match the calculated // checksum. ErrChunkCorrupt = errors.New("Chunk corrupt") // ErrChunkMoved is returned when the Offset recorded in the Chunk header does not match the offset it was // found at in the Store. ErrChunkMoved = errors.New("Chunk at unexpected offset") // ErrGenMismatch is returned when the Generation of the chunk is not equal to the Generation of the // first chunk in the Store. ErrGenMismatch = errors.New("Chunk generation mismatch") // ErrLastCheckpointMismatch is returned when the offset of the last valid Checkpoint in the Store // is not equal to what it was when the Store was Closed. ErrLastCheckpointMismatch = errors.New("Last checkpoint offset changed") // ErrZeroChunk is returned when a chunk is all zeroes, which should never happen. ErrZeroChunk = errors.New("Zero chunk") // ErrNeedRecovery is returned when there is a run of invalid Chunks in between two valid Chunks // in the Store. That indicates that there is corruption in the store, but that there is still // valid data that might be recoverable. ErrNeedRecovery = errors.New("Needs recovery or clear") // ErrReadOnly is returned when a write operation is attempted on a store that was opened with the // ReadOnly option set to true. ErrReadOnly = errors.New("Store is open read-only") // ErrStoreClosed is returned when any method other than Open is called on a Closed store. ErrStoreClosed = errors.New("Store is closed") // ErrStoreStopped is returned when there is an underlying write error. ErrStoreStopped = errors.New("Store is stopped due to a lower-level write error.") // ErrBadBatch is returned when the number of Batches to write is not equal to the amount of data in the batches. ErrBadBatch = errors.New("Bad batch") // ErrNotFlushed is returned if you try to read a Chunk past the end of the last Checkpoint ErrNotFlushed = errors.New("Read past flushed data") )
Functions ¶
Types ¶
type Buffer ¶ added in v0.8.0
Buffer is anything that satisfies both the io.ReaderAt interface and that has a known Size.
type Chunk ¶
type Chunk struct {
// contains filtered or unexported fields
}
Chunk is an individual piece of data stored in the Store. It always starts at an Alignment offset, and has the following structure:
- [0:4]: crc32.Castagnoli checksum of the rest of the chunk data. Used to detect data corruption. Everything after this is checked by the CRC.
- [4:8]: Magic number. First (`1sT!`) and Checkpoint (`cKpT`) are used internally for the first chunk and the completed checkpoint marker, all others are available for users.
- [8:16]: Chunk generation. Generation is established by the first chunk in the sequence, and resetting the Store increments it.
- [16:24]: The Size of the chunk, including the chunk header.
- [24:32]: The Offset in the store the Chunk was written to.
- [32:] Chunk payload. Opaque to the chunk store.
func (*Chunk) Equal ¶ added in v0.8.0
Check to see if two Chunk objects are equal. Checks jsut the headers, not the payload, which is Good Enough for test purposes.
func (*Chunk) Gen ¶
Gen is the Generation of the Chunk. All valid Chunks in the Store have the same Gen as the First chunk in the Store.
func (*Chunk) OnDiskSize ¶ added in v0.8.0
Size of the Chunk on disk, including the header and padding.
func (*Chunk) Payload ¶
Payload copies the data stored in the Chunk into target, which must be large enough to store all the data. If you only need to read part of the data, use ReadAt instead.
func (*Chunk) ReadAt ¶ added in v0.7.4
ReadAt implements io.ReaderAt. It can be used to read parts of the payload. If the Store is encrypted, use of multiple small ReadAt calls in the same Chunk will have significant overhead due to the Go standard library not being able to cache and reuse stream cipher handlers. If the Go cipher devs ever choose to expose their XORKeyStreamAt method, that situation will change.
func (*Chunk) TargetSlice ¶ added in v0.6.0
TargetSlice is a utility that grows the passed-in slice until it can hold the entire payload.
type Options ¶ added in v0.6.0
type Options struct {
// Key is an optional key used for encrypting data at rest, If set, this key is
// mixed in with the random per-generation key that data at rest is encrypted with as well.
Key []byte
// Plaintext determines whether written data should not be encrypted. By default, all data will be
// encrypted at rest.
Plaintext bool
// ReadOnly determines whether this Store can be written to.
// If set, all write operations will fail.
ReadOnly bool
// Unsafe determines whether the Flush method will force sync to disk.
// If set, it will not.
Unsafe bool
// Clear determines whether the Store will be cleared upon open.
Clear bool
}
Options contain the options that the store should be opened with.
type Store ¶
type Store struct {
// contains filtered or unexported fields
}
Store stores Chunks.
func OpenScratch ¶
OpenScratch opens a scratch chunk store. Any data in the Store will be cleared, and the Flush operation will not force data to disk.
func (*Store) CheckAt ¶
CheckAt checks the Chunk at offset to ensure that it is well-formed and that the data has not been altered.
func (*Store) Clear ¶
Clear clears the Store by writing a new First chunk with a new Generation and then flushing that chunk.
func (*Store) Close ¶
Close closes a Store by unmapping the backing file then closing it. You must call Flush() beforehand to guarantee that all data has been written first.
func (*Store) CopyInto ¶ added in v0.8.0
CopyInto copies the Chunks in src into itself, The returned list of Chunks are members of s.
Chunk data is not guaranteed to be present on disk or accessible via chunk.Payload or chunk.ReadAt until the store has been flushed.
func (*Store) Each ¶
Each calls thunk once on each flushed Chunk. Calling Each concurrent with Write or Clear may result in undefined behaviour.
func (*Store) EachAfter ¶ added in v0.7.4
EachAfter iterates over all the committed chunks after start. If start is an empty Chunk, iteration will start at the beginning of the Store.
Inside of
func (*Store) Flush ¶
Flush writes modified data back to the disk. Any data not flushed will be lost in a crash or when the store is closed. Flush will wait on all pending writes to finish.
func (*Store) Open ¶
Open a previously-closed Store. This assumes that the Store had been flushed and closed without error. It will error out if the state of the Store has changed.
func (*Store) OpenAndClear ¶
OpenAndClear opens a new Store and clears it out all in one operation. This should be used when you explicitly want to ignore the data in a Store.
func (*Store) ReadAt ¶
ReadAt reads a Chunk starting at Offset. It will panic if offset does not point at a valid Chunk. The returned Chunk is only valid until Write needs to remap the Store due to needing more space on disk.
func (*Store) ResizeTo ¶ added in v0.7.3
ResizeTo will resize the Store to as close to the target size it can get without losing data.
func (*Store) Shrink ¶
Shrink will discard extra segments past the end of the write barrier at the end of the Store. It is equivalent to calling s.ShrinkTo(0)
func (*Store) ShrinkTo ¶ added in v0.7.3
ShrinkTo will discard extra segments until either the size equals target rounded to the nearest segment boundary.
func (*Store) StreamInto ¶ added in v0.8.0
StreamInto streams chunks from s into target, starting at the chunk immediatly following after and ending with the last Chunk that has been flushed to disk. Both the after Chunk and the next Chunk are members of s, not target. StreamInto will block anything on Target that waits on all pending writes.
Chunk data is not guaranteed to be present on disk or accessible via chunk.Payload or chunk.ReadAt until the target store has been flushed.
func (*Store) Write ¶
Write data as a new Chunk into the Store, expanding the Store as needed. You must Flush the Store to ensure data is written to disk and checkpointed. Failure to call Flush will result in the data accumulated since the last Flush being discarded the next time the Store is opened.
Write returns the Chunk that was written. The Chunk will remain valid until the store is Cleared. Chunk data is not guaranteed to be present on disk or accessible via chunk.Payload or chunk.ReadAt until the store has been flushed.
func (*Store) WriteBatch ¶ added in v0.8.0
WriteBatch should be used when you have a bunch of individual Chunks using the same magic number to write.
magic is the magic string that all the Chunks will have on disk. res is a slice of Chunks that will be populated with the Chunks that were written to disk. It must be either nil or the same length as chunkBufs. chunkBufs contains the buffers that each Chunk should be populated with.
If an error occurs during the write process, a non-nil error will be returned, and you should ignore anything in the res slice.
The following code is equivalent in effect:
chunks := make([]Chunk,500)
var err error
for i := range chunks {
chunks[i], err = s.Write("StUf",[][]byte{[]byte("foo")})
}
chunks := make([]Chunk,500)
payloads := make([][][]byte, 500)
foo = []byte("foo")
for i := range payloads {
payloads[i] = [][]byte{foo}
}
err = s.WriteBatch("StUf",chunks,payloads)
WriteBatch is much more performant than Write in a loop when flushing a bunch of small Chunks.
Chunk data is not guaranteed to be present on disk or accessible via chunk.Payload or chunk.ReadAt until the store has been flushed.
type Thunk ¶ added in v0.8.0
Thunk is the function type that Each and EachAfter take to let calling code do something with the Chunks being iterated over. You can copy the Chunk outside of the Thunk, and it will work normally with the usual Chunk lifecycle rules. If you need to do something with the payload the Chunk carries, use the ReadAt method on the Buffer that gets passed in to avoid excess disk IO.
Source Files
Directories