| 1 |
CRAM encoding internals |
| 2 |
======================= |
| 3 |
|
| 4 |
A quick summary of functions involved. |
| 5 |
|
| 6 |
The encoder works by accumulating a bunch of BAM records (via the |
| 7 |
cram_put_bam_seq function), and at a certain point (eg counter of |
| 8 |
records, or switching reference) the array of BAM records it turned |
| 9 |
into a container, which in turn creates slices, holding CRAM |
| 10 |
data-series in blocks. The function that turns an array of BAM |
| 11 |
objects into the container is below. |
| 12 |
|
| 13 |
cram_encode_container func: |
| 14 |
Validate references MD5 against header, unless no_ref mode |
| 15 |
If embed_ref <= 1, fetch ref |
| 16 |
Switch to embed_ref=2 if failed |
| 17 |
|
| 18 |
Foreach slice: |
| 19 |
If embed_ref == 2 |
| 20 |
call cram_generate_reference |
| 21 |
if failed switch to no_ref mode |
| 22 |
Foreach sequence |
| 23 |
call process_one_read to append BAM onto each data series (DS) |
| 24 |
call cram_stats_add for each DS to gather metrics |
| 25 |
call cram_encode_aux |
| 26 |
|
| 27 |
# We now have cram DS, per slice |
| 28 |
call cram_encoder_init, per DS (based on cram_stats_add data) |
| 29 |
|
| 30 |
Foreach slice: |
| 31 |
call cram_encode_slice to turn DS to blocks |
| 32 |
call cram_compess_slice |
| 33 |
|
| 34 |
call cram_encode_compression_header |
| 35 |
|
| 36 |
Threading |
| 37 |
--------- |
| 38 |
|
| 39 |
CRAM can be multi-threaded, but this brings complications. |
| 40 |
|
| 41 |
The above function is the main CPU user, so it is this bit which can |
| 42 |
be executed in parallel from multiple threads. To understand this we |
| 43 |
need to now look at how the primary loop works when writing a CRAM: |
| 44 |
|
| 45 |
Encoding main thread: |
| 46 |
repeatedly calls cram_put_bam_seq |
| 47 |
calls cram_new_container on first time through to initialise |
| 48 |
calls cram_next_container when current is full or we need to flush |
| 49 |
calls cram_flush_container_mt to flush last container |
| 50 |
pushes BAM object onto current container |
| 51 |
|
| 52 |
If non-threaded, cram_flush_container_mt does: |
| 53 |
call cram_flush_container |
| 54 |
call cram_encode_container to go from BAM to CRAM data-series |
| 55 |
call cram_flush_container2 (writes it out) |
| 56 |
|
| 57 |
If threaded, cram_flush_container_mt does: |
| 58 |
Main: Dispatch cram_flush_thread job |
| 59 |
Thread: call cram_encode_container to go from BAM to CRAM data-series |
| 60 |
Main: Call cram_flush_result to drain queue of encoded containers |
| 61 |
Main: Call cram_flush_container2 (writes it out); |
| 62 |
|
| 63 |
|
| 64 |
|
| 65 |
Decisions on when to create new containers, detection of sorted vs unsorted, |
| 66 |
switching to multi-seq mode, etc occur at the main thread in |
| 67 |
cram_put_bam_seq. |
| 68 |
|
| 69 |
We can change our mind on container parameters at any point up until |
| 70 |
the cram_encode_container call. At that point these parameters get |
| 71 |
baked into a container compression header and all data-series |
| 72 |
generated need to be in sync with the parameters. |
| 73 |
|
| 74 |
It is possible that some parameter changes can get detected while |
| 75 |
encoding the container, as it is there where we fetch references. Eg |
| 76 |
the need to enable embedded reference or switch to non-ref mode. |
| 77 |
|
| 78 |
While encoding a container, we can change the parameters for *this* |
| 79 |
container, and we can also set the default parameter for subsequent |
| 80 |
new parameters via the global cram fd to avoid spamming attempts to |
| 81 |
load a reference which doesn't exist, but we cannot change other |
| 82 |
containers that are being processed in parallel. They'll fend for |
| 83 |
themselves. |
| 84 |
|
| 85 |
References |
| 86 |
---------- |
| 87 |
|
| 88 |
To avoid spamming the reference servers, there is a shared cache of |
| 89 |
references being currently used by all the worker threads (leading to |
| 90 |
confusing terminology of reference-counting of references). So each |
| 91 |
container fetches its section of reference, but the memory for that is |
| 92 |
handled via its own layer. |
| 93 |
|
| 94 |
The shared references and ref meta-data is held in cram_fd -> refs (a |
| 95 |
refs_t pointer): |
| 96 |
|
| 97 |
// References structure. |
| 98 |
struct refs_t { |
| 99 |
string_alloc_t *pool; // String pool for holding filenames and SN vals |
| 100 |
|
| 101 |
khash_t(refs) *h_meta; // ref_entry*, index by name |
| 102 |
ref_entry **ref_id; // ref_entry*, index by ID |
| 103 |
int nref; // number of ref_entry |
| 104 |
|
| 105 |
char *fn; // current file opened |
| 106 |
BGZF *fp; // and the hFILE* to go with it. |
| 107 |
|
| 108 |
int count; // how many cram_fd sharing this refs struct |
| 109 |
|
| 110 |
pthread_mutex_t lock; // Mutex for multi-threaded updating |
| 111 |
ref_entry *last; // Last queried sequence |
| 112 |
int last_id; // Used in cram_ref_decr_locked to delay free |
| 113 |
}; |
| 114 |
|
| 115 |
Within this, ref_entry is the per-reference information: |
| 116 |
|
| 117 |
typedef struct ref_entry { |
| 118 |
char *name; |
| 119 |
char *fn; |
| 120 |
int64_t length; |
| 121 |
int64_t offset; |
| 122 |
int bases_per_line; |
| 123 |
int line_length; |
| 124 |
int64_t count; // for shared references so we know to dealloc seq |
| 125 |
char *seq; |
| 126 |
mFILE *mf; |
| 127 |
int is_md5; // Reference comes from a raw seq found by MD5 |
| 128 |
int validated_md5; |
| 129 |
} ref_entry; |
| 130 |
|
| 131 |
Sharing of references to track use between threads is via |
| 132 |
cram_ref_incr* and cram_ref_decr* (which locked and unlocked |
| 133 |
variants). We free a reference when the usage count hits zero. To |
| 134 |
avoid spamming discard and reload in single-thread creation of a |
| 135 |
pos-sorted CRAM, we keep track of the last reference in cram_fd and |
| 136 |
delay discard by one loop iteration. |
| 137 |
|
| 138 |
There are complexities here around whether the references come from a |
| 139 |
single ref.fa file, are from a local MD5sum cache with one file per |
| 140 |
reference (mmapped), or whether they're fetched from some remote |
| 141 |
REF_PATH query such as the EBI. (This later case typically downloads |
| 142 |
to a local md5 based ref-cache first and mmaps from there.) |
| 143 |
|
| 144 |
The refs struct start off by being populated from the SAM header. We |
| 145 |
have M5 tag and name known, maybe a filename, but length is 0 and seq |
| 146 |
is NULL. This is done by cram_load_reference: |
| 147 |
|
| 148 |
cram_load_reference (cram_fd, filename): |
| 149 |
if filename non-NULL |
| 150 |
call refs_load_fai |
| 151 |
Populates ref_entry with filename, name, length, line-len, etc |
| 152 |
sanitise_SQ_lines |
| 153 |
If no refs loaded |
| 154 |
call refs_from_header |
| 155 |
populates ref_entry with name. |
| 156 |
Sets length=0 as marker for not-yet-loaded |
| 157 |
|
| 158 |
The main interface used from the code is cram_get_ref(). It takes a |
| 159 |
reference ID, start and end coordinate and returns a pointer to the |
| 160 |
relevant sub-sequence. |
| 161 |
|
| 162 |
cram_get_ref: |
| 163 |
r = fd->refs->ref_id[id]; // current ref |
| 164 |
call cram_populate_ref if stored length is 0 (ie ref.fa set) |
| 165 |
search REF_PATH / REF_CACHE |
| 166 |
call bgzf_open if local_path |
| 167 |
call open_path_mfile otherwise |
| 168 |
copy to local REF_CACHE if required (eg remote fetch) |
| 169 |
|
| 170 |
If start = 1 and end = ref-length |
| 171 |
If ref seq unknown |
| 172 |
call cram_ref_load to load entire ref and use that |
| 173 |
|
| 174 |
If ref seq now known, return it |
| 175 |
|
| 176 |
// Otherwise known via .fai or we've errored by now. |
| 177 |
call load_ref_portion to return a sub-seq from index fasta |
| 178 |
|
| 179 |
The encoder asks for the entire reference rather than a small portion |
| 180 |
of it as we're usually encoding a large amount. The decoder may be |
| 181 |
dealing with small range queries, so it only asks for the relevant |
| 182 |
sub-section of reference as specified in the cram slice headers. |
| 183 |
|
| 184 |
|
| 185 |
TODO |
| 186 |
==== |
| 187 |
|
| 188 |
- Multi-ref mode is enabled when we have too many small containers in |
| 189 |
a row. |
| 190 |
|
| 191 |
Instead of firing off new containers when we switch reference, we |
| 192 |
could always make a new container after N records, separating off |
| 193 |
M <= N to make the container such that all M are the same reference, |
| 194 |
and shuffling any remaining N-M down as the start of the next. |
| 195 |
|
| 196 |
This means we can detect how many new containers we would create, |
| 197 |
and enable multi-ref mode straight away rather than keeping a recent |
| 198 |
history of how many small containers we've emitted. |
| 199 |
|
| 200 |
- The cache of references currently being used is a better place to |
| 201 |
track the global embed-ref and non-ref logic. Better than cram_fd. |
| 202 |
Cram_fd is a one-way change, as once we enable non-ref we'll stick |
| 203 |
with it. |
| 204 |
|
| 205 |
However if it was per-ref in the ref-cache then we'd probe and try |
| 206 |
each reference once, and then all new containers for that ref would |
| 207 |
honour the per-ref parameters. So a single missing reference in the |
| 208 |
middle of a large file wouldn't change behaviour for all subsequence |
| 209 |
references. |
| 210 |
|
| 211 |
Optionally we could still do meta-analysis on how many references |
| 212 |
are failing, and switch the global cram_fd params to avoid repeated |
| 213 |
testing of reference availability if it's becoming obvious that none |
| 214 |
of them are known. |