Methods, systems, and apparatus, including computer program products, for orthogonal coding for data storage. In one aspect, a method includes receiving a block of data comprising m rows and n columns of data chunks. For each row in the block of data, (c-n) columns of error-correcting row code chunks are generated using a first linear error-correcting code in systematic form and the particular row's data chunks. For each column in the block of data and for each generated column, particular column and (r-m) error-correcting column code chunks for the particular column are allocated to a distinct group of storage nodes, wherein: the column code chunks are generated using a second linear error-correcting code in systematic form and the particular column's data chunks or row code chunks; m and n are greater than one; and c is greater than n and r is greater than m.