A method implemented by a packet forwarder device (802; 804; 806) for dynamic flow learning, wherein the packet forwarder comprises a plurality of forwarding threads and a plurality of provisioning threads executed by the device, the method comprising: receiving a packet to be forwarded by the packet forwarder, wherein the packet is of a new flow of traffic from the perspective of a forwarding data structure utilized by the plurality of forwarding threads to forward packets; responsive to determining, by a forwarding thread of the plurality of forwarding threads according to an admission mechanism, that the forwarding thread is allowed to submit a request for the new flow to be learned by the packet forwarder, inserting data corresponding to the packet into an entry of an operation queue of a plurality of operation queues, wherein each of the plurality of operation queues is exclusively operated on by a corresponding provisioning thread of the plurality of provisioning threads; obtaining, by the provisioning thread corresponding to the operation queue, the inserted data from the entry of the operation queue; updating, by the provisioning thread, a bucket from a plurality of buckets (502A-502M) of a control data structure to include flow data for the new flow, wherein each of the plurality of buckets is exclusively operated on by a corresponding provisioning thread of the plurality of provisioning threads and thus is mapped to a corresponding operation queue of the plurality of operation queues; updating, by the provisioning thread, a forwarding bucket of a plurality of forwarding buckets (602A-602T) of the forwarding data structure based upon the updated bucket of the control data structure; and forwarding, by a second forwarding thread, an additional one or more packets of the new flow based upon the updated forwarding bucket of the forwarding data structure. receiving a packet to be forwarded by the packet forwarder, wherein the packet is of a new flow of traffic from the perspective of a forwarding data structure utilized by the plurality of forwarding threads to forward packets; responsive to determining, by a forwarding thread of the plurality of forwarding threads according to an admission mechanism, that the forwarding thread is allowed to submit a request for the new flow to be learned by the packet forwarder, inserting data corresponding to the packet into an entry of an operation queue of a plurality of operation queues, wherein each of the plurality of operation queues is exclusively operated on by a corresponding provisioning thread of the plurality of provisioning threads; obtaining, by the provisioning thread corresponding to the operation queue, the inserted data from the entry of the operation queue; updating, by the provisioning thread, a bucket from a plurality of buckets (502A-502M) of a control data structure to include flow data for the new flow, wherein each of the plurality of buckets is exclusively operated on by a corresponding provisioning thread of the plurality of provisioning threads and thus is mapped to a corresponding operation queue of the plurality of operation queues; updating, by the provisioning thread, a forwarding bucket of a plurality of forwarding buckets (602A-602T) of the forwarding data structure based upon the updated bucket of the control data structure; and forwarding, by a second forwarding thread, an additional one or more packets of the new flow based upon the updated forwarding bucket of the forwarding data structure.