text:
US20160182088A1 - Method For File Updating And Version Control For Linear Erasure Coded And Network Coded Storage - Google Patents
Method For File Updating And Version Control For Linear Erasure Coded And Network Coded Storage Download PDF
US10270468B2 (en
Márton A. Sipos
Daniel E. Lucani
Janus Heide
Morten V. Pedersen
Frank H.P. Fitzek
2014-12-19 Priority to US201462094125P priority Critical
2015-12-18 Application filed by Aalborg Universitet filed Critical Aalborg Universitet
2015-12-18 Priority to US14/973,850 priority patent/US10270468B2/en
2016-01-06 Assigned to AALBORG UNIVERSITET reassignment AALBORG UNIVERSITET ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: FITZEK, FRANK H.P., PEDERSEN, MORTEN V., HEIDE, JANUS, SIPOS, MÁRTON A., LUCANI, DANIEL E.
H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
H03M13/13—Linear codes
H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
H03M13/154—Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
G06F11/00—Error detection; Error correction; Monitoring
G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
G06F11/14—Error detection or correction of the data by redundancy in operation
G06F3/06—Digital input from or digital output to record carriers, e.g. RAID, emulated record carriers, networked record carriers
G06F3/0601—Dedicated interfaces to storage systems
G06F3/0602—Dedicated interfaces to storage systems specifically adapted to achieve a particular effect
G06F3/0614—Improving the reliability of storage systems
G06F3/0619—Improving the reliability of storage systems in relation to data integrity, e.g. data losses, bit errors
G06F3/0628—Dedicated interfaces to storage systems making use of a particular technique
G06F3/0638—Organizing or formatting or addressing of data
G06F3/064—Management of blocks
G06F3/0668—Dedicated interfaces to storage systems adopting a particular infrastructure
G06F3/067—Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
G06F8/00—Arrangements for software engineering
G06F8/60—Software deployment
G06F8/65—Updates
G06F8/658—Incremental updates; Differential updates
H03M13/134—Non-binary linear block codes not provided for otherwise
H04L67/10—Network-specific arrangements or communication protocols supporting networked applications in which an application is distributed across nodes in the network
H04L67/1097—Network-specific arrangements or communication protocols supporting networked applications in which an application is distributed across nodes in the network for distributed storage of data in a network, e.g. network file system [NFS], transport mechanisms for storage area networks [SAN] or network attached storage [NAS]
H03M13/1515—Reed-Solomon codes
Described herein are systems and processes to provide file updating for distributed storage performed using linear codes, such as network codes and random linear network coding (RLNC). The processes enable efficiently updating coded file fragments without requiring a full upload of a new coded fragments. Separate processes for modifying, deleting, and adding data elements are described.
CROSS REFERENCE TO RELATED APPLICATION
This application claims the benefit under 35 U.S.C. §119(e) of U.S. Provisional Application No. 62/094,125 filed Dec. 19, 2014, which application is incorporated herein by reference in its entirety.
As is known in the art, distributed storage has attracted interest from both industry and researchers as a flexible, cost-efficient, high performance, and potentially secure solution for geographically distributed data centers, edge caching or sharing storage among users. Distributed storage systems are designed to store data reliably over long periods of time using a collection of storage nodes which are individually unreliable. Different techniques are known for achieving reliability in such a system. A simple approach is to replicate data across multiple nodes, however this approach can be inefficient in terms of network data transfer and storage space.
Some distributed and cloud storage solutions rely on erasure codes to provide high reliability while reducing the overall storage space. Erasure codes allow a distributed storage system to split a packet in multiple fragments, encode them, and spread the coded fragments across nodes, delivering the same or better reliability than data replication but with less redundancy (i.e., storage space) than simple replication. One of the challenges with erasure codes is that redundancy must be refreshed as storage nodes fail, requiring large data transfers to occur across the network.
In this context, distributed and cloud storage utilizing network codes has shown a large potential for trading off storage cost and network use for repairing lost fragments of data as well as a flexible mechanism to update storage conditions and requirements on-the-fly.
It is recognized herein that, although it is known to use network codes and erasure codes for distributed storage, existing systems fail to provide efficient techniques for updating coded fragments. For example, in some existing systems, when any portion of a file is changed (e.g., when bits have been changed, added, or removed from a file), the entire file must be recoded and all coded fragments must be transmitted through the network, placing a large strain on the network. This problem may be compounded if several versions of a file need to be maintained. Although the difference between the original and the modified data can be stored using less space in an unencoded form, this approach lacks the benefits offered by coding and does not allow for a seamless update of the file without first decoding the original file to later apply the history of changes.
Other storage systems, such as systems that use RAID, provide limited update capability by only allow files to be appended to. Here, changing a file requires storing not only the original file, but also storing additions to the file at separate locations. This results in high storage usage over time and complicates data access.
Described herein are systems and techniques that exploit the linear operations of erasure codes to provide an efficient means to update coded fragments in the network without sending the original data and without sending all coded fragments. Moreover, the disclosed systems and techniques allow for the efficient implementation version control within coded storage systems while reducing the network use and storage use of the system overall. The disclosed systems and techniques support parts of files being added, deleted, or individual bytes being modified. Further, the disclosed systems and techniques can be utilized in distributed storage and cloud systems linear erasure codes and is fully compatible with random linear network codes and other network code variants. The systems and techniques can be used to provide storage for data centers and also to exploit multiple cloud storage providers and/or locations simultaneously, as the cost for sending a new fully coded packet is high, both in network use and storage.
According to one aspect of the disclosure, a method is provided for use in a distributed storage system having a plurality of nodes. The method comprises: receiving, at a source node, original data; encoding the original data into plurality of coded fragments using a linear code; transmitting at least a first one of the coded fragments from the source node to a first sink node; receiving, at the source node, modified data; calculating, at the source node, a coded difference between the original data and the modified data; transmitting the coded difference from the source node to the first sink node; and recovering, at the first sink node, at least a first portion of the modified data using the coded difference and the at least a first one of the coded fragments.
With this particular arrangement, a technique to efficiently update coded fragments seamlessly and without requiring a full upload of a new coded fragment is provided. The technique provides file updating for distributed storage performed using linear codes, such as network codes and random linear network coding (RLNC). The technique further allows for efficient implementation of version control (i.e., maintaining backup versions of files) while relying on efficient representations of the evolution of the data.
In some embodiments of the method, encoding the original data comprises encoding the original data using a linear network code. The method may further include transmitting additional ones of the coded fragments from the source node to a first sink node and, at the first sink node, jointly decoding the coded difference and the additional ones of the coded fragments to recover all of the modified data. In certain embodiments, the method further comprises storing, at the first sink node, the at least a first one of the coded fragments and the coded difference.
In various embodiments, calculating a coded difference between the original data and the modified data comprises remapping the original data to replace occurrences of a special value with a different value. Calculating the coded difference between the original data and the modified data may comprise replacing deleted data elements with the special value. Transmitting the coded difference from the source node to the first sink node may include transmitting an index within the original data where a first data element is inserted and transmitting a number of data elements inserted. The method may further include storing, at the first sink node, the index within the original data with the first data element is inserted and the number of data elements inserted.
In some embodiments, the method further includes: transmitting at least a second one of the coded fragments from the source node to a second sink node; transmitting the coded difference from the source node to the second sink node; and recovering, at the second sink node, at least a second portion of the modified data using the coded difference and the at least a second one of the coded fragments.
In certain embodiments of the method, calculating a coded difference between the original data and the modified data may include transforming the original data to group together changes. In some embodiments, transmitting the coded difference from the source node to the first sink node may include compressing the coded difference.
According to another aspect of the disclosure, a method for use in a version control system comprises: receiving a first file version; storing a representation of the first file version to a storage device; receiving a second file version; calculating a coded difference between the first and second file versions using a linear code; storing the coded difference between the first and second file versions to the storage device; and in response to receiving a request to retrieve the second file version: retrieving the representation of the first file version from the storage device; retrieving the coded difference between the first and second file versions from the storage device; and applying the coded difference between the first and second file versions to the representation of the first file version to generate a copy of the second file version.
In some embodiments, storing a representation of the first file version comprises storing a plaintext representation of the first file version. In certain embodiments, storing a representation of the first file version comprises: encoding the first file version into plurality of coded fragments using the linear code; and storing the plurality of coded fragments to the storage device.
In particular embodiments, the method further comprises: receiving a third file version; storing a representation of the third file version to the storage device; calculating a coded difference between the third and second file versions using a linear code; and storing the coded difference between the third and second file versions to the storage device. The method may also include, in response to receiving a request to retrieve the second file version: retrieving the representation of the third file version from the storage device; retrieving the coded difference between the third and second file versions from the storage device; and applying the coded difference between the third and second file versions to the representation of the third file version to generate a copy of the second file version.
According to yet another aspect of the disclosure, a method for use in a version control system may include: receiving a first file version; storing a representation of the first file version to a storage device; receiving a second file version; storing a representation of the second file version to a storage device; calculating a coded difference between the second and first file versions using a linear code; storing the coded difference between the second and first file versions to the storage device. The method may further include, in response to receiving a request to retrieve the first file version: retrieving the representation of the second file version from the storage device; retrieving the coded difference between the second and first file versions from the storage device; and applying the coded difference between the second and first file versions to the representation of the second file version to generate a copy of the first file version.
In some embodiments, storing a representation of the first/second file version comprises storing a plaintext representation of the first/second file version. In various embodiments, storing a representation of the second file version comprises: encoding the second file version into plurality of coded fragments using the linear code; and storing the plurality of coded fragments to the storage device.
The concepts, systems, and techniques sought to be protected herein may be more fully understood from the following detailed description of the drawings, in which:
FIG. 1 is a block diagram of an illustrative distributed storage system configured to efficiently update coded fragments within a network environment;
FIG. 1A is a block diagram of an illustrative storage node that may form a part of a distributed storage system;
FIGS. 2A-2C are flow diagrams of illustrative processes that can be used to efficiently update coded fragments within the distributed storage system of FIG. 1; and
FIG. 3 is a schematic representation of an illustrative computer that may form a part of the distributed storage system of FIG. 1.
The drawings are not necessarily to scale, or inclusive of all elements of a system, emphasis instead generally being placed upon illustrating the concepts, systems, and techniques sought to be protected herein.
Before describing embodiments of the concepts, systems, and techniques sought to be protected herein, some terms are explained. A "network" is made up of a plurality of processing sites generally referred to as "stations" or "nodes" connected by one or more physical and/or logical connections. When the connections enable transmission of a signal between the nodes, the connections are generally referred to as "links". As used herein, a link may be unidirectional (i.e. transmission of a signal in one direction between the nodes) or bidirectional (i.e. transmission of signals in both direction between the nodes).
Each node typically performs a switching function and one or more additional functions. The nodes may be coupled together in a variety of different network structures typically referred to as "network topologies." For example, network nodes may be coupled in so-called mesh topologies, ring (or circular) topologies, star topologies and tree topologies. Other topologies are also known.
The transmission of a signal from a first or source node to a second or receiver node may involve the transmission of the signal through one or more intermediate links and nodes coupled between the source node and the receiver node. Such a succession of links and nodes between a source node and a receiver node is referred to as a path.
The terms "source" and "source node" are used herein to refer to a node in a network that transmits (or sends) packets (referred to as "source packets") to one or more other nodes via one or more links in the network. The terms "sink, "sink node," "receiver," and "receiver node" are used herein to refer to a node in a network that receives packets through a link in the network.
The term "symbol" is used herein to refer to a unit of data transmitted through a network, such as a packet of data. It should be understood that the concepts, systems, and techniques described herein are not limited to any particular symbol sizes, data dimensions, or data formats. The terms "fragment" and "symbol" may be used synonymously herein.
The term "field size" refers to the order of a finite field (sometimes referred to as a "Galois field"). The notation GF(n) refers to a finite field of size n.
Referring to FIG. 1, a distributed storage system 100 is shown within an illustrative network environment. The illustrative distributed storage system 100 comprises a plurality of storage nodes 102 a . . . 102 n (generally denoted 102). In this example, each storage node 102 is connected to a respective one of a plurality of local-area networks (LANs) 104 a . . . 104 n (generally denoted 104), which may be interconnected via wide-area network (WAN) 106 such as the Internet.
A given LAN 104 may correspond to an Ethernet network, a WiFi network, a cellular network, or any other suitable type of network. In some embodiments, a given LAN and the storage nodes 102 connected thereto correspond to a cloud storage provider. Thus, it will be appreciated that a distributed storage system 100 can span multiple clouds, thereby providing improved performance, reliability, data availability, and other advantages. In various embodiments, at least one LAN 104 and the corresponding storage nodes 102 are collocated within a data center.
The storage nodes 102 a . . . 102 n may include, or otherwise have read/write access, to a respective storage devices 108 a . . . 108 n (generally denoted 108). The storage devices 108 may be provided as hard disk drives, flash drives or other non-volatile memory, network attached storage (SAN), disk arrays, or any other suitable type of storage. The storage devices 108 may be operable to store arbitrary-sized chunks of data, which may correspond to files or fragments thereof (including coded file fragments).
In operation, user applications (or "users") can issue commands to read and write data to the distributed storage system 100. From a user's perspective, data may be written and read as files, objects, streams, messages, etc. For simplicity of explanation, user data will be described below in terms of files, although the concepts, systems, and techniques sought to be protected herein are not limited to file-based applications.
Since individual storage devices 108 and/or individual storage nodes 102 are assumed to be unreliable, meaning they may not provide a sufficiently high level of data availability for a given application or use case, user data is stored across one or more of the storage devices 108. In addition to storing new files, users can issue commands to modify existing files. In general, there are three types of modifications: (1) changing data elements within a file without increasing the file's size (e.g., replacing N elements with N different elements); (2) adding elements to the file, thereby increasing the file size; and (3) removing elements from the file decrease its size.
As used herein, the term "data element" (or "element") refers to an arbitrary unit of data within a file, such as a bit, a byte, a word, etc.
In various embodiments, storage nodes 102 utilize a coding technique to generate a plurality of coded fragments (or "packets") from a single file. For example, a storage node 102 may split the file into a plurality of fragments and then use linear network coding to generate a plurality of coded fragments as linear combinations thereof. The coded fragments may then be transmitted to various nodes 102 for storage. If the file is subsequently modified, the coded fragments must be updated on the respective nodes 102. Advantageously, nodes of the system 100 utilize techniques described herein below to efficiently update the coded fragments without requiring the entire modified file to be encoded and transmitted through the network.
Consider a file with data M having elements taken from a given Galois Field GF(q). A user can issue a command to an arbitrary storage node 102 to store the file. The node 102 that processes the write command divides the original file into multiple fragments and encodes the fragments (e.g., using a linear erasure code or linear network code in GF(q)) into coded fragments X using a series of coding vectors (sometimes referred to as "coefficient vectors") V to generate the coded data. The coded fragments are then transmitted to and stored within one or more different nodes 102.
It is recognized herein that when the file is modified to M′, it is inefficient and unnecessary to transmit all coded fragments for M′ through the network. Instead, a storage node 102 can calculate and transmit information that describes the coded difference between the original file M and the modified file M′. The general approach that can be used is to create coded symbols that contain the differences for each symbol of encoded data and only sending the coded symbols over the network to the respective storage nodes (or "sinks") 102. In turn, a sink node 102 can use relatively simple computations to apply the encoded differences to update the stored data to reflect the changes that were made. The encoded differences can also be stored at the sink nodes 102 and thus multiple versions of files can be stored in a storage-efficient manner.
In some embodiments, the source node 102 may compress the encoded differences to reduce (and ideally minimize) the amount of information transmitted through the network. To increase the effectiveness of compression algorithms, the source node 102 may transform the order in which data is stored. For example, a source node may align data in such a way that modifications bundled together in the original data only affect parts of the coded difference symbols. This minimizes the number of non-zero elements in these symbols.
In certain embodiments, the source node 102 may assign a special value (e.g., zero, although the choice is arbitrary) to signal deletion of data in the original file M. To be able use the chosen value for this purpose, it must not be present in the original data. Thus, the system 100 may utilize a reversible technique that removes all occurrences of the special value from the data by remapping it to different value.
FIG. 1A shows a storage node 102′ that may be the same as or similar to a storage node 102 of FIG. 1. The illustrative storage node 102′ includes file storage 120, a file update processor 122, a fragment encoder 124, a network interface 126, a fragment decoder 128, and a fragment update processor 130. The various components 120-30 may be provided from any suitable combination of hardware and/or software configured to perform the functions described herein.
File storage 120 provides read and write access to files, file fragments, and coded file fragments stored upon a storage device (e.g., a storage device 108 of FIG. 1). The network interface 126 provides network transmit and receive capability and may be coupled, for example, to a local area network 104 of FIG. 1.
When a file is updated within file storage 120, the file update processor 102 may compare the contents of the original file with that of the modified file to determine whether (1) existing data elements were modified within the file, (2) data elements were deleted from the file, and/or (3) data elements were added to the file.
Depending on the type of change, the fragment encoder 124 can utilize an appropriate processing technique to calculate a coded difference between the files. In particular, if data elements were modified (1), the fragment encoder 124 may utilize processing show in FIG. 2A and described below; if data elements were deleted (2), the fragment encoder 124 may utilize processing show in FIG. 2B and described below; and if data elements were added (3), the fragment encoder 124 may utilize processing show in FIG. 2C and described below.
The coded fragments may be transmitted to one or more other storage nodes via the network interface 126, where they are received and decoded by the fragment decoder 128. As with the fragment encoder 124, the fragment decoder 128 employs various different processing (also described below in conjunction with FIGS. 2A-2C) depending on the type of change to the file (which may be signaled along with the coded packets). The fragment update processor 130 may store the decoded file fragments within the receiving node's local file storage 120 and/or may apply the fragments to previously received data to recover the modified data.
FIGS. 2A-2C, which are described herein below, show illustrative processes for file updating in a distributed storage system using linear codes, such as erasure codes (e.g., Reed-Solomon), network codes, and random linear network coding (RLNC). The various processes of FIGS. 2A-2C may be implemented within one or more nodes of a distributed storage system, such as distributed storage system 100 of FIG. 1.
Rectangular elements (typified by element 202 in FIG. 2A), herein denoted "processing blocks," represent computer software instructions or groups of instructions. Alternatively, the processing and decision blocks may represent steps performed by functionally equivalent circuits such as a digital signal processor circuit or an application specific integrated circuit (ASIC). The flow diagrams do not depict the syntax of any particular programming language. Rather, the flow diagrams illustrate the functional information one of ordinary skill in the art requires to fabricate circuits or to generate computer software to perform the processing required of the particular apparatus. It should be noted that many routine program elements, such as initialization of loops and variables and the use of temporary variables are not shown. It will be appreciated by those of ordinary skill in the art that unless otherwise indicated herein, the particular sequence of blocks described is illustrative only and can be varied without departing from the spirit of the concepts, systems, and techniques sought to be protected herein. Thus, unless otherwise stated the blocks described below are unordered meaning that, when possible, the functions represented by the blocks can be performed in any convenient or desirable order.
Before describing FIGS. 2A-2C in detail, some notation is explained:
M denotes original data, which may be organized as a matrix;
M′ denotes modified data, which may also be organized as a matrix;
{circumflex over (M)} denotes the difference between original and modified data, i.e. {circumflex over (M)}=M′−M;
V denotes a matrix defined by one or more coding vectors (e.g., vectors of coefficients used for linear network coding);
X denotes an encoded representation of original data;
X′ denotes an encoded representation of modified data;
{circumflex over (X)} denotes the coded difference between original and the modified data: {circumflex over (X)}=X′−X;
del denotes a vector of deleted indexes;
ins denotes a vector of elements to be inserted;
ind denotes the location (e.g., index) within the original data where the vector of elements is to be inserted;
At denotes a transformed version of a given matrix A (e.g., Mt denotes a transformed version of original data M);
Ar denotes a remapped version of a given matrix A (e.g., Xr denotes a remapped version of original encoded data X);
à denotes a version of a given matrix A that may contain invalid elements (e.g., elements that should be deleted);
A+ denotes a version given matrix A that contains extra columns; and
A− denotes a version matrix A that has had a sequence of its elements removed.
Using the above notation, the following operations can be defined (in the following equations it should be appreciated that M and/or M′ can be replaced with remapped and/or transformed versions of the same):
X=M·V—encoding original data;
X′=M′·V—encoding modified data;
{circumflex over (X)}={circumflex over (M)}·V—encoding the difference between original and modified data;
{circumflex over (M)}=M′−M—calculating the difference between original and modified data; and
{circumflex over (X)}=X′−X=(M′−M)·V—calculating the coded difference between original and modified data.
FIG. 2A shows an illustrative process 200 that may be used when modifying elements within original data M. As used herein, "modifying elements" refers to changing existing elements in the data and does not involve deleting or adding new elements, therefore the size of the data remains unchanged.
The original data M includes an arbitrary number of elements taken from a given finite field (e.g., GF(3)). The original data elements can be partitioned into one or more so-called "fragments" that can be arranged in matrix form. The source can generate (or otherwise obtain) one or more coding vectors v1, v2, v3, etc. each having elements drawn from the same finite field. The coding vectors can be arranged as columns within the matrix V (e.g., V=[v1; v2; . . . ]). The coding vector elements may be selected randomly or using any suitable technique.
It is assumed that, prior to process 200 being performed, a given sink node has received one or more coded fragments corresponding to the original data M. The sink node is also assumed to have knowledge of the coding vectors V.
The process 200 may receive as inputs original data M and modified data M′. At block 202, the original data M is remapped to produce Mr. In some embodiments, remapping involves using a reversible technique to remove occurred of special values from the original data. Using zero as an arbitrary choice for the special value, remapping can be expressed as:
M = ( m 1 m 2 … 0 … 0 … m 255  m 256 … 0 … )  ↓  M r = ( α m 1 m 2 … α … α … m 255  β m 256 … β … )
TABLE 1 shows an illustrative implementation of remapping that may be used within processing block 202 and/or processing block 206. The implementation removes the special value (here, zero) from a vector of bytes and substitutes it with values that are not present in the input data ("original").
1: procedure REMAP(original)
2: for each 255 long block of original do
3: unused_symbol ← find a symbol between 0..255, which ∉ block
save the unused_symbol as the remapping element
4: result[block_begin + block_ctr · 256] ← unused_symbol
remap the zero values to the remapping element
5: for i ← 0 to len(block) do
6: if block[i] = 0 then
7: result[block_begin + block_ctr · 256 + i + 1] ← unused_symbol
8: else
9: result[block_begin + block_ctr · 256 + i + 1] ← original[block_begin +
i]
10: end if
11: end for
12: block_ctr ← block_ctr + 1
14: return result
15: end procedure
Still referring to TABLE 1, each block in the remapped data starts with a remapping element that stores the value that was used to substitute the special values (zero in this example) with. This is followed by a limited number of data elements (e.g., bytes). For example, in the case of GF(28) data, the remapping element may be followed by at most 255 bytes of data. In general, if the field of size q is used, each block of remapped data can include at most q−1 symbols where each symbol has a size of at most [log2 q]bits. This corresponds to the maximum number of individual values that can be represented by the remapping byte minus 1, guaranteeing that there will be at least one value between, for example, 0 and 255 that does not appear in that block. The technique also works with elements smaller or larger than a byte. The maximum amount of data in each block is the amount of values that can be represented by the remapping element minus 1. For example, by using 16 bit values, the maximum number of elements in each block increases from 28 −1=255 to 216 −1=65535. It will be appreciated that the larger the size of the elements, the lower the overhead of the remapping element. As a result, fewer bytes need to be added on each fragment. For example, for GF(28), one byte is required for every 255 bytes, whereas for GF(216) two bytes are required for every 131,070 bytes.
Once the data is remapped, the special value can be used for signaling purposes. For example, as described further below, the special value can be used to identify deleted elements when transmitting an encoded difference.
Still referring to FIG. 2A, at block 204, the remapped data Mr may undergo a transformation procedure, resulting in Mr t. In various embodiments, the transformation changes the order of elements to make them align in a particular way when arranged in vector or matrix form. The goal is to be able to represent changes that are grouped together more efficiently.
The remapped data Mr can be represented as a matrix (e.g., a two-dimension array), where the number of rows corresponds to the number of symbols and the number of columns corresponds to the size of a symbol. The matrix is referred to as "incomplete" because the last row may have fewer elements compared to other rows.
The transformation procedure described herein is similar to a matrix transposition, but with special processing to account for a potentially incomplete last row. Placing elements that were close to each other in the original matrix in the same column or in adjacent columns in the transformed matrix ensures that any changes made to data that is close to each other will only affect the encoded difference in a localized manner. The illustrative transformation procedure may be expressed as follows, wherein k represents a number of symbols and s represents the size of a symbol.
M r = ( m 1 m 2 … … m s m s + 1 m s + 2 … … m 2  s ⋮ ⋮ ⋮ ⋱ ⋮ m ( k - 2 ) · s + 1 … … … m ( k - 1 ) · s m n - l … m n ) →  M r t = ( m 1 m k + 1 … … m n - k + 1 m 2 m k + 2 … … ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ m k - 1 … … … m n m k … m l · k )
TABLE 2 shows an illustrative implementation of a transformation procedure that may be used within processing block 204 and/or processing block 208. The input "original" may be provided as a two-dimensional array of data elements.
1: procedure TRANSFORM(original, symbol_size)
// current_element is the index of the data to be copied
2: current_element ← 0
// calculate the length of the last row
3: last_row_length ← len(original) mod symbol_size
4: for i ← 0 to len(original) do
5: result[i] ← original[current_element]
6: if (i + 1) mod symbol_size > last_row_length then
7: offset ← 1
11: current_element ← current_element + offset
12: if (i + 1) mod symbol_size = 0 then
13: current_element ← (i + 1) / symbol_size
At blocks 206 and 208, the modified data M′ may be similarly remapped and transformed to produce M′r t. In some embodiments, the processing of blocks 206 and 208 is the same as or similar to that of blocks 202 and 204 as described above.
At block 210, the difference between Mr t and M′r t is calculated as {circumflex over (M)}r t=M′r t−Mr t. In vector form, the difference between original data X and modified data X′ can be calculated by performing XOR on their elements individually as follows.
X=(x 2 x 2 . . . x n) XOR
X′=(x′ 1 x′ 2 . . . x′ n)
{circumflex over (X)}=(x 1 ⊕x′ 1 x 2 ⊕x′ 2 . . . x n ⊕x′ n)
TABLE 3 shows an illustrative implementation of processing may be used with block 210, where the arguments "original" and "changed" may correspond to Mr t and M′r t, respectively, in vector form.
1: procedure CALCULATE DIFF(original, changed)
2: for i < len(original) do
3: difference[i] F original[i] XOR changed[i]
4: end for
5: return difference
6: end procedure
At block 212, the difference {circumflex over (M)}r t may be encoded using the coding vectors V as {circumflex over (X)}r t={circumflex over (M)}r t·V. Any suitable coding technical can be used, including linear network coding or random linear network coding (RLNC). It will be appreciated that the encoded difference {circumflex over (X)}r t may comprise one or more coded fragments.
The coded fragments {circumflex over (X)}r t can be transmitted from the source node to one or more sink nodes, with different coded fragments being sent to different sink nodes as appropriate. A given sink node may have previously received coded fragments corresponding to the original data M. These previously received coded fragments are generally denoted X and may be arranged, for example, in matrix form. A sink node, having previously received original coded fragments X and having now received the encoded difference {circumflex over (X)}r t can recover the modified data M′ as follows.
At block 214, the encoded difference {circumflex over (X)}r t can be applied to the original coded fragments X to generate X′r t. In various embodiments, the process of applying the difference is the same as, or similar to, that of calculating the difference. Thus, the processing of block 214 may be identical, or similar to, that of block 210 as described above and illustrated in TABLE 3.
At block 216, X′r t can be decoded to produce a transformed and remapped version of the modified data as M′r t=X′r t ·V−1. Any suitable decoding technique can be used, e.g., Gaussian elimination.
At block 218, an inverse transformation procedure can be applied to the decoded data M′r t to produce remapped modified data M′r. This is the reverse operation of the transform routine, as shown in the following equations.
M r ′   t  ( s , k ) = ( m 1 m 2 … … m s m s + 1 m s + 2 … … m 2  s ⋮ ⋮ ⋮ ⋱ ⋮ m ( k - 2 ) · s + 1 … … … m ( k - 1 ) · s m n - l … m n ) →  M r ′   ( s , k ) = ( m 1 m k + 1 … … m n - k + 1 m 2 m k + 2 … … ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ m k - 1 … … … m n m k … m l · k )
is TABLE 4 shows an illustrative implementation of an inverse transformation procedure that may be used within processing block 218.
1: procedure TRANSFORM−1 (transformed, symbol_size)
// calculate number of columns
3: symbols = ceil(len(transformed) / symbol_size)
// calculate length of last row
4: last_row_length ← len(transformed) mod symbol_size
5: for i ← 0 block of original do
6: result[current_element] ← transformed[i]
10: offset ← 0
12: current_element ← current_element + symbols − offset
13: if current_element ≧ len(transformed) then
At block 220, an inverse mapping (or "unmap") procedure can be applied to the remapped modified data M′r to recover the modified data M′. The inverse mapping procedure may be a reverse of the mapping operation, as follow.
M r ′ = ( α m 1 ′ m 2 ′ … α … α … m 255 ′  β m 256 ′ … β … )   ↓   M ′ = ( m 1 ′ m 2 ′ … 0 … 0 … m 255 ′  m 256 ′ … 0 … )
An illustrative implementation of an inverse mapping procedure in shown in TABLE 5. In this example, the procedure takes a vector of bytes as input and substitutes the special values (e.g., zeros) back into it based on the signaling elements. This procedure can be performed for elements larger or smaller than a byte as well.
1: procedure UNMAP(remapped)
2: for each 256 long block of remapped do
// retrieve the remapped symbol
3: remapped_symbol ← remapped[begin_block]
// unmap the remapped values to zero
5: if block[i] = remapped_symbol then
6: result[block_begin + i − block_ctr − 1] ← 0
8: result[block_begin + i − block_ctr − 1] ← remapped[block_begin + i]
9: end if
In various embodiments, the processing of blocks 202-212 can be performed at a source node and the processing of blocks 214-220 can be performed at one or more sink nodes.
The process 200 may be better understood using the following simplified example. In this example, it is assumed that coding is performed using a linear erasure code in GF(3), wherein the code has elements −, 0, and + and summation and product operations defined in TABLES 6 and 7, respectively.
⊕ − 0 +
− + − 0
0 − 0 +
+ 0 + −
− 0 +
− + 0 −
+ − 0 +
It is further assumed that, in the following example, the original data M includes twelve (12) elements partitioned into fragments each having four (4) elements. In particular, assume Mr is defined as:
M r = [ + - - - - + + + - + + - ]
First, the source encodes N symbols that are sent and received by the sink. Here, it assumed that the source encodes two symbols (N=2), however more coded fragments can be generated depending on desired redundancy. The source generates (or otherwise obtains) the following coding vectors vi and v2, each having three (3) elements, which can be arranged into a matrix as shown in the following example:
V = [ v 1 ; v 2 ] = [ + 0 - + 0 - ]
Thus, the coded symbols can be calculated as:
X = M r · V = [ - 0 0 + 0 - 0 - ]
It is assumed herein that the sink has knowledge of X prior to execution of process 200 (e.g., the corresponding coded fragments were received from the source node).
Next, on the source side, the original data is updated M→M′≠M, where the update can be expressed as:
{circumflex over (M)}=M′−M
or equivalently:
{circumflex over (M)} r =M′ r −M r
For example, assume the following update to the original data (in remapped form) where the change is marked with parentheses:
M r ′ = [ + - - - - + + ( - ) - + + - ]
The source can calculate the update as:
M ^ r = [ + - - - - + + - - + + - ] - [ + - - - - + + + - + + - ] = [ 0 0 0 0 0 0 0 + 0 0 0 0 ]
It should be appreciated that the update {circumflex over (M)}r could instead be calculated against transformed versions of {circumflex over (M)}r and M′r, for example as shown at block 210 of FIG. 2A.
The source can then either transmit a compressed version of {circumflex over (M)}r to the sink or it can generate coded updates for the two original coded fragments by taking the product of {circumflex over (M)}r and the original coding vectors (which remain unchanged), i.e., {circumflex over (X)}={circumflex over (M)}r·V.
Having received the encoded difference X, the sink node can then use then calculate the modified encoded data as:
X ′ = X + X ^ = [ - 0 0 + 0 - 0 - ] + [ 0 0 0 0 0 0 0 + 0 0 0 0 ] · [ + 0 - + + - ] = [ - 0 0 + 0 - 0 - ] + [ 0 0 0 0 - + 0 0 ] = [ + - - - - + + ( - ) - + + - ]
The source can encode and send an additional symbol using a third coding vector v3, for example:
x ′ = M r ′ · v 3 = [ + - - - - + + - - + + - ] · [ - - 0 ] = [ 0 - 0 + ]
The sink can the jointly decode the first two coded update symbols X′ and the third coded update symbol x′ to decode the updated data.
M r ′ = [ X ′  x ′ ] · [ V  v 3 ] - 1 = [ - 0 0 0 + - - 0 0 0 - + ] · [ - + + 0 0 - + + + ] = [ + - - - - + + - - + + - ]
This, as illustrated by the preceding example, a sink node can produce the updated data without requiring the updated data to be transmitted in full.
FIG. 2B shows an illustrative process 230 that may be used when deleting elements from original data M. As used herein, the phrase "deleting element" refers to the process of removing an arbitrary number of elements from arbitrary locations in the original data, thereby decreasing the size of the data.
As inputs, the process 230 may receive the original data M and information about the deletes (denoted del). In some embodiments, the delete information del comprises a list of locations (e.g., indexes) within the original data M corresponding to the location of the deleted elements.
At blocks 232 and 234, the original data M may be remapped and transformed to produce Mr t. The processing of blocks 232 and 234 may be the same as, or similar to, that of blocks 202 and 204, respectively, which processing blocks are described above in conjunction with FIG. 2A.
At block 236, deleted data M′r t may be generated using the remapped, transformed data Mr t and the delete information del. In various embodiments, the deleted data M′r t is generated by replacing elements of the original data identified by the list of indexes del with a special value (e.g., zero). This processed is illustrated by the following equations wherein elements md1, md2, etc. correspond to the deleted elements.
M = ( m 1 m 2 … m d   1 … m d   2 … )  ↓  M ′ = ( m 1 ′ m 2 ′ … 0 … 0 … )
TABLE 8 shows an implementation of a procedure that may be used within block 236. This illustrative procedure creates a version of the input data ("original") having deleted elements replaced with a special value (e.g., zero). It is assumed that the input data has been previously remapped to ensure that it does not contain the special value.
// del is a list of indexes to be deleted
1: procedure CREATE DEL. DATA(original, del)
// index may be adjusted for remapping
3: if adjust_index(i) ε del then
4: result[i] ← 0
6: result[i] ← original[i]
9: return result
At block 238, the difference of the deleted data M′r t and the remapped, transformed original data Mr t is calculated, resulting in {circumflex over (M)}r t. At block 240, the difference AC may be encoded as {circumflex over (X)}r t and the resulting coded fragments may be transmitted to one or more sink nodes. The processing of blocks 238 and 240 may be the same as or similar to that of blocks 210 and 212, respectively, of FIG. 2A.
It is recognized herein that it may be possible to calculate the difference {circumflex over (M)}r t without generating deleted data M′r t. This can be accomplished, for example, by modifying the removed elements individually, as all other values will correspond to the special value (e.g., zero).
A sink node, having previously received encoded data X and having now received the encoded difference {circumflex over (X)}r t can recover the modified data M′ as follows. At blocks 242-246, the sink node processes the received encoded difference {circumflex over (X)}r t along with the previously received encoded data X to produce remapped modified data M′r. The processing of blocks 242, 244, and 246 may be the same as or similar to that of blocks 214, 216, and 218, respectively, as described above in conjunction with FIG. 2A.
In contrast to process 200 (FIG. 2A), which handles modifying existing data elements, here the reverse mapping procedure cannot be directly applied to remapped modified data M′r to recover the modified data M′. Instead, the signaling data applied at the source node (e.g., the special value applied at block 236) must first be removed.
At block 248, a mask of deleted items del is produced from the remapped modified data M′r. In various embodiments, this involves identifying the indices of all special values (e.g., zeros) in the input data as follows, wherein the elements marked for deleting are denoted md1, md1, etc.
M = ( m 1 ′ m 2 ′ … 0 … 0 … )  ↓  M ′ = ( m 1 ′ m 2 ′ … m d   1 … m d   2 … )
TABLE 9 shows an illustrative implementation that may be used within processing block 248.
1: procedure CREATE DEL. MASK(original)
2: delete_count ← 0
4: if original[i] = 0 then
// save the deleted index
5: result[delete_count] ← i
6: delete_count ← delete_count + 1
At block 250, an inverse remapping routine may be applied to the remapped modified data M′r to produce a so-called "invalid" version modified data {tilde over (M)}′. The resulting data {tilde over (M)}′ is referred to as "invalid" because it may contain some invalid elements (i.e., elements that were deleted). The processing of block 250 may be the same as or similar to that of block 220 as described above in conjunction with FIG. 2A.
At block 252, the deleted mask del is applied to the "invalid" modified data {tilde over (M)}′ to produce the actual modified data M′. This may involve removing values from the data (in vector form) based on a list of deleted indices, as follows.
M ′ ~ = ( m 1 ′ … m a ′ 0 m a + 1 ′ … 0 … m b ′ 0 m b + 1 ′ … m n ′ )  ↓  M ′ = ( m 1 ′ … m a ′ m a + 1 ′ … … m b ′ m b + 1 ′ … m n ′ )
TABLE 10 shows an illustrative implementation that may be used within processing block 252.
1: procedure APPLY MASK(original, del)
4: if adjust_index(i) ∉ del
// copy non-deleted items
5: result[i − delete_count]← original[i]
In various embodiments, the processing of blocks 232-240 is performed at a source node, and the processing of blocks 242-252 is performed at one or more sink nodes.
FIG. 2C shows an illustrative process 260 that may be used when adding elements to original data M. As used herein, the phrase "adding elements" refers to the process of inserting an arbitrary number of elements (e.g., bytes, characters, or other unit of data) into the original data M, thereby increasing the size of the data. As inputs, the process may receive original data M, one or more elements to insert ins and a location ind within the original data where those elements should be inserted. In various embodiments, the insert location ind is an array index.
At blocks 262 and 264, original data M may be remapped and transformed as described above in conjunction with blocks 202 and 204 of FIG. 2A.
At block 266, columns are inserted into the remapped, transformed original data matrix Mr t to produce Mr t+. In some embodiments, the values within inserted columns may be set to a special value (e.g., zero) and elements that are to be overwritten are copied into the last inserted column. The following equations illustrate this procedure, where the insert location is denoted "b."
M r t  ( s , k ) = ( m 1 … a f … m n - k + 1 ⋮ b ⋮ ⋮ ⋮ c ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ d … … m n m k … e m l · k ) → M r t +  ( s , k ) = ( m 1 … a … 0 f … m n - k + 1 ⋮ 0 b ⋮ ⋮ ⋮ 0 c ⋮ ⋮ ⋮ 0 ⋮ ⋮ ⋮ ⋮ 0 d … … m n m k … 0 … e m l · k )
1: procedure INSERT COLUMNS(original, insertLength, index, symbols)
2: columns_to_insert ← calculate number of columns to insert using insertLength
3: for i ← 0 to index do
4: result[adjust_index(i)] ← original[adjust_index(i)]
6: for i ← 0 to columns_to_insert · symbols do
// fill newly inserted columns with zeros
7: result[adjust_index(index + 1)] ← 0
9: overwritten_length ← symbols − (index mod symbols)
// copy elements that are going to be overwritten into the last inserted column
10: for i ← 0 to overwritten_length do
11: result[adjust_index(index + columns_to_insert · symbols + i)]
12: ← original[adjust_index(index + i + overwritten_length)]
At block 268, the remapped, transformed original data Mr t, the insert elements ins, and the insert location ind may be used to produce insert data Mr t. In various embodiments, this includes: (1) adding padding (e.g., zeros) to the list of insert elements ins so that the data aligns after the insert operation; and (2) copying the padded list of insert elements into the transformed original data Mr t. The following equations illustrate this procedure.
// ins is a list (e.g., an array) of elements to insert
// ind is the insert location (e.g., an index)
// symbols is the number of rows
1: procedure CREATE INS. DATA (original, ins, ind, symbols)
// pad the ins array with zeros to make its length a multiple of "symbols"
2: for i ← len(ins) to len(ins) + symbols − (len(ins) mod symbols) do
3: ins[i] ← 0
// copy original data elements located before the insert
5: for i ← 0 to ind do
// insert data elements
8: for i ← ind to len(ins) do
9: result[adjust_index(i)] ← ins[i]
// copy original data located after the insert
11: for i ← ind + len(ins) to len(original) + len(ins) do
12: result[adjust_index(i)] ← original[adjust_index(i + len(ins))]
At block 270, the difference of the insert data M′r t and the remapped, transformed original data Mr t may be calculated. At block 272, this difference {circumflex over (M)}r t may encoded as {circumflex over (X)}r t and may be transmitted to one or more sink nodes. The processing of blocks 270 and 272 may be the same as or similar to that of blocks 210 and 212, respectively, of FIG. 2A.
In various embodiments, the insert location ind and the number of elements inserted len(ins) are also transmitted from the source node to sink nodes. These values are used as inputs to block 280, as described below. In some embodiments, a sink node may store the insert location ind and the number of inserted elements len(ins) in addition to the encoded difference (e.g., {circumflex over (X)}r t). This allows the sink to be able to successfully apply the encoded difference at later times, which may be a requirement for version control systems.
It is appreciated herein that steps of creating insert data, inserting columns into the original data, and calculating the difference can be performed as part of a single procedure. Thus, for example, two or more of processing blocks 266, 268, and 270 may be combined and/or omitted.
It is also appreciated herein that it may be possible to calculate the difference without creating the inserted data. For example, this can be accomplished by calculating the difference for only the inserted columns and setting all other elements to a special value (e.g., zero). ind
A sink node, having previously received encoded data X and having now received the encoded difference {circumflex over (X)}r t, along with insert location ind and the number of elements inserted len(ins), can recover the modified data M′ as follows.
At blocks 274, 276 and 278, the sink node processes the received encoded difference along with the previously received encoded to produce remapped modified data M′r. The processing of blocks 274, 276, and 278 may be the same as or similar to that of blocks 214, 216, and 218, respectively, as described above in conjunction with FIG. 2A.
At block 280, the insert location ind and the number of elements inserted len(ins) can be used to remove the inserted elements from the remapped modified data M′rto produce M′−. Processing block 280 may also produce as output the list of inserted elements ins, but without any padding (e.g., zeros) that may have been added by the source. This procedure is illustrated in the following equations.
1: procedure REMOVE INS. ELEMENTS (original, ind, length, symbols)
2: j ← 0
3: padding ← length mod symbols
5: if i ≧ ind and i < ind + length + padding then
6: if i < ind + length then
7: inserted[j] ← original[i]
9: j ← j + 1
10: else
11: result[i − j] ← original[i]
14: return result, inserted
At block 282, remapped modified data (with the inserted elements removed) M′r − is "unmapped" to produce M′−. The processing of block 282 may be the same as or similar to the processing of block 220 shown in FIG. 2A and described above in conjunction therewith.
At block 284, the inserted elements ins, which were extracted by processing block 280, may be inserted into M′− to recover the modified data M′. This operation may be similar to that of block 268. However, whereas block 268 operates on mapped, transformed data, processing block 284 operates on unmapped, untransformed data. In following equations, which illustrate processing that may be performed within block 284, the inserted elements ins are assumed to be inserted at location m′b.
1: procedure ADD INS. ELEMENTS (original, ind, ins)
5: for i ← ind to ind + len(ins) do
6: result[i] ← ins[i − ind]
8: for i ← ind + len(ins) to len(original) + len(ins) do
9: result[i] ← original[i − len(ins)]
Although the concepts, systems, and techniques are described herein in the context of distributed storage systems, it should be appreciated that they may be utilized in other applications, such as massive online multiplayer gaming, version control systems, and various other distributing computing applications.
For example, the techniques described herein can be used to support version control systems with coded storage (i.e., storing data using erasure codes). Version control typically keeps track of the changes to the files and would store those changes. If the version control system is coded (fully or in parts), the goal is to update the coded fragments with minimal overhead, but at the same time store these coded differences between versions so that you have a record of the changes. Thus, the techniques described above for efficiently calculating, storing, and using coded differences are well suited for use in version control systems.
There are several possibilities with how coding is used in a version control system. For example, a system may the original version of a file along with code differences between subsequent versions of the file. If the original version of the file is requested, it can be retrieved "directly" from storage. If a later version of the file is requested, coded differences may be applied to the original version to generate a copy of the latest version. Alternatively, a system may store the latest version of a file along with code differences between previous versions of the file. A hybrid approach is also possible, wherein the system stores the latest version of a file every so often (e.g., after every N updates).
Another consideration is how to store the original/latest version of the file. In some embodiments, original/latest file data can be stored in a completely coded fashion: the system generates and stores coded fragments for the original/latest file version in addition to storing coded updates. This use case is valuable for security/privacy: the coded file fragments can be stored across multiples storage devices such that it is not exposed within any single device. Alternatively, if reliability (but not security/privacy) is the goal, a plaintext representation of the original/latest file version may be stored along with additional coded fragments.
FIG. 3 shows an illustrative computer or other processing device 300 that may form a part of a distributed storage system (e.g., system 100 of FIG. 1) and may be configured to perform at least part of the processing described herein (e.g., the processes shown in FIGS. 2A-2C and described above in conjunction therewith). The computer 300 includes a processor 302, a volatile memory 304, a non-volatile memory 306 (e.g., hard disk), an output device 308 and a graphical user interface (GUI) 310 (e.g., a mouse, a keyboard, a display, for example), each of which is coupled together by a bus 318. The non-volatile memory 306 stores computer instructions 312, an operating system 314, and data 316. In one example, the computer instructions 312 are executed by the processor 302 out of volatile memory 304. In one embodiment, an article 320 comprises non-transitory computer-readable instructions.
Processing may be implemented in hardware, software, or a combination of the two. In various embodiments, processing is provided by computer programs executing on programmable computers/machines that each includes a processor, a storage medium or other article of manufacture that is readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices. Program code may be applied to data entered using an input device to perform processing and to generate output information.
The system can perform processing, at least in part, via a computer program product, (e.g., in a machine-readable storage device), for execution by, or to control the operation of, data processing apparatus (e.g., a programmable processor, a computer, or multiple computers). Each such program may be implemented in a high level procedural or object-oriented programming language to communicate with a computer system. However, the programs may be implemented in assembly or machine language. The language may be a compiled or an interpreted language and it may be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may be deployed to be executed on one computer or on multiple computers at one site or distributed across multiple sites and interconnected by a communication network. A computer program may be stored on a storage medium or device (e.g., CD-ROM, hard disk, or magnetic diskette) that is readable by a general or special purpose programmable computer for configuring and operating the computer when the storage medium or device is read by the computer. Processing may also be implemented as a machine-readable storage medium, configured with a computer program, where upon execution, instructions in the computer program cause the computer to operate.
Processing may be performed by one or more programmable processors executing one or more computer programs to perform the functions of the system. All or part of the system may be implemented as special purpose logic circuitry (e.g., an FPGA (field programmable gate array) and/or an ASIC (application-specific integrated circuit)).
All references cited herein are hereby incorporated herein by reference in their entirety.
Having described certain embodiments, which serve to illustrate various concepts, systems, and techniques sought to be protected herein, it will be apparent to those of ordinary skill in the art that other embodiments incorporating these concepts, systems, and techniques may be used. Elements of different embodiments described hereinabove may be combined to form other embodiments not specifically set forth above and, further, elements described in the context of a single embodiment may be provided separately or in any suitable sub-combination. Accordingly, it is submitted that scope of protection sought herein should not be limited to the described embodiments but rather should be limited only by the spirit and scope of the following claims.
1. A method for use in a distributed storage system having a plurality of nodes, the method comprising:
receiving, at a source node, original data;
encoding the original data into plurality of coded fragments using a linear code;
transmitting at least a first one of the coded fragments from the source node to a first sink node;
receiving, at the source node, modified data;
calculating, at the source node, a coded difference between the original data and the modified data;
transmitting the coded difference from the source node to the first sink node; and
recovering, at the first sink node, at least a first portion of the modified data using the coded difference and the at least a first one of the coded fragments.
2. The method of claim 1 wherein encoding the original data comprises encoding the original data using a linear network code.
transmitting additional ones of the coded fragments from the source node to a first sink node; and
at the first sink node, jointly decoding the coded difference and the additional ones of the coded fragments to recover all of the modified data.
4. The method of claim 1 further comprising storing, at the first sink node, the at least a first one of the coded fragments and the coded difference.
5. The method of claim 1 wherein calculating a coded difference between the original data and the modified data comprises remapping the original data to replace occurrences of a special value with a different value.
6. The method of claim 5 wherein calculating the coded difference between the original data and the modified data comprises replacing deleted data elements with the special value.
7. The method of claim 5 where transmitting the coded difference from the source node to the first sink node comprises transmitting an index within the original data where a first data element is inserted and transmitting a number of data elements inserted.
8. The method of claim 7 further comprising storing, at the first sink node, the index within the original data with the first data element is inserted and the number of data elements inserted.
transmitting at least a second one of the coded fragments from the source node to a second sink node;
transmitting the coded difference from the source node to the second sink node; and
recovering, at the second sink node, at least a second portion of the modified data using the coded difference and the at least a second one of the coded fragments.
10. The method of claim 1 wherein calculating a coded difference between the original data and the modified data comprises transforming the original data to group together changes.
11. The method of claim 1 wherein transmitting the coded difference from the source node to the first sink node comprises compressing the coded difference.
12. A method for use in a version control system, the method comprising:
receiving a first file version;
storing a representation of the first file version to a storage device;
receiving a second file version;
calculating a coded difference between the first and second file versions using a linear code;
storing the coded difference between the first and second file versions to the storage device; and
in response to receiving a request to retrieve the second file version:
retrieving the representation of the first file version from the storage device;
retrieving the coded difference between the first and second file versions from the storage device; and
applying the coded difference between the first and second file versions to the representation of the first file version to generate a copy of the second file version.
13. The method of claim 12 wherein storing a representation of the first file version comprises storing a plaintext representation of the first file version.
14. The method of claim 12 wherein storing a representation of the first file version comprises:
encoding the first file version into plurality of coded fragments using the linear code; and
storing the plurality of coded fragments to the storage device.
receiving a third file version;
storing a representation of the third file version to the storage device;
calculating a coded difference between the third and second file versions using a linear code;
storing the coded difference between the third and second file versions to the storage device; and
retrieving the representation of the third file version from the storage device;
retrieving the coded difference between the third and second file versions from the storage device; and
applying the coded difference between the third and second file versions to the representation of the third file version to generate a copy of the second file version.
storing a representation of the second file version to a storage device;
calculating a coded difference between the second and first file versions using a linear code;
storing the coded difference between the second and first file versions to the storage device; and
in response to receiving a request to retrieve the first file version:
retrieving the representation of the second file version from the storage device;
retrieving the coded difference between the second and first file versions from the storage device; and
applying the coded difference between the second and first file versions to the representation of the second file version to generate a copy of the first file version.
18. The method of claim 16 wherein storing a representation of the second file version comprises storing a plaintext representation of the second file version.
19. The method of claim 16 wherein storing a representation of the second file version comprises:
encoding the second file version into plurality of coded fragments using the linear code; and
US14/973,850 2014-12-19 2015-12-18 Method for file updating and version control for linear erasure coded and network coded storage Active US10270468B2 (en)
US201462094125P true 2014-12-19 2014-12-19
US14/973,850 US10270468B2 (en) 2014-12-19 2015-12-18 Method for file updating and version control for linear erasure coded and network coded storage
US10270468B2 US10270468B2 (en) 2019-04-23
US14/973,850 Active US10270468B2 (en) 2014-12-19 2015-12-18 Method for file updating and version control for linear erasure coded and network coded storage
US20170038978A1 (en) * 2015-08-05 2017-02-09 HGST Netherlands B.V. Delta Compression Engine for Similarity Based Data Deduplication
CN106708651A (en) * 2016-11-16 2017-05-24 北京三快在线科技有限公司 Erasure code-based partial write-in method and device, storage medium and equipment
US10034200B2 (en) * 2015-10-23 2018-07-24 Motorola Mobility Llc Iteratively transmitting random linear network encoded packets from multiple transmission nodes
US10191809B2 (en) * 2016-08-17 2019-01-29 International Business Machines Corporation Converting a data chunk into a ring algebraic structure for fast erasure coding
US10282127B2 (en) 2017-04-20 2019-05-07 Western Digital Technologies, Inc. Managing data in a storage system
US20020078205A1 (en) * 2000-11-17 2002-06-20 Lloyd Nolan Resource control facility
US20060236319A1 (en) * 2005-04-15 2006-10-19 Microsoft Corporation Version control system
US7251668B2 (en) * 2003-06-19 2007-07-31 International Business Machines Corporation Configuration management file rename utility
US20070271303A1 (en) * 2006-05-18 2007-11-22 Manuel Emilio Menendez Personal file version archival management and retrieval
US20080126440A1 (en) * 2006-11-28 2008-05-29 International Business Machines Corporation Methods, systems, and computer program products for file version control management
US20080154983A1 (en) * 2006-12-20 2008-06-26 Hong Fu Jin Precision Industry (Shenzhen) Co., Ltd Interface apparatus and method for managing file versions
US20080313241A1 (en) * 2007-06-15 2008-12-18 Microsoft Corporation Distributed data storage using erasure resilient coding
US20130086133A1 (en) * 2011-09-29 2013-04-04 General Electric Company Method and apparatus for file revision tracking
US20130275390A1 (en) * 2009-07-31 2013-10-17 Microsoft Corporation Erasure coded storage aggregation in data centers
US20140317222A1 (en) * 2012-01-13 2014-10-23 Hui Li Data Storage Method, Device and Distributed Network Storage System
Nolan US Publication 2002/078205 *
Papailiopoulos et al. 2012 Simple regenerating codes: Network coding for cloud storage
US8706980B2 (en) 2014-04-22 Method and apparatus for slice partial rebuilding in a dispersed storage network
US8165221B2 (en) 2012-04-24 System and method for sampling based elimination of duplicate data
US8351600B2 (en) 2013-01-08 Distributed storage network and method for encrypting and decrypting data using hash functions
US8819482B2 (en) 2014-08-26 Method and apparatus for distributed storage integrity processing
US8370297B2 (en) 2013-02-05 Approach for optimizing restores of deduplicated data
US9509514B2 (en) 2016-11-29 Deleting encoded data slices in a dispersed storage network
US7640484B2 (en) 2009-12-29 Triple parity technique for enabling efficient recovery from triple failures in a storage array
US20100332751A1 (en) 2010-12-30 Distributed storage processing module
CN101582698B (en) 2014-02-12 Protection of data from erasures using subsymbole based
US9645967B2 (en) 2017-05-09 Concurrent set storage in distributed storage network
US9996413B2 (en) 2018-06-12 Ensuring data integrity on a dispersed storage grid
EP2288991B1 (en) 2018-01-10 Method of storing a data set in a distributed storage system, distributed storage system and computer program product for use with said method
US9442800B2 (en) 2016-09-13 Data migration between a raid memory and a dispersed storage network memory
US8918674B2 (en) 2014-12-23 Directory file system in a dispersed storage network
US9015431B2 (en) 2015-04-21 Distributed storage revision rollbacks
JP4718340B2 (en) 2011-07-06 Storage system, control method, and program
US8762346B2 (en) 2014-06-24 Data de-duplication in a dispersed storage network utilizing data characterization
US9009564B2 (en) 2015-04-14 Storing data in a distributed storage network
US20120254689A1 (en) 2012-10-04 Updating error recovery information in a dispersed storage network
US9380032B2 (en) 2016-06-28 Encrypting data for storage in a dispersed storage network
US9154298B2 (en) 2015-10-06 Securely storing data in a dispersed storage network
CN103444087B (en) 2018-02-09 Elastic flexible source code for encoding and decoding block mapping
US8706701B1 (en) 2014-04-22 Scalable cloud file system with efficient integrity checks
US9811405B2 (en) 2017-11-07 Cache for file-based dispersed storage
Owner name: AALBORG UNIVERSITET, DENMARK
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SIPOS, MARTON A.;LUCANI, DANIEL E.;HEIDE, JANUS;AND OTHERS;SIGNING DATES FROM 20151210 TO 20151218;REEL/FRAME:037419/0652
2019-02-13 STPP Information on status: patent application and granting procedure in general
Free format text: PUBLICATIONS -- ISSUE FEE PAYMENT VERIFIED


ATHENA, UMATILLA COUNTY, OREGON, JULY 21 1893.
and Wisconsin, at 5:30 p. n.
cific points at u:ia p. m.
order window open from 9 a m. to 4 p.m.
(. I dially invited to visit the lodge.
J J in good standing always welcome.
Practices in nil court s of the state of Oregon.
BATHROOM IV CONNECTION WITH BHOP.
t Next to M. Finneran & Co.'s Athena, Or.
I DISEASES OF WOMEN A SPECIALTY.
I Office with Dr. Sharp, 3rd Street. Athena.
; : PIANO AND ORGAN.
1 with F. llozensweig, at C. W. HolUs' Athena.
by taking two or three diwes each week.
Jan. 1st tf. N. A. Miller.
niONT. FIRST. AND VINE STS., PORTLAND, OR.
lroves them to be the most popular in market.
DlKtluiculNhet for Strength aad Dnrobilttjr.
,D V 3'i42&Si PROVED TEDDER.
Ykrohinf ud Cleftuinf Gnus cm construcinl.
THAT HE HAS STRUCK IT RICH.
like any other crazy "prospector."
eral section in the world today.
new discoveries being made daily.
more of the glittering, the "Mable"
is "proof of the pudding."
mill and are "running through"
proaching this, is very rich.
low metal as the only "good"
why this clamor "cheap money"
trinsic value. Its "sheerest" folly.
mine better than many others.
of property, so with the goldite.
at all. The industrial interests?
permantly remain at a premium.
gets etc. I am Yours. I. McQ.
met at the home of Rev. A. R.
ly at the C. A. Barrett Co.
order to make a test case.
The Governor of Colorado Talks.
6eat3 and yelled until exhausted.
are about 80 stone-cutters at work.
can bo so carefully mapped out.
the contract price of $275 per ton.
It Has Not Been Stopped.
in the company, that is untrue.
stop the; train, but to no effect.
gaged in a desperate struggle.
A Son's Letter to His Father.
the blame for all my misfortune."
I am in prison to spend my life.


text:
Fudbalski klub Sarajevo () is a Bosnian professional football club based in Sarajevo, Sarajevo Canton, the capital city of Bosnia and Herzegovina and is one of the most successful clubs in the country.

This is a list of all the players that have played for the club since its foundation, in 1946.

Only players that have played at least one match in any of the following competitions: domestic league, domestic cup and European competitions.

Players that only played in friendlies, tournaments and that were on trial are not included.

A

 Rashid Abubakar
 Almin Abdihodžić
 Samir Abdurahmanović
 Edin Ademović
 Adi Adilović
 Joachim Adukor
 Almir Aganspahić
 Mersudin Ahmetović
 Anton Agošton
 Muhamed Alaim
 Safet Alajbegović
 Kemal Alispahić
 Mehmed Alispahić
 Haris Ališah
 Marin Aničić
 Boško Antić
 Ensar Arifović
 Branislav Arsenijević
 Zijad Arslanagić
 Alen Avdić
 Daniel Avramovski

B

 Miloš Babić
 Dražen Bagarić
 Milenko Bajić
 Saša Balić
 Elvir Baljić
 Srđan Bajić
 Dejan Bandović
 Tomislav Barbarić
 Mario Barić
 Bernard Barnjak
 Alen Bašić
 Boro Beatović
 Elmir Behlulović
 Elvedin Beganović
 Almir Bekić
 Amer Bekić
 Zoran Belošević
 Leon Benko
 Džemal Berberović
 Hamza Bešić
 Nemanja Bilbija
 Marco Bilić
 Ibrahim Biogradlić
 Miroslav Blažević
 Stjepan Blažević
 Darko Bodul
 Branko Bošnjak
 Tomislav Bošnjak
 Boban Božović
 Dragan Božović
 Miroslav Brozović
 Sead Bučan
 Muhamed Buljubašić

C

 Džemil Cerić
 Fadil Cerić
 Tarik Cerić
 Gojko Cimirot
 Boris Cmiljanić
 Ljuban Crepulja
 Nermin Crnkić
 Stojan Crnogorac

Ć

 Marko Ćetković
 Miodrag Ćirković

Č
 Hamza Čataković
 Frane Čirjak
 Adin Čiva
 Denis Čomor
 Muhidin Čoralić

D

 Muamer Dalipagić
 Fahrija Dautbegović
 Mirsad Dedić
 Matej Delač
 Salih Delalić
 Kenan Dervišagić
 Secouba Diatta
 Sreten Dilberović
 Belmin Dizdarević
 Patrik Doçi
 Vojislav Dragović
 Vlatko Drobarov
 Feđa Dudić
 Esad Dugalić
 Haris Duljević
 Amer Dupovac
 Zlatko Dupovac
 Samir Duro

Đ

 Andrej Đokanović
 Miloš Đurković

Dž

 Elvis Džafić
 Adin Džafić
 Muhamed Džakmić

E

 Savo Ekmečić

F

 Matthias Fanimo
 Mirsad Fazlagić
 Said Fazlagić
 Irfan Fejzić
 Sedik Fejzić
 Amar Ferhatović
 Asim Ferhatović
 Hamid Ferhatović
 Nidal Ferhatović
 Nijaz Ferhatović

G
 Nebojša Gavrić
 Nudžein Geca
 Midhat Gluhačević
 Nermin Gogalić
 Emir Granov
 Vladan Grujić
 Boris Gujić
 Giorgi Guliashvili
 Hilmo Gutić
 Adnan Gušo
 Aleksandar Guzina
 Gedeon Guzina

H

 Edin Hadžialagić
 Faruk Hadžibegić
 Damir Hadžić
 Emir Hadžić
 Dado Hamzagić
 Dino Hamzić
 Faris Handžić
 Haris Handžić
 Irfan Handžić
 Kenan Handžić
 Admir Hasančić
 Nermin Haskić
 Anes Haurdić
 Anel Hebibović
 César Augusto Hermenegildo
 Reuf Herco
 Nedim Hiroš
 Drago Hmelina
 Aaron Horton
 Dušan Hodžić
 Faruk Hodžić
 Ibro Hodžić
 Sead Hodžić
 Dženan Hošić
 Almedin Hota
 Adnan Hrelja
 Almir Hurtić
 Ermin Huseinbašić
 Said Husejinović
 Edin Husić

I

 Ferid Idrizović
 Faruk Ihtijarević
 Harmony Ikande
 Armin Imamović
 Dino Islamović
 Perica Ivetić

J

 Haris Jaganjac
 Adis Jahović
 Mato Jajalo
 Davor Jakovljević
 Dragan Jakovljević
 Anto Jakovljević
 Emir Janjoš
 Mehmed Janjoš
 Slobodan Janjuš
 Amar Jašarević
 Sead Jesenković
 Dušan Jevtić
 Bojan Jović
 Davor Jozić
 Ivica Jozić
 Dušan Jovanović
 Juninho Botelho
 Goran Jurišić
 Nedim Jusufbegović
 Osman Jusufbegović

K

 Ahmad Kalasi
 Adnan Kanurić
 Adis Kapetanović
 Mirza Kapetanović
 Sead Kapetanović
 Vladimir Karalić
 Žarko Karamatić
 Haris Karamehmedović
 Elvis Karić
 Rijad Kobiljar
 Damir Kojašević
 Nikola Komazec
 Muhamed Konjić
 Predrag Koprivica
 Miroljub Kostić
 Germain Kouadio
 Adnan Kovačević
 Goran Kovačević
 Vladan Kovačević
 Denis Kramar
 Sulejman Krpić
 Simo Krunić
 Mirzet Kruprinac
 Dane Kuprešanin
 Numan Kurdić

L
 Darko Lazić
 Igor Lazić
 Frank Liivak
 Zoran Ljubičić
 Đuka Lovrić
 Franjo Lovrić
 Enver Lugušić
 Emerson Reis Luiz
 Zoran Lukić

M

 Marinko Mačkić
 Smajo Mahmutović
 Osman Maglajlija
 Anton Mandić
 Milan Makić
 Marko Maksimović
 Ajdin Maksumić
 Lev Mantula
 Marciano José do Nascimento
 Srboljub Markušević
 Ilija Martinović
 Matija Matko
 Ivan Matošević
 Alen Melunović
 Nijaz Merdanović
 Senad Merdanović
 Enes Mešanović
 Jasmin Mešanović
 Mirza Mešić
 Marko Mihojević
 Nihad Milak
 Slobodan Milanović
 Ninoslav Milenković
 Hrvoje Miličević
 Semjon Milošević
 Damir Mirvić
 Risto Mitrevski
 Gregor Mohar
 Refik Muftić
 Musa Muhammed
 Haris Muharemović
 Veldin Muharemović
 Nihad Mujakić
 Ismet Mulavdić
 Husref Musemić
 Vahidin Musemić
 Alen Mustafić
 Zinedin Mustedanagić
 Džemaludin Mušović
 Fuad Muzurović

N

 Nathan
 Safet Nadarević
 Miloš Nedić
 Vladimir Nikitović
 Mile Novaković
 Saša Novaković
 Nerčez Novo
 Jean-Louis Nouken
 Samir Nuhanović

O

 Emir Obuća
 Godfrey Ogbonna
 Branko Okić
 Ševko Okić
 Renan Oliveira
 Mirko Oremuš
 Abdulah Oruč
 Amer Osmanagić
 Adnan Osmanhodžić
 Senedin Oštraković

P

 Kerim Palić
 Dalibor Pandža
 Đorđe Pantić
 Predrag Pašić
 Bojan Pavlović
 Ivica Pavlović
 Edin Pehlić
 Aleksandar Pejović
 Albin Pelak
 Ranko Petković
 Vladimir Petković
 Vukašin Petranović
 Selmir Pidro
 Ismir Pintol
 Denijal Pirić
 Emir Plakalo
 Almir Pliska
 Edin Prljača
 Fahrudin Prljača
Boško Prodanović
 Radoš Protić
 Aleksei Prudnikov
 Antal Puhalak
 Dario Purić
 Bojan Puzigaća

R

 Darko Raca
 Ferid Radeljaš
 Manojlo Radinović
 Samir Radovac
 Amar Rahmanović
 Dejan Raičković
 Ante Rajković
 Milan Rajlić
 Irfan Ramić
 Admir Raščić
 Sulejman Rebac
 Rasim Reiz
 Srebrenko Repčić
 Senad Repuh
 Ševkija Resić
 Aleksandar Ristić
 Mirza Rizvanović
 Edin Rustemović

S

 Amar Sabljica
 Rijad Sadiku
 Mirnel Sadović
 Đani Salčin
 Fuad Salihović
 Elvis Sarić
 Marko Savić
 Radomir Savić
 Ivan Sesar
 Dragoljub Simić
 Edin Smajić
 Haris Smajić
 Dragan Simić
 Ibrahim Sirćo
 Džemo Smječanin
 Admir Softić
 Duško Stajić
 Milan Stepanov
 Mladen Stipić
 Miloš Stojčev
 Memnun Suljagić
 Asmir Suljić
 Safet Sušić
 Sead Sušić
 Tino-Sven Sušić

Š

 Muhamed Šahinović
 Zdravko Šaraba
 Murat Šaran
 Edin Šaranović
 Samir Šarić
 Fuad Šašivarević
 Vučina Šćepanović
 Nail Šehović
 Salih Šehović
 Besim Šerbečić
 Vicko Ševelj
 Sreten Šiljkut
 Aladin Šišić
 Alen Škoro
 Anel Škoro
 Edhem Šljivo
 Aleksandar Šofranac
 Radan Šunjevarić
 Suad Švraka
 Zijad Švrakić

T

 Mario Tadejević
 Dragan Talajić
  Benjamin Tatar
 Ivan Tatomirović
 Anđelko Tešan
 Muhidin Teskeredžić
 Ognjen Todorović
 Almir Tolja
 Sedin Torlak
 Muharem Trako
 Anid Travančić
 Vule Trivunović
 Emir Tufek
 Almir Turković
 Nedim Tutić

U

 Fahrudin Ulak
 Dženan Uščuplić
 Ervin Uščuplić

V

 Azrudin Valentić
 Dal Varešanović
 Mirza Varešanović
 Vejsil Varupa
 Nermin Vazda
 Jasminko Velić
 Krste Velkoski
 Nenad Vidaković
 Risto Vidaković
 Želimir Vidović
 Vukašin Višnjevac
 Anton Vlajčić
 Damir Vrabac
 Dinko Vrabac
 Dragoslav Vujanović
 Svetozar Vujović
 Dragoslav Vukadin
 Slaviša Vukićević
 Sretko Vuksanović
 Irfan Vušljanin

Z

 Nenad Zečević
 Vlado Zadro
 Ševal Zahirović
 Zoran Zekić
 Sead Zilić
 Almedin Ziljkić
 Nemanja Zlatković
 Dilaver Zrnanović
 Muhidin Zukić

Ž

 Marcel Žigante
 Drago Žigman
 Dobrivoje Živkov
 Boris Živković

(not completed yet)

External links
Official Website
FK Sarajevo at Facebook
FK Sarajevo at Twitter
FK Sarajevo at UEFA
FKSinfo

Sarajevo
Association football player non-biographical articles

redpajama_set_name: RedPajamaWikipedia


text:
Q: Is this an error in Typescript compiler I noticed an issue where a user defined typeguard on a union type doesn't behave symmetrically. I hope this an error on my end :-/
The issue shows up in test2() where the type is not inferred properly from the typeguard.
class PropPacket {
    constructor(public key: string, public value: number) {}
}

class EventPacket {
    constructor(public key: string) {}
}

type Packet = PropPacket | EventPacket;

function isPropPacket(p: EventPacket | PropPacket): p is PropPacket {
    return p instanceof PropPacket;
}

function isEventPacket(p: EventPacket | PropPacket): p is EventPacket {
    return p instanceof EventPacket;
}

function test1(p: Packet) {
    if (isPropPacket(p)) {
        // `p` is PropPacket
        p.key;
        p.value;
    } else {
        // `p` is EventPacket
        p.key;
    }
}

function test2(p: Packet) {
    if (isEventPacket(p)) {
        p.key;
    } else {
        // ERROR: thinks `p` is `never` type
        p.key;
        p.value;
    }
}

You can see the issue by pasting the code in the typescript playground (https://www.typescriptlang.org/play/)

A: This happens because all EventPackets are in fact PropertyPackets. Typescript has a structural type system which does not consider two classes to be distinct by declaration, only by the properties and methods they contain.

redpajama_set_name: RedPajamaStackExchange


One of my dreams is to become proficient at horse-back riding. Throughout my life, I've had a few lessons; just enough to know there is a LOT more involved then just sitting on the back of a horse for an hour ride at many vacation spots that offer stable rides. Probably the biggest reason for my interest is the human-animal connection; the ability to communicate with another species. This ability is something I've been able to achieve with numerous animals of various species but to be able to do it in saddle on a horse… Well, that is my dream.
About two and a half years ago, I rescued two abused and neglected donkeys. Although donkeys are equines, donkeys are a bit different then horses in how they communicate. Jack and Jill (named by the child of their previous owners) mean the world to me. Through time and patience, both have recovered from their previous lives and have given me the greatest gift of all: their trust. One of the ways I've learned to communicate with Jack and Jill is through horse riding lessons. The signals and "buttons" used to communicate when riding a horse are the same as they are with the donkeys. And although both donkeys have come a long way from their previous lives, it isn't quite the same as riding "in saddle".
I've looked at a few options in taking riding lessons but have never followed up on them. It seems "life" always seems to get in the way and "riding" always got put on the back burner. That is until I was offered the chance to lease the most beautiful horse I could ever imagine!
Galliano is a Missouri Fox Trotter gaited palomino gelding. With a temperament rating of 2/10, he would be considered a "husband safe horse". Just what I would need! I entertained the idea of living with this horse on and off over the course of a few days before I contacted his owner to let her know of my interest. We set up a time for me to come out to meet Galliano and to ride him. I was like a kid the night before Christmas. I could hardly believe that I might actually live with this horse and develop that "in saddle" bond I've always dreamed of having… Wow!
The morning we were to go meet and ride Galliano had me full of nervous energy. I worried about all sorts of things mainly my ability to ride this horse? I knew I could provide for his basic needs; his needs would not be that different then the donkey's needs. And so as we drove up the mountain to where this horse lived, I imagined my dream coming true.
Upon meeting Galliano, I was overwhelmed at how beautiful he was. At 15.2 hands high, he was the perfect height for me to ride. As my lesson with this horse began, some of my initial fears were put to rest as I listened to his general routines and began to groom him to be saddled. Led out to the arena to ride, his behavior was impeccable!
The lesson was wonderful! Riding Galliano had me concentrating hard at what I had previously learned riding horses along with listening to the particulars of this horse. It was a blue sky sunny day with just the beginning of crispness in the air of approaching fall weather. And I was in heaven! Regardless of outcome, this will always be one of the best days of my life!
As the lesson continued and more of his "gaits" were explored, I knew I was going faster then my riding ability. I should have slowed down, I should have known my limitations, I should have not tried to keep up with the instructor who rides daily; who grew up riding horses. But I was having too much fun to listen to that inner voice. Instead of working on form, instead of realizing my core strength was not where it needed to be to ride that fast, instead of being afraid of consequences, I was "riding". Well until I wasn't! Following his horse mate and cutting the corner, I was out of the saddle and when I came down, Galliano was NOT under me. Falling off this horse was like slow motion. One minute everything was fine and the next I was headed for the ground!
I landed hard on my shoulder/ribs. Galliano? He stopped perfectly still wondering what I was doing on the ground? I heard people yelling at me to be still yet I was squirming to get out from under this horse. Quickly assessed and finding nothing broken, I was helped to a standing position. I was mortified by embarrassment that I had fallen off this horse. And I hurt! As the saying goes regarding getting back into the saddle, I did although in hindsight, I'm not sure how I physically did this? And after walking in a circle, I dismounted and led Galliano back to the hitching post to be unsaddled. Still embarrassed that I had fallen, I hid my pain well, at least I think I did, but I could feel the stinging pain any time I tried to twist or move any of the muscles on my left side.
Time passed and soon we were home. Hubby determined that I probably broke a few ribs and definitely sprained/strained more then a few muscles. All I knew was that I had done this to myself. I should have slowed down. I should have known better. Sigh! Friday night found me in a lot of pain especially after the long drive home that allowed my muscles to tighten. And Saturday, I spent the day in bed with pain being relieved by meds from a prescription written seven years ago! I'm better today although still taking pain medication and moving gingerly; I even took a shower and got dressed today; woohoo!
It's going to take a few weeks to heal from this life lesson. I'm just thankful I didn't hit my head or break any bones! As for Galliano… emailing his owners that this probably wasn't the best time for me to bring in a horse with my limited riding abilities was probably one of the hardest emails I've ever written! IF I am ever going to have a horse of my own, I need to take riding lessons first! And while I COULD take those lessons on Galliano, it wouldn't be fair to him to NOT be ridden while I was learning more of the basics. And now that I've injured myself, it will be at least a few months before I can even entertain the idea of getting back "in the saddle". By then, my bruises will have healed as well as my wounded ego. And maybe then, I'll try again?
Still, that day on the back of Galliano will remain as one of the best days of my life! For awhile, he and I were one. That has to be one of the most incredible feelings I have ever experienced. I am so grateful to his owners who gave me this opportunity to ride such a magnificent horse; to my husband for believing in me enough to allow and to encourage me to even entertain this idea of mine; and of course to Galliano… for just being himself.
He is beautiful, and you have such a patient, loving attitude. I hope you heal up soon and get back in the saddle, maybe a little slower – and safer. Horses take me into the woods, into a peaceful state of mind.
Thank you!! Yes, I'll come back from this because… Horses are simply amazing animals! Next time, I'll try to remember just a tad of common sense, LOL!


I burned my hand last night. I was reaching in the oven to pull out my dinner, and my hand rubbed right against the hot part at the top of the oven.
I was pulling out this really delicious veggie lasagna I had made myself.
BWHAHAHAHAHA. No way dude. I was pulling out the Taco Bell I had drive thru'd and placed in the oven on warm so it would stay sort of hot while I showered. Turning the oven on was a bigger step in the cooking department than I've taken in a while.
"I made myself." As if.


"I got my t-shirt two years ago and it still fits great!" -Anna P.
"People always ask, where did you get that tee?" -Norris M.
I could end my "about us" post with that statement but I don't want to leave you without a more detailed explanation of why I decided to open the Just Shirtin The Issue online store.
A long time ago in the year (2010) and far away (in New Jersey) while at a New Year's Eve party I took inventory of things around me as I did not want to forget how special the moment was. Did you ever do that? Smell a scent or look at something which jogs a memory and say, "remember that time?" I wanted to capture that emotion and believed that slogans were the way to go. How best to offer your opinion or feeling at any moment? At that moment the idea for Just Shirtin The Issue was born where we offer "Slogans Good Enough to Wear."
I enjoy hearing from people who say, "Hey t-shirt girl, thanks for my shirt!" They tell me about how they wore it at a dance congress in Spain, during a vacation, or just staying local and enjoying the night out. The t-shirt doesn't make people happy, the memories it brings by wearing it will.
At our online store you can find a way for the world to "see" what you believe.
Thanks for visiting, shopping and supporting us at Just Shirtin The Issue.